Fair scheduling in wireless packet networks

ABSTRACT

Fair scheduling of delay and rate-sensitive packet flows over a wireless channel is not addressed effectively by most contemporary wireline fair scheduling algorithms because of two unique characteristics of wireless media: (a) bursty channel errors, and (b) location-dependent channel capacity and errors. Besides, in packet cellular networks, the base station typically performs the task of packet scheduling for both downlink and uplink flows in a cell; however a base station has only a limited knowledge of the arrival processes of uplink flows.In this paper, we propose a new model for wireless fair scheduling based on an adaptation of fluid fair queueing to handle location-dependent error bursts. We describe an ideal wireless fair scheduling algorithm which provides a packetized implementation of the fluid model while assuming full knowledge of the current channel conditions. For this algorithm, we derive the worst-case throughput and delay bounds. Finally, we describe a practical wireless scheduling algorithm which approximates the ideal algorithm. Through simulations, we show that the algorithm achieves the desirable properties identified in the wireless fluid fair queueing model.

REFERENCES

• 1: J,C.R. Bennett and H. Zhang, "WF2Q: Worst-case fair weighted fair queueing," Prac. IEEE INFOCOM'96, March 1996.
• 2: P. Bhagwat, P. Bhattacharya, A. Krishma and S. Tripathi, "Enhancing throughput over wireless LANs using channel state dependent packet scheduling," to ap. pear on Proc. of IEEE INFOCOM'97.
• 3: 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
• 4: C. Chang, J. Chang, K. Chen and M. You, "Guaranteed quality-of-service wireless access to ATM," preprint, 1996.
• 5: 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
• 6: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 7: S. Golestani, "A self-clocked fair queueing scheme for broadband applications," Proc. IEEE INFOCOM'9.{, June 1994.
• 8: Pawan Goyal , Harrick M. Vin , Haichen Chen, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.157-168, August 28-30, 1996, Palo Alto, California, United States
• 9: Mark J. Karol , Kai Y. Eng , Zhao Liu, An efficient demand-assignment multiple access protocol for wireless packet (ATM) networks, Wireless Networks, v.1 n.3, p.269-279, 1995
• 10: A. Muir and 3. J. Garcia-Luna-Aceves, "Supporting real-time multimedia traffic in a wireless LAN,' Proc. $PIE Multimedia Computing and Networking 1097, February 1997.
• 11: A. Parekh. "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks," PhD The. s/s, MIT LAboratory for Information and Decision Systems, Technical Report LIDS-TR-2089 1992.
• 12: 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]
• 13: Lixia Zhang, VirtualClock: a new traffic control algorithm for packet-switched networks, ACM Transactions on Computer Systems (TOCS), v.9 n.2, p.101-124, May 1991 [doi>10.1145/103720.103721]
• 14: H. Zhang, "Service disciplines for guaranteed performance service in packet-switching networks," Proc. o{ IEEE, 83(10), October 1995.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  G. Mathematics of Computing

General Terms:
Design, Documentation, Management, Theory