[Olsr-dev] Improving SPF with binary heaps

[Saulo Queiroz]

Hi Ferry,

Diogo will send an email reporting some results he has achieved.
He intends to support the patch and other member of our team will
join him in this task.

best


On 10 July 2015 at 02:50, Ferry Huberts <(spam-protected)> wrote:

>
>
> 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
>
>
> --
> Olsr-dev mailing list
> (spam-protected)
> https://lists.olsr.org/mailman/listinfo/olsr-dev
>



-- 
Saulo Jorge bq
-
"In theory, there is no difference between practice and theory, in practice
there is"
-- Someone
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20150711/c330017a/attachment.html>