Nalanda

Citation: De Couto, D. S., Aguayo, D., Bicket, J., and Morris, R. 2003. A high-throughput path metric for multi-hop wireless routing. In Proceedings of the 9th Annual international Conference on Mobile Computing and Networking (San Diego, CA, USA, September 14 - 19, 2003). MobiCom ‘03. ACM, New York, NY, 134-146. DOI= http://doi.acm.org/10.1145/938985.939000

This paper, by some of the same authors as the Roofnet paper, presents the idea of the Expected Transmission Count (ETX) metric that was developed further and used in Roofnet’s routing protocol. ETX is evaluated on a 29-node wireless testbed, as an extension to the DSDV and DSR protocols.

In presenting ETX, the authors contrast it to the commonly used metric used in ad hoc networks, minimum hop count. While useful as a metric in wired networks, minimum hop count suffers from a number of flaws when used in wireless networks. The most important of these, perhaps, is the assumption that links either work, or do not; wireless links typically have intermediate loss ratios. Lower hop counts may also maximize the distance traveled per hop, leading to increased signal attenuation and higher probabilities of loss. Finally, a random choice amongst routes with the same hop count is not likely to pick the best route, as the characteristics of the individual links in this route are not taken into account. This last problem worsens as a network grows, and the number of possible paths increases.

To remedy these problems, ETX attempts to find routes which would have the fewest transmissions, and retransmissions, of packets, by measuring packet loss ratios in both directions on each link. Measurement in both directions is important, to account for 802.11b ACKs being sent back along a link, as it is not unlikely that links may be asymmetric to some degree in an ad hoc network. Packet loss is measured as the delivery ratio for a link: the number of packets received, divided by the number of packets transmitted by the sender. Since ETX is designed to minimize the number of packets transmitted, this also results is lower spectrum use, thereby increasing overall network capacity, and a decrease in energy per packet, which is a particularly an important consideration for devices with limited battery life.

From measurements, it appears that packet size is an important consideration which ETX does not account for. ETX sends small probe packets of fixed size to determine link quality, but these are somewhat larger than 802.11b ACK packets, and inevitably much smaller than data packets. As a result, ETX underestimates the delivery ratio for ACK packets, and, more importantly, may overestimate the delivery ratio for large packets.

In order to be useful, ETX makes a few assumptions: that there are link layer retransmissions, and that radios operate on fixed, rather than variable, power levels. Additionally, the authors suggest that ETX may not be responsive to mobility, as link quality may change too quickly for propagation of accurate route metrics. I’m not so sure about this last point; it seems to me that ETX might be a useful addition to a protocol like DSR in a network with high mobility.