[Olsr-dev] Improving SPF with binary heaps

[Diogo Gonçalves]

*Hi all,I've studied performance of olsrd's SPF under different priority
queues.We find it quite surprising that in olsrd Dijkstra is based on AVL
insteadof binary heaps. Different from binary heaps, AVL is not originally
intendendas a priority queue. To achieve O(log n) performance, AVL requires
nodes withunique key values, which is not reasonable for a priority queues
since differentnodes can have the same priority. In fact, in the olsrd's
SPF, nodes with samepriority are put into a list. Then decrase-key
procedure can be O(n) in some casesand Dijkstra becomes O(n*n) instead of
O(n*logn). Binary heap is the most popularpriority queue for Dijkstra,
achieving O(n*logn) regardless nodes have the same priority.I put in my
github an initial version of binary heaps (BH) for olsrd [1].With traces
from a 200-node mesh [2], Dijkstra-BH behaved very similar to
Dijkstra-AVL.However, from 800 nodes, Dijkstra-BH drammatically
outperformed Dijkstra-AVL.Comments, improvements and bugfixes are
welcome,thanks in advance.[1] https://github.com/diogomg/olsrd
<https://github.com/diogomg/olsrd>[2]
https://opsci.informatik.uni-rostock.de/index.php/Network_quality_measurements#Datasets
<https://opsci.informatik.uni-rostock.de/index.php/Network_quality_measurements#Datasets>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20150709/93bfa4f9/attachment.html>