Version vom 24. November 2007, 14:09 Uhr

<google>OLSR</google>

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 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).

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.

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

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

Current Status

• olsrd 0.5.4 was released! Thx everybody a lot! Big credits go out to Hannes and Bernd.
• 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

sponsor

200px|supported by IPA made possible by a grant from IPA. Thanks we really appreciate your help and your courage to support us!

Subprojects

SPF refactoring

LSDB refactoring

RIB refactoring

UML test server

Data Sturctures and Algorithms

Who wants to contribute?

Who is working on what?

<mm>flash</mm>

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
• more cleanups
  • olsrd is doing lots of malloc()s and free()s - use ltrace to see this.
    • review malloc()/free() if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
    • are there very frequently malloc()ed and free()d struct? Perhaps a free list can help to avoid lots of malloc()/free() 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 xmalloc(), olsr_ is IMHO quite long and there too many olsr_ perfixed types and functions right now.)
  • fixup error reporting/tracing/logging
  • add synchronization and make the daemon multi-threading (e.g. the bmf plugin uses it right now, 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). Work in progress
  • The incoming and outgoing packets are deserialized and serialized via pointers to packed structs. This is somewhat dangerous as other compilers or the same compielr for other architectures may or may not behave the same. And - worse - it misleads people to copy the same data various times around or play with pointers so no one can easily see ehat'e going on. I (Bernd) started with a more direct approach in src/lq_packet.c where we have one "unsigned char *" which walks sequentially through the incoming packet and gets the value with small inline functions into where one needs it later on - mostly some simple struct which is a normal C struct and used by the core code.
  • 'net_outbuffer_push() memcpy()es the packet from the caller supplied buffer into another buffer. Well, that's one more copy operation for every outgoinf packet.
  • ....

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.ietf.org/internet-drafts/draft-ietf-manet-olsrv2-02.txt
  • http://www.ietf.org/internet-drafts/draft-ietf-manet-packetbb-02.txt
  • http://olsrv2.online.fr/blog/ OLSRv2 Development Blog
• 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.

• WOSPF-OR Uni Oslo Wireless OSPF with Overlapping Relays
• W-OSPF INRA/Boing Wireless OSPF
• A Cross-Layer Admission Control Framework for Wireless Ad-Hoc Networks using Multiple Antennas, Bechir Hamdaoui and Parameswaran Ramanathan

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/