OLSR-NG: Unterschied zwischen den Versionen

Aus FunkFeuer Wiki
Wechseln zu: Navigation, Suche
K (→‎Who is working on what?)
(re-wording to make henning happy)
 
(73 dazwischenliegende Versionen von 11 Benutzern werden nicht angezeigt)
Zeile 2: Zeile 2:
  
  
−
= NEWS =
+
<div style="background: red; border: 1px solid #999; padding: 5px; margin-bottom: 5px;">'''WARNING: This page is very outdated by now! It purely serves to document the Netidee project of ~2007'''<br>Please go to ''' http://www.olsr.org ''' for    more current and up to date info. This is here for historical reasons.</div>
  
−
<p>We have released our first set of improvements to the olsrd SPF calculation module.</p>
 
−
 
−
 
−
== SPF implementation ==
 
−
When executing the [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm SPF calculation]
 
−
upon every iteration the least cost path needs to be extracted and put on the result list.
 
−
For that purpose olsrd-current does keep a linear list which has O(N) [http://en.wikipedia.org/wiki/Asymptotic_complexity asymptotic_complexity] to traverse.
 
−
Every node needs to be visited, which
 
−
has again O(N) [http://en.wikipedia.org/wiki/Asymptotic_complexity asymptotic_complexity]. This results in a total behavior of O(N^2) which can eat a lot
 
−
of CPU where N is large (for example when there are hundreds of olsrd nodes in a network).
 
−
 
−
== speed by efficient sorting ==
 
−
modern SPF implementations use data structures which are efficient at sorting the preliminary path costs like
 
−
[http://en.wikipedia.org/wiki/Min_heap min_heaps] or [http://en.wikipedia.org/wiki/AVL_tree AVL_trees]. Since olsrd already
 
−
had a nice and efficient AVL tree implementation, the two SPF related data structures (the candidate and path tree) are implemented using
 
−
AVL trees with the path etx metric as the key. Determining the minimal path cost in an AVL tree comes at a cost of O(log(N)) which results
 
−
in a total [http://en.wikipedia.org/wiki/Asymptotic_complexity asymptotic_complexity] of O(N * log(N)), which scales much nicer now in large networks.
 
−
 
−
== Results ==
 
−
In the [http://www.funkfeuer.at funkfeuer.at] network topology of 190 nodes the raw SPF execution was reduced by 45%. Note that the raw SPF execution represents only about 20% of the CPU cost in a running olsrd. At funkfeuer.at we have observed an overall decrease in the CPU load of about 12% on the embedded routers.
 
−
 
−
== Outlook ==
 
−
10-20% (depending on network size) in the route-handling module is admittedly not exciting. During refactoring the SPF implementation the olsrd-ng development team, has spotted further bottlenecks in the existing implementation. We are tackling this one by one, and would need active participation of the wireless communities to test our improvements and verify if we have added any undesired regressions. so stay tuned and report bugs to the [mailto:olsr-dev@lists.olsr.org olsrd-dev] mailing list.
 
−
<hr>
 
−
please check out the [http://tema.lo-res.org/~aaron/spf-refactoring.diff.gz patch]
 
−
 
−
= sponsor =
 
−
 
−
[[Bild:netideelogo.png|800px|supported by IPA]] made possible by a grant from [http://www.netidee.at IPA].  Thanks we really appreciate your help and your courage to support us!
 
−
 
−
= main links =
 
−
 
−
Main OLSR-NG project blog: http://olsr.funkfeuer.at
 
−
 
−
Slides from the OLSR-NG kickoff presentation: http://outpost.funkfeuer.at/~aaron/olsr-ng.pdf
 
−
 
−
We communicate on the olsr-dev mailinglist: https://www.olsr.org/mailman/listinfo/olsr-dev . All commit messages can be seen on the olsr-cvs list
 
  
 
= Goals =
 
= Goals =
  
−
# Clean up the code of OLSR (http://www.olsr.org),
+
Our mission is simple. Build the most scalable and usable routing daemon routing wireless and fixed line segments.
−
# improve the algorithms of OLSR and make it more scalable.
+
The routing daemon shall scale up to
−
# Furthermore, produce a new RFC for a (potential) new mesh routing protocol which is based on the experiences of OLSR coding (at the moment the most promising candidate for this RFC is [http://open-mesh.net/batman B.A.T.M.A.N])
+
−
 
+
−
 
+
−
OLSR-NG is a open source project. Meaning everybody is invited to join in and help.  
+
−
We do have some bounties for the best solutions. If you want to participate, drop us an email: mailto:aaron@lo-res.org and mailto:bernd@firmix.at
+
  
 +
# 10000 (10K) nodes and
 +
# 20000 (20K) routes
 +
running on low-cost hardware (200 Mhz RISC CPUs / 32MB of memory).
  
 
One of the main goals is to make OLSR more scalable '''in practice'''.
 
One of the main goals is to make OLSR more scalable '''in practice'''.
 
[[Bild:O-Dijkstra.gif|350px|right|Complexity for n=1000 nodes of different data structures in the Dijkstra shortest path (SPF) algorithm. ]]
 
[[Bild:O-Dijkstra.gif|350px|right|Complexity for n=1000 nodes of different data structures in the Dijkstra shortest path (SPF) algorithm. ]]
  
−
In the this picture you can see the different complexity graphs for the SPF under the assumption that every node has 10 edges . As you can see, the red line has O(n^2) complexity. This conforms to the current implementation of OLSR from www.olsr.org. OLSR-NG plans to reduce the complexity to the green or even the yellow level. This will allow the mesh network clouds to become larger by a factor ~ 1000 (on the routing layer / layer 3).
+
In the this picture you can see the different complexity graphs for the SPF under the assumption that every node has 10 edges . As you can see, the red line has O(n^2) complexity. This conformed to the implementation of OLSR from www.olsr.org ('''before''' the OLSR-NG project). OLSR-NG reduced the complexity to the green level. This will allow the mesh network clouds to become larger by a factor ~ 1000 (on the level of calculating the dijkstra (shortes path) algorithm so far).
  
−
= Current Status =
 
  
−
* olsrd 0.5 was released! Thx everybody a lot!
+
For achieving that we first want to
−
* UML test server is being worked on. This will allow the B.A.T.M.A.N team to test their protocol and us to test our scalability ideas with 1000nd of olsr instances.
+
−
* Ongoing code cleanups
+
−
* AVL tree optimizations
+
  
−
== [http://www.user-mode-linux.org UML] test server ==
+
# fix the existing olsrd and add new data structures and algorithms.
 +
# Once olsrd is running fast we focus on protocol issues like
 +
## measuring better links metrics, like including the bandwidth (ETT)
 +
## link-state db synchronization issues (rather then brute force retransmission).
 +
All protocol extensions shall be documented as an internet-draft and submitted to the IETF MANET working group http://www.ietf.org/html.charters/manet-charter.html
  
−
current load and statistics: http://texas.funkfeuer.at
 
  
−
[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]
+
Next we want to improve the management tools of olsrd like the
  
−
[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
+
# http_info plugin or
−
(check out the [[TopologyPics archive]] also)
+
# txt_info plugins or
 +
# building a new XMLinfo plugin
  
−
topo map 1500 UML instances running in parallel. Note the packetloss!
+
such that that large clouds consisting of thousands of nodes
 +
can be troubleshooted in an effective way.
  
−
We have already been running 2000 instances and there was still  plenty of RAM left. So 1000 is a very safe bet. However according to the UML docu we can probably safely assume that we can scale up miuch higher because UML will only take the RAM that each instance actually needs.
+
Main OLSR-NG project blog: http://olsr.funkfeuer.at
−
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...
+
Slides from the OLSR-NG kickoff presentation: http://marvin.funkfeuer.at/~aaron/olsr-ng.pdf
  
 +
= Current Status =
  
−
=== current open todos UML server ===
+
=== stable ===
−
Next important (*) things to do:
+
* olsrd 0.5.5 was released! Thx everybody a lot! -  See changes int the [http://sourceforge.net/project/shownotes.php?release_id=574533&group_id=117612 Changelog]
−
* DONE(aka) update texas's BIOS - FIXED
+
−
* add the packet loss tc rules (zethix already prepared it)
+
−
* create random netowkrs (easy)
+
−
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
+
−
* DONE(zethix) create scripts to find out which olsrd instances crashed
+
−
* create scripts to find out if a UML instance is not responsive anymore
+
−
* find better measurement tools . Look into sar
+
−
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
+
−
* DONE(aka) recompile host kernel and enable the preemtion patch
+
−
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
+
−
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
+
−
* find more meaningful topology visualization tools (http://www.caida.org)
+
−
* add b.a.t.m.a.n to the root filesystem. (?)
+
−
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]
+
  
−
=== User HOWTO ===
+
=== upcoming 0.5.6 ===
  
−
  NOTE! You are root on the system. Effectively we need lots of sudo privs. So... use it wisely.
+
'''buglist:''' Things that ''need'' to be changed before we release 0.5.6
  
−
# log in
+
<pre>
−
# make clean
+
sven-ola: stimmt. glaub' ich auch. Da sind noch 2 Bugs drin.
−
# edit common.sh and adapt the parameters to your needs
+
[12:19pm] sven-ola: oder sogar drei. Das sind aus meiner Sicht:
−
  #!/bin/sh
+
[12:20pm] sven-ola: 1) das nach neustart unter http://localhost:2006/links derselbe Node mehrfach auftaucht
−
  #
+
[12:20pm] sven-ola: 2) das etx_ff mit olsr-0.5.5 (oder etx_fpm) nur bis LQ=0.6 kommt
−
  # VARS
+
[12:20pm] sven-ola: 3) unter windoof: mehrfach Ifaces geht nicht (das mir eigentlich egal)
−
  #
+
[12:22pm] sven-ola: bin mal kurz weg (olsrd neu start == nix inet)
−
  MAX_INSTANCES=1500
+
...
−
  ROOT_FS=root_fs
+
fein. wobei das dringenste ist "neustart zeigt link mehrfach" - wenn das passiert muss man den nachbarn neu starten sonst gibts keine ordentlichen routen. Und wenn man gerade kein ssh zum Nachbarn hat, kann man lange warten <ggg>
−
  NICELVL="-n 5"
+
</pre>
−
  u=$USER
+
−
  #SINGLE=1
+
−
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE  parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
+
−
# the UML instance can read files and programs from
+
−
  $HOME/public_uml/share
+
−
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.
+
  
−
  N.B. This directory is shared between all UML instances that you will
+
* Mac OS X: sendto() has wrong family parameter in OS X -> nothing gets send out
−
  start in your simulation, so, they all have read-only access to it.
+
* Bug in etx_ff <-> etx_fpm compatibility: if etx_ff (openBSD) does, then the topo entry still stays in (linux) etx_fpm
−
  It will appear inside each UML as /mnt/share/. There is also another,
+
* re-test everything on *all* OSes
−
  per-instance, read-write directory that you can use to save data for
+
−
  later analysis (e.g. redirect olsrd stdout to a file and print some
+
−
  debugging info there). This second directory will be under
+
−
  $HOME/public_uml/exp/<UML IP> (where UML IP is the ip address of each
+
−
  UML instance). It will also appear as /mnt/exp inside UML's environment.
+
  
−
# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.
+
= sponsor =
  
−
# make
+
[[Bild:netideelogo.png|200px|supported by IPA]]
  
−
This will start the simulation.
+
The initial work of OLSR-NG was made possible by a grant from [http://www.netidee.at IPA]. 
  
−
  N.B. When the simulation is started, an olsrd instance is started on
+
After the grant, OLSR-NG still continues as a project. We are again looking for sponsors who believe in this work.
−
  the host as well. You can use it if you need to interact with the
+
−
  olsrd network - for instance, topology maps are generated through this
+
−
  instance (see below).  
+
  
−
# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
+
= Sub projects =
−
  screen -ls              (as root)
+
−
to list all available sessions, and
+
−
  screen -S blabla.10.0.x.y -d -RR
+
−
to attach to a session. This will give you shell access to the system.
+
  
−
  N.B. All modifications to the root filesystem will be preserved only
+
==[[SPF refactoring]]==
−
  for the duration of the simulation! Once it is stopped, changes will
+
==[[LSDB refactoring]]==
−
  be lost!
+
==[[RIB refactoring]]==
 +
==[[miscellaneous improvements]]==
 +
==[[UML test server]]==
 +
==[[Data Structures and Algorithms]]==
  
−
# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!
 
  
−
# stop it via
+
= Who wants to contribute? =
−
  make clean
+
−
or
+
−
  make stop
+
  
−
Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!
+
OLSR-NG is a open source project. Meaning everybody is invited to join in and help.
 +
We do have some bounties for the best solutions. If you want to participate, drop us an email: mailto:aaron@lo-res.org, mailto:hannes@gredler.at or mailto:bernd@firmix.at
  
−
'''Some things to note'''
+
== Bounties ==
  
−
* the topology visualisation scripts run with nice level +5
+
please take a look at the slides http://marvin.funkfeuer.at/~aaron/olsr-ng.pdf and get in contact with us directly.
−
the UML instances with nicelevel +10 (see run.sh)
+
−
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
+
−
*
+
  
−
=== Open questions/bug reports? ===
+
== Source code ==
−
 
+
* Mercurial repo instructions
−
= Who wants to contribute? =
+
  http://www.olsr.org/?q=mercurial/
  
 
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
 
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
Zeile 191: Zeile 119:
  
 
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
 
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
−
!align="left" | Who
+
!align="left" | Who
 
!align="left" | What
 
!align="left" | What
 
!align="left" | Status
 
!align="left" | Status
 +
!align="left" | Comments
 
|-  class="oeffentlich"
 
|-  class="oeffentlich"
 
| Bernd Petrovitsch, Thomas Lopatic, Hannes Gredler
 
| Bernd Petrovitsch, Thomas Lopatic, Hannes Gredler
 
| release 0.5
 
| release 0.5
 
| DONE
 
| DONE
 +
|
 
|-
 
|-
 
| ???
 
| ???
 
| release 0.5 make packages for  freifunk FW, DD-WRT, etc, windows (XP, Vista), ... and test them
 
| release 0.5 make packages for  freifunk FW, DD-WRT, etc, windows (XP, Vista), ... and test them
−
| OPEN
+
| OPEN
 +
| freifunk FW is done by Sven-Ola Tücke, .rpm and .deb by various people on olsr-dev@lists.olsr.org, Windows: ???
 
|-
 
|-
−
| ???
+
| Aaron
 
| analyze IP autoconfig mechanisms and find the best one
 
| analyze IP autoconfig mechanisms and find the best one
 
| OPEN
 
| OPEN
 +
|
 
|-
 
|-
 
| Hannes Gredler
 
| Hannes Gredler
 
| tcpdump parses olsr packets,  
 
| tcpdump parses olsr packets,  
 
| DONE
 
| DONE
 +
|
 
|-
 
|-
 
| Hannes Gredler
 
| Hannes Gredler
−
| SPF improvments
+
| SPF improvements
 
| DONE
 
| DONE
 +
|
 
|-
 
|-
 
| Hannes Gredler
 
| Hannes Gredler
 
| reduce malloc thrashing during SPF computation
 
| reduce malloc thrashing during SPF computation
−
| not yet started
+
| DONE
 +
|
 
|-
 
|-
 
| Hannes Gredler
 
| Hannes Gredler
−
| improve post-SPF handling (route table conciliation)
+
| improve post-SPF handling (route table conciliation, best path selection)
 
| DONE
 
| DONE
 +
|
 +
|-
 +
| Bernd Petrovitsch
 +
| rework the logging/tracing/error reporting
 +
| WIP/stalled due to work in other areas
 +
|
 +
|-
 +
| Bernd Petrovitsch
 +
| rework the LQ-TC and LQ-HELLO input parsing, avoiding malloc/free thrashing
 +
| DONE
 +
| The output side can also be avoid ''malloc()'' and ''free()''. Alas, the code is more complicated there.
 +
|-
 +
| Bernd Petrovitsch/Hannes Gredler/???
 +
| supersede all of the ''*_chgestruct()'' functions: All of them are called in exactly one place. So one can inline them there and use the ''pkg_get_*()'' functions to check and use the data. This also avoids more malloc/free thrashing and reduces the amount of code.
 +
| WIP
 +
|
 
|-
 
|-
 
| Hannes Gredler
 
| Hannes Gredler
 
| spurious neighbor loss on nodes with high neighbor count
 
| spurious neighbor loss on nodes with high neighbor count
 
| OPEN/investigating
 
| OPEN/investigating
 +
|
 
|-  
 
|-  
 
| Aaron Kaplan,Bernd Petrovitsch
 
| Aaron Kaplan,Bernd Petrovitsch
 
| olsr-ng test server
 
| olsr-ng test server
 
| DONE
 
| DONE
 +
|
 
|-
 
|-
 
| Aaron Kaplan
 
| Aaron Kaplan
 
| theory, complexity analysis. Goal: find the best complexity on the algorithmic side.
 
| theory, complexity analysis. Goal: find the best complexity on the algorithmic side.
 
| DONE
 
| DONE
 +
| theory tells that fibonacci heaps are best, practise tells that an AVL tree as a minheap implementation fits the complexity of frequent re-keyings better
 
|-
 
|-
 
| Zethix, Aaron Kaplan
 
| Zethix, Aaron Kaplan
 
| UML cluster setup
 
| UML cluster setup
 
| WIP, currently we can start around 2000 UML instances. But the uml_switch software still drops packets between virtual interfaces. http://www.openvz.org seems also like a promising solution
 
| WIP, currently we can start around 2000 UML instances. But the uml_switch software still drops packets between virtual interfaces. http://www.openvz.org seems also like a promising solution
 +
|
 +
|-
 +
| Aaron Kaplan, Hannes
 +
| draft. write a draft about LQ extensions
 +
| OPEN
 +
|
 +
|-
 +
| Bernd Petrovitsch
 +
| Variuos '''Cleanup''' Mini- Projects
 +
| DONE/WIP
 +
| reworked floating point ops in src/mantissa.[ch] to minimize run-time impact, fixed dependencies, reworked ip address copying and comparison to get it type-safe,
 +
|-
 +
| Sebastian Sauer
 +
| LinkQuality / metrics (e.g. ETX/ETT) improvements
 +
| OPEN/WIP (no code yet committed)
 +
| evaluate best current practice;
 +
|-
 +
| Sebastian Sauer
 +
| FishEye improvements
 +
| OPEN/investigating
 +
| evaluate best current practice;
 +
|-
 +
| Sebastian Sauer
 +
| effect of OLSR parameters on the mesh
 +
| OPEN/investigating
 +
| evaluate best current practice; spot and (maybe) eliminate dangers/instabilities
 +
|-
 +
| Sebastian Sauer
 +
| selfish nodes / malicious nodes
 +
| OPEN/investigating
 +
| risk assessments
 +
|-
 
|}
 
|}
  
 
<mm>[[olsr-ng.mm|flash]]</mm>
 
<mm>[[olsr-ng.mm|flash]]</mm>
−
 
−
 
−
 
−
contact mailto:aaron@lo-res.org  or Bernd if you are interested in participating!
 
−
 
−
= Next Steps =
 
−
 
−
* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "Verteilte systeme"], 20.4.2007 will present our ideas about optimizing complexity. Aaron also wants to adress more students from the TU to participate. DONE. Let's see if new participants want to join.
 
−
* finalize the UML test server
 
−
* try out the optimization ideas and document the speedup
 
−
* more cleanups
 
−
** olsrd is doing '''lots of''' <tt>malloc()</tt>s and <tt>free()</tt>s - use </tt>ltrace</tt> to see this.
 
−
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around
 
−
*** are there very frequently <tt>malloc()</tt>ed and </tt>free()<tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> handling
 
−
** we have several coding styles in there
 
−
** add wrappers to hide type casts for Windows (and perhaps others). Reserve some prefix (e.g. ''x'' is used for this often as in <tt>xmalloc()</tt>, ''olsr_'' is IMHO quite long)
 
−
** fixup error reporting/logging
 
−
** add synchronization and make the daemon multi-threading (e.g. the httpinfo plugin could benefit from such a thing)
 
−
** make the parameter parsing of the plugins more consistent (some are case-sensitive, some are not, most do not check syntax errors)
 
−
** ....
 
−
 
−
= Bounties =
 
−
 
−
 
−
please take a look at the slides and get in contact with us directly at the moment!
 
−
 
−
= Source code =
 
−
* CVS repos: 
 
−
  (as user "ipo23" )
 
−
    export CVS_RSH=ssh
 
−
    cvs -z3 -d:ext:ipo23@olsrd.cvs.sourceforge.net:/cvsroot/olsrd co -P olsrd-current
 
−
  as anonymous user)
 
−
      cvs -d:pserver:anonymous@olsrd.cvs.sourceforge.net:/cvsroot/olsrd login
 
−
      cvs -z3 -d:pserver:anonymous@olsrd.cvs.sourceforge.net:/cvsroot/olsrd co -P olsrd-current
 
  
 
= Links =
 
= Links =
 
== Papers, Theory ==
 
== Papers, Theory ==
 +
 
* [http://ietfreport.isoc.org/idref/rfc3626/ RFC-3626]: the "OLSR RFC"
 
* [http://ietfreport.isoc.org/idref/rfc3626/ RFC-3626]: the "OLSR RFC"
 
* [http://www.lix.polytechnique.fr/hipercom/index.php?option=com_content&task=view&id=152&Itemid=1 Workshop at Hipercom Oct 2006]
 
* [http://www.lix.polytechnique.fr/hipercom/index.php?option=com_content&task=view&id=152&Itemid=1 Workshop at Hipercom Oct 2006]
Zeile 291: Zeile 244:
 
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
 
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
 
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF
 
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF
 +
* [http://ieeexplore.ieee.org/iel5/7693/4381387/04381410.pdf?isnumber=4381387&prod=JNL&arnumber=4381410&arSt=4014&ared=4024&arAuthor=Hamdaoui%2C+B.%3B+Ramanathan%2C+P. A Cross-Layer Admission Control Framework] for Wireless Ad-Hoc Networks using Multiple Antennas, Bechir Hamdaoui and Parameswaran Ramanathan
 +
* [http://www.orbit-lab.org/wiki/FAQ ORBIT simulator]
  
 
== misc ==
 
== misc ==
 
* Homepage: http://www.olsr.org/
 
* Homepage: http://www.olsr.org/
 
* NATO C3 Agency (NC3A) Radio Protocols Lab https://elayne.nc3a.nato.int/
 
* NATO C3 Agency (NC3A) Radio Protocols Lab https://elayne.nc3a.nato.int/
−
* commercial INRIA HIPERCOM spin-off http://www.luceor.com/
+
* commercial start-up http://www.luceor.com/
 
* commercial MIT Roofnet spin-off http://www.meraki.net/
 
* commercial MIT Roofnet spin-off http://www.meraki.net/
 +
 +
 +
[[Category:Dokumentation]]
 +
[[Category:Software]]
 +
[[Category:Routing]]
 +
[[Category: Abkürzungen]]

Aktuelle Version vom 12. Februar 2011, 21:26 Uhr

<google>OLSR</google>


WARNING: This page is very outdated by now! It purely serves to document the Netidee project of ~2007
Please go to http://www.olsr.org for more current and up to date info. This is here for historical reasons.


Goals

Our mission is simple. Build the most scalable and usable routing daemon routing wireless and fixed line segments. The routing daemon shall scale up to

  1. 10000 (10K) nodes and
  2. 20000 (20K) routes

running on low-cost hardware (200 Mhz RISC CPUs / 32MB of memory).

One of the main goals is to make OLSR more scalable in practice. 350px|right|Complexity for n=1000 nodes of different data structures in the Dijkstra shortest path (SPF) algorithm.

In the this picture you can see the different complexity graphs for the SPF under the assumption that every node has 10 edges . As you can see, the red line has O(n^2) complexity. This conformed to the implementation of OLSR from www.olsr.org (before the OLSR-NG project). OLSR-NG reduced the complexity to the green level. This will allow the mesh network clouds to become larger by a factor ~ 1000 (on the level of calculating the dijkstra (shortes path) algorithm so far).


For achieving that we first want to

  1. fix the existing olsrd and add new data structures and algorithms.
  2. Once olsrd is running fast we focus on protocol issues like
    1. measuring better links metrics, like including the bandwidth (ETT)
    2. link-state db synchronization issues (rather then brute force retransmission).

All protocol extensions shall be documented as an internet-draft and submitted to the IETF MANET working group http://www.ietf.org/html.charters/manet-charter.html


Next we want to improve the management tools of olsrd like the

  1. http_info plugin or
  2. txt_info plugins or
  3. building a new XMLinfo plugin

such that that large clouds consisting of thousands of nodes can be troubleshooted in an effective way.

Main OLSR-NG project blog: http://olsr.funkfeuer.at Slides from the OLSR-NG kickoff presentation: http://marvin.funkfeuer.at/~aaron/olsr-ng.pdf

Current Status

stable

  • olsrd 0.5.5 was released! Thx everybody a lot! - See changes int the Changelog

upcoming 0.5.6

buglist: Things that need to be changed before we release 0.5.6 

sven-ola: stimmt. glaub' ich auch. Da sind noch 2 Bugs drin.
[12:19pm] sven-ola: oder sogar drei. Das sind aus meiner Sicht:
[12:20pm] sven-ola: 1) das nach neustart unter http://localhost:2006/links derselbe Node mehrfach auftaucht
[12:20pm] sven-ola: 2) das etx_ff mit olsr-0.5.5 (oder etx_fpm) nur bis LQ=0.6 kommt
[12:20pm] sven-ola: 3) unter windoof: mehrfach Ifaces geht nicht (das mir eigentlich egal)
[12:22pm] sven-ola: bin mal kurz weg (olsrd neu start == nix inet)
...
fein. wobei das dringenste ist "neustart zeigt link mehrfach" - wenn das passiert muss man den nachbarn neu starten sonst gibts keine ordentlichen routen. Und wenn man gerade kein ssh zum Nachbarn hat, kann man lange warten <ggg>
  • Mac OS X: sendto() has wrong family parameter in OS X -> nothing gets send out
  • Bug in etx_ff <-> etx_fpm compatibility: if etx_ff (openBSD) does, then the topo entry still stays in (linux) etx_fpm
  • re-test everything on *all* OSes

200px|supported by IPA

The initial work of OLSR-NG was made possible by a grant from IPA.

After the grant, OLSR-NG still continues as a project. We are again looking for sponsors who believe in this work.

Sub projects

SPF refactoring

LSDB refactoring

RIB refactoring

miscellaneous improvements

UML test server

Data Structures and Algorithms

Who wants to contribute?

OLSR-NG is a open source project. Meaning everybody is invited to join in and help. We do have some bounties for the best solutions. If you want to participate, drop us an email: mailto:aaron@lo-res.org, mailto:hannes@gredler.at or mailto:bernd@firmix.at

Bounties

please take a look at the slides http://marvin.funkfeuer.at/~aaron/olsr-ng.pdf and get in contact with us directly.

Source code

  • Mercurial repo instructions 
 http://www.olsr.org/?q=mercurial/
Who is willing to work on something Contact info
Aaron Kaplan mailto:aaron@lo-res.org
Roman Steiner mailto:roman.steiner@gmx.at
Bernd Petrovitsch mailto:bernd@firmix.at
Andrej Rursev (zethix) mailto:zethix@gmail.com
Hannes Gredler mailto:hannes@gredler.at

Who is working on what?

Who What Status Comments
Bernd Petrovitsch, Thomas Lopatic, Hannes Gredler release 0.5 DONE
 ??? release 0.5 make packages for freifunk FW, DD-WRT, etc, windows (XP, Vista), ... and test them OPEN freifunk FW is done by Sven-Ola Tücke, .rpm and .deb by various people on olsr-dev@lists.olsr.org, Windows: ???
Aaron analyze IP autoconfig mechanisms and find the best one OPEN
Hannes Gredler tcpdump parses olsr packets, DONE
Hannes Gredler SPF improvements DONE
Hannes Gredler reduce malloc thrashing during SPF computation DONE
Hannes Gredler improve post-SPF handling (route table conciliation, best path selection) DONE
Bernd Petrovitsch rework the logging/tracing/error reporting WIP/stalled due to work in other areas
Bernd Petrovitsch rework the LQ-TC and LQ-HELLO input parsing, avoiding malloc/free thrashing DONE The output side can also be avoid malloc() and free(). Alas, the code is more complicated there.
Bernd Petrovitsch/Hannes Gredler/??? supersede all of the *_chgestruct() functions: All of them are called in exactly one place. So one can inline them there and use the pkg_get_*() functions to check and use the data. This also avoids more malloc/free thrashing and reduces the amount of code. WIP
Hannes Gredler spurious neighbor loss on nodes with high neighbor count OPEN/investigating
Aaron Kaplan,Bernd Petrovitsch olsr-ng test server DONE
Aaron Kaplan theory, complexity analysis. Goal: find the best complexity on the algorithmic side. DONE theory tells that fibonacci heaps are best, practise tells that an AVL tree as a minheap implementation fits the complexity of frequent re-keyings better
Zethix, Aaron Kaplan UML cluster setup WIP, currently we can start around 2000 UML instances. But the uml_switch software still drops packets between virtual interfaces. http://www.openvz.org seems also like a promising solution
Aaron Kaplan, Hannes draft. write a draft about LQ extensions OPEN
Bernd Petrovitsch Variuos Cleanup Mini- Projects DONE/WIP reworked floating point ops in src/mantissa.[ch] to minimize run-time impact, fixed dependencies, reworked ip address copying and comparison to get it type-safe,
Sebastian Sauer LinkQuality / metrics (e.g. ETX/ETT) improvements OPEN/WIP (no code yet committed) evaluate best current practice;
Sebastian Sauer FishEye improvements OPEN/investigating evaluate best current practice;
Sebastian Sauer effect of OLSR parameters on the mesh OPEN/investigating evaluate best current practice; spot and (maybe) eliminate dangers/instabilities
Sebastian Sauer selfish nodes / malicious nodes OPEN/investigating risk assessments

<mm>flash</mm>

Links

Papers, Theory

  AdHocSys is a two-year European project to provide reliable broadband services in rural and mountain regions. This objective
  will be achieved by means of the creation of a wireless ad hoc broadband network, with special enhancements to reliability
  and availability. The network consists of one or several gateways connecting to the global Internet and several intermediate
  nodes which provide multihop connections between the gateways and end users.

misc

Von „https://oldwiki.funkfeuer.at/index.php?title=OLSR-NG&oldid=11137“