[Olsr-dev] Improving SPF with binary heaps

[Ferry Huberts]

On 10/07/15 07:18, Henning Rogge wrote:
> Hi,
>
> olsrd is considered (by me and Ferry) end-of-live... we don't want

true


However,

I'd be willing to consider this if you support the patch with 
performance data and do tests against the current implementation to 
catch regressions.
If the performance data shows that we really need this for scalability 
then I'll consider merging this.
You'd make it easier for me to merge if you can find a way to keep the 
old implementation so that one can choose which implementation to use.


If the complexity of the patch is high then you'd also need lots of 
comments in the code to make it easier for me to review.

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

-- 
Ferry Huberts