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

Douglas DeCouto, Daniel Aguayo, John Bicket, Robert Morris, Wireless Networks 11, 419-34, 2005.

I had read a version of this paper a little while ago, but some reviewing duty sent me back to it to confirm a thing or two. It introduces the ETX measure, which is an additive measure to find the path between two nodes on a wireless mesh network which minimizes the number of retransmission.

That it is additive is a good thing, and it does not have the issues of other metric: shortest hop count might find long links with bad quality and the actual performance of shortest path is demonstrated in the paper to be quite poor. Using a product of delivery ratio (which is additive too if you take the logs) or the minimal PDR (again, additive in a (max,+) algebra) will favor multi-hop links with good PDR over a single link with lesser PDR, but the relaying interference of the multi-hop path will divide the bandwidth of the path by two, so it is not a good metric either.

ETX computes the delivery rate of a link in each direction and is computed as the inverse of the product of these rates. The higher the ETX count, the more the expected the number of re-transmission, so the routing should choose the path with the lowest cumulative ETX. Performance is actually improved, especially as path are longer.

What is nice about the paper: it is very nicely explained. It is thinner in technical content than I remembered (basically it is the idea of the ETX metrics which matters) but each choice is very nicely argued and motivated, and each decision made very clear. So it is a very nice read.

The main thing I am now taking from the paper is that the performance of the metric is the invert of the packet delivery in both directions. However, one direction is the ACK direction, and this can be improved by sending mutliple ACKs, or by adding enough redundancy in the ACK to decode it successfully every time. Then your ETX drop. For instance, if you have 1/2 pdr in each direction, your ETX is 4. If you add enough coding redundancy so as to decode the Ack succesfully every time, then your ETX drops to 2. That's a pretty major gain. It is obvious, but the paper does not suggest doing it.