[Olsr-dev] SPF refactoring

[Hannes Gredler]

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