SPF refactoring

SPF implementation

When executing the 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) asymptotic_complexity to traverse. Every node needs to be visited, which has again O(N) 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 min_heaps or 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 asymptotic_complexity of O(N * log(N)), which scales much nicer now in large networks.

Results

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