OLSR-NG
<google>OLSR</google>
Inhaltsverzeichnis
NEWS
please check out hannes's new patches
sponsor
800px|supported by IPA made possible by a grant from 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
- Clean up the code of OLSR (http://www.olsr.org),
- improve the algorithms of OLSR and make it more scalable.
- 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 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
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 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).
Current Status
- olsrd 0.5 was released! Thx everybody a lot!
- 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
UML test server
current load and statistics: http://texas.funkfeuer.at
center|600px|topo map 1500 UML instances running in parallel. Note the packetloss! (check out the TopologyPics archive also)
topo map 1500 UML instances running in parallel. Note the packetloss!
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. UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...
current open todos UML server
Next important (*) things to do:
- update texas's BIOS
- 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 OpenVZ and olsr_switch
User HOWTO
NOTE! You are root on the system. Effectively we need lots of sudo privs. So... use it wisely.
- log in
- make clean
- edit common.sh and adapt the parameters to your needs
#!/bin/sh # # VARS # MAX_INSTANCES=1500 ROOT_FS=root_fs NICELVL="-n 5" 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 start in your simulation, so, they all have read-only access to it. It will appear inside each UML as /mnt/share/. There is also another, 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.
- make
This will start the simulation.
N.B. When the simulation is started, an olsrd instance is started on 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
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 for the duration of the simulation! Once it is stopped, changes will be lost!
- 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 complete graph, then your version has little packetloss!
- stop it via
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!
Some things to note
- the topology visualisation scripts run with nice level +5
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?
Who wants to contribute?
Who is willing to work on something | Contact info |
---|---|
Aaron Kaplan | mailto:aaron@lo-res.org |
Roman Steiner | mailto:roman.steiner@gmx.at |
Bernd Petrovich | 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 |
---|---|---|
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 |
??? | analyze IP autoconfig mechanisms and find the best one | OPEN |
Hannes Gredler | tcpdump parses olsr packets, | DONE |
Hannes Gredler | SPF improvments | DONE |
Hannes Gredler | reduce malloc thrashing during SPF computation | not yet started |
Hannes Gredler | improve post-SPF handling (route table conciliation) | WIP |
Aaron Kaplan,Bernd Petrovitsch | olsr-ng test server | DONE |
Aaron Kaplan | theory, complexity analysis. Goal: find the best complexity on the algorithmic side. | DONE |
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 |
<mm>[[Olsr-ngTODO]</mm>
mind map for all the TODO/work items
contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!
Next Steps
- TU Wien lecture "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
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
Papers, Theory
- RFC-3626: the "OLSR RFC"
- Workshop at Hipercom Oct 2006
- OLSR-v2 Draft 01 at hipercom
- http://www.adhocsys.org/
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
- Homepage: http://www.olsr.org/
- NATO C3 Agency (NC3A) Radio Protocols Lab https://elayne.nc3a.nato.int/
- commercial INRIA HIPERCOM spin-off http://www.luceor.com/
- commercial MIT Roofnet spin-off http://www.meraki.net/