The iSLIP scheduling algorithm for input-queued switches
The iSLIP scheduling algorithm for input-queued switches
复制标题
DOI：
10.1109/90.769767
复制
发表时间：
1999-04
期刊：
影响因子：
--
通讯作者：
N. McKeown
中科院分区：
文献类型：
--
作者：
N. McKeown
越来越多的高性能网络互连协议路由器、LAN和异步传输模式（ATM）交换机使用基于纵横制交换机的交换背板。大多数情况下，这些系统使用输入队列来保存等待穿过交换结构的分组。众所周知，如果使用简单的先进先出（FIFO）输入队列来保存分组，则即使在良性条件下，行首（HOL）阻塞也将可实现的带宽限制为最大值的大约58.6%。本文介绍了利用虚输出缓冲技术克服HOL阻塞的方法。调度算法用于配置交叉开关，决定数据包的服务顺序。先前的结果表明，使用合适的调度算法，可以实现100%的吞吐量。在本文中，我们提出了一个调度算法称为iSLIP。iSLIP是一种迭代的循环算法，可以在均匀流量下实现100%的吞吐量，但在硬件中实现起来很简单。迭代和noniterative版本的算法，沿着与修改后的版本优先流量。仿真结果表明，在良性和突发业务条件下的iSLIP的性能。iSLIP的原型和商业实现存在于聚合带宽范围从50到500 Gb/s的系统中。当流量不均匀时，iSLIP快速适应公平的调度策略，保证永远不会饿死输入队列。最后，我们描述了iSLIP的实现复杂度。基于优先级编码器的二维（2-D）阵列，已经构建了支持多达32个端口的单芯片调度器，并且每秒做出大约1亿个调度决策。
An increasing number of high performance internetworking protocol routers, LAN and asynchronous transfer mode (ATM) switches use a switched backplane based on a crossbar switch. Most often, these systems use input queues to hold packets waiting to traverse the switching fabric. It is well known that if simple first in first out (FIFO) input queues are used to hold packets then, even under benign conditions, head-of-line (HOL) blocking limits the achievable bandwidth to approximately 58.6% of the maximum. HOL blocking can be overcome by the use of virtual output queueing, which is described in this paper. A scheduling algorithm is used to configure the crossbar switch, deciding the order in which packets will be served. Previous results have shown that with a suitable scheduling algorithm, 100% throughput can be achieved. In this paper, we present a scheduling algorithm called iSLIP. An iterative, round-robin algorithm, iSLIP can achieve 100% throughput for uniform traffic, yet is simple to implement in hardware. Iterative and noniterative versions of the algorithms are presented, along with modified versions for prioritized traffic. Simulation results are presented to indicate the performance of iSLIP under benign and bursty traffic conditions. Prototype and commercial implementations of iSLIP exist in systems with aggregate bandwidths ranging from 50 to 500 Gb/s. When the traffic is nonuniform, iSLIP quickly adapts to a fair scheduling policy that is guaranteed never to starve an input queue. Finally, we describe the implementation complexity of iSLIP. Based on a two-dimensional (2-D) array of priority encoders, single-chip schedulers have been built supporting up to 32 ports, and making approximately 100 million scheduling decisions per second.