Dynamic scheduling algorithm based on queue parameter balancing and generalized large-deviation techniques

Provisioning network resources to meet the Quality of Service (QoS) demands with a higher utilization of the network is a key issue for future wired and wireless multiservice broadband networks. Such resource provisioning may be achieved by a dynamic scheduling algorithm and an admission control algorithm. It has been proven that a scheduling and admission scheme based on stochastic bounds can provide a larger multiplexing gain than that based on deterministic bounds in terms of capacity utilization. Due to both the multiple-timescale characteristics of many multimedia applications, as well as potential intractability arising from complex interactions among traffic streams and the shared multiplexer, developing dynamic resource allocation schemes for a statistical service is particularly challenging. In this thesis, we model a single node of a network with K independent traffic streams as a Multi-Server Multi-Queue (MSMQ) system model, and propose a new dynamic scheduling algorithm which is based on the idea of proportionally balancing a prescribed queue parameter, such as packet delay or buffer size, so that the performance of sub-queues conforms to stated QoS requirements. We call such algorithms QPB algorithms. We will demonstrate that under this scheme, as the offered load increases, all connections simultaneously achieve their QoS performance bounds in the statistical sense. Furthermore, we incorporated the QPB algorithm into Large-Deviation Technique (LDT) to replace the conventional FIFO service discipline, and hence a Generalized Large-Deviation Technique (GLDT) was developed. By selecting different balancing parameters, we are able to obtain different performance bounds, i.e. the GLDT can provide performance guarantees for different QoS measures. The combination of the QPB scheduling algorithm and GLDT admission control policy forms a perfect dynamic resource sharing scheme for heterogeneous traffic streams with QoS provisioning, which is based on stochastic bounds instead of deterministic bounds. So such a dynamic resource sharing scheme is simple, flexible, easily implementable, and has a larger statistical multiplexing gain and low computational complexity. In fact, using the QPB scheduling policy, we have extended the LDT analysis to general traffic streams with different QoS requirements. We further specialize these algorithms to wireless multimedia networks, in which all queueing buffers are remotely distributed and no global buffer is available. In particular, reservation protocols to support QPB on them as well as their performance tight bounds are discussed. We have also presented a numerical analysis approach to determine the performance tight bounds. Finally, as another application of QPB algorithm, we map the QPB scheduling algorithm and GLDT admission control algorithm to a dynamic power assignment (DPA) algorithm for multimedia in multirate DS-CDMA/TDMA system. The DPA algorithm is jointly optimal in terms of resource sharing and power control. Under a linear approximately mapping, the DPA sharing algorithm can also be viewed as a bit error rate (BER) weighted dynamic sharing algorithm.