iSLIP调度算法研究及其实现  

Research of an iSLIP Scheduling Algorithm and its Implementation

作　　者：刘化君[1] 刘斌[2] 

机构地区：[1]南京工程学院计算机工程系,江苏南京210013 [2]清华大学计算机科学与技术系,北京100084

出　　处：《小型微型计算机系统》2003年第9期1593-1596,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金课题 (60 173 0 0 9); 985项目资助

摘　　要：目前 ,为提高交换系统吞吐率 ,设计开发高性能网络交换机或路由器内部交换结构的技术已趋成熟 .但易于在硬件中实现的、高效的队列调度算法仍然是一项值得研究的重要技术 .文章首先讨论了对于输入缓冲采用 FIFO队列交换系统 ,其吞吐率主要受 HOL队首阻塞的影响 .然后研究了 i SL IP调度算法的基本原理、迭代仲裁步骤及它在硬件中的实现 .针对硬件交换转发判决这一关键问题 ,给出了在输入队列交换机中采用虚拟输出队列的交换结构和多优先级调度算法的硬件实现方案 .最后 ,对 i SL IP算法的性能进行了分析比较 ,证明 i SL IP算法的实现方案不仅实现简单 。Current technology development makes it feasible to build extremely high throughput switch and router, which explicit employs switching high-performance fabric. However, the research of scheduling algorithm with high efficiency and easiness is still a challenge. In this paper, we firstly discuss that the factor of throughput is affected mostly by HOL (head of line blocking), for input buffered with FIFO queues per input port. Then, we introduce the principle of iSLIP scheduling algorithm, step arbitration of iSLIP for one iteration and its implementation in hardware. We describe the implementation of a scheduling algorithm for configuring crossbar in input-queued switches that support virtual output queues and multiple priorities. In the end of paper, analysis and comparison of iSLIP algorithm performance are made, the results shows its easiness to be implemented and good performance.

关 键 词：队列调度 交换结构 HOL阻塞 迭代匹配调度算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]