Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Regular Section -- Papers -- Network |
Channel-Aware Distributed Throughput-Based Fair Queueing for Wired and Wireless Packet Communication Networks
1 The author is with the Doctoral Program in Systems and Information Engineering, University of Tsukuba, Tsukuba-shi, 305-8573 Japan., 2 The author is with the Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba-shi, 305-8573 Japan. E-mail: takagi{at}sk.tsukuba.ac.jp
Fair queueing is a service scheduling discipline to pursue the fairness among users in packet communication networks. Many fair queueing algorithms, however, have problems of computational overhead since the central scheduler has to maintain a certain performance counter for each flow of user packets based on the global virtual time. Moreover, they are not suitable for wireless networks with high probability of input channel errors due to the lack or complexity in the compensation mechanism for the recovery from the error state. In this paper, we propose a new, computationally efficient, distributed fair queueing scheme, which we call Channel-Aware Throughput Fair Queueing (CATFQ), that is applicable to both wired and wireless packet networks. In our CATFQ scheme, each flow is equipped with a counter that measures the weighted throughput achievement while it has a backlog of packets. At the end of every service to a packet, the scheduler simply selects a flow with the minimum counter value as the one from which a packet is served next. We show that the difference between any two throughput counters is bounded. Our scheme significantly reduces the scheduler's computational overhead and guarantees fair throughput for all flows. For wireless networks with error-prone channels, the service chance lost in bad channel condition is compensated quickly as the channel recovers. Our scheme suppresses the service for leading flows, brings short-term fairness for flows without channel errors, and achieves long-term fairness for all flows. These merits are verified by simulation.
Key Words: fair queueing, generalized processor sharing, packet scheduling, throughput counter, wireless packet network
Manuscript received February 28, 2007. Manuscript revised August 22, 2007.
Reference
[1] J.C.R. Bennett and H. Zhang, "Hierarchical packet fair queueing algorithms," ACM SIGCOMM'96, pp.143–156, Palo Alto, CA, Aug. 1996. [2] J.C.R. Bennett and H. Zhang, "WF2Q: Worst-case fair weighted fair queueing," IEEE INFOCOM'96, pp.120–128, San Francisco, CA, March 1996. [3] Cisco IOS Quality of Service Solutions Configuration Guide, Cisco Systems, Inc., 2004. http://www.cisco.comunivercdcctddocproductsoftwareios122122cgcrfqos_c/qcfbook.pdf [4] A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queueing algorithm," ACM SIGCOMM'89, pp.3–12, Austin, TX, Sept. 1989. [5] S. Golestani, "A self-clocked fair queueing scheme for broadband applications," IEEE INFOCOM'94, pp.636–646, Toronto, June 1994. [6] A.G. Greenberg and N. Madras, "How fair is fair queueing?," J. Association for Computing Machinery, vol.39, no.3, pp.568–598, July 1992. [7] Y. Liu, S. Gruhl, and E.W. Knightly, "WCFQ: An opportunistic wireless scheduler with statistical fairness bounds," IEEE Trans. Wireless Communications, vol.2, no.5, pp.1017–1028, Sept. 2003. [8] S. Lu, V. Bharghavan, and R. Srikant, "Fair scheduling in wireless packet networks," IEEE/ACM Trans. Netw., vol.7, no.4, pp.473–489, Aug. 1999. [9] T.S.E. Ng, I. Stoica, and H. Zhang, "Packet fair queueing algorithms for wireless networks with location-dependent errors," IEEE INFOCOM'98, pp.1103–1111, San Francisco, CA, March 1998. [10] OPNET Modeler, OPNET Technologies, Inc., 2005. http://www.opnet.comproductsmodelerhome.html [11] A.K. Parekh and R.G. Gallager, "A generalized processor sharing approach to flow control in integrated services networks — The single node case," IEEE/ACM Trans. Netw., vol.1, no.3, pp.344–357, June 1993. [12] Planning a Wireless Network, Hewlett-Packard Development Company, L.P., 2006. http://www.hp.com/rnd/pdfs.8-02.11technicalbrief.pdf [13] C. Semeria, "Supporting differentiated service classes: Queue scheduling disciplines," White paper, Juniper Netw., Inc., 2001. [14] M. Shreedhar and G. Varghese, "Efficient fair queueing using deficit round robin," ACM SIGCOMM'95, pp.231–242, Cambridge, MA, Aug. 1995. [15] D. Stiliadis and A. Varma, "Efficient fair queueing algorithms for packet-switched networks," IEEE/ACM Trans. Netw., vol.6, no.2, pp.175–185, April 1998. [16] Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Higher-Speed Physical Layer Extension in the 2.4 GHz Band, The Institute of Electrical and Electronics Engineers, Inc., 2000. http://standards.ieee.org/getieee802/download/802.11b-19-99.pdf
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by KIM, S.-Y.
Articles by TAKAGI, H.
Social Bookmarking
What's this?