OLSR-NG: Unterschied zwischen den Versionen
Aus FunkFeuer Wiki
Hannes (Diskussion | Beiträge) |
Aaron (Diskussion | Beiträge) (re-wording to make henning happy) |
||
| (29 dazwischenliegende Versionen von 9 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
<google>OLSR</google> | <google>OLSR</google> | ||
| + | |||
| + | |||
| + | <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> | ||
| + | |||
= Goals = | = Goals = | ||
| Zeile 13: | Zeile 17: | ||
[[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 | + | 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 34: | Zeile 38: | ||
can be troubleshooted in an effective way. | can be troubleshooted in an effective way. | ||
| − | OLSR-NG | + | 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 = | = Current Status = | ||
| − | * olsrd 0.5. | + | === stable === |
| − | + | * 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] | |
| − | + | ||
| − | = | + | === upcoming 0.5.6 === |
| − | + | '''buglist:''' Things that ''need'' to be changed before we release 0.5.6 | |
| − | = | + | <pre> |
| + | 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> | ||
| + | </pre> | ||
| − | + | * 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 | |
| − | = | + | = sponsor = |
| − | + | [[Bild:netideelogo.png|200px|supported by IPA]] | |
| − | + | The initial work of OLSR-NG was made possible by a grant from [http://www.netidee.at 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/ | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | = | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1" | {| width="80%" class="events" cellpadding="5" cellspacing="0" border="1" | ||
| Zeile 187: | Zeile 119: | ||
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1" | {| width="80%" class="events" cellpadding="5" cellspacing="0" border="1" | ||
| − | !align="left" | + | !align="left" | Who |
!align="left" | What | !align="left" | What | ||
!align="left" | Status | !align="left" | Status | ||
| Zeile 229: | Zeile 161: | ||
| Bernd Petrovitsch | | Bernd Petrovitsch | ||
| rework the logging/tracing/error reporting | | rework the logging/tracing/error reporting | ||
| − | | WIP | + | | WIP/stalled due to work in other areas |
| | | | ||
| − | + | |- | |
| Bernd Petrovitsch | | Bernd Petrovitsch | ||
| − | | rework the LQ-TC and LQ-HELLO input parsing, avoiding malloc thrashing | + | | rework the LQ-TC and LQ-HELLO input parsing, avoiding malloc/free thrashing |
| DONE | | DONE | ||
| − | | The output side can also be avoid malloc() and free(). Alas, the code is more complicated there. | + | | 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 | ||
| Zeile 245: | Zeile 182: | ||
| olsr-ng test server | | olsr-ng test server | ||
| DONE | | DONE | ||
| − | | | + | | |
|- | |- | ||
| Aaron Kaplan | | Aaron Kaplan | ||
| Zeile 265: | Zeile 202: | ||
| Variuos '''Cleanup''' Mini- Projects | | Variuos '''Cleanup''' Mini- Projects | ||
| DONE/WIP | | DONE/WIP | ||
| − | | reworked floating point ops in src/mantissa.[ch] to minimize run-time impact, fixed dependencies, | + | | 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 | | Sebastian Sauer | ||
| Zeile 290: | Zeile 227: | ||
<mm>[[olsr-ng.mm|flash]]</mm> | <mm>[[olsr-ng.mm|flash]]</mm> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
= 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 447: | Zeile 245: | ||
* [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://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 | + | * 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.
Please go to http://www.olsr.org for more current and up to date info. This is here for historical reasons.
Inhaltsverzeichnis
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
- 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. 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
- 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
Next we want to improve the management tools of olsrd like the
- http_info plugin or
- txt_info plugins or
- 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
sponsor
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
- 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.
- 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
- ORBIT simulator
misc
- Homepage: http://www.olsr.org/
- NATO C3 Agency (NC3A) Radio Protocols Lab https://elayne.nc3a.nato.int/
- commercial start-up http://www.luceor.com/
- commercial MIT Roofnet spin-off http://www.meraki.net/
