基于基数排序的集成服务优先队列算法

Radix Sort Based Int-serv Priority Queue Algorithm

传统的服务质量(QoS)算法分为差别服务和集成服务两种,前者提供相对的服务质量保证,而后者则可以提供绝对的服务质量保证,二者最终都可以归结为优先队列算法。在核心路由器中QoS对优先队列的要求比较高,差别服务需要提供OC-768(40Gbps)线速、很大的有效排队长度和较小的最小时延。集成服务除了上述要求还需要很大的优先级数目。受到基数排序算法的启发,论文设计了一种基于基数排序的适用于集成服务的优先队列算法,具有以下特点:(1)带宽可以达到OC-768线速,优先级数目和有效排队长度不受限制,最小时延可以接受。(2)结构比较简单,不需要非常复杂的电路设计。

Traditional quality of service(QoS)can be parted into int-serv and diff-serv.The former provides a relative QoS guarantee while the later provides absolute QoS guarantee.Both can boil down into a priority queue algorithm.In core routers QoS has a higher requirement to priority queue performance.Diff -serv is expected to have OC-768(40Gbps)line rate,large available queue length and less least delay.Besides these requirements int-serv needs large priority levels as a plus.Enlightened by radix sort algorithm,it proposes a int-serv suitable priority queue algorithm based on radix sort method in this paper with properties below:(1)OC-768line rate,no limits of priority levels,available queue length and acceptable least delay.(2)Ordinary structure without complicated circuits design.