A High-Throughput Path Metric for Multi-Hop Wireless Networking

First of all, I would usually refer to this paper as "the ETX paper," and will make a few general comments about this work. One, if it seems surprising that something this simple could be novel as late as 2003, I think a few points are in order. Previous routing protocols for wired network like RIP or OSPF do allow metrics for path computation and use Dijkstra or Bellman-Ford to compute routes (in the case of link state protocols), but they tend to use rather simplistic link metrics like hop count or bandwidth. The most important difference between these link metrics and this work is that the link quality in wireless cannot generally be know beforehand. Thus, the key change is not really the particular metric, but the the fact you need to do on-the-fly estimation of the link quality.

A fundamental difference between wireless and wired network is that the process of routing in wireless can be thought of as a two step process. In the first step, "topology formation," a routing topology is chosen, where decisions are made are which links are to be used, and the second, "routing," actual paths are chosen through the network. What should be noted is that the innovation of ETX is to combine these two steps where the metric implicitly weeds out poor links. In contrast, the previous technique of routing based on hop count does not make this separation; in order to form a hop-count based path, you must first take a position on which links are available to be routed over. This issue is explored more deeply in Alec Woo's thesis; the basic result is that you can't just have a threshold to determine which links are good to route over. We also discuss this issue in [1].

One way this work is over simplistic is its treatment of the estimation problem. Their estimator computes a simple windowed estimate over 10 seconds of the packet reception ratio in both directions, and inverts this to form an expected transmission count. This metric has a number of nice properties, like correlation with energy cost of using the link, and also provides an estimate for an appropriate number of link-layer retransmissions to use. There has been some advance on this front; more current implementations might use an EWMA filter, but there is still the parameter tuning problem of choosing a horizon. Newer link estimators like [2] attempt to add more information to further improve performance.

Their evaluation is lengthy and somewhat tedious at this point; perhaps it was more of a surprise five years ago then it is now that a decent path metric is a good idea.


[1] The Effect of Link Churn on Wireless Routing. Stephen Dawson-Haggerty,
Jorge Ortiz, Xiaofan Fred Jiang and David E. Culler. Technical Report
No. UCB/EECS-2008-109, University of California Berkeley, Computer Science
Division. 2008.
[2] Four-Bit Wireless Link Estimation. Rodrigo Fonseca,Omprakash Gnawali,Kyle Jamieson, and Philip Levis. HotNets 2007