Soft QoS provisioning using the token bank fair queuing scheduling algorithm

TitleSoft QoS provisioning using the token bank fair queuing scheduling algorithm
Publication TypeJournal Article
Year of Publication2003
AuthorsWong, W. K., H. Zhu, and V. C. M. Leung
JournalWireless Communications, IEEE
Pagination8 - 16
Date Publishedjun.
Keywordsaccess protocols, algorithm complexity, bandwidth utilization, delay bounds, delays, heterogeneous traffic, integrated services, land mobile radio, mean packet delay, multimedia applications, multiuser channels, packet radio networks, policing functions, quality of service, queueing theory, radio links, reservation-based TDMA/TDD wireless channel, service integrated real-time traffic, servicing functions, soft QoS provisioning, statistical multiplexing performance, TBFQ scheduling mechanism, telecommunication traffic, time division multiple access, token bank fair queuing, token bank fair queuing scheduling algorithm, violation probability, wireless downlink traffic, wireless packet-switched networks, wireless uplink traffic, work-conserving algorithm

Future-generation wireless packet networks will support multimedia applications with diverse QoS requirements. Much of the research on scheduling algorithms has been focused on hard QoS provisioning of integrated services. Although these algorithms give hard delay bounds, their stringent requirements sacrifice the potential statistical multiplexing performance and flexibility of the packet-switched network. Furthermore, the complexities of the algorithms often make them impractical for wireless networks. There is a need to develop a packet scheduling scheme for wireless packet-switched networks that provides soft QoS guarantees for heterogeneous traffic, and is also simple to implement and manage. This article proposes token bank fair queuing (TBFQ), a soft scheduling algorithm that possesses these qualities. This algorithm is work-conserving and has a complexity of O(1). We focus on packet scheduling on a reservation-based TDMA/TDD wireless channel to service integrated real-time traffic. The TBFQ scheduling mechanism integrates the policing and servicing functions, and keeps track of the usage of each connection. We address the impact of TBFQ on mean packet delay, violation probability, and bandwidth utilization. We also demonstrate that due to its soft provisioning capabilities, the TBFQ performs rather well even when traffic conditions deviate from the established contracts.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia