Evaluation of packet scheduling algorithms in mobile ad hoc networks

ABSTRACT

We examine the queuing dynamics at nodes in an ad hoc mobile network and evaluate network performance under different packet scheduling algorithms using Dynamic Source Routing (DSR) and Greedy Perimeter Stateless Routing (GPSR) as the underlying routing protocols. Typically, packet schedulers in ad hoc networks give priority to control packets over data packets and serve data packets in FIFO order. We find that setting priorities among data packets can decrease end-to-end packet delay significantly. In particular, we find that among the algorithms we studied, those that give priority to data packets with short distance metrics show the smallest delay and the highest throughput, without increasing routing overhead. In addition, we show that with both DSR and GPSR, giving priority to control packets over data packets affects the performance significantly when mobility is high. With DSR, giving priority to control packets reduces the average delay. In contrast, with GPSR, this scheduler increases the average delay.

REFERENCES

• 1: David B. Johnson, David A. Maltz, Yih-Chun Hu, and Jorjeta G. Jetcheva. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. IETF Internet draft, Mobile Ad-hoc Network Working Group, IETF, February 2002 (work in progress).
• 2: Charles E. Perkins, Elizabeth M. Royer, and Samir Das. Ad Hoc On Demand Distance Vector (AODV) Routing. IETF Internet draft, Mobile Ad-hoc Network Working Group, IETF, January 2002 (work in progress).
• 3: 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]
• 4: Samir R. Das, Charles E. Perkins, and Elizabeth M. Royer. Performance comparison of two on-demand routing protocols for ad hoc networks. In Proceedings of the IEEE INFOCOM, Tel-Aviv, Israel, March 2000.
• 5: Per Johansson , Tony Larsson , Nicklas Hedman , Bartosz Mielczarek , Mikael Degermark, Scenario-based performance analysis of routing protocols for mobile ad-hoc networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.195-206, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313535]
• 6: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 7: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 8: Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345925]
• 9: Haiyun Luo , Songwu Lu , Vaduvur Bharghavan, A new model for packet scheduling in multihop wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.76-86, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345923]
• 10: V. Kanodia , C. Li , A. Sabharwal , B. Sadeghi , E. Knightly, Distributed multi-hop scheduling and medium access with delay and throughput constraints, Proceedings of the 7th annual international conference on Mobile computing and networking, p.200-209, July 2001, Rome, Italy [doi>10.1145/381677.381697]
• 11: V. Kanodia , A. Sabharwal , B. Sadeghi , E. Knightly, Ordered packet scheduling in wireless ad hoc networks: mechanisms and performance analysis, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513808]
• 12: K. Fall and K. Varadhan, editors. ns notes and documentation. The VINT Project, UC Berkeley, LBL, USC/ISI, and Xerox PARC, July 1999.
• 13: David A. Maltz, Josh Broch, Jorjeta Jetcheva, and David B. Johnson. The Effects of On-Demand Behavior in Routing Protocols for Multi-Hop Wireless Ad Hoc Networks. IEEE Journal on Selected Areas in Communications special issue on mobile and wireless networks. August 1999.
• 14: D. Karger, C. Stein, and J. Wein. Scheduling algorithms. In CRC Handbook of Computer Science. 1997.
• 15: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 16: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round robin, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.231-242, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 17: Byung-Gon Chun. Evaluation of Scheduling Algorithms in Mobile Ad Hoc Networks. MS Thesis, Stanford University, May 2002.
• 18: Songwu Lu , Vaduvur Bharghavan , Rayadurgam Srikant, Fair scheduling in wireless packet networks, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.63-74, September 14-18, 1997, Cannes, France
• 19: Songwu Lu , Thyagarajan Nandagopal , Vaduvur Bharghavan, A wireless fair service algorithm for packet cellular networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.10-20, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288242]
• 20: Mark Crovella, Bob Frangioso, and Mor Harchol-Balter. Connection Scheduling in Web Servers. In USENIX Symposium on Internet Technologies and Systems (USITS), Boulder, Colorado, October 1999.
• 21: Nikhil Bansal , Mor Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.279-290, June 2001, Cambridge, Massachusetts, United States

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Experimentation, Measurement, Performance