[Olsr-dev] Improving SPF with binary heaps

[Henning Rogge]

Hi,

olsrd is considered (by me and Ferry) end-of-live... we don't want
patches for the core code anymore, because they can introduce all
kinds of subtle bugs which sometimes take years to get out again.

If you want to use your idea, I would suggest looking at the olsrd2
code, which also use at the moment an AVL tree for the priority
queue... the problem is less severe there (because the metric has a
much higher range, which makes collisions less likely, but the olsrd2
code has not that many years of optimizations behind it.

Henning Rogge

On Thu, Jul 9, 2015 at 9:32 PM, Diogo Gonçalves
<(spam-protected)> wrote:
> 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 instead
> of binary heaps. Different from binary heaps, AVL is not originally
> intendend
> as a priority queue. To achieve O(log n) performance, AVL requires nodes
> with
> unique key values, which is not reasonable for a priority queues since
> different
> nodes can have the same priority. In fact, in the olsrd's SPF, nodes with
> same
> priority are put into a list. Then decrase-key procedure can be O(n) in some
> cases
> and Dijkstra becomes O(n*n) instead of O(n*logn). Binary heap is the most
> popular
> priority 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
> [2]
> https://opsci.informatik.uni-rostock.de/index.php/Network_quality_measurements#Datasets
>
> --
> Olsr-dev mailing list
> (spam-protected)
> https://lists.olsr.org/mailman/listinfo/olsr-dev