Distributed fair scheduling in a wireless LAN

ABSTRACT

Fairness is an important issue when accessing a shared wireless channel. With fair scheduling, it is possible to allocate bandwidth in proportion to weightsof the packet flows sharing the channel. This paper presents a fully distributed algorithm for fair scheduling in a wireless LAN. The algorithm can be implemented without using a centralized coordinator to arbitrate medium access. The proposed protocol is derived from the Distributed Coordination Function in the IEEE 802.11 standard. Simulation results show that the proposed algorithm is able to schedule transmission such that the bandwidth allocated to different flows is proportional to their weights. An attractive feature of the proposed approach is that it can be implemented with simple modifications to the IEEE 802.11 standard.

REFERENCES

• 1: J. C. R. Bennett and H. Zhang, "Wf2q: Worst-case fair weighted fair queueing," in INFOCOM'96, March 1996.
• 2: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 3: G. L. Choudhury and S. S. Rappaport, "Priority access schemes using CSMA-CD,' IEEE Transactions on Communications, vol. COM-33, pp. 620-626, July 1985.
• 4: A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queueing algorithm," in Proc. SIGCOMM, September 1995.
• 5: D. Eckhardt, P. Steenkiste, "Effort-limited Fair (ELF) Scheduling for Wireless Networks," In Proc. IEEE INFOCOM 2000.
• 6: K. Fall and K. Varadhan, "ns Notes and documentation," tech. rep., VINT Project, UC-Berkeley and LBNL, 1997.
• 7: R. Garces and J. J. Garcia-Luna-Aceves, "Near-optimum channel access protocol based on incremental collision resolution and distributed transmission queues," in IEEE INFOCOM, San Francisco, March-April 1998.
• 8: Mario Gerla , Ken Tang , Rajive Bagrodia, TCP Performance in Wireless Multi-hop Networks, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.41, February 25-26, 1999
• 9: S. J. Golestani, "A self-clocked fair queueing scheme for broadband applications," in IEEE INFOCOM, 1994.
• 10: Pawan Goyal , Harrick M. Vin , Haichen Cheng, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.690-704, Oct. 1997 [doi>10.1109/90.649569]
• 11: S. Gupta, "Study of distributed fair scheduling in a wireless LAN," Master of Science thesis in preparation, Texas A&M University, May 2000.
• 12: IEEE, "IEEE std 802.11 - wireless LAN medium access control (MAC) and physical layer (PHY) specifications," 1997.
• 13: R. Jain, G. Babic, B. Nagendra, and C. Lam, "Fairness, call establishment latency and other performance metrics," Tech. Rep. ATM_Forum/96-1173, ATM Forum Document, August 1996.
• 14: S. Keshav, "On the efficient implementation of fair queueing,' Journal o.f Internetworkin#: Research and Ezperience, vol. 2, pp. 57-73, September 1991.
• 15: Can Emre Koksal , Hisham Kassab , Hari Balakrishnan, An analysis of short-term fairness in wireless media access protocols (poster session), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.118-119, June 18-21, 2000, Santa Clara, California, United States
• 16: 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]
• 17: Thyagarajan Nandagopal , Songwu Lu , Vaduvur Bharghavan, A unified architecture for the design and evaluation of wireless fair queueing algorithms, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.132-142, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313520]
• 18: T. S. Ng, I. Stoica, and H. Zhang, "Packet fair queueing: Algorithms for wireless networks with location-dependent errors," in INFOCOM, March 1998.Fair queuing in wireless networks
• 19: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 20: Parameswaran Ramanathan , Prathima Agrawal, Adapting packet fair queueing algorithms to wireless networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.1-9, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288239]
• 21: Suzanne M. Sharrock , David H.C. Du, Efficient CSMA/CD-Based Protocols for Multiple Priority Classes, IEEE Transactions on Computers, v.38 n.7, p.943-954, July 1989 [doi>10.1109/12.30847]
• 22: 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
• 23: J. L. Sobrinho and A. S. Krishnakumar, "Real-time traffic over the IEEE 802.11 medium access control layer," Bell Labs Technical Journal, pp. 172-187, Autumn 1996.
• 24: N. H. Vaidya and P. Bahl, "Fair scheduling in broadcast environments," Tech. Rep. MSR-TR-99-61, Microsoft Research, August 1999.

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Design, Measurement, Performance, Standardization, Theory