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

[Rodrigo Fonseca]

> > 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'.
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).

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.

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