Network State Information Aided Scheduling Algorithms With Statistical Guarantees

Scheduling is an important mechanism to support QoS in packet networks. Most traditional scheduling algorithms, which are based on deterministic settings, are intrinsically conservative. Mechanisms based on statistical settings provide probabilistical guarantees, and thus allow the link to operate at a much high utilization. Control network has been proved to be able to improve the network stability and the accuracy of network state information dramatically, and provides a new way to improve the performance of scheduling by taking use of the network state information. In this thesis, the author provides systematical investigation on the subject of network state information aided scheduling algorithms with statistical guarantees.The thesis deeply analyzes the single node performance of EDF scheduler under statistical settings, mainly focusing on the relationship between the probabilities of delay bound violations and the required delay bounds. By extending the current EDF analytical framework, and introducing EBB into the analysis as the traffic characterization, a more practical result is achieved. And through a comparison study with the FIFO mechanism, the characteristics of single node EDF statistical performance are thoroughly investigated. All the conclusions are validated against simulations. Beside the aggregate analysis, an investigation for per-flow performance is also made, and is also validated by simulations. After that, a discussion on the access ability of single node EDF scheduler under statistical settings is presented.Based on the analytical results derived on single node EDF scheduler, and combining with the relative conclusions of control network, the thesis proposes the concept of network state information aided scheduling, and proposes two network state information aided scheduling algorithms, called DP-EDF and DDP-EDF. Taking use of the results derived for single node EDF scheduler, analyses of the end-to-end performance for the proposed algorithms are provided. The thesis proves that the DP-EDF yields optimal performance in terms of probability of end-to-end in time transmission when the delay violation probability of every single node is reasonable low, and the DDP-EDF can always achieve performance gain. Simulation results are presented for validation. And finally, some implementation issues are also discussed.