D. De Couto, D. Aguayo, J. Bicket, R. Morris, “A High Throughput Path Metric for Multi-Hop Wireless Routing,” ACM Mobicom Conference, (September 2003). [PDF]

Summary

This paper presents ETX (expected transmission count), a new metric to find high-throughput paths on multi-hop wireless networks (802.11b), which minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to its ultimate destination. Contrary to the minimum hop-count (MHC) metric, ETX incorporates link loss ratios, asymmetry in loss ratios between the two directions, and interference among successive links. Measurements in a 29-node testbed show that ETX improves average throughput of multi-hop routes by up to a factor of two over MHC.

The authors motivate ETX design by pointing out several flaws in MHC:

• MHC-based protocols implicitly assume that links either work (if probe packets go through) or don’t work at all. However, in wireless networks, links with intermediate loss ratios can exist that are good enough to transmit control packets (probe packets) but cannot transmit data packets  introducing errors. Also many links have asymmetric delivery ratios, which cannot be captured using MHC.
• By minimizing the hop-count, MHC protocols maximize distance traveled by each hop, which decreases signal strength and increases loss ratio. In addition, in a dense network many routes can exist with same MHC and arbitrarily selecting one route can significantly effect total transmission time.
• Experimental results show that MHC performs well whenever the shortest route is also the fastest route, especially when there is a one-hop link with low loss ratio. With increasing number of hops, MHC throughput decreases almost linearly.

Somewhat better approaches than MHC, product of per-link delivery ratios (PPLDR), bottleneck-loss-ratio (BLR), end-to-end delay (E2ED), also fail to account the wide range of loss ratios, asymmetry in loss ratios, and interference between successive hops. PPLDR and BLR fails to account for inter-hop interference (e.g., perfect two-hop link is better than a one-hop link with 1% loss ratio) and E2ED introduces oscillation due to its high sensitivity to network load (as queues go larger and smaller, E2ED can vary widely).

ETX calculates forward and reverse delivery ratios of a link and uses the inverse of the product of the two to estimate expected number of transmissions. The ETX of a route is calculated by summing indivual ETXes of each link. As a result, ETX accounts for asymmetry (by using forward and reverse loss ratios), interference (by summing up ETXes along the path), and link loss ratios (by definition). Since delivery ratios are directly related to throughput, ETX can better predict throughput than MHC and other approaches.

The rest of paper provides gory details of the modifications they had to make to the DSDV and DSR protocols to make them work with ETX. Apparently, no one, not even the people who created DSDV and DSR,  are 100% sure about different implementation details; the authors did whatever they saw fit to make them work.

In the evaluation section, the authors match up ETX-modified DSDV and DSR against their MHC counterparts and convincingly find ETX winning every rounds!

Critique

ETX is much better than MHC, but it was sort of obvious from their motivation briefing. A better evaluation could have been against PPLDR or E2ED. Btw, the same group came up with a even better metric ETT (estimated transmission time) in their future work.

ETX performed bad for large packet sizes. The authors argued that using small probe packets introduced and over-estimation of link qualities, which was visible for larger packet sizes. Why they did not consider large prob packets (possibly of same size as the data packets) and evaluate performance in that is not clear.

Somewhere in the paper it is mentioned that ETX tends to reduce spectrum use, which was not clear.