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

This paper presents the ETX (Expected Transmission Count) metric, which finds the most reliable path on a multi-hop wireless network. This metric takes into account problems that cause loss on the network, unlike a simple minimum hop-count. The idea is that a longer path might still be faster than a shorter path if the longer path is more reliable. They attempt to calculate the expected number of retransmissions using packet loss measurements.

They set up a 29-node wireless testbed across five floors of an office building. They then showed that a minimum hop-count metric did not find the highest-throughput route. I'm a little suspicious of their calculation of the highest-throughput route after the fact; they have to estimate the interference on each route. I also found Figure 2 really darn confusing. It seems like the min hop-count metric gets closer to the highest-throughput as the packets per second increases, and at one point (around 200-250 pps) EXCEEDS the highest throughput??

Their experiment on the testbed shows that their design of a new metric needs to account for a wide range of loss ratios; asymmetric loss ratios; and interference between successive hops in a multi-hop path. The ETX for a single link is the predicted number of data transmissions based on the forward and reverse delivery ratios of the link. The ETX for a route is the sum of the ETX for each link in that route.

This paper fits into our ongoing discussion of how the network stack is broken up into layers. ETX assumes that the link layer is making retransmissions (since they are trying to minimize the number of retransmissions). ETX doesn't route around congestion; they say this is a bonus because it avoids oscillations, but I wonder if this actually could be a useful feature?

They then implement ETX (as part of both DSDV and DSR) and compare the paths it finds to min hop-count. I find their graphs pretty impossible to read -- I can't tell which line is which in Figure 6. Looking at Figure 7, it appears that ETX did perform better (at least on paths that were longer than one hop). One question I'd have about their methodology is whether a network should really be modeled as just random pairs of communicating nodes; it seems like network usage might be clustered in certain areas (i.e., one node is getting a lot more traffic), which would change interference patterns.