OLSR-NG: Unterschied zwischen den Versionen

Aus FunkFeuer Wiki
Wechseln zu: Navigation, Suche
(remove double email lists)
(rephrased and fixed link to kick off slides)
Zeile 13: Zeile 13:
 
[[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).
  
  
Zeile 35: Zeile 35:
  
 
Main OLSR-NG project blog: http://olsr.funkfeuer.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
+
Slides from the OLSR-NG kickoff presentation: http://marvin.funkfeuer.at/~aaron/olsr-ng.pdf
  
 
= Current Status =
 
= Current Status =

Version vom 25. November 2007, 13:58 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 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

  • 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

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

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://outpost.funkfeuer.at/~aaron/olsr-ng.pdf and get in contact with us directly.

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


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
Bernd Petrovitsch rework the LQ-TC and LQ-HELLO input parsing, avoiding malloc thrashing DONE The output side can also be avoid malloc() and free(). Alas, the code is more complicated there.
Hannes Gredler spurious neighbor loss on nodes with high neighbor count OPEN/investigating
Aaron Kaplan,Bernd Petrovitsch olsr-ng test server DONE Well, the thing doesn't boot ATM. God knows why ....
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,
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=8114“