A high-throughput path metric for multi-hop wireless routing

ABSTRACT

This paper presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29-node 802.11b test-bed demonstrate the poor performance of minimum hop-count, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer.

REFERENCES

• 1: The Network Simulator --- ns-2, 2003. http://www.isi.edu/nsnam/ns.
• 2: Baruch Awerbuch, David Holmer, and Herbert Rubens. High throughput route selection in multi-rate ad hoc wireless networks. Technical report, Johns Hopkins University, Computer Science Department, March 2003. Version 2.
• 3: Hari Balakrishnan , Venkata N. Padmanabhan , Srinivasan Seshan , Randy H. Katz, A comparison of mechanisms for improving TCP performance over wireless links, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.756-769, Dec. 1997 [doi>10.1109/90.650137]
• 4: Brahim Bensaou , Yu Wang , Chi Chung Ko, Fair medium access in 802.11 based wireless ad-hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 5: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 6: Shigang Chen and Klara Nahrstedt. Distributed quality-of-service routing in ad hoc networks. IEEE Journal on Selected Areas in Communcations, 17(8), August 1999.
• 7: T.-W. Chen, J.T. Tsai, and M. Gerla. QoS routing performance in multihop, multimedia, wireless networks. In Proceedings of IEEE ICUPC '97, 1997.
• 8: Kwan-Wu Chin , John Judge , Aidan Williams , Roger Kermode, Implementation experience with MANET routing protocols, ACM SIGCOMM Computer Communication Review, v.32 n.5, November 2002 [doi>10.1145/774749.774758]
• 9: Brian H. Davies and T. R. Davies. The application of packet switching techniques to combat net radio. Proceedings of the IEEE, 75(1), January 1987.
• 10: Rohit Dube, Cynthia D. Rais, Kuang-Yeh Wang, and Satish K. Tripathi. Signal stability-based adaptive routing (SSA) for ad hoc mobile networks. IEEE Personal Communications, February 1997.
• 11: Tom Goff , Nael B. Abu-Ghazaleh , Dhananjay S. Phatak , Ridvan Kahvecioglu, Preemptive routing in Ad Hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.43-52, July 2001, Rome, Italy [doi>10.1145/381677.381682]
• 12: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 13: Yu-Ching Hsu, Tzu-Chieh Tsai, Ying-Dar Lin, and Mario Gerla. Bandwidth routing in multi-hop packet radio environment. In Proceedings of the 3rd International Mobile Computing Workshop, 1997.
• 14: Yih-Chun Hu and David B. Johnson. Design and demonstration of live audio and video over multihop wireless ad hoc networks. In Proceedings of the MILCOM 2002.
• 15: David B. Johnson. Routing in ad hoc networks of mobile hosts. In Proc. of the IEEE Workshop on Mobile Computing Systems and Applications, pages 158--163, December 1994.
• 16: David B. Johnson, David A. Maltz, and Yih-Chun Hu. The Dynamic Source Routing protocol for mobile ad hoc networks (DSR). Internet draft (work in progress), IETF, April 2003. http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-09.txt.
• 17: John Jubin and Janet D. Tornow. The DARPA packet radio network protocols. Proceedings of the IEEE, 75(1), January 1987.
• 18: Eun-Sun Jung , Nitin H. Vaidya, A power control MAC protocol for ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570651]
• 19: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 20: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 21: Chunhung Richard Lin. On-demand QoS routing in multihop mobile networks. In Proc. IEEE Infocom, April 2001.
• 22: Henrik Lundgren , Erik Nordströ , Christian Tschudin, Coping with communication gray zones in IEEE 802.11b based ad hoc networks, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570790.570799]
• 23: Anastassios Michail and Anthony Ephremides. Algorithms for routing session traffic in wireless ad-hoc networks with energy and bandwidth limitations. In Proceedings of 12th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, 2001.
• 24: Christina Parsa and J. J. Garcia-Luna-Aceves. TULIP: A link-level protocol for improving TCP over wireless links. In Proc. IEEE Wireless Communications and Networking Conference 1999 (WCNC 99), September 1999.
• 25: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 26: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 27: Rice Monarch Project. Wireless and mobility extensions to ns-2. http://www.monarch.cs.rice.edu/cmu-ns.html.
• 28: Ratish J. Punnoose, Pavel V. Nitkin, Josh Broch, and Daniel D. Stancil. Optimizing wireless network protocols using real-time predictive propagation modeling. In Radio and Wireless Conference (RAWCON), August 1999.
• 29: Ram Ramanathan and Regina Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. In Proc. IEEE Infocom, March 2000.
• 30: Samarth H. Shah and Klara Nahrstedt. Predictive location-based QoS routing in mobile ad hoc networks. In Proceedings of IEEE International Conference on Communications, 2002.
• 31: Prasum Sinha, Raghupathy Sivakumar, and Vaduvur Bharghavan. CEDAR: A core-extraction distributed ad hoc routing algorithm. In Proc. IEEE Infocom, March 1999.
• 32: Audun Tornquist. Modular and adaptive ad hoc routing in Click. Master's thesis, University of Colorado, 2001.
• 33: Mark Yarvis, W. Steven Conner, Lakshman Krishnamurthy, Jasmeet Chhabra, Brent Elliott, and Alan Mainwaring. Real-world experiences with an interactive ad hoc sensor network. In Proceedings of the International Workshop on Ad Hoc Networking, August 2002.
• 34: Chenxi Zhu and M. Scott Corson. QoS routing for mobile ad hoc networks. In Proc. IEEE Infocom, June 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
802.11b, DSDV, DSR, ETX, ad hoc networks, multi-hop wireless networks, rooftop networks, route metrics, wireless routing