一种提供延迟保证的多级FIFS队列包调度算法

包调度算法是提供服务质量保证的一个重要部分.传统的每流区分的包调度方法通常不能支持较好的扩展性,不适应当前网络带宽的迅速增长.而非每流区分的方法又不能提供每流的服务保证.动态包状态(dynamic packet state,简称DPS)方法提供了一种在无须维护每流状态下提供保证服务的方法,该方法在保证服务质量的同时大大提高了扩展性.但是它仍然需要每包的调度,其复杂度和包的数量有关.在DPS的基础上提出了一种用多级FIFS队列提供延迟保证的包调度算法,并给出了该算法实现服务保证的约束条件.理论分析和仿真实验结果都表明:该算法可以实现常数时间的包调度复杂性,同时具有和DPS同样的延迟性能.

A Multi-Level FIFS Queue Packet Scheduling Algorithm to Provide Delay Guarantee

Packet scheduling algorithm is an important element to provide quality of service (QoS) guarantee. Traditional per-flow packet scheduling methods are often not able to support good scalability. While, the non-per-flow-differentiated methods usually can not provide service guarantee for very individual flow. DPS (dynamic packet state) provides a method to support guaranteed service without per-flow control. It can provide both the service performance and scalability. But its per-packet scheduling results in high computational complex are related with the number of packets. A packet scheduling algorithm with multi-level FIFS queues, which is based on DPS, is provided in this paper to get guaranteed service. And the constrained conditions to delay guarantee under this algorithm is also provided. The theoretical analysis and simulations show that the algorithm can schedule packets with constant time complexity and the same delay performance as DPS.