FunkFeuer Wiki - Benutzerbeiträge [de]

OLSR-NG

2008-02-14T11:26:46Z

Hannes: remove pointer to CVS repo

OLSR-NG

2008-02-08T09:54:36Z

Hannes: /* Current Status */

OLSR-NG

2008-01-20T18:44:45Z

Hannes: Add link to Mercurial howto

OLSR-NG

2007-11-24T13:29:57Z

Hannes: remove double email lists

Miscellaneous improvements

2007-11-24T13:26:58Z

Hannes:

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''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 ''struct''s. 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.
** ....

OLSR-NG

2007-11-24T13:26:27Z

Hannes: move out olsr issues

OLSR-NG

2007-11-24T13:20:17Z

Hannes:

Data Structures and Algorithms

2007-11-24T13:18:08Z

Hannes:

= Heaps =

[[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for Dijkstra path exploration (relax function)

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)).
Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%. all results are in us based on a Intel celeron running at 1300 Mhz.

== Fibonacci heap ==

<pre>
--- 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,
</pre>

== AVL heap ==

<pre>
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,
</pre>

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

Data Structures and Algorithms

2007-11-24T13:16:16Z

Hannes:

Data Structures and Algorithms

2007-11-24T13:14:28Z

Hannes: /* Heaps */

= Heaps =

* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)).
Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%. all results are in us based on a Intel celeron running at 1300 Mhz.

== Fibonacci heap ==

<pre>
--- 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,
</pre>
== AVL heap ==
<pre>
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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== AVL heap ==

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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

Data Structures and Algorithms

2007-11-24T13:13:20Z

Hannes: /* Fibonacci heap */

= Heaps =

* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

== Fibonacci heap ==

<pre>
--- 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,
</pre>
== AVL heap ==
<pre>
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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== AVL heap ==

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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

Data Structures and Algorithms

2007-11-24T13:12:15Z

Hannes: first cut for data Structures

OLSR-NG

2007-11-24T13:10:29Z

Hannes:

OLSR-NG

2007-11-24T13:09:52Z

Hannes: move data structures and algorithms out

UML test server

2007-11-24T13:04:07Z

Hannes: give UML server pages a new home

= [http://www.user-mode-linux.org UML] test server =

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

== current open todos UML server ==
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

== User HOWTO ==

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

== Open questions/bug reports? ==

OLSR-NG

2007-11-24T13:03:15Z

Hannes: move the UML server section

OLSR-NG

2007-11-24T13:01:18Z

Hannes:

<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

# 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. ]]

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

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

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

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

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

= Subprojects =

==[[SPF refactoring]]==
==[[LSDB refactoring]]==
==[[RIB refactoring]]==

= 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 . All commit messages can be seen on the olsr-cvs list

== [http://www.user-mode-linux.org UML] test server ==

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

=== current open todos UML server ===
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

=== User HOWTO ===

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

=== Open questions/bug reports? ===

= Who wants to contribute? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | 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? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
!align="left" | Comments
|- class="oeffentlich"
| 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>[[olsr-ng.mm|flash]]</mm>

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

= Next Steps =

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''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 ''struct''s. 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

= Theory section =

== data structures ==
* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

fibonacci heap:

<pre>
--- 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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

==Notes==
<references/>

= Links =
== Papers, Theory ==
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [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

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

OLSR-NG

2007-11-24T12:59:25Z

Hannes: move SPF refactoring into a dedicated page

<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

# 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. ]]

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

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

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

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

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

= Subprojects =

==[[SPF refactoring]]==

= 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 . All commit messages can be seen on the olsr-cvs list

== [http://www.user-mode-linux.org UML] test server ==

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

=== current open todos UML server ===
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

=== User HOWTO ===

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

=== Open questions/bug reports? ===

= Who wants to contribute? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | 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? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
!align="left" | Comments
|- class="oeffentlich"
| 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>[[olsr-ng.mm|flash]]</mm>

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

= Next Steps =

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''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 ''struct''s. 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

= Theory section =

== data structures ==
* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

fibonacci heap:

<pre>
--- 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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

==Notes==
<references/>

= Links =
== Papers, Theory ==
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [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

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

SPF refactoring

2007-11-24T12:58:13Z

Hannes: initial cut for SPF refactoring

= SPF implementation =
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 =
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.

OLSR-NG

2007-11-24T12:33:46Z

Hannes: /* SPF refactoring */

<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

# 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. ]]

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

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

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

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

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

= Subprojects =

==[[SPF refactoring]]==

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

= 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 . All commit messages can be seen on the olsr-cvs list

== [http://www.user-mode-linux.org UML] test server ==

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

=== current open todos UML server ===
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

=== User HOWTO ===

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

=== Open questions/bug reports? ===

= Who wants to contribute? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | 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? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
!align="left" | Comments
|- class="oeffentlich"
| 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>[[olsr-ng.mm|flash]]</mm>

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

= Next Steps =

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''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 ''struct''s. 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

= Theory section =

== data structures ==
* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

fibonacci heap:

<pre>
--- 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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

==Notes==
<references/>

= Links =
== Papers, Theory ==
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [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

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

OLSR-NG

2007-11-24T12:32:46Z

Hannes: flesh out SPF refactoring page

<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

# 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. ]]

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

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

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

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

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

= Subprojects =

==[[SPF refactoring]]==

= 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 . All commit messages can be seen on the olsr-cvs list

== [http://www.user-mode-linux.org UML] test server ==

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

=== current open todos UML server ===
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

=== User HOWTO ===

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

=== Open questions/bug reports? ===

= Who wants to contribute? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | 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? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
!align="left" | Comments
|- class="oeffentlich"
| 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>[[olsr-ng.mm|flash]]</mm>

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

= Next Steps =

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''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 ''struct''s. 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

= Theory section =

== data structures ==
* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

fibonacci heap:

<pre>
--- 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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

==Notes==
<references/>

= Links =
== Papers, Theory ==
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [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

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

OLSR-NG

2007-11-24T12:27:59Z

Hannes: rework goals

<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

# 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. ]]

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

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

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

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

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

= 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 . All commit messages can be seen on the olsr-cvs list

== [http://www.user-mode-linux.org UML] test server ==

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

=== current open todos UML server ===
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

=== User HOWTO ===

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

=== Open questions/bug reports? ===

= Who wants to contribute? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | 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? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
!align="left" | Comments
|- class="oeffentlich"
| 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>[[olsr-ng.mm|flash]]</mm>

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

= Next Steps =

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''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 ''struct''s. 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

= Theory section =

== data structures ==
* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

fibonacci heap:

<pre>
--- 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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

==Notes==
<references/>

= Links =
== Papers, Theory ==
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [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

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

OLSR-NG

2007-11-24T12:04:31Z

Hannes: /* Who is working on what? */

<google>OLSR</google>

= NEWS =

We have released our first set of improvements to the olsrd SPF calculation module.

== SPF implementation ==
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 ==
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 ==
10-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.
<hr>
please check out the [http://tema.lo-res.org/~aaron/spf-refactoring.diff.gz patch]

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

= 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 . All commit messages can be seen on the olsr-cvs list

= Goals =

# Clean up the code of OLSR (http://www.olsr.org),
# 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])

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

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

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

=== current open todos UML server ===
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

=== User HOWTO ===

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

=== Open questions/bug reports? ===

= Who wants to contribute? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | 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? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
!align="left" | Comments
|- class="oeffentlich"
| 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>[[olsr-ng.mm|flash]]</mm>

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

= Next Steps =

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''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 ''struct''s. 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

= Theory section =

== data structures ==
* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

fibonacci heap:

<pre>
--- 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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

==Notes==
<references/>

= Links =
== Papers, Theory ==
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [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

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

OLSR-NG

2007-09-18T17:47:33Z

Hannes: fibonacci heap bashing

<google>OLSR</google>

= NEWS =

We have released our first set of improvements to the olsrd SPF calculation module.

== SPF implementation ==
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 ==
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 ==
10-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.
<hr>
please check out the [http://tema.lo-res.org/~aaron/spf-refactoring.diff.gz patch]

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

= 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 . All commit messages can be seen on the olsr-cvs list

= Goals =

# Clean up the code of OLSR (http://www.olsr.org),
# 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])

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

= 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

== [http://www.user-mode-linux.org UML] test server ==

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

=== current open todos UML server ===
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

=== User HOWTO ===

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

=== Open questions/bug reports? ===

= Who wants to contribute? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | 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? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
!align="left" | Comments
|- class="oeffentlich"
| 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: ???
|-
| ???
| 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
|
|-
| Bernd Petrovitsch
| Variuos '''Cleanup''' Mini- Projects
| DONE/WIP
| reworked floating point ops in src/mantissa.[ch] to minimize run-time impact, fixed dependencies,
|}

<mm>[[olsr-ng.mm|flash]]</mm>

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

= Next Steps =

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''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 ''struct''s. 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

= Theory section =

== data structures ==
* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

fibonacci heap:

<pre>
--- 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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

==Notes==
<references/>

= Links =
== Papers, Theory ==
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF

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

OLSR-NG

2007-09-18T17:45:39Z

Hannes: inplace SPF is done

<google>OLSR</google>

= NEWS =

We have released our first set of improvements to the olsrd SPF calculation module.

== SPF implementation ==
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 ==
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 ==
10-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.
<hr>
please check out the [http://tema.lo-res.org/~aaron/spf-refactoring.diff.gz patch]

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

= 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 . All commit messages can be seen on the olsr-cvs list

= Goals =

# Clean up the code of OLSR (http://www.olsr.org),
# 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])

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

= 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

== [http://www.user-mode-linux.org UML] test server ==

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

=== current open todos UML server ===
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

=== User HOWTO ===

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

=== Open questions/bug reports? ===

= Who wants to contribute? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | 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? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
!align="left" | Comments
|- class="oeffentlich"
| 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: ???
|-
| ???
| 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
|
|-
| 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
|
|-
| Bernd Petrovitsch
| Variuos '''Cleanup''' Mini- Projects
| DONE/WIP
| reworked floating point ops in src/mantissa.[ch] to minimize run-time impact, fixed dependencies,
|}

<mm>[[olsr-ng.mm|flash]]</mm>

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

= Next Steps =

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''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 ''struct''s. 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

= Theory section =

== data structures ==
* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

fibonacci heap:

<pre>
--- 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,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

==Notes==
<references/>

= Links =
== Papers, Theory ==
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF

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

OLSR-NG

2007-08-23T12:49:50Z

Hannes: Update working packages

<google>OLSR</google>

= NEWS =

We have released our first set of improvements to the olsrd SPF calculation module.

== SPF implementation ==
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 ==
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 ==
10-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.
<hr>
please check out the [http://tema.lo-res.org/~aaron/spf-refactoring.diff.gz patch]

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

= 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 . All commit messages can be seen on the olsr-cvs list

= Goals =

# Clean up the code of OLSR (http://www.olsr.org),
# 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])

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

= 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

== [http://www.user-mode-linux.org UML] test server ==

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

=== current open todos UML server ===
Next important (*) things to do:
* DONE(aka) update texas's BIOS - FIXED
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

=== User HOWTO ===

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

=== Open questions/bug reports? ===

= Who wants to contribute? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | 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? =

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
|- class="oeffentlich"
| 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
|-
| ???
| 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
| WIP
|-
| Hannes Gredler
| improve post-SPF handling (route table conciliation, best path selection)
| DONE
|-
|Bernd Petrovitsch
| rework the logging system
| WIP
|-|-
|Bernd Petrovitsch
| rework the TC-LQ input parsing, avoiding malloc thrashing
| 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
|-
| 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
|}

<mm>[[olsr-ng.mm|flash]]</mm>

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

= Next Steps =

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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''' <tt>malloc()</tt>s and <tt>free()</tt>s - use <tt>ltrace</tt> to see this.
*** review <tt>malloc()</tt>/<tt>free()</tt> if it theys are superflous and can be implemented with buffers on the stack or just moving pointers around.
*** are there very frequently <tt>malloc()</tt>ed and <tt>free()</tt>d ''struct''? Perhaps a free list can help to avoid lots of <tt>malloc()</tt>/<tt>free()</tt> 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 <tt>xmalloc()</tt>, ''olsr_'' is IMHO quite long and there too many ''olsr_'' perfixed types and functions right now.)
** fixup error reporting/logging
** add synchronization and make the daemon multi-threading (e.g. 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''
** dependencies do not work - '''done'''
** merge quagga-svn and svan-ola quagga-patch and test it.
** ....

= 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

= Theory section =

== data structures ==
* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)).

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|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)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

==Notes==
<references/>

= Links =
== Papers, Theory ==
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF

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

OLSR-NG

2007-06-29T23:06:10Z

Hannes: /* Who is working on what? */

OLSR-NG

2007-06-29T23:00:55Z

Hannes: /* Who is working on what? */

OLSR-NG

2007-06-23T16:22:50Z

Hannes: add description and rationale about the recent SPF improvements

OLSR-NG

2007-06-21T17:55:41Z

Hannes: update hannes working packages

<google>OLSR</google>

== sponsor ==

[[Bild:netideelogo.png|800px|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!

== 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 . All commit messages can be seen on the olsr-cvs list

== Goals ==

# Clean up the code of OLSR (http://www.olsr.org),
# 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])

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

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

=== [http://www.user-mode-linux.org UML] test server ===

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

==== current open todos UML server ====
Next important (*) things to do:
* update texas's BIOS
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

==== User HOWTO ====

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

==== Open questions/bug reports? ====

== Who wants to contribute? ==

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | Contact info
|-
| Aaron Kaplan
| mailto:aaron@lo-res.org
|-
| Roman Steiner
| mailto:roman.steiner@gmx.at
|-
| Bernd Petrovich
| mailto:bernd@firmix.at
|-
| Andrej Rursev (zethix)
| mailto:zethix@gmail.com
|-
| Hannes Gredler
| mailto:hannes@gredler.at
|}

== Who is working on what? ==

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
|- class="oeffentlich"
| 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
|-
| ???
| analyze IP autoconfig mechanisms and find the best one
| OPEN
|-
| Hannes Gredler
| tcpdump parses olsr packets,
| DONE
|-
| Hannes Gredler
| SPF improvments
| DONE
|-
| Hannes Gredler
| reduce malloc thrashing during SPF computation
| not yet started
|-
| Hannes Gredler
| improve post-SPF handling (route table conciliation)
| WIP
|-
| 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
|}

[[Bild:Olsr-ng.png|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 [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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

== 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 ===
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF

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

OLSR-NG

2007-06-21T17:54:33Z

Hannes: fixup email

<google>OLSR</google>

== sponsor ==

[[Bild:netideelogo.png|800px|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!

== 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 . All commit messages can be seen on the olsr-cvs list

== Goals ==

# Clean up the code of OLSR (http://www.olsr.org),
# 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])

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

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

=== [http://www.user-mode-linux.org UML] test server ===

current load and statistics: http://texas.funkfeuer.at

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology-1-small.png|center|600px|topo map 1500 UML instances running in parallel. Note the packetloss!]]
(check out the [[TopologyPics archive]] also)

topo map 1500 UML instances running in parallel. Note the packetloss!

We have already been running 2000 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.
UML actually has other shortcomings: high CPU overhead, lots of context swiches. Trying to increase the performance at the moment...

==== current open todos UML server ====
Next important (*) things to do:
* update texas's BIOS
* add the packet loss tc rules (zethix already prepared it)
* create random netowkrs (easy)
* create network topologies based on a power law distribution ( a bit harder, but realistic for the internet)
* DONE(zethix) create scripts to find out which olsrd instances crashed
* create scripts to find out if a UML instance is not responsive anymore
* find better measurement tools . Look into sar
* DONE(aka) recompile host kernel and get rid of the "BUG: soft lockup detected on CPU#0!" messages
* DONE(aka) recompile host kernel and enable the preemtion patch
* DONE(zethix,aka) make hostfs so that developers can easily upload a new olsrd version to all uml instances. They should see the difference easily. Look into hostfs
* DONE(ake) increase performance of the UML simulator itself (decrease HZ, look into SKAS3 patch again, 32 bit recompile, talk with jeff etc)
* find more meaningful topology visualization tools (http://www.caida.org)
* add b.a.t.m.a.n to the root filesystem. (?)
* compare the scheduling / scalability of the test with [http://openvz.org/ OpenVZ] and [http://www.olsr.org/docs/README-Olsr-Switch.html olsr_switch]

==== User HOWTO ====

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

# log in
# make clean
# edit common.sh and adapt the parameters to your needs
#!/bin/sh
#
# VARS
#
MAX_INSTANCES=1500
ROOT_FS=root_fs
NICELVL="-n 5"
u=$USER
#SINGLE=1
We supply you with a good working root filesystem (root_fs) so no need to change that. The SINGLE parameter just says that you want to start a single instance and be logged in (needed for debugging purposes)
# the UML instance can read files and programs from
$HOME/public_uml/share
This is where you can put your programs or your version of olsrd (and its libs) or the B.A.T.M.A.N. binaries.

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.

# put your special rcS file into $HOME/public_uml/share/etc/init.d/ . This rcS file will be called from the UML instances /etc/init.d/rcS startup script. Starting olsrd etc must be done from this user supplied rcS. In case there is no user supplied rcS, then the standard olsrd with the standard settings of the root_fs (/etc/olsrd.conf) us started.

# make

This will start the simulation.

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

# Issuing commands inside UML manually - the 'make' command creates a screen session for every UML process it creates, and redirects its input and output there. You can use screen to attach to a particular session. Use
screen -ls (as root)
to list all available sessions, and
screen -S blabla.10.0.x.y -d -RR
to attach to a session. This will give you shell access to the system.

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!

# observe the success on http://texas.funkfeuer.at or create a new topo map via ( cd /var/www/topo; ./doit.sh ). If you see a [http://en.wikipedia.org/wiki/Complete_graph complete graph], then your version has little packetloss!

# stop it via
make clean
or
make stop

Please make sure (by looking at http://texas.funkfeuer.at) if you are the only person running a simulation at the moment!

'''Some things to note'''

* the topology visualisation scripts run with nice level +5
the UML instances with nicelevel +10 (see run.sh)
-> Never ever go higher than nicelevel 0 because then you will disturb the system monitoring (munin) tools and we will not be able to see what the seimulation is doing.
*

==== Open questions/bug reports? ====

== Who wants to contribute? ==

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who is willing to work on something
!align="left" | Contact info
|-
| Aaron Kaplan
| mailto:aaron@lo-res.org
|-
| Roman Steiner
| mailto:roman.steiner@gmx.at
|-
| Bernd Petrovich
| mailto:bernd@firmix.at
|-
| Andrej Rursev (zethix)
| mailto:zethix@gmail.com
|-
| Hannes Gredler
| mailto:hannes@gredler.at
|}

== Who is working on what? ==

{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
|- class="oeffentlich"
| 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
|-
| ???
| analyze IP autoconfig mechanisms and find the best one
| OPEN
|-
| 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
|}

[[Bild:Olsr-ng.png|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 [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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

== 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 ===
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF

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

OLSR-NG

2007-04-17T18:29:21Z

Hannes: /* Who is working on what? */

== sponsor ==

[[Bild:netideelogo.png|800px|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!

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

# Clean up the code of OLSR (http://www.olsr.org),
# 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://www.open-mesh.org 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.
[[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).

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

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology.png|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 400 instances and there was still plenty of RAM left. So 500 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. More reserach on this is still needed however...

More info on the [http://www.user-mode-linux.org UML] server coming soon...

== Who is working on what? ==
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
|- class="oeffentlich"
| 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 500+ UML instances. http://www.openvz.org seems also like a promising solution
|}

[[Bild:Olsr-ng.png|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 [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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 ===
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF

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

Datei:Olsr-ng.mm

2007-04-17T18:27:55Z

Hannes: Mind Map der TODO Items

Mind Map der TODO Items

OLSR-NG

2007-04-17T18:26:20Z

Hannes: /* Who is working on what? */

== sponsor ==

[[Bild:netideelogo.png|800px|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!

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

# Clean up the code of OLSR (http://www.olsr.org),
# 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://www.open-mesh.org 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.
[[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).

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

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology.png|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 400 instances and there was still plenty of RAM left. So 500 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. More reserach on this is still needed however...

More info on the [http://www.user-mode-linux.org UML] server coming soon...

== Who is working on what? ==
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
|- class="oeffentlich"
| 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 500+ UML instances. http://www.openvz.org seems also like a promising solution
|}

[[Bild:Olsr-ng.png|mind map (using freemind) for all the work items]]

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

== Next Steps ==

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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 ===
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF

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

Datei:Olsr-ng.png

2007-04-17T18:23:34Z

Hannes: Mind map aller Ideen / Todos

Mind map aller Ideen / Todos

OLSR-NG

2007-04-17T18:21:29Z

Hannes: add mind map

== sponsor ==

[[Bild:netideelogo.png|800px|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!

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

# Clean up the code of OLSR (http://www.olsr.org),
# 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://www.open-mesh.org 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.
[[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).

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

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology.png|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 400 instances and there was still plenty of RAM left. So 500 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. More reserach on this is still needed however...

More info on the [http://www.user-mode-linux.org UML] server coming soon...

== Who is working on what? ==
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
|- class="oeffentlich"
| 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 500+ UML instances. http://www.openvz.org seems also like a promising solution
|}

[[Bild:olsr-ng.png|mind map (using freemind) for all the work items]]

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

== Next Steps ==

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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 ===
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF

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

OLSR-NG

2007-04-16T12:47:42Z

Hannes: Hannes working items

== sponsor ==

[[Bild:netideelogo.png|800px|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!

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

# Clean up the code of OLSR (http://www.olsr.org),
# 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://www.open-mesh.org 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.
[[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).

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

[[Bild:Texas.funkfeuer.at.png|right|300px|our UML server]]

[[Bild:Topology.png|center|500px|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 400 instances and there was still plenty of RAM left. So 500 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. More reserach on this is still needed however...

More info on the [http://www.user-mode-linux.org UML] server coming soon...

== Who is working on what? ==
{| width="80%" class="events" cellpadding="5" cellspacing="0" border="1"
!align="left" | Who
!align="left" | What
!align="left" | Status
|- class="oeffentlich"
| 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 500+ UML instances. http://www.openvz.org seems also like a promising solution
|}

contact mailto:aaron@lo-res.org or Bernd if you are interested in participating!

== Next Steps ==

* TU Wien lecture [http://tuwis.tuwien.ac.at/lva/tuwien/384090 "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 ===
* [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=60&Itemid=50 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.
* [http://folk.uio.no/kenneho/index.php?page=studies&subpage=wospf WOSPF-OR] Uni Oslo Wireless OSPF with Overlapping Relays
* [http://hipserver.mct.phantomworks.org/ietf/ospf/ W-OSPF] INRA/Boing Wireless OSPF

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