一种基于输入队列的交换机快速会聚调度算法

A High Speed Converging Scheduling Algorithms Based on Input Queued Switches

随着网络带宽需求的增加,高性能交换机的地位日趋重要。交换机包括3个部分:(1)在输入端口保存到达此端口的信元的输入缓冲。(2)在输出端口保存将要发送的信元的输出缓冲。(3)调度输入信元到所需输出端口的调度模块。当由多个输入端口要求输出到同一输出端口的时候由此调度算法来裁决一个输入输出对。一般而言,交换机的性能很大一部分取决于这一调度算法的性能,但并不希望这一调度算法成为交换机性能的瓶颈。该文讨论了许多近年来常用的算法,在此基础上同时提出一种新的的调度算法。通过计算机模拟结果可以看出这种算法具有更高的效率,更快的会聚速度。

The demand for more network bandwidth is causing a growing interest in high performance switches.A switch consists of three part:(i)input queues to buffer the cells arriving on input ports,(ii)output queues to buffer the cells going out on output ports,and(iii)a switch fabric to transfer cells from inputs to the desired outputs.The switch fabric operates under a scheduling algorithm,which arbitrates among cells from different inputs destined to the same output.In general,this algorithm is very important to design high performance switch,and we expect the scheduling algorithm not to be the bottleneck of the performance of switch.This paper presents a number of scheduling approaches,including several proposed in the literature and one novel algorithm we have devised,and then consider the performance of these scheduling policies by computer simulation.