[Tinyos-devel] Re: from longer CTP/LQI experiments

[Rodrigo Fonseca]

>
> I'm against all of these approaches. They are heavyweight for what
> seems to be a rare event. The only problem these transient loops
> introduce is a waste of energy. We can always put a max-THL threshold
> if we're concerned about this. Note that even with the loops, CTP is
> still more efficient than LQI.
>
> Phil
>

I am not sure this is a rare event. I conjecture that this fast
sending of packets in loops is the cause of the terrible performance
in Tutornet with very low alphas.
The alternatives I discussed above are for avoiding or fixing the
loops. You are right that we don't have to break the loops, but should
do something about them. Just adding a max-thl will drop the packets,
but other subsequent packets will have the same fate. If a node
detects it is in a loop it should refrain from sending until the loop
is fixed.

Perhaps we should throttle the sending rate proportionally to the thl
of a packet? We want to slow down if we are in a loop.

Here's another idea: we add a path bloom filter to the beacon packets.
When trying to select a parent, you look at the path bloom filter and
see if *you* are part of the path. If you are, you don't select that
parent. This way, you will never select your descendants as your
parents, and loops are not possible. The result of false-positives is
that you may refrain from selecting valid paths, and the filter has to
be dimensioned to control the chance of this happening.

For example, if we have an 10-byte bloom filter (80 bits), expect 10
nodes in a path, and use 4 or 5 hash functions, the probability of a
false positive is around 2%. Recall that the beacon packets are very
small currently, as we don't need to send reverse quality info.

Rodrigo