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

[Omprakash Gnawali]

On Dec 27, 2007 6:40 PM, Philip Levis <pal at cs.stanford.edu> wrote:
>
> On Dec 27, 2007, at 6:21 PM, Rodrigo Fonseca wrote:
>
> > This is what this loop *looks*  like, in a quasi-standard network
> > timing diagram (please see the attached png and the simple perl script
> > that generates it).
> >
> > We can notice two things: the nodes are quite stubborn, and take a
> > long time to change their minds. They keep sending the packets on the
> > same path over and over again. It seems to me that adding some limited
> > loop memory (either to packets at forwarding time or keeping track of
> > path segments at route formation time) would go a long way. We would
> > need to see the distribution of the number of unique nodes in a path
> > to evaluate the size of such memory.
>
> 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?

node 40:

1198215867.459412: NET_C_TREE_SENT_BEACON 36 0 100 4777 0
1198216093.640462: NET_C_TREE_NEW_PARENT 30 0 89 4931 0
1198216099.8334: NET_C_TREE_NEW_PARENT 38 0 100 4937 0
1198216104.395694: NET_C_TREE_NEW_PARENT 37 0 100 5254 0
1198216109.234895: NET_C_TREE_SENT_BEACON 37 0 140 5418 0

node 38:

1198215970.689580: NET_C_TREE_SENT_BEACON 36 0 100 4274 0
1198216097.641703: NET_C_TREE_NEW_PARENT 41 0 100 4307 0
1198216103.761647: NET_C_TREE_SENT_BEACON 41 0 120 4585 0
1198216103.789552: NET_C_TREE_SENT_BEACON 41 0 120 4590 0
1198216103.963615: NET_C_TREE_SENT_BEACON 41 0 120 4598 0


node 37:

1198215871.819253: NET_C_TREE_SENT_BEACON 36 0 100 4003 0
1198216094.366184: NET_C_TREE_NEW_PARENT 38 0 100 4061 0
1198216103.273925: NET_C_TREE_SENT_BEACON 38 0 110 4064 0
1198216108.709444: NET_C_TREE_SENT_BEACON 38 0 130 4210 0
1198216108.813358: NET_C_TREE_SENT_BEACON 38 0 130 4215 0


node 41:

1198215932.693101: NET_C_TREE_SENT_BEACON 36 0 100 5171 0
1198216095.735322: NET_C_TREE_NEW_PARENT 40 0 100 5215 0
1198216103.519034: NET_C_TREE_SENT_BEACON 40 0 110 5473 0
1198216111.855892: NET_C_TREE_NEW_PARENT 34 0 108 5781 0
1198216117.292504: NET_C_TREE_SENT_BEACON 34 0 118 5822 0

node 36:

1198215489.324781: NET_C_TREE_SENT_BEACON 31 0 90 14344 0
1198215491.172421: NET_C_TREE_SENT_BEACON 31 0 90 14353 0
1198216087.895590: NET_C_TREE_NEW_PARENT 34 0 93 16542 0
1198216088.132099: NET_C_TREE_SENT_BEACON 34 0 103 16549 0
1198216092.42822: NET_C_TREE_SENT_BEACON 34 0 118 16563 0
1198216121.196314: NET_C_TREE_SENT_BEACON 34 0 118 16598 0


- om_p