OLSR-NG: Unterschied zwischen den Versionen

struct

 NOTE! You are root on the system. Effectively we need lots of sudo privs. So... use it wisely.

 #!/bin/sh
 #
 # VARS
 #
 MAX_INSTANCES=1500
 ROOT_FS=root_fs
 NICELVL="-n 5"
 u=$USER
 #SINGLE=1

 $HOME/public_uml/share

 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.

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

 screen -ls              (as root)

 screen -S blabla.10.0.x.y -d -RR

 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!

 make clean 

 make stop

malloc()
free()
ltrace
malloc()
free()
malloc()
free()
malloc()
free()
xmalloc()
 (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

--- SPF-stats for 203 nodes, 335 routes (total/init/run/route/kern/cleanup):,, 237, 
--- SPF-stats for 203 nodes, 337 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 337 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 339 routes (total/init/run/route/kern/cleanup):,, 239, 
--- SPF-stats for 203 nodes, 339 routes (total/init/run/route/kern/cleanup):,, 238, 
--- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 240,
--- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 236, 
--- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 238, 
--- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 238, 
--- SPF-stats for 203 nodes, 345 routes (total/init/run/route/kern/cleanup):,, 239, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238, 
--- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 238, 

AVL heap:
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 143,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145, 
--- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144, 
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145, 
--- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145, 
--- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145, 
--- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 142, 
--- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 146, 

  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.

@@ Zeile 1: / Zeile 1: @@
 <google>OLSR</google>
+= Goals =
-=  NEWS =
+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
-<p>We have released our first set of improvements to the olsrd SPF calculation module.</p>
+# 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'''.
+[[Bild:O-Dijkstra.gif|350px|right|Complexity for n=1000 nodes of different data structures in the Dijkstra shortest path (SPF) algorithm. ]]
-== SPF implementation ==
+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).
-When executing the [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm SPF calculation]
-upon every iteration the least cost path needs to be extracted and put on the result list.
-For that purpose olsrd-current does keep a linear list which has O(N) [http://en.wikipedia.org/wiki/Asymptotic_complexity asymptotic_complexity] to traverse.
-Every node needs to be visited, which
-has again O(N) [http://en.wikipedia.org/wiki/Asymptotic_complexity asymptotic_complexity]. This results in a total behavior of O(N^2) which can eat a lot
-of CPU where N is large (for example when there are hundreds of olsrd nodes in a network).
-== speed by efficient sorting ==
-modern SPF implementations use data structures which are efficient at sorting the preliminary path costs like
-[http://en.wikipedia.org/wiki/Min_heap min_heaps] or [http://en.wikipedia.org/wiki/AVL_tree AVL_trees]. Since olsrd already
-had a nice and efficient AVL tree implementation, the two SPF related data structures (the candidate and path tree) are implemented using
-AVL trees with the path etx metric as the key. Determining the minimal path cost in an AVL tree comes at a cost of O(log(N)) which results
-in a total [http://en.wikipedia.org/wiki/Asymptotic_complexity asymptotic_complexity] of O(N * log(N)), which scales much nicer now in large networks.
-== Results ==
+For achieving that we first want to
-In the [http://www.funkfeuer.at funkfeuer.at] network topology of 190 nodes the raw SPF execution was reduced by 45%. Note that the raw SPF execution represents only about 20% of the CPU cost in a running olsrd. At funkfeuer.at we have observed an overall decrease in the CPU load of about 12% on the embedded routers.
-== Outlook ==
+# fix the existing olsrd and add new data structures and algorithms.
--20% (depending on network size) in the route-handling module is admittedly not exciting. During refactoring the SPF implementation the olsrd-ng development team, has spotted further bottlenecks in the existing implementation. We are tackling this one by one, and would need active participation of the wireless communities to test our improvements and verify if we have added any undesired regressions. so stay tuned and report bugs to the [mailto:olsr-dev@lists.olsr.org olsrd-dev] mailing list.
+# Once olsrd is running fast we focus on protocol issues like
-<hr>
+## measuring better links metrics, like including the bandwidth (ETT)
-please check out the [http://tema.lo-res.org/~aaron/spf-refactoring.diff.gz patch]
+## 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
-= sponsor =
-[[Bild:netideelogo.png|200px|supported by IPA]] made possible by a grant from [http://www.netidee.at IPA].  Thanks we really appreciate your help and your courage to support us!
+Next we want to improve the management tools of olsrd like the
-= main links =
+# http_info plugin or
+# txt_info plugins or
+# building a new XMLinfo plugin
-Main OLSR-NG project blog: http://olsr.funkfeuer.at
+such that that large clouds consisting of thousands of nodes
+can be troubleshooted in an effective way.
-Slides from the OLSR-NG kickoff presentation: http://outpost.funkfeuer.at/~aaron/olsr-ng.pdf
+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
-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
+= Current Status =
-= Goals =
+* 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
-# Clean up the code of OLSR (http://www.olsr.org),
+= sponsor =
-# 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 [http://open-mesh.net/batman B.A.T.M.A.N])
+[[Bild:netideelogo.png|200px|supported by IPA]] made possible by a grant from [http://www.netidee.at IPA].  Thanks we really appreciate your help and your courage to support us!
-OLSR-NG is a open source project. Meaning everybody is invited to join in and help.
+= main links =
-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
+Main OLSR-NG project blog: http://olsr.funkfeuer.at
-One of the main goals is to make OLSR more scalable '''in practice'''.
+Slides from the OLSR-NG kickoff presentation: http://outpost.funkfeuer.at/~aaron/olsr-ng.pdf
-[[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).
+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
-= 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
 == [http://www.user-mode-linux.org UML] test server ==

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

Operation	Binary	Binomial	Fibonacci
createHeap	Θ(1)	Θ(1)	Θ(1)
findMin	Θ(1)	O(lg n) or Θ(1)	Θ(1)
deleteMin	Θ(lg n)	Θ(lg n)	O(lg n)
insert	Θ(lg n)	O(lg n)	Θ(1)
decreaseKey	Θ(lg n)	Θ(lg n)	Θ(1)
merge	Θ(n)	O(lg n)	Θ(1)

OLSR-NG: Unterschied zwischen den Versionen

Version vom 24. November 2007, 13:27 Uhr

Inhaltsverzeichnis

Goals

Current Status

sponsor

main links

UML test server

current open todos UML server

User HOWTO

Open questions/bug reports?

Who wants to contribute?

Who is working on what?

Next Steps

Bounties

Source code

Theory section

data structures

other interesting data structures not directly related

See also

Notes

Links

Papers, Theory

misc

Navigationsmenü

Ansichten

Meine Werkzeuge

Navigation

Externe Links

Wiki

Suche

Werkzeuge