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
 |
Abstract |
|---|
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.