[Discuss] Fwd: [Olsr-cvs] olsrd-current CHANGELOG,1.61,1.62

[Aaron Kaplan]

Hallo!

ich wollte euch nur auf eine wichtige sache hinweisen, die vielleicht  
untergegangen ist.
Die scheinbar harmlose commit message unten heisst, dass wir

  complexity O(n*log(n)) statt O(n^2) ist offiziell im OLSR source  
drinnen haben :)

was heisst das? Das heisst wir sind jetzt von der CPU last auf der  
gruenen linie
auf

   http://wiki.funkfeuer.at/index.php/Bild:O-Dijkstra.gif

sind. (Vorher wars die rote). Merkbar wird das erst bei grossen  
netzen. Dann aber massgeblich!

Ich denke, dass wir somit das wichtigste Ziel von OLSR-NG vorerst  
einmal erreicht haben.
Wahrlich, es muesste laut theoretischer Informatik noch besser gehen,  
aber in der praxis ist das jetzt schon mal
viel.

Soweit ich weiss ist der neue olsrd schon in der aktuellesten  
freifunk firmware vorhanden.
Ein ganz grosser dank gebuehrt Hannes Gredler, Sven-Ola Tuecke und  
Bernd Petrovitsch fuer die viele viele arbeit die in all dem steckt!!  
Ebenfalls moechte ich mich bei der IPA (netidee.at) bedanken, die  
dieses projekt unterstuetzt.

lg,
a.



Begin forwarded message:

> From: Bernd Petrovitsch <(spam-protected)>
> Date: July 6, 2007 12:43:48 AM GMT+02:00
> To: (spam-protected)
> Subject: [Olsr-cvs] olsrd-current CHANGELOG,1.61,1.62
>
> Update of /cvsroot/olsrd/olsrd-current
> In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv28283
>
> Modified Files:
> 	CHANGELOG
> Log Message:
> added the SPF refactoring from Hannes Gredler <(spam-protected)>:
>
> 1. use of an AVL tree as a min-heap implementation
>
>    as a means for efficient sorting.
>    (the etx metric is used as the key in the candidate tree)
>
> 2. next-hop propagation
>
>    rather than tracking the previous node in olsr_relax()
>    i have changed that model and pre-populate all one-hop neighbors
>    with their own IP adress as 'next-hop' and pull that
>    pointer up once new paths are explored.
>
>    as a result no walker for counting hops and extracting next-hops
>    is required - it turns out at this is slighly more efficient
>    than the existing behaviour (even with the cache applied).
>
>
> Index: CHANGELOG
> ===================================================================
> RCS file: /cvsroot/olsrd/olsrd-current/CHANGELOG,v
> retrieving revision 1.61
> retrieving revision 1.62
> diff -C2 -d -r1.61 -r1.62
> *** CHANGELOG	2 Jul 2007 11:05:48 -0000	1.61
> --- CHANGELOG	5 Jul 2007 22:43:46 -0000	1.62
> ***************
> *** 5,11 ****
>
>   MISC
> ! Upgrade to olsr-bmf 1.5
>
> ! latitude/longitude support is now in the nameservice plugin
>
>   CLEANUPS
> --- 5,32 ----
>
>   MISC
> ! Upgrade to olsr-bmf 1.5 from Erik Tromp <(spam-protected)>
>
> ! latitude/longitude support is now in the nameservice plugin done by
> ! Sven-Ola Tuecke <(spam-protected)>
> !
> ! added the spf refactoring patch from  Hannes Gredler  
> <(spam-protected)> whicht saves
> ! a noteworthy amount of CPU time. To quite him:
> ! ----  snip  ----
> ! 1. use of an AVL tree as a min-heap implementation
> !
> !    as a means for efficient sorting.
> !    (the etx metric is used as the key in the candidate tree)
> !
> ! 2. next-hop propagation
> !
> !    rather than tracking the previous node in olsr_relax()
> !    i have changed that model and pre-populate all one-hop neighbors
> !    with their own IP adress as 'next-hop' and pull that
> !    pointer up once new paths are explored.
> !
> !    as a result no walker for counting hops and extracting next-hops
> !    is required - it turns out at this is slighly more efficient
> !    than the existing behaviour (even with the cache applied).
> ! ----  snip  ----
>
>   CLEANUPS
>
>
> -- 
> Olsr-cvs mailing list
> (spam-protected)
> http://lists.olsr.org/mailman/listinfo/olsr-cvs
>

---
there's no place like 127.0.0.1
until we found ::1 -- which is even bigger