第3卷第3期 智能系统学报 Vol 3 Na 3 2008年6月 CAA I Transactions on Intelligent Systems Jun 2008 基于输入排队的高速交换调度算法研究 张重洋，申金媛，刘润杰，张文英，穆维新 郑州大学信息工程学院，河南郑州450052) 摘要：高速交换网络一般采用基于定长信元的交换结构，其性能决定于排队策略和信元调度算法.输入排队策略 只有和一个有效的调度算法相结合，才能保证交换结构具有良好的吞吐率和时延等性能.主要阐述了基于VOQ的最 大数量匹配算法，最大权重匹配算法，稳定结合算法，神经网络算法等输入排队调度算法，分别从技术特点，性能指 标和实现复杂度等多个方面进行比较和分析.分析了分布式和集中式两大类调度算法的工作方式，并根据各类算法 的特点提出，神经网络算法可以通过定义其优先级函数实现其余各类算法」 关键词：输入排队；虚拟输出队列；二部图匹配；调度算法 中图分类号：1P18文献标识码：A文章编号：16734785(2008)03-0265-05 A study on scheduling a lgorithm s for high-speed switching networks ba sed on nput-queung ZHANG Chong-yang,SHEN Jin-yuan,L U Run-jie,ZHANG Wen-ying,MU Wei-xin (Institute of Inmation Engineering.Zhengzhou University,Zhengzhou 450052,China) Abstract:Most high-speed switching networks adopt a switching fabric with fixed-length cells,and their perfom- ance depends heavily upon queuing strategies and the cell scheduling algorithm.Only when the input-queuing strat- egy is combined with a proper switching algorithm can throughput and tme delay for the switching fabric be opti m ized This paper mainly discusses virtual output queuing (VOQ)-based algorithms,among them the maxium number matching algorithm,the maxmum weight matching algorithm,the stable combination matching algorithm, and the Hopfield neural netork(HNN)scheduling algorithm The mechaniss,perfomance and mplementation- al comp lexity of these algorithms are compared and analyzed The working modes of distributed and centralized scheduling algorithms are analyzed Finally,from the findings in our research,it is concluded that the HNN algo- rithm can realize other algorithms by defining a priority functon Keywords:input-queuing virtual output queuing bipartite graph matching scheduling algorithm 在高速信元交换中，为消除或减小队首(head of 0586.采用虚拟输出队列(virtual of queuing,. lie,HOL)阻塞和解决信元对交换线路的竞争造成VOQ)的输入排队方法不需要更高的加速比，可以 的丢失问题，必须对信元进行缓冲排队，在时间上将 消除队首阻塞，并使吞吐率达到100%2).目前，许 冲突信元分开.根据缓冲队列相对于交换结构的位 多产品都采用基于Crossbar交换结构的“输入排队 置，调度算法可分为输入排队(input-queued,Q)算 +VOQ"排队系统，如Tiy-Tea太比特路由器原 法、输出排队(ouput-queued,OQ)算法以及组合输 型和Cis0GSR12000系列的P路由器I) 入输出(combined input/output-queued,CDQ)排队 1基本问题与算法 算法三大类.目前研究的重点，应用最多的是输入排 队算法.传统的输入排队采用简单的FO(先进先 在信元交换中，每一个信元周期开始时，输入端 出)机制，因为存在队首阻塞，其吞吐率只有 口向调度器请求与相应的输出端口建立连接，调度 器根据调度算法确定无冲突的端口配置方案.调度 收稿日期：2007-11-15 基金项目：河南省杰出青年基金资助项目(512000400)，教育部留学 算法所寻求的结果就是在一个信元时隙内通过多次 回因人员科研启动基金资助项目. 迭代达到输入和输出端口的最优匹配，从而使吞吐 通讯作者：申金媛.Emaik jyshen@z四edu cn 率接近100%.因此调度问题可以看成解决二部图 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3卷第 3期 智 能 系 统 学 报 Vol. 3 №. 3 2008年 6月 CAA I Transactions on Intelligent System s Jun. 2008 基于输入排队的高速交换调度算法研究 张重洋 ,申金媛 ,刘润杰 ,张文英 ,穆维新 (郑州大学 信息工程学院 ,河南 郑州 450052) 摘 要 :高速交换网络一般采用基于定长信元的交换结构 ,其性能决定于排队策略和信元调度算法. 输入排队策略 只有和一个有效的调度算法相结合 ,才能保证交换结构具有良好的吞吐率和时延等性能. 主要阐述了基于 VOQ的最 大数量匹配算法 ,最大权重匹配算法 ,稳定结合算法 ,神经网络算法等输入排队调度算法 ,分别从技术特点 ,性能指 标和实现复杂度等多个方面进行比较和分析. 分析了分布式和集中式两大类调度算法的工作方式 ,并根据各类算法 的特点提出 ,神经网络算法可以通过定义其优先级函数实现其余各类算法. 关键词 :输入排队 ;虚拟输出队列 ;二部图匹配 ;调度算法 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2008) 0320265205 A study on scheduling algor ithm s for high2speed switching networks based on input2queuing ZHANG Chong2yang, SHEN Jin2yuan, L IU Run2jie, ZHANGW en2ying, MU W ei2xin ( Institute of Information Engineering, Zhengzhou University, Zhengzhou 450052, China) Abstract: Most high2speed switching networks adop t a switching fabric with fixed2length cells, and their perform2 ance depends heavily upon queuing strategies and the cell scheduling algorithm. Onlywhen the input2queuing strat2 egy is combined with a p roper switching algorithm can throughput and time delay for the switching fabric be op ti2 m ized. This paper mainly discusses virtual output queuing (VOQ ) 2based algorithm s, among them the maximum number matching algorithm, the maximum weight matching algorithm, the stable combination matching algorithm, and the Hopfield neural network (HNN) scheduling algorithm. The mechanism s, performance and imp lementation2 al comp lexity of these algorithm s are compared and analyzed. The working modes of distributed and centralized scheduling algorithm s are analyzed. Finally, from the findings in our research, it is concluded that the HNN algo2 rithm can realize other algorithm s by defining a p riority function. Keywords: input2queuing; virtual output queuing; bipartite graph matching; scheduling algorithm 收稿日期 : 2007211215. 基金项目 :河南省杰出青年基金资助项目 ( 512000400) ,教育部留学 回国人员科研启动基金资助项目. 通讯作者 :申金媛. E2mail: jyshen@zzu. edu. cn. 在高速信元交换中 ,为消除或减小队首 ( head of line, HOL)阻塞和解决信元对交换线路的竞争造成 的丢失问题 ,必须对信元进行缓冲排队 ,在时间上将 冲突信元分开. 根据缓冲队列相对于交换结构的位 置 ,调度算法可分为输入排队 ( input2queued, IQ )算 法、输出排队 ( output2queued, OQ )算法以及组合输 入输出 ( combined input/output2queued, C IOQ )排队 算法三大类. 目前研究的重点 ,应用最多的是输入排 队算法. 传统的输入排队采用简单的 FIFO (先进先 出 ) 机 制 , 因 为 存 在 队 首 阻 塞 , 其 吞 吐 率 只 有 0. 586 [ 1 ] . 采用虚拟输出队列 ( virtual of queuing, VOQ)的输入排队方法不需要更高的加速比 ,可以 消除队首阻塞 ,并使吞吐率达到 100% [ 223 ] . 目前 ,许 多产品都采用基于 Crossbar交换结构的“输入排队 +VOQ ”排队系统 ,如 Tiny2Tera太比特路由器原 型 [ 4 ]和 Cisco GSR 12000系列的 IP路由器 [ 5 ] . 1 基本问题与算法 在信元交换中 ,每一个信元周期开始时 ,输入端 口向调度器请求与相应的输出端口建立连接 ,调度 器根据调度算法确定无冲突的端口配置方案. 调度 算法所寻求的结果就是在一个信元时隙内通过多次 迭代达到输入和输出端口的最优匹配 ,从而使吞吐 率接近 100%. 因此调度问题可以看成解决二部图