<div dir="ltr"><div><div>Hi Ferry,<br><br></div>Diogo will send an email reporting some results he has achieved. <br></div><div>He intends to support the patch and other member of our team will<br></div><div>join him in this task.<br></div><div><br></div><div>best<br></div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On 10 July 2015 at 02:50, Ferry Huberts <span dir="ltr"><<a href="mailto:mailings@hupie.com" target="_blank">mailings@hupie.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=""><br>
<br>
On 10/07/15 07:18, Henning Rogge wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
<br>
olsrd is considered (by me and Ferry) end-of-live... we don't want<br>
</blockquote>
<br></span>
true<br>
<br>
<br>
However,<br>
<br>
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.<br>
If the performance data shows that we really need this for scalability then I'll consider merging this.<br>
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.<br>
<br>
<br>
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.<div class="HOEnZb"><div class="h5"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
patches for the core code anymore, because they can introduce all<br>
kinds of subtle bugs which sometimes take years to get out again.<br>
<br>
If you want to use your idea, I would suggest looking at the olsrd2<br>
code, which also use at the moment an AVL tree for the priority<br>
queue... the problem is less severe there (because the metric has a<br>
much higher range, which makes collisions less likely, but the olsrd2<br>
code has not that many years of optimizations behind it.<br>
<br>
Henning Rogge<br>
<br>
On Thu, Jul 9, 2015 at 9:32 PM, Diogo Gonçalves<br>
<<a href="mailto:diogomachadogoncalves@gmail.com" target="_blank">diogomachadogoncalves@gmail.com</a>> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi all,<br>
<br>
I've studied performance of olsrd's SPF under different priority queues.<br>
We find it quite surprising that in olsrd Dijkstra is based on AVL instead<br>
of binary heaps. Different from binary heaps, AVL is not originally<br>
intendend<br>
as a priority queue. To achieve O(log n) performance, AVL requires nodes<br>
with<br>
unique key values, which is not reasonable for a priority queues since<br>
different<br>
nodes can have the same priority. In fact, in the olsrd's SPF, nodes with<br>
same<br>
priority are put into a list. Then decrase-key procedure can be O(n) in some<br>
cases<br>
and Dijkstra becomes O(n*n) instead of O(n*logn). Binary heap is the most<br>
popular<br>
priority queue for Dijkstra, achieving O(n*logn) regardless nodes have the<br>
same priority.<br>
I put in my github an initial version of binary heaps (BH) for olsrd [1].<br>
With traces from a 200-node mesh [2], Dijkstra-BH behaved very similar to<br>
Dijkstra-AVL.<br>
However, from 800 nodes, Dijkstra-BH drammatically outperformed<br>
Dijkstra-AVL.<br>
Comments, improvements and bugfixes are welcome,<br>
<br>
thanks in advance.<br>
<br>
[1] <a href="https://github.com/diogomg/olsrd" rel="noreferrer" target="_blank">https://github.com/diogomg/olsrd</a><br>
[2]<br>
<a href="https://opsci.informatik.uni-rostock.de/index.php/Network_quality_measurements#Datasets" rel="noreferrer" target="_blank">https://opsci.informatik.uni-rostock.de/index.php/Network_quality_measurements#Datasets</a><br>
<br>
--<br>
Olsr-dev mailing list<br>
<a href="mailto:Olsr-dev@lists.olsr.org" target="_blank">Olsr-dev@lists.olsr.org</a><br>
<a href="https://lists.olsr.org/mailman/listinfo/olsr-dev" rel="noreferrer" target="_blank">https://lists.olsr.org/mailman/listinfo/olsr-dev</a><br>
</blockquote>
<br>
</blockquote>
<br>
-- <br></div></div><span class="HOEnZb"><font color="#888888">
Ferry Huberts</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
-- <br>
Olsr-dev mailing list<br>
<a href="mailto:Olsr-dev@lists.olsr.org" target="_blank">Olsr-dev@lists.olsr.org</a><br>
<a href="https://lists.olsr.org/mailman/listinfo/olsr-dev" rel="noreferrer" target="_blank">https://lists.olsr.org/mailman/listinfo/olsr-dev</a></div></div></blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature">Saulo Jorge bq<br>-<br>"In theory, there is no difference between practice and theory, in practice there is"<br>-- Someone</div>
</div>