[Tinyos-devel] Re: CTP vs LQI

[Omprakash Gnawali]

On Dec 20, 2007 10:06 AM, Philip Levis <pal at cs.stanford.edu> wrote:
>
>
> On Dec 19, 2007, at 8:51 PM, Omprakash Gnawali wrote:
>
> > On Dec 19, 2007 10:56 AM, Philip Levis <pal at cs.stanford.edu> wrote:
> >>
> >>
> >> On Dec 19, 2007, at 4:08 AM, Omprakash Gnawali wrote:
> >>
> >>>> Om, can you run multiple alpha=9 and alpha=8 tests and then plot
> >>>> them
> >>>> against LQI tests?
> >>>
> >>> http://enl.usc.edu/~om_p/net2/post-hotnets/figures.html
> >>>
> >>> The points of interest are labeled aa8, aa9, ba8, and ca8. These are
> >>> the last four points on all the graphs. All these runs were about
> >>> 4000s long. They use the alpha values of 8, 9, 8, and 8. aa8,
> >>> aa9, and
> >>> aa8 runs were done back to back on the 15th. ca8 was done last night
> >>> using the GetLinkQuality fix that Jung suggested. The fix was to
> >>> return INFINITY if the link is not mature. The problem he found
> >>> was a
> >>> node might pin the root and never become a mature link (if it
> >>> does not
> >>> receive further beacons) in which case we should return INFINITY.
> >>> The
> >>> fix does not seem to have much impact on metrics other than max node
> >>> degree.
> >>>
> >>> How to answer: is alpha of 9 better than an alpha of 8? a9 seems to
> >>> have slightly higher delivery ratio than a8 and slightly lower cost
> >>> than a9. aa9 seems to have slightly higher delivery ratio than
> >>> aa8 or
> >>> ba8 and slightly lower cost than aa8 or ba8. So, I see some
> >>> consistency but it is not clear how statistically significant this
> >>> result is.
> >>>
> >>
> >> What's fascinating is the difference in depth. Given that CTP has a
> >> slightly higher cost/packet, a much lower drop rate, and a much
> >> higher average depth, does this mean that basically MLQI is dropping
> >> all of the distant packets? It would be interesting to see the CDF of
> >> per-source cost ratios (CTP/MLQI).
> >>
> >> Phil
> >>
> >
> >
> > I spent a good part of today studying the per packet cost and tree
> > depth. Here is the link to the figures:
> > http://enl.usc.edu/~om_p/net2/post-hotnets/figures.html
> >
> > The new metric is called goodcost - while cost used to measure the
> > total number of transmissions in the network, goodcost only counts the
> > number of transmissions associated with packets that were delivered to
> > the sink. The goodcost graph is immediately below the cost graph. Two
> > observations:
> >
> > 1. Goodcost and cost for CTP with high alpha values are similar.
> >
> > 2. Goodcost is smaller than cost for LQI. Similar result for CTP
> > with low
> > alpha values.
> >
> > The goodcost and cost graphs together show that LQI puts quite some
> > effort in the network on pkts that could not be delivered. On the
> > other
> > hand CTP tries hard to delivery most of the pkts which is why goodcost
> > and cost are similar. So, CTP costs are low because of high
> > delivery ratio
> > while LQI costs are low because of low retransmission count.
> >
> > To look at the details of goodcost, I plotted 14 distribution graphs
> > at the bottom
> > of the page. What is really interesting is the shape of the
> > distribution for LQI
> > and CTP - CTP distribution seems to be steeper than that of LQI. I
> > guess this
> > means for LQI sometimes the path is good and sometimes it is not.
> > But for
> > CTP the path is good most of the time and when it is not a few of
> > those times,
> > the packets swirl around the network: this explains the steepness
> > for majority
> > of the pkts and flatness near the top for all CTP runs.
> >
> > Is depth low because MLQI is dropping pkts from farther away?
> >
> > I think we need to look at two aspects of MLQI here:
> >
> > 1. The network topology. If you look at the tree on these pages,
> > you will
> > notice that the trees are actually short - at least according to
> > the parent
> > information on the pkts that were received at the sink. Looking at
> > the topology
> > formed by MLQI on those three experiments, we see a hub effect on
> > each topology (node 20, 16, and 16):
> > http://enl.usc.edu/~om_p/net2/post-hotnets/expt-12092007-1/index.html
> > http://enl.usc.edu/~om_p/net2/post-hotnets/expt-12012007-5/index.html
> > http://enl.usc.edu/~om_p/net2/post-hotnets/expt-12012007-6/index.html
> >
> > It is interesting that a large max degree is not helpful for MLQI
> > while
> > it is desirable for CTP because it tries to have large degree based on
> > links that are good. This is yet another insight on node degrees.
> >
> > 2. We can also look at the physical distance between the sources and
> > the sink and determine if MLQI drops pkts from nodes that are
> > physically
> > farther away.
> >
> > There is a graph called "Delivery ratio by node id" which shows the
> > delivery ratio for each node. We can clearly see the pattern here -
> > larger node id's in general correspond to lower delivery ratio for
> > MLQI
> > and CTP with small alpha values. You can look
> > at the physical layout of the nodes here for added clarity:
> > http://enl.usc.edu/projects/tutornet/index.html
> >
>
> Running LQI with the same retransmit threshold as CTP seems like a
> good experiment.
>
> Also, it would be interesting to see the time distribution of the
> very high cost packets. Are they mostly an artifact of forming the
> topology, or do they continue to happen even after the network has
> been running for hours?
>
> Phil
>

I added four sets of graph to see if goodcost is roughly the same over time:
http://enl.usc.edu/~om_p/net2/post-hotnets/figures.html

The first set is called "cumpktcount(t) with goodcost(pkt)> 20 (ctp)
goodcost(pkt) > 8 (lqi)".
This graph plots the cumulative pkt count with "high" cost over time.
There are three
groups of links - the groups correspond to the experiments with
different durations. The first
six experiments (a1..lqi2) were about 1300 seconds long, the next set
(lqi3..ctpa5) were
about 3700 seconds long, and the last set (aa8..ca8) were about 4050
seconds long. If
the high cost pkts mostly occur in the beginning, we expect the
distribution to start out
steep and flatten later. If these occurrences are uniform, we expect
the distributions to be
linear. Two groups of the distributions are linear suggesting that the
high cost pkts are random
events. The middle group (in the graph) which actually correspond to
the last set of data that
goes to 4050 shows relatively more high cost pkts in the beginning
compared to later
in the experiment: 50% of the high cost pkts in the first 1/4 of the experiment.

We can look at the data in more detail using the next three sets of
data that are titled
goodcost(t), cumgoodcost(seq), and  cumgoodcost(t), which are at the
bottom of the page.
These three sets plot goodcost for all (high as well as low cost)
pkts. High cost pkts
are seen jumping out of the mass of colors randomly throughout the
experiment in goodcost(t).
The cumgoodcost(seq) seems mostly linear - which says that there is no systemic
improvement or degradation of tree quality over time. One
can see a few kinks here and there in the very beginning but later it
is mostly linear. We see
roughly the same thing in cumgoodcost(t) which plots goodcost as a
function of time instead
of pkt arrive. When there are pkt drops (lqi configurations) -
the transitions are almost flat because when the pkts are dropped
there is no measurement
and the next pkt is received with roughly the same cost as the previous one.
But if the pkt drops and goodcost over time are uniform, even with the
flat transitions, we still expect the cumgoodcost(t) to
be roughly linear. So, cumgoodcost(t) takes into account drops as well
as goodcost while
cumgoodcost(seq) only takes into account goodcost.

Finally cumgoodcost(seq) for ctp with low alpha shows piecewise
linearity with vertical jumps.
This corresponds to large number of retx that trigger parent selection
(which incurs a lot of cost) and finally
when a new path is established the linear part starts again because
rest of the pkts can use
the newly formed path. This might explain the situation with 4bita5 around 40s.

- om_p