Packet scheduling in wireless systems by token bank fair queueing algorithm

The amalgamation of wireless systems is a vision for the next generation wireless systems where multimedia applications will dominate. One of the challenges for the operators of next generation networks is the delivery of quality-of-service (QoS) to the end users. Wireless scheduling algorithms play a critical and significant role in the user perception of QoS. However, the scarcity of wireless resources and its unstable channel condition present a challenge to providing QoS. To that end, this thesis proposes a novel scheduling algorithm Token Bank Fair Queuing (TBFQ) that is simple to implement and has the soft tolerance characteristic which is suitable under wireless constraints. TBFQ combines both token-based policing mechanism and fair throughput prioritization rule in scheduling packets over packet-switched wireless systems. This results in a simple design and yet achieves better performance and fairness than existing wireless scheduling strategies.; The characterization of the algorithm, which leads to its tight bound performance, is conducted through numerical analysis that recursively determines the steady-state probability distribution of the bandwidth allocation process and ultimately the probability distribution of input queue. We found that the convergence of the recursion is remarkably fast and provides an accurate model and gives a tight bound. The performance of the algorithm is further analyzed through simulation in both TDMA and CDMA systems. In CDMA systems, the algorithm is modified and enhanced to take advantage of the advanced features offered by such system. Furthermore, a novel scheduling framework is proposed as part of the strategy for the deployment of the algorithm within a wireless network. An appropriate call admission control algorithm is also proposed for TBFQ.