【作者】 王雷；

【导师】 曹志刚；

【作者基本信息】 清华大学 ， 信息与通信工程， 2004， 硕士

【摘要】 调度机制是网络提供服务质量(QoS)保证的重要组件。传统的基于确定性保证的调度算法对资源的利用过于保守,统计性保证的调度算法为业务提供基于概率的性能保证,可以有效的提高链路带宽的利用率。同时,近年来得到较多讨论的控制网络被证明可以显著地提高网络状态信息的稳定性与置信度,这为调度算法的研究提供了新的思路,合理利用网络状态信息对调度机制进行指导可以有效地提高调度算法的性能。基于以上考虑,论文对基于统计保证的网络状态信息辅助的调度算法进行了深入研究。论文首先对统计性保证下EDF调度机制的单节点性能进行了分析,重点研究了EDF调度机制单节点超时概率与业务延时要求之间的关系问题。论文扩展了现有EDF调度机制统计性性能分析的基本框架,在原有框架基础上做进一步近似,并引入EBB作为业务特性模型,获得了更具实际意义的结果,为后面网络状态信息辅助调度算法的提出提供了重要理论依据。通过与FIFO机制分析结果的对比,论文对EDF机制单节点统计性保证的性能特点进行了深入剖析,并提供仿真实验进行验证。论文还对EDF调度机制的单个流性能进行分析,并同样提供仿真进行验证。此后,论文又对基于统计性保证EDF调度机制的单节点接纳能力进行了讨论。论文在上述关于EDF调度机制单节点统计性能分析的基础上,结合控制网络的相关思想和结论,提出了网络状态信息辅助的调度算法的概念,并提出了两种基于统计保证的网络状态信息辅助的调度算法,DP-EDF和DDP-EDF。此后,论文利用前面EDF调度机制单节点统计性能分析的结论,对所提算法的性能进行了分析。论证了DP-EDF所采用的平均延时比例平均的延时上界分配方法在控制端到端超时概率方面具有最优性,以及DDP-EDF在端到端超时概率的性能上也有恒大于0的增益。并同时提供仿真结果进行验证。最后,论文还对算法在实现过程中可能遇到的一些问题进行了讨论。更多还原

【Abstract】 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 <WP=5>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.更多还原