[Olsr-dev] Improving SPF with binary heaps

[Saulo Queiroz]

In fact there are several possible topology combinations that lead nodes to
have the same
priority at a given instant of the SPF computation. Below it is illustrated
a scenario where
nodes have the same priority even with all link having different ETX.
The source S is extracted first because has priority zero. THen D and A
have priorities 3 and 2, respectivelly. Then A is extracted and C is
inserted in the queue with the same priority of D.
Then, the priority queue running in S will be O(n) instead of O(log n).

 S is the source, has priority zero. Then, A has highest priority and is
extracted.
 S------3------D (priority=3)
 |
2|
 |
 A(priority=2)
  \
   \1
    \
     C (priority=3)



On 9 July 2015 at 18:06, Bastian Bittorf <(spam-protected)> wrote:

> * Diogo Gonçalves <(spam-protected)> [09.07.2015 23:02]:
> > Yes, in this case, all nodes with the same ETX value(var 'leader' equals
> > 0) are put in next and prev pointers(like a list) of the first
> avl_node(var
> > 'leader' equals 1) with the ETX value inserted in the tree.
>
> we have such a "dumb" setup running:
> 1 node is connected to ~100 other nodes via ethernet.
> everybody has EXT 0.100 (etx_ffeth) to the "master" and
> OLSR consumes really much cpu-time. There are other nodes
> (wireless) too in the network, so for administration it was
> easy to just "speak" OLSR everywhere...
>
> our workaround was to choose large timing values
> (e.g. HELLO-interval of 10 seconds)...
>
> bye, bastian
>
> --
> 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/20150709/224b3df9/attachment.html>