For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Channel-Aware Distributed Throughput-Based Fair Queueing for Wired and Wireless Packet Communication Networks
Sang-Yong KIM Hideaki TAKAGI
IEICE TRANSACTIONS on Communications
Publication Date: 2008/04/01
Online ISSN: 1745-1345
Print ISSN: 0916-8516
Type of Manuscript: PAPER
fair queueing, generalized processor sharing, packet scheduling, throughput counter, wireless packet network,
Full Text: PDF>>
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.