高性能路由器分组调度算法研究

Study on a Packet Scheduling Algorithm in High Performance Routers

Internet同时面临着两个问题:更快的交换路由结构和引入服务质量（QoS）保证,每个问题都可以独立解决.高性能路由器可以用输入缓冲的交叉开关（crossbar）代替共享内存来获得更快的速度;QoS能够通过分组公平排队算法PFQ（packet fair queuing）来得到.然而到目前为止,这两个问题的解决还是互斥的——所有的分组公平排队算法研究都需要路由器采用输出排队或者集中式共享内存.基于输入输出结合排队CIOQ（combinedinput output queuing）结构,设计和实现了一种分组调度算法DF2Q（distributed feedback fair queuing）.该调度算法最重要的特征是引入了反馈机制.分析并讨论了DF2Q的性能.实验结果表明,它能够很好地避免内部拥塞和提高资源利用效率.

Internet is facing two problems simultaneously: a faster switching/routing infrastructure and guaranteed quality-of-service (QoS). Each problem can be solved independently. High performance routers can be made faster by using input-queued crossbars instead of shared memory systems. QoS can be provided by usingpacket fair queuing (PFQ) algorithm. Until now, however, the two solutions have been mutually exclusive-all ofthe work on PFQ algorithm has required that routers use output-queuing or centralize shared memory. In this paper, on the basis of CIOQ (combined input output queuing) architecture, a packet scheduling algorithm DF2Q (distributed feedback fair queuing) is designed and implemented. The most important feature of this algorithm is the introducing of feedback mechanism, the performance of DF2Q is analyzed and discussed. Experimental results show that it can avoid internal congestion effectively and improve the efficiency of resource utilizing.