A High Throughput Path Metric for Multi-Hop Wireless Rounting

D. De Couto, D. Aguayo, J. Bicket, R. Morris, "A High Throughput Path Metric for Multi-Hop Wireless Rounting," ACM Mobicom Conference, (September 2003).

This paper presented ETX (Expected Transmission Count) metric which finds high throughput paths on multi-hop wireless networks and is much superior to the minimum hop count metric used before this paper was written. The authors implemented this metric in DSDV and DSR routing protocols and measured actual data on a 29 node 802.11b test-bed.

The authors started off by highlighting the fact that metrics like min hop count assume black and white links that is a given link either 'works' or doesn't. While this is reasonable to assume in wired networks, wireless links have considerable intermediate losses which might make some sets of links useful over others which the existing metric ignores. This led the authors into designing a much realistic metric which must account for the following issues:

• Link loss ratios.
• Asymmetric link ratios.
• Successive hop interference.

Though End-to-End delay metric pretty much accounts for all of the above, the authors claimed that having a congestion dependent metric can result in wide oscillations in path routes. Moreover, they claimed that load balancing/congestion control can anyway be performed by separate algorithms. This led to the proposal of the ETX metric. Simply put, ETX of a link predicted number of data transmissions required to ssend a packet over that link, including retransmissions. Mathematically, ETX = 1/(df * dr) where df and  dr are the forward and reverse delivery ratios respectively. These are measured by each node periodically broadcasting packets and the neighboring node keeping a ratio count of the packets it received and the packets it should have received during a w second length window. Further, the authors implemented this metric in DSDV and DSR algorithms and observed that ETX provided considerably better routes than min hop count metric. However, the authors observed that for a run with 1,386 byte packets, though ETX offered improvement over min hop count, the gain was not as large as for small packets. This was because of the fact that ETX was using small probes to estimate the link metric and their delivery counts did not accurately depict the actual loss rate due to difference in size.

Critique

My criticism for this paper has mostly got to do with the question of 'how much actual improvement it does it result in over minimum hop metric'?  Given the practical packet size issue, we saw that ETX doesn't always work as nicely as it is theoretically expected to. Not to mention that computing (and most importantly maintaining) ETX  metrics involves considerable overhead as compared to simple minimum hop count metric. Moreover, I would assume that minimum hop count is not a very good metric and is more of a workaround solution that performs badly for lossy links as is clearly shown by the author. If this is indeed the case, why didn't the authors compare their work to more realistic metrics (like the product approximation of per-link delivery ratios proposed by Yarvis et. al, which the authors did mention in their related work!) ?