Subject: [Roll] state overhead for ETX computation / draft-gnawali-roll-etxof

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 22 Mar 2010 23:26:29 -0700

Dear all,

There was a question during my presentation today on the ETX Objective Function
about the state requirement to estimate the ETX metric of links. The concern was
a parent needs to keep track of PRR for link to each child. If a parent has 1000
children, the PRR estimation table needs to have 1000 entries.

Although the draft I was presenting or the metrics draft does not go into the
details of ETX computation, it is important to be convinced that it is possible
to compute ETX without such unacceptable state overhead.

Traditionally, ETX
is estimated by collecting unidirectional PRR estimates and combining
them using 1 / (Pr*Pb).
This method is presented as an example in the metrics draft, for example. If we
use this approach, it is true that
if a parent had n children, you would need n entries in the ETX
estimation table.
However, there are newer, and also mature, ways to compute ETX that
does not require an entry for each
children to estimate bi-directional ETX.

There was a paper in Mobicom 2006 [EAR], that showed how to use the
data-link acks to
measure ETX without estimating PRR for each direction separately.
There was a paper
in HotNets 2007 [4bitle] that showed ETX measurements that also used
data-link acks.
This paper compares a DAG formed using the "traditional" ETX estimates
and using the
[4bitle] estimator. The observation was, if we don't have room in our
ETX estimation
table for each neighboring node, the DAG formed is sub-optimal due to
the unavailability
of bi-directional ETX on many links that are perfectly usable.
However, with the 4bitle
ETX estimation, you can maintain a small number of entries on the ETX without
compromising the quality of the DAG, while still routing based on the
ETX metric.

In later work, a routing protocol called CTP Noe [CTP] showed how to
use the 4bitle
ETX estimator in a number of scenarios in sparse and dense networks.
Even in the densest
network, which had a (min,max) node degree of (214,305), CTP Noe was able to
estimate the link ETX and compute efficient and reliable routes
between the nodes and
the root using ETX. Even in such a network, it was sufficient to have
10 entries in
the ETX estimation table.

We cannot use the "traditional" estimation technique in these dense
networks with
high node degree, but there are proven, and now mature techniques
to compute ETX for dense networks. So, state overhead is not a concern for
link ETX measurement even in dense networks with a large number of
neighbors and children.

[EAR] K.-H. Kim and K. Shin. On Accurate Measurement of Link Quality
in Multi-hop Wireless Mesh Networks. In Proc. of the ACM
MobiCom Conf., pages 38–49, Los Angeles, CA, Sept. 2006.

[4bitle] R. Fonseca, O. Gnawali, K. Jamieson, and P. Levis. Four Bit
Wireless Link Estimation. In Hotnets-VI, Atlanta, GA, Nov.
2007.

[CTP] O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis.
Collection Tree Protocol. In Proceedings of the 7th ACM Conference
on Embedded Networked Sensor Systems (SenSys), 2009.

- om_p