[Olsr-dev] SPF refactoring

Hannes Gredler (spam-protected)
Thu Jun 21 14:21:57 CEST 2007

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.


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.


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


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



   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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: spf-refactoring.diff.gz
Type: application/octet-stream
Size: 8770 bytes
Desc: not available
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20070621/044ed9a1/attachment.obj>

More information about the Olsr-dev mailing list