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

Summary

This paper proposes a new metric to use when finding the highest-throughput path on multi-hope wireless routing.  This new metric, called Expected Trasmission Count, uses link loss ratios, asymmetry in loss ratios and interference between successive links in a path to find the path that requires the lowest number of transmissions, including retransmissions, to successfully deliver the packet to its destination.

The typical metric currently used in multi-hop wireless routing is minimum hop-count.  The authors first determined the performance of minimum-hop-count routing using a 29-node wireless testbed.  They used both the DSDV and DSR protocols.  They found that minimum-hop-count works well when the shortest route is also the fastest one.  However, when it has a choice among a number of multi-hop routes, it usually picks a much slower than optimal path.

Next, the authors explain, implement and evaluate ETX.  The ETX metric measures the number of transmissions required to send a packet to its destination. 

ETX = 1 / (df * dr) 

where df = forward delivery ratio and dr = reverse delivery ratio.

When testing ETX with DSDV, ETX was found to perform better than DSDV when the packet is being sent on a high loss ratio link and the best path is multi-hop.  Some part of ETX's improvement is due to avoiding extremely asymmetric links, even better than the handshaking scheme with the same goal.

ETX was tested with DSR with its link-layer feedback turned on and off.  When it was turned off, ETX showed a significant improvement in initial route selection.  However, when feedback was turned on, ETX showed only a slight improvement to some pairs of nodes.

One drawback to ETX is that it uses a fixed packet size to make its calculations.  However, it was shown that packet size has a significant effect on delivery ratio.  Because of this, ETX tends to underestimates the delivery ratio of ACK packets, resulting in a overestimation of the number of required transmissions.

Criticism & Questions

I enjoyed reading this paper.  I think they had very sound methodology, especially in testing minimum-hop-count so they could have a fair comparison.  Since there are at least 2 more ad-hoc multi-hop routing protocols (which we read about in the next paper), I would like to see the effect that ETX would have on those protocols as well.  One complaint about the paper is that the graphs were really hard to read and really hard to differentiate between the various lines.