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

[Omprakash Gnawali]

On Dec 27, 2007 10:39 PM, Rodrigo Fonseca <rfonseca at cs.berkeley.edu> wrote:
>
> > > The assumption is that if there's a loop, then CTP can detect it and
> > > break it. The single-hop route ETX value in the packet lets CTP
> > > detect loops: if a node receives a packet whose sender has a lower
> > > ETX, then CTP pauses data transmissions and sends a routing beacon,
> > > which should hopefully then update that sender's route ETX for this
> > > node and possibly lead to a new route selection.
> > >
> > > Unless, of course, the three nodes are disconnected from the rest of
> > > the network...
> > >
> > > Phil
> > >
> >
> > What if the sender has the same ETX?
> >
> > The loop starts around 1198216099. The third argument to NEW_PARENT
> > and SENT_BEACON is the etx from that parent and from the node. All of
> > them, when they choose a new parent, the parents are estimated to have
> > an etx of 100... Should we say it is a loop if etx is <= than current
> > node's etx rather than < ?
> >
> > That still does not explain how we got into the loop in the first
> > place. Here is my guess: nodes 40, 38, 37, and 41 report node 36 as
> > their parent before the loop events. They all report that node 36 has
> > an etx of 100. By 16092, the etx of 36 has gone up to 118; 36 sends a
> > beacon with this new etx. Now the nodes 40, 38, 37, and 41, which
> > probably have low and equal etx to 36 realize that they can do much
> > better by selecting each other as their parent and they switch to a
> > new parent immediately after 16092. Combination of getting into a loop
> > and not breaking out of it because of the "<" check results in pkts
> > looping. Does this make sense?
>
> Om,
>
> Phil is right in that if the nodes get disconnected, the cycle formed
> between 40, 38, and 41, will 'count to infinity'.

Yes, but the nodes were not disconnected so they were counting to the
best parent that had a path to the root.


> The <= check will detect more loops than the <, but the nodes will not
> break it until the count reaches the cost that connects the loop to
> the network again (in this case the cost to link to node 36).

The "<" and "<=" comment was just about this particular loop - it
seems like "<=" would have broken the loop sooner.


> Can you take a look at the successive beacons nodes 40, 38, 41 send,
> if they are indeed counting to infinity? It seems that they are.

In the excerpts above, node 41 selected a new parent in 1198216111 and
the loop was broken. Until this time, the nodes were counting to
infinity (incrementing their etx) but the counting did not go on for
even one full iteration. In iteration 0, they created a cycle, then in
the next iteration, they broke out of that particular cycle.


>
> There are ways to really break the loop:
>   - in the routing protocol: change to a DSDV-like
> versioned-information (so you don't select old information)
>   -                                           change to a path-vector
> protocol (no loops and no C-T-I)
>   - When forwarding: keep a limited history of the path in the
> packets, and not send to a node in the loop again. There has to be
> some way in the routing protocol to memorize this, once you select a
> parent that breaks the loop
>
> Maybe a compromise is to use a path-vector like protocol, but instead
> of keeping the entire path, keep the last K nodes in the path. This
> would prevent loops of size K.
>
> Rodrigo
>

A reactive approach would be to detect a loop and count to infinity
faster so that we find a new parent faster. This loop would have been
broken sooner if the loop was detected faster because we already have
a mechanism to send a becon if a loop is detected.

- om_p