基于轮转算法的缓冲交叉开关调度算法的设计与实现

计算机科学 ›› 2013, Vol. 40 ›› Issue (Z6): 108-111.

基于轮转算法的缓冲交叉开关调度算法的设计与实现

刘飞,李冰,张磊磊

南京泛盈信息科技有限公司南京211100;IC学院无锡214000;IC学院无锡214000

出版日期:2018-11-16 发布日期:2018-11-16

Design and Implementation of Buffered Crossbar Scheduling Algorithm with Round Robin Scheduling

LIU Fei,LI Bing and ZHANG Lei-lei

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 研究了一种低复杂度、高性能的交换机调度算法——轮转(Round Robin)调度算法及其硬件实现,它是基于缓冲交叉开关交换结构的。缓冲交叉开关交换结构相比于无缓冲的交叉开关交换结构,仅需要简单的调度算法对输入VOQ队列和交叉点缓存输出分别进行调度,这大大简化了调度算法硬件实现的复杂程度,减小了系统延迟。因此,结合轮转算法和缓冲交叉开关交换结构各自的优点,可以设计出高性能的交换机。

关键词: 轮转算法,缓冲交叉开关,调度算法

Abstract: In this paper a low complexity,high-performance scheduling algorithm-Round Robin scheduling algorithm and its hardware implementation is given．It is based on buffered crossbar switch fabric．Compared to the bufferless crossbar switch fabric,buffered crossbar switch fabric only requires simple schedulers that operate independently for each output crosspoint queue column and independently for each VOQ queue．This greatly simplifies the scheduling complexity of hardware and reduces system latency．So by combinating the advantage of Round Robin scheduling algorithm and buffered crossbar,a high performance switch can be implemented.

Key words: Round robin algorithm,Buffered crossbar,Scheduling algorithm

刘飞,李冰,张磊磊. 基于轮转算法的缓冲交叉开关调度算法的设计与实现[J]. 计算机科学, 2013, 40(Z6): 108-111. https://doi.org/

LIU Fei,LI Bing and ZHANG Lei-lei. Design and Implementation of Buffered Crossbar Scheduling Algorithm with Round Robin Scheduling[J]. Computer Science, 2013, 40(Z6): 108-111. https://doi.org/

参考文献

[1] Magill R B,Rohrs C E,Stevenson R L．Output-queued switch emulation by fabrics with limited memory[J]．IEEE Journal on Selected Areas Communications,2003,21(4):606-615
[2] Karol M,Hluchyj M,Morgan S．Input versus output queueing on a space division switch[J]．IEEE Transactions on Communications,1987,35(12):1347-1356
[3] McKeown N．Scheduling Algorithms for Input-Queued Switches[D]．Ph D dissertation,University of California at Berkley,1995
[4] McKeown N,Mekkittikul A,Anantharam V,et al．Achieving100% throughput in an input-queued switch(extended version)[J]．IEEE Transactions on Communications,1999,47(8):1260-1267
[5] Nabeshima M．Performance evaluation of a combined input- and crosspoint-queued switch[J]．IEICE Transactions on Communications,2000,E83-B(3):737-741
[6] Rojas-Cessa R,Oki E,Jing Z,et al．CIXB-1:Combined input-once-cell-crosspoint buffered switch[C]∥IEEE Workshop on High Performance Switching and Routing．Dallas,USA:IEEE Press,2001:324-329
[7] Chuang S T,Iyer S,McKeown N．Practical algorithms for performance guarantees in buffered crossbars[C]∥IEEE INFOCOM’05．Miami,FL:IEEE Infocom,2005:981-991
[8] Berger M S．Delivering 100% throughput in a Buffered Crossbar with Round Robin scheduling[C]∥High Performance Switching and Routing．IEEE HPSR,Poznan,Poland:2006:5-10
[9] Lin M,McKeown N．The throughput of a buffered crossbarswitch[J]．IEEE Communications Letters,2005,5:465-467
[10] Yoshigoe K,Christensen K J．An evolution to crossbar switches with virtual output queuing and buffered crosspoints[J]．IEEE Network,2003,17(5):48-56
[11] 李勇,罗军舟,吴俊．一种交叉点小缓存CICQ交换机高性能调度算法[J]．计算机研究与发展,2006,43(12):2033-2040

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed