[Berlin-wireless] Fwd: [Olsr-dev] SPF refactoring

Aaron Kaplan aaron
Fr Jun 22 15:25:38 CEST 2007



Begin forwarded message:

> From: Hannes Gredler <hannes at juniper.net>
> Date: June 21, 2007 2:21:57 PM GMT+02:00
> To: olsr-dev at olsr.org
> Subject: [Olsr-dev] SPF refactoring
>
> hi olsr developers,
>
> find attached a patch that reworks the SPF implementation of olsrd.
>
> the patch works twofold to get to a decent N*lg(N) runtime performance
> of the SPF algorithm and result processing.
>
> 1. use of an AVL tree
>
>    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).
>
> --
>
> find below some runtime measurements taken on a 1300Mhz celeron
> based on the funkfeuer.at topology with > 350 nodes.
>
> explanation:
>
> init:  the time for synthesizing the vertices from the TC messages
>        and neighbor tables.
>
> run:   basic dijkstra runtime
>
> route: host route processing
>
> han:   hna route processing.
>
> -->olsrd-current
>
>    --- SPF-stats: init 662us, run 302us, route 248us, hna 335us
>    --- SPF-stats: init 637us, run 303us, route 234us, hna 327us
>    --- SPF-stats: init 680us, run 302us, route 271us, hna 445us
>    --- SPF-stats: init 721us, run 303us, route 286us, hna 363us
>    --- SPF-stats: init 704us, run 302us, route 270us, hna 353us
>    --- SPF-stats: init 671us, run 304us, route 254us, hna 555us
>    --- SPF-stats: init 658us, run 303us, route 246us, hna 332us
>    --- SPF-stats: init 705us, run 304us, route 271us, hna 443us
>    --- SPF-stats: init 726us, run 305us, route 282us, hna 363us
>    --- SPF-stats: init 707us, run 304us, route 271us, hna 352us
>    --- SPF-stats: init 708us, run 304us, route 269us, hna 347us
>    --- SPF-stats: init 724us, run 304us, route 282us, hna 403us
>    --- SPF-stats: init 673us, run 304us, route 253us, hna 334us
>
> -->olsrd-spf-refactoring
>
>    --- SPF-stats: init 667us, run 168us, route 213us, hna 398us
>    --- SPF-stats: init 676us, run 170us, route 227us, hna 443us
>    --- SPF-stats: init 644us, run 170us, route 203us, hna 287us
>    --- SPF-stats: init 677us, run 180us, route 232us, hna 454us
>    --- SPF-stats: init 665us, run 169us, route 214us, hna 455us
>    --- SPF-stats: init 660us, run 169us, route 215us, hna 455us
>    --- SPF-stats: init 719us, run 169us, route 233us, hna 276us
>    --- SPF-stats: init 715us, run 168us, route 241us, hna 575us
>    --- SPF-stats: init 700us, run 168us, route 239us, hna 374us
>    --- SPF-stats: init 680us, run 168us, route 224us, hna 525us
>    --- SPF-stats: init 709us, run 168us, route 239us, hna 279us
>    --- SPF-stats: init 659us, run 169us, route 209us, hna 413us
>    --- SPF-stats: init 688us, run 181us, route 227us, hna 347us
>    --- SPF-stats: init 646us, run 170us, route 220us, hna 342us
>
>
> <-- as you can see there is still some headroom for improvement,
>     my next target is the route and hna_route processing.
>
> asking for inclusion in the CVS and testing based on large topologies.
>
> tx,
>
> /hannes
>
> P.S.
>   many thanks to thomas lopatic for extending the avl library
>   to fit my needs (most notable deletion and thread walking support)
>   and bernd petrovitch/aaron kaplan for making the funkfeuer.at
>   topology available for testing.
-------------- nächster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : spf-refactoring.diff.gz
Dateityp    : application/octet-stream
Dateigröße  : 8770 bytes
Beschreibung: nicht verfügbar
URL         : <http://lists.berlin.freifunk.net/pipermail/berlin/attachments/20070622/73ce9fe9/attachment.obj>
-------------- nächster Teil --------------
> -- 
> Olsr-dev mailing list
> Olsr-dev at lists.olsr.org
> https://lists.olsr.org/mailman/listinfo/olsr-dev

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






Mehr Informationen über die Mailingliste Berlin