具有o(N^2)复杂性的输入缓冲队列加权调度算法

A WEIGHTED SCHEDULING ALGORITHM WITH o(N^2) COMPLEXITY FOR INPUT-BUFFERED QUEUE

Internet核心路由器多采用输入缓冲交换矩阵 ,研究输入缓冲队列的调度算法十分重要 .加权调度算法具有较高的性能 ,但由于硬件实现困难 ,因此很少得到应用 .提出了一种简单的加权调度算法 L 2 QF,该算法采用串行轮询的思想 ,根据虚拟输出队列的长度依次为每个输入端口选择一个输出端口 .L 2 QF算法具有 L QF算法的性能 ,但复杂性仅为 o( N2 ) .由于 L 2 QF是所有 L QF算法中复杂性最低的算法 ,而且以叠代的方式执行 。

Most Internet core routers use input queued switches. It is important to research on scheduling algorithms for input queued switches. Weighted scheduling algorithms have high performance but few of them have been used because they are too complex to be implemented in hardware. A new weighted algorithm, L2QF, is presented in this paper. This algorithm uses the ways of serial polling, selecting one output port for each input port in turn according to the length of virtual output queues. L2QF has the same performance as LQF, but its complexity is only o(N 2) . Because L2QF has the lowest complexity among all the LQF algorithms and can be executed within many iterations, it is readily to be implemented in hardware.