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

[Omprakash Gnawali]

On Dec 28, 2007 10:14 AM, Rodrigo Fonseca <rfonseca at cs.berkeley.edu> wrote:
> >
> > 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.

How do we know we are in a loop? Just looking at THL isn't enough. If
we know we are in a loop, the mechanism we have might be good enough
to quickly break out of 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
>

I was thinking about a similar idea on data pkts - to encode the path
taken thus far using a byte or two but doing this on the beacons, as
you note, is a much better idea.

Are you assuming universal hash functions for these probabilities? Are
there good hash functions on motes that require little CPU and code
overhead?

- om_p