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

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

One line summary: This paper presented ETX, a new routing metric for wireless networks that attempts to maximize path throughput; this paper also explains why min hop count is a poor metric for use in wireless networks and performs an evaluation comparing min hop count with ETX.

Summary

This paper presented a new metric for routing in wireless networks called the expected transmission count (ETX). It compares ETX with the most commonly used metric: minimum hop count, which is implicitly based on the assumptions that links either work well or don’t work at all. The authors give several reasons why, as a result, routing protocols that use min hop count as their metric for selecting paths achieve poor performance in wireless networks. They further quantify these reasons via evaluation of the min hop count metric in a test bed. One reason min hop count performs poorly is that by minimizing the number of hops, it maximizes the distance traveled in each hop, which is likely to also minimize the signal strength and maximize the loss ratio. Min hop count performs well when the shortest path is also the fastest path, but that is frequently not the case in wireless networks. When there are a number of paths with the same minimum hop count, routing protocols often choose one at random, and this is unlikely to be the best choice. Another issue is that min hop count does not deal well with asymmetric links, which are common in wireless networks. Lastly, min hop count does not take into account the wide range of loss ratios for links in wireless networks.

Given these considerations, the authors state that ETX must be able to account for the wide range of link loss ratios, the existence of asymmetric links, and the interference between hops in a multi-hop path. ETX is designed to maximize throughput. The ETX of a path is the sum of the ETX of each link in the path. The ETX of a link is defined as one over the expected probability that a transmission over that link is successfully received and acknowledged. This probability is calculated using the delivery ratios in both forward and reverse directions over the link. Delivery ratios are calculated using probe packets. Five important characteristics of ETX according to the authors are (1) it is based on delivery ratios, (2) it detects and handles asymmetry, (3) it uses precise link loss ratio measurements, (4) it penalizes routes with more hops, and (5) it minimizes spectrum use. Some drawbacks of ETX are that it only makes sense for networks with link layer retransmissions, it assumes radios have a fixed transmit power, it is susceptible to problems due to MAC unfairness under high load, when the highest throughput path has more than three hops it might not choose that path, and lastly, it does not account for mobility.

ETX was evaluated by implementing two routing protocols, DSDV and DSR, to use it as the routing metric and compare with those same protocols using min hop count as the routing metric. Some conclusions they draw with respect to DSDV are that ETX performs better than min hop count especially when min hop count uses paths with asymmetric links, ETX incurs more overhead than min hop count, ETX overestimates the delivery ratio for large data packets and underestimates it for small ACKs, ETX outperforms DSDV with a handshaking scheme, and ETX performance improves when a certain delay-use modification is used. With respect to DSR, they found that link failure feedback allows DSR with min hop count to perform as well as DSR with ETX.

Critique

I didn’t like this paper as well as I liked the Roofnet paper. I don’t think that ETX turned out to be as impressive in the evaluation section as the authors made it sound in the initial sections, so that was kind of disappointing. In the Roofnet paper, they don’t actually use ETX directly, but use a more sophisticated metric called ETT. I thought the authors’ explanations in the beginning of the paper for why min hop count performs poorly in wireless networks were nice. I wasn’t as impressed with the rest of it. I thought it was interesting that DSR with min hop count and link failure notification allowed DSR to perform pretty much as well as DSR with ETX. I wonder how ETX would compare with other tougher competitors beyond just the naïve min hop count metric. ETX clearly has some unsatisfactory features, including the overhead of using it with DSDV and its tendency to misestimate the delivery ratio for packets that are much smaller or much larger than probe packets. Also, some other things about the evaluation section confused me. For instance, their explanation of why you shouldn’t compare runs was confusing. It seems that they used entirely different parameters (packet size, transmit power) in different runs according to the labels on the graphs, but then they say you shouldn’t compare them because the network conditions change over time, not because the parameters are different. Even though I am not very enthusiastic about this paper and ETX didn’t turn out to be as great as the authors imply at the beginning of the paper, there is probably still a lot of interesting things to learn from in here, things to do as well as things not to do. The authors clearly learned from this experience because they created an improved metric, ETT, for Roofnet.