OLSR-NG: Unterschied zwischen den Versionen

Aus FunkFeuer Wiki
Wechseln zu: Navigation, Suche
(→‎UML test server)
K (→‎Goals)
Zeile 23: Zeile 23:
  
  
−
One of the main goals is to make OLSR more scalable <i>in practice</i>.  
+
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. ]]
  

Version vom 20. April 2007, 02:10 Uhr

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

Goals

  1. Clean up the code of OLSR (http://www.olsr.org),
  2. improve the algorithms of OLSR and make it more scalable.
  3. 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

right|300px|our UML server

center|600px|topo map of first UML instances running in parallel. All instances are connected via one single uml_switch (virtual HW switch)

topo map of first UML instances running in parallel. All instances are connected via one single uml_switch (virtual HW switch)

We have already been running 1000 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. Aaron was already running 2000 instances.

More info on the UML server coming soon...

Who is working on what?

Who What Status
Bernd Petrovitsch, Thomas Lopatic, Hannes Gredler release 0.5 DONE
Hannes Gredler tcpdump parses olsr packets, DONE
Hannes Gredler SPF improvments WIP
Hannes Gredler reduce malloc thrashing during SPF computation WIP
Hannes Gredler improve post-SPF handling (route table conciliation) not yet started
Aaron Kaplan,Bernd Petrovitsch olsr-ng test server WIP
Aaron Kaplan theory, complexity analysis. Goal: find the best complexity on the algorithmic side. The basic ideas seem like 90% finished. Will be presented at the TU lecture "Verteilte Systeme" ("Distributed Systems"), 20.4.2007
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

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
  • 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

  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

misc

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