Hannes: initial cut for SPF refactoring

2007-11-24T12:58:13Z

initial cut for SPF refactoring

Neue Seite

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

SPF refactoring - Versionsgeschichte

Hannes: initial cut for SPF refactoring