Token bank fair queuing: a new scheduling algorithm for wireless multimedia services

Abstract The token bank fair queuing algorithm (TBFQ) is a novel scheduling algorithm that is suitable for wireless multimedia services. The bandwidth allocation mechanism integrates the leaky bucket structure with priority handling to address the problem of providing quality‐of‐service (QoS) guarantees to heterogeneous applications in the next generation packet‐switched wireless networks. Scheduling algorithms are often tightly integrated with the wireless medium access control (MAC) protocol. However, when heterogeneous wireless systems need to be integrated and interoperate with each other, it is desirable from the QoS provisioning standpoint to decouple scheduling algorithm from the MAC protocol. In this paper we propose a framework of seamless QoS provisioning and the application of TBFQ for uplink and downlink scheduling in wireless networks. We study its performance under a generic medium access framework that enables the algorithm to be generalized to provide QoS guarantees under various medium access schemes. We give a brief analysis of the algorithm and compare its performance with common scheduling algorithms through simulation. Our results demonstrate that TBFQ significantly increases wireless channel utilization while maintaining the same QoS, unlike many fair queuing algorithms, TBFQ does not require time‐stamping information of each packet arrival—an impractical feature in an already resource scarce environment. This makes TBFQ suitable for wireless multimedia communication. Copyright © 2004 John Wiley & Sons, Ltd.