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

Summary
This paper looks at improving routing in wireless networks that often use routes with more than one hop. Their metric, expected transmission count (ETX), tries to find the route that has the fewest number of expected transmissions on the path to the destination. In a network with no loss, this is clearly the same as a minimum hop-count algorithm, but in real networks with expected losses, this is not the case. As the paper point out, minimizing hop-count will tend to favor long hops, which in the wireless world are often weak links with poor throughput and high loss rates. This leads to poor path selection in practice.

The paper shows simulated results the indicate that, in networks where paths are typically 3 or more hops, ETX performs much better than a minimum hop-count algorithm.

The ETX metric considers expected losses in both the forward and backward direction. If df is the probabilty that a packet is sucesfully transmitted in the forward direction and dr in the reverse, then ETX = 1 / (df x dr). The delivery ratios are computed using probe packets.

The authors implement ETX in the DSDV and DSR routing schemes. Their results show that it works well in both cases with some minor modifications.

Finally the authors point out that their metrics are not perfect as the probe packets are always the same size (and smaller than typical data packets) but links might have different characteristics when the packets are of different sizes. It seems like this could be solved by including metrics from actual packet transmissions into the algorithm, and also by varying the probe packet size.

Thoughts
I liked this paper. It gives a clear description of the problem with minimum hop-count routing, and nicely explains their new metric.

A few issues I had:

• The graph style for the throughput measurements is terrible and makes extracting data from the graph difficult. This is mostly just a formatting gripe however.
• There is a 'probe window' in which a certain number of probes are supposed to have been sent. The delivery ratios are calculated using this expected value and the actual # of received probes. This requires all nodes in the network to have the same configuration for window size and probe frequency and could make incremental upgrade difficult.
• Probe packets contains the # of probes received from all it's neighbors. In a dense network this could make the probe packets quite big and hurt overall throughput.
• DSR with failure feedback does almost as well as ETX. Does this indicate that really all we care about is failed links and we don't need to do all the extra work ETX is doing?

Still, I enjoyed this paper and think it's worth keeping on the reading list.