大容量交换机多级交换结构及其调度算法的研究和设计

摘要随着因特网和宽带通信技术的高速发展，因特网的信息流量和设备的数量以惊人的速度增长，同时传输技术的长足发展使得传输容量大幅度提高。交换机和路由器是架构因特网的主要互连设备，因而对交换机和路由器提出了更高的要求。高速、高性能的交换机和路由器是实现高速骨干网并决定其性能的关键所在。本文首先介绍了三级Clos网络的应用以及无阻塞条件，在此基础上提出了基于三级Clos网络大容量分组交换机的体系结构，并且分析了交换机的数据流程，输入控制器和输出控制器的帧处理，以及集中调度器的功能结构。本文详细讨论了集中调度器的逻辑结构以及分组调度策略的设计。集中调度器在交换机设计中处于中心位置，是整个交换机协调工作的关键。本文提出了一种基于帧的双重匹配调度策略，该策略分为模块级匹配和端口级匹配两部分，采用启发式并行匹配算法进行路由，采用本文根据iSLIP输入排队调度算法提出的E-iSLIP算法进行调度。E-iSLIP算法采用竭力服务策略和优先级概念，可以改善算法在突发流量下的性能。在这些设计思想的指导下，本文对E-iSLIP算法进行了性能仿真，仿真结果表明，与iSLIP算法相比，E-iSLIP算法在突发流量下的性能有明显改善，在均匀流量下是稳定的，而且采用了优先级的E-iSLIP算法比未采用优先级之前具有更好的公平性。关键词：交换机，Clos网络，调度，iSLIP，突发流量IAbstractWiththerapiddevelopmentofInternetandbroadbandcommunicationstechnology,theinformationanddevicesofInternetisgrowingwithexponentialspeed,meanwhile,thecapacityoftransmissionislargelyimprovedbythegrowingtransmissiontechnology.SwitchesandroutersarehighlydemandedandthekeyofrealizationofhighspeedbackbonenetworkasthemaininterconnectiondevicesofInternetconstruction.Thispaperintroducestheapplicationandnonblockingconditionsofthethree-stageClosnetworkfirstly.Afterthat,thearchitectureofapacketswitchbasedonthethree-stageClosnetworkisproposed.Next,thedataflow,frameprocessingofinputportcontrollerandoutputportcontrollerandthestructureofcentralizedpacketscheduleraredescribed.Afterintroducingtheconceptsandarchitecturesofthemultistageswitch,theauthorfocusesonthedesignofpacketschedulerandthestrategyofscheduling.Packetscheduleristhecenterandkeyofthedesignofswitch.Adual-levelmatchingstrategybasedonframeisproposedinthispaper.Thestrategyiscomposedofmodule-levelmatchingandport-levelmatching,aheuristicparallelmatchingalgorithmisusedforrouting,andtheE-iSLIPalgorithmbasedontheiSLIPalgorithmisusedforscheduling.TheexhaustiveservicestrategyandpriorityconceptarebothusedintheE-iSLIPalgorithmtoimprovetheperformanceunderbursttraffic.Afterthat,thesimulationofE-iSLIPandiSLIPareintroducedindetailsandtheresultsofsimulationareanalyzedalso.ItcanbeseenclearlythattheE-iSLIPoutperformstheiSLIPalgorithmunderbursttrafficindelayperformanceandmaintainsstableunderuniformtraffic.Besides,E-iSLIPwhichemploysprioritieshasbetterfairnessthanthatwithoutpriorities.Keywords:Switch,Clos-Network,Scheduling,iSLIP,BurstTrafficII独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期：

年

月

日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在_____年解密后适用本授权书。本论文属于

不保密□。（请在以上方框内打“√”）学位论文作者签名：

指导教师签名：日期：

年

月

日

日期：

年

月

日1绪论1.1太比特路由器的产生及其研究进展随着Internet和宽带通信技术的飞速发展，Internet主机的数量正以每两年增加3倍的速度增长，Internet流量正以每3个月增加1倍的速度增长。同时传输技术的长足发展使得传输容量大幅度提高。目前，提高系统传输容量的最佳技术是密集波分复用(DWDM:DenseWavelengthDivisionMultiplexing)和超DWDM(Ultra-denseWDM)技术，该技术可在单根光纤上实现多个信道复用，对该技术的研究取得了很大进步。最近，NEC公司发布了在单根光纤上实现最大容量10.92Tbit/s(27340Gb/s)的三波带(S带、C带、L带)超密集波分复用光中继传输技术。因而具有几百根光纤的一个光纤管道的容量已经达到拍比特级(petabit，即1015bit)。光纤和光互联技术的进步使网络带宽容量扩大了10000倍[1]，但仅有传输带宽的增加是不够的，电子技术的发展没能跟上光技术的发展步伐，交换机/路由器的带宽只增加了10倍[1]，不能有效地利用DWDM技术所创造的巨大原始带宽。为了使网络性能全面提高，需要Internet中的“立交桥”—路由器工作得更快，而传统的路由器已经无法满足组建高速骨干网络的需求，发展太比特路由器越来越受到人们的重视。太比特路由器技术是一个很新的研究热点，因此，目前发表的研究成果有限，而且大部分发表在2000年后。最早研究太比特路由器的文献是Stanford大学的Dally于1998年发表的论文[2];，该文的研究成果是第一台商用太比特路由器—AviciTSR的理论基础。国外研究太比特路由器技术的单位主要有大学、路由器产品公司。其中包括:Polytechnic大学Chao领导的研究小组[3,4]；Washington大学Turner领导的“TerabitBurstSwitching”项目，是基于光结构的太比特路由器技术[5];Princeton大学Wolf领导的研究小组[6];IBM公司的研究小组[7];在Dally教授和McKeown教授领导下，Stanford大学的“TheOpticalRouter”项目(目标是研制出100terabit/s交换容量的路由器)是比较多产的，发表了较多的研究成果[8-11];另外还有一些文献，虽然其研究目标并不一定针1对太比特路由器，只要是有关高速、高性能的交换技术，都可以将其有益的思想引入到太比特路由器，因为太比特路由器技术就是在采用了许多ATM技术发展起来的，所以，研究太比特路由器的单位和专家许多是起步于研究ATM技术。太比特路由器一般基于电结构、光电混合结构或全光结构，鉴于现在和未来几年的光电技术水平，目前光电混合结构是比较经济、合理、可行的，如:Stanford大学的“TheOpticalRouter”项目研制的太比特路由器就是基于光电混合结构。从长远看，全光结构的太比特路由器将是必然的发展趋势。太比特路由器技术的研究工作近两年在国内才开始。研究单位及学术带头人包括清华大学的吴建平教授、解放军理工大学郑少仁教授和中科院沈阳计算所栾贵兴教授等。目前国际上成熟的太比特路由器不是很多，Avici,Nexabit(现已被Lucent公司收购)和Pluris是在研制太比特路由器方面领先的三家公司。典型的产品有AviciTSR,LucentNX64000和PlurisTNR。此外，Cisco公司、Juniper公司、charlotte等公司都提出了自己的太比特路由器研制计划。我国目前尚没有太比特路由器产品，但是，在2002年，国家863计划中提出了建设“高性能宽带信息示范网(3Tnet)”的研制计划，该高性能宽带信息示范网(3Tnet)集成了太比特高速光传输、太比特智能光网络、太比特IP路由器和太比特应用支撑环境。其中的分项研究课题就有:太比特路由器研制计划，目前正在由清华大学为主体实施攻关。总体上来说，国内的研究成果还停留在理论阶段。太比特路由器向着路由器群集、分布式、可扩展方向发展。串行高速和光交换技术将在交换阵列中采用，光纤背板将取代电子背板;太比特路由器通过冗余备用模块来提高系统的可靠性;ASIC技术的普遍使用将大大提高路由的转发能力，越来越多地使用基于硬件的交换和分组转发引擎;接口速率也将会越来越高，可直接支持全光网络的互连。总之，未来的太比特路由器将会向着超高速、高带宽、光纤化、智能安全化和易扩展方向发展。21.2太比特路由器关键技术的研究现状太比特路由器交换结构的研究现状交换结构的应用很广，在交换系统、多处理器系统、交换机和路由器中都有应用。路由器经历了从单处理器到多处理器、从共享总线到交换结构的发展过程。交叉开关(crossbar)结构与前几代的结构相比，其具有易实现各端口之间的线速无阻塞互连、能同时传输多个信元等优点，同时它也较好地解决了IP多播、广播以及服务质量等问题，例如:Stanford大学研制的TinyTera路由器就是交叉开关结构。因为这些优点，传统路由器和ATM交换机基本上都采用交叉开关这种结构。但是，由于单级交换结构(以交叉开关结构为代表)的可扩展性差，在太比特路由器中采用多级交换结构来提高可扩展性是很有必要的。多级交换结构常见的是Banyan结构，在Banyan结构的基础又扩展出Clos、Benes、Batcher-Banyan等交换结构[12]。现有的太比特路由器大部分采用多级交换结构。太比特路由器要求可以支持数百个端口，这些线卡不可能全部安装在一个机架上，因此就需要一种全新的分布式交换系统，它能够支持分装在多个机架上的几百个线卡，允许线卡与交换单元在物理上分离，使它们工作起来逻辑上如同一个完整的路由器。太比特路由器研制的核心问题之一是分布式无阻塞交换体系结构。交换网络不仅要支持机架内线卡之间的高速交换，还要支持机架间的选路与交换。同时，还要保持各条链路之间的流量均衡，以实现无阻塞交换。目前，国外产品机架间的互连都采用多级或多维交换结构。这些扩展方式以往大多应用于巨型计算机中。如何采用这种互连结构实现太比特路由器系统的无阻塞交换，保证各端口之间数据传输的公平性和各链路上流量的均衡性，是必须攻克的技术难点。目前采用得较多的结构是多维交换结构，例如，在AviciTSR中采用的是三维圆环面(torus)交换结构。在PlurisTNR中采用的是超立方体(hypercube)结构，采用这种3结构可以提供高吞吐率，同时可以提供组播、广播服务，并保证服务质量。在HyperChipPBR-1280中采用的是多维超立方体结构。现在的太比特路由器经常用交叉开关作为基本元素，按某种拓扑结构组成多级交换结构，构成一个太比特路由器的机架;又采用多维交换结构(如:超立方体结构)在机架间互连，构成完整的太比特路由器。太比特路由器分组调度策略的研究现状及发展趋势路由器的内部调度和分组快速处理技术己经成为太比特路由器的核心技术。如何在太比特路由器内部提供更有效的调度算法就成为了目前网络技术研究领域的一个热点。在分布式的路由器体系结构中，为了调度的需要应该采用一定的分组缓冲策略，也称为分组排队策略。一般来说路由器转发子系统中的队列管理按其所处位置可以有三种方式:输入队列(IQ,InputQueue);输出队列(OQ,OutputQueue);组合输入输出队列(CIOQ,CombinedInputandOutputQueues)。传统的路由器一般基于输出排队，在这种结构下，到达输入端口的信元马上被交换到相应的输出端口。OQ的优点是能够提供最优的吞吐量和延迟控制，其调度算法在理论上已得到深入的研究，实现简单。但为了保证OQ的正常运行，交换结构的内部带宽和输出队列的存储器访问速率必须是输入端口链路速率的N倍(N是输入端口数，如果输入速率不同，则为端口速率之和)，即要求N倍的加速比，随着链路速率或端口数的增加，在现有的工艺水平下很难实现高速的基于OQ的交换结构。为了克服OQ结构的可扩展性问题，人们又考虑采用输入排队。到达的信元首先被保存在输入端口的缓冲区中，然后通过调度算法决定信元何时通过交换结构传送到输出端口。IQ的优点是不需要加速比，但是存在链头阻塞问题(HOL,headoflineblocking):如果队列链头的信元被阻塞，同队列到其他输出端口的信元就不能被转发。研究表明，当端口数较多时，在所有输出均匀分布的Bernoulli到达下，IQ只能达到58.6%的吞吐率[13]。解决输入排队链头阻塞问题的一种简单方案是虚拟输出排队(VOQ,virtualoutputqueuing)[14]，在这种结构下，每个输入端口为每个输出设置一个队列，从4而消除了链头阻塞并保持加速比为1。理论研究和仿真实验都表明，一个采用最大权重匹配调度算法的VOQ路由器可以到达100%的吞吐率。但是，VOQ路由器的一个不足是很难提供QoS(QualityofService)保证，原因在于信元的转发不仅与输入端口的通信量有关，而且受调度算法的影响。提高VOQ路由器性能的一种方法是利用加速比，这需要在输入和输出端口都设置缓冲区。这种结构称为组合输入/输出排队(CIOQ)。研究表明[14]，加速比为2的CIOQ路由器能够完全仿真一个OQ路由器。这样，可以利用CIOQ继承OQ的吞吐率和延迟特性。但是，要在CIOQ路由器中实现QoS保证，关键在于设计一个有效的配置交换结构的调度算法。如何基于流进行支持服务质量的调度将是调度算法的进一步的研究方向。目前，太比特路由器一般采用输入排队(虚拟输出排队)或组合输入/输出排队结构。高速路由器根据体系结构的不同可分为集中式和分布式两种。集中式的优点是调度方案简单、易于实施，但是，很难在一个短的时间片内实现调度。分布式的路由器由多个并行的带独立调度器的交换结构组成，一个负载平衡算法将每个输入端口的信元发送到某个交换结构，然后由交换结构决定何时转发信元到输出端口，分布式结构的最大优点是降低了交换结构的输入/输出链路速率，从而增大了时间片，因此可以使用复杂的调度算法。现有的采用分布式结构的路由器包括ADSA[6]和PPS(parallelpacketswitch)[15]。与PPS相比，ADSA具有算法简单和控制信息少的优点，但这种分布式结构性能需要在实际网络环境中做进一步的测试，其负载平衡算法也需要深入研究。Chang等人最近提出了一个新颖的实现较简单的负载平衡两级交换结构(LB-BvN,loadbalancedBirkhof-vonNeuman)及其调度算法[16]，不仅能够达到100%的吞吐率及保证延迟限度，而且不需要大于1的加速比和复杂的调度算法，可以应用于电子交换结构和光交换结构的太比特路由器中。但是该调度算法的缺点是有可能造成信元失序，虽然Chang等人又提出基于FCFS(firstcomefirstserved)和EDF(earliestdeadlinefirst)的调度算法[17]，来解决其信元失序问题，但是FCFS要求在第2级输入前增加复杂的抖动控制机制，EDF要从第2级输入队列中找出时戳最小的信元，都不容易实现。5针对该交换结构，需要人们深入研究，提出较好解决信元失序的调度算法。未来的太比特路由器调度算法首先要适应网络带宽的快速增长，具有良好的可扩展性和性能，不能成为网络传输的瓶颈，同时，在延迟、公平性和服务类型的多样化等方面也要有较好的保证。1.3本课题的研究目的、意义和本文主要内容本文课题的目标就是光电混合大容量交换机研制开发项目的第一阶段，即利用线速1Gb/s的1616crossbar交换芯片开发基于多级交换网络的128128Gb/s大容量交换机。本文研究基于多级交换网络的大容量交换机的体系结构及分组调度策略，以及交换机的输入排队调度算法。全文组织结构及主要内容如下：第一章简要介绍太比特路由器的产生及国内外研究现状，并对太比特路由器的新功能以及研究现状进行了描述，指出分组调度策略在太比特路由器研究中的重要意义。第二章提出了基于三级Clos网络的多级交换机体系结构，并且对数据流程以及各个模块的功能进行了介绍。第三章分析了集中调度器的逻辑结构，提出了一种基于帧的双重匹配调度策略，用于解决三级Clos网络的信元调度和路由分配问题。第四章介绍调度算法的相关概念以及现有的输入排队调度算法的调度规则，并提出一种采用竭力服务策略的输入排队调度算法E-iSLIP算法。第五章对提出的输入排队调度算法E-iSLIP进行性能仿真及分析。第六章对本论文进行了总结并探讨课题下一步的工作。62多级交换机系统结构设计2.1前言交换结构的选取对路由器的性能有很大的影响，由于多级交换结构良好的扩展性，目前的大容量路由器和交换机多采用基于多级交换网络的交换结构，例如Bayern，Benes，Clos网络等都在交换结构设计中发挥了重要作用。本章提出用三级Clos网络构造大容量交换机的方案，首先提出了基于三级Clos网络的多级交换机体系结构，然后分别分析了交换机的数据包流程，信元和帧的数据格式，输入控制模块和输出控制模块中的帧处理过程，以及集中调度器的逻辑结构。2.2多级交换机体系结构网络交换背景三级Clos网络[18]是采用基本交换单元来搭建大型交换结构的最常用的拓扑。Clos网络可以用来有效实现低延迟，高带宽，面向连接的ATM交换。Clos类型的交换结构还有经济和技术上的吸引力。根据他们的内在容错和多径路由的特性，是提供可靠的宽带交换的非常有吸引力的一个选择。三级Clos网络由于其模块化和可扩展性被广泛用于商用多处理器互连网络和交换阵列。例如IBMGF-11并行系统Memphis交换机，NEC的ATOM，Hitachi的超级分布式交换系统OPTIMA，和TORUS电光混合T比特交换机----ATMOS光交换机，Lucent的Atlanta套片，Myrinet的Myrinet-2000系列光纤通道交换机等等。分组交换三级Clos网络目前流行两种结构，SSS(Space-Space-Space,S3)结构采用无缓存的空分交换单元实现。MSM(Memory-Space-Memory)结构采用第一级和第三级为共享缓存单元，第二级为无缓存空分交换单元实现。我们提出的是采用SSS结构的Clos网络。7欲将任意一个输入单元的输入端连向任意一个输出单元的的输出端时，有的多级互连网络会产生阻塞，有的则不会产生阻塞。对于产生阻塞的多级互连网络，有的可以通过重新调整现有的连接而避免之，有的则不能。多级互连网络处于阻塞状态是指对于存在空闲的输入级输入端点和输出级输出端点时，多级互连网络找不到一条空闲的链路将它们连接起来。根据阻塞情况的不同可以将Clos型多级互连网络细分为以下三种:(1)严格无阻塞Clos型多级互连网络是指多级互连网络不管处于什么状态，对于任意的空闲输入级输入端点和输出级输出端点，总存在空闲的链路将它们连接起来。而不需调整多级互连网络中己建立起来的连接。(2)广义无阻塞Clos型多级互连网络是指多级互连网络中存在发生阻塞的可能性，但是可以通过路由控制算法避免阻塞的发生，且不必重新调整多级互连网络中已建立起来的连接。(3)可重排无阻塞Clos型多级互连网络是指多级互连网络发生阻塞时，通过路由控制算法重新调整现有的连接,从而在输入级输入端和输出级输出端之间，找到一条空闲的链路建立起连接。对于以上三种不同类型的Clos多级互连网络，其体系结构是不同的。在此给出三级Clos型互连网络在各种情况下的无阻塞的条件:(1)对三级Clos网络C(m,n,k)，如果m≥2n−1，则此网络是严格无阻塞的，即只要一条连接的起点和终点是空闲的，任意时刻都可以在交换结构中建立这条连接而不影响网络中已经建立的连接。(2)如果m≥3n/2，则此多级互连网络是广义无阻塞的。(3)如果m≥n，则此网络是可重排无阻塞的，即只要一条连接的起点和终点是空闲的，任意时刻都可以在交换结构中直接或对已有的连接重选路由来建立这条连接。以上是适用于电路交换的三级Clos网络的无阻塞条件。对于分组交换结构，如果将每个内部信元视为一个呼叫，以信元为单位进行路由选择。在信元到达之前建立通路，在信元过去后释放该连接，则上述结论也适用于分组交换的三级Clos网络。由以上的条件可以看出，如果中间级交换单元的数量越少，则多级互连网络产生8阻塞的可能性就越大，因此，就越要求优良的路由控制算法来实现无阻塞的连接。对于多级互连网络而言，我们总希望使用最少的交换单元来实现连接。这样可以降低成本。由于在输入、输出交换单元数，和输入交换单元的输入端口、输出交换单元的输出端口数在相对固定的情况下。唯有减少中间交换单元数来降低成本。这就意味着必须提高路由控制算法的复杂度来避免发生阻塞。从以上的三种阻塞情况来看，可重排无阻塞多级互连网络所需要的中间级交换单元数最少，所以我们以下将研究基于三级可重排无阻塞Clos型互连网络的交换机体系结构。多级交换机系统结构PS请求允许

IPC

帧头信息SwitchFabric

OPC1Gb/s

LC

VOQ

FA

FD

FIFO

LC

1Gb/sIMCMOM系统时钟PS：集中调度器LC：线卡IPC：输入控制器

OPC：输出控制器VOQ：虚拟输出队列FIFO：先入先出队列

FD：解帧模块FA：组帧模块IM：输入单元

CM：中间单元OM：输出单元SwitchFabric：交换结构图2.1

多级交换机系统结构如图2.1所示是多级交换机的系统结构[19-22]，基本模块包括线卡（linecard），输入端口控制器（IPC，inputportcontroller），输出端口控制器（OPC，outputportcontroller），交换结构(switchfabric)，集中调度器（PS，centralizedpacketscheduler），系统时钟分配单元（systemclockdistributionunit）。交换结构是三级Clos网络结构，9................................................由输入交换单元（IM,inputswitchmodule），中间交换单元（CM，centralswitchmodule），输出交换单元（OM，outputswitchmodule）组成，每个交换单元都是crossbar交换芯片。我们假设交换网络规模为128128(128个输入端，128个输出端)，交换单元为1616的交换芯片，则根据可重排无阻塞条件，IM，CM，OM的数目分别为8，8，8，若输入和输出端口线速为1Gb/s，则可以达到128Gb/s的交换容量。所有的输入数据包都在线卡中分解成等长的信元，存在线卡缓存中。所有的信元都在IPC和OPC中缓存，中间的交换结构是无缓存的。IPC上的虚拟输出队列(VOQ,virtualoutputqueue)和集中调度器为交换机提供冲突解决。在输入端，输入数据包缓存在线卡中，然后被分割成信元并且根据目的端口存入相应的VOQ中，相同目的端口的信元存在同一个VOQ。IPC上的VOQ作为线卡上VOQ缓存结构的“镜像”，只要能保持信元在线卡和IPC之间的流动，IPC上的VOQ相比线卡上对应的“镜像”VOQ就可以小得多。在信元发送给目的端口线卡之前，OPC中的缓存用来存储这些信元。在输出端口线卡中有虚拟输入队列（VIQ，virtualinputqueue）用来缓存从交换结构传来的信元，把它们重组成数据包。集中调度器帧载荷

帧头

交换网络输入信元

r

组帧

帧头

帧

r解帧

FIFO

输出信元VOQ输入控制器

k

m

k

输出控制器图2.2

数据流程图图2.2表示了数据是如何流经系统的。在输入端口线卡中，不定长的数据包被分割成定长为64B的信元（包括信元头开销），然后把信元从线卡发给IPC，在IPC中，每一个VOQ都采用并行缓存结构，使得每次同时可以读取r个信元。这r个信元在IPC里面的组帧模块中组成一帧。当线卡端口速率为1Gb/s时，一个信元时隙为T=10512ns，假设r=8，则每一帧的周期为f=rT=4096ns。在交换网络的每一级，相应的帧头被提取出来进行处理，控制交换单元。由于集中调度器已经解决了竞争冲突，在交换网络的每一级，通过选择交换单元相应的输出链路，数据帧可以找到一条合适的路径通过交换网络。当帧到达目标OPC后，通过OPC解帧模块，帧被分解成相应的r个信元，然后OPC把信元发给线卡。载荷

图2.3

入端口出端口数据结构图

有效位图2.3描述了在交换每一级的数据结构。每一个输入信元的载荷前面都包含两个头部域，OL表示信元的输出端口号，IL表示信元的输入端口号。信元头部的有效位表示信元是否有效。如果是NN的三级Clos交换网络C(m,n,k)，则信元头部长度为1+log2N+log2Nbits，N=128，则信元头部大小为15bits。帧的头部域包含CM号，OM号，输出端口号，有效位四部分，帧的头部长度为1+log2k+log2m+log2nbits，因为m=n=k=8，所以帧的头部长度为10bits。有效位表示帧是否包含有效信元。图2.4描述了信元如何经过IPC。数据包A来自输入端口1，要到目的端口1。在到达IPC之前，A已经被分割成定长的信元，存在相应的线卡中。在这个例子里，A被分解成16个信元（A0到A15），所有的信元都以轮转方式存在r(r=8)个帧缓存中。11FM1A8

A0

1N选择器A15

A8

A7

A0

A11

FM4

A3

1

TA8

TA0

组帧

F2

F1NA15

A7FM8

F2

F1A15

A7

1N

IPC图2.4

IPC中的帧处理信元到达IPC中的帧缓存，立即发送请求信号给集中调度器。若是128128的交换规模，则每个IPC在每个时隙发送给集中调度器的信息为2log2128=14bits。设集中调度器与IPC的通信总线位宽为20bits，频率62.5MHZ，则发送14bits信息大约需要15ns，发送128个端口的请求信息约需要3个信元周期T。调度器返回给IPC组帧模块的帧头信息为10bits，通过总线传送约需要15ns，发送给128个端口同样需要3个信元周期T，因为我们的调度方式是基于帧调度，每一帧有8个信元，所以总共留给调度器的调度时间为2个T，即1024ns。集中调度器采用基于帧的双重匹配策略进行调度，再把允许信号返回给允许发送的IPC，A0到A7组成第一帧，A8到A15组成第二帧。图2.5描述了数据帧如何在OPC中进行处理以及在线卡中如何将信元重组成数据包。帧首先在解帧模块被拆成信元，然后根据信元头，在第一个帧周期，A0到A7进入OPC缓存中的8个FIFOs，在第二个帧周期，A8到A15进入相同的8个FIFOs。然后将这些信元从FIFO中读到线卡。线卡中的VIQ将信元重组成数据包A。12....................................选择器F2

F1

解帧

TA8

TA0

FIFOsA8A0A11A3

A15...A8线卡1

包A

A7...A0A15F2

A7F1

A15

A7OPC1图2.5

OPC中的帧处理为了保持时钟同步，一个系统帧时钟将提供给系统的各个模块。每一个交换动作，包括读写缓存，拆组数据帧，都要根据相同的帧时钟信号同步。还有一个基准时钟用来进行比特同步，该时钟频率1GHZ。集中调度器的结构如图2.6所示，它由k个SIMs和k个SOMs组成，每一个对应于三级Clos网络相应的IM和OM。每一个SIM都有n个输入端口仲裁器（IPAs），有n个虚拟输出端口仲裁器（VOPAs），每个虚拟输出端口仲裁器对应于相应的OM的一个输出端口。每一个SIM有一个输入模块仲裁器（IMA），每一个SOM有一个输出模块仲裁器（OMA）。一个可重新匹配的crosspoint交换芯片用来连接这些SIMs和SOMs。每一个输入线卡（ILC）有N个VOQs，每一个VOQ对应于一个输出端口。一个计数器C(i,j)用来记录相应的VOQ(i,j)的信元数目。13............SIM1线卡1

C(1,1)C(1,2)

IPA(1,1)

VOPA(1,1)

Crosspoint交换片

SOM1信元到达信息

C(1,N)线卡n

C(1,1)C(1,2)C(1,N)

IPA(1,n)

IMA1VOPA(1,n)

OMA1SIMk线卡N-n+1

C(N-n+1,1)C(N-n+1,2)

IPA(k,n)

VOPA(k,1)

SOMk信元到达信息

C(N-n+1,N)线卡N

C(N,1)C(N,2)C(N,N)

IPA(k,n)

IMAkVOPA(k,n)

OMAkSIM：输入单元调度模块SOM：输出单元调度模块C(i,j)：计数器

OMA：输出单元仲裁器IPA：输入端口仲裁器IMA：输入单元仲裁器VOPA：虚拟输出端口仲裁器图2.6

调度器结构图在每一次匹配循环的开始，每一个SOM发送m+2nbits信息给相应的SIM，其中mbits表示对应OM的m条输入链路的状态，2nbits表示对应OM的n个输出端口的状态。每一个输出端口有四种可能的状态：00表示输出端口未占用，01表示输出端口在上一帧的周期里占用，占用优先级为低。10表示输出端口在上一帧的周期里占用，占用优先级为高。11表示输出端口在这个帧周期里已经占用。假定SIMs和SOMs的匹配序列已经决定，例如，在一个循环里，SIMi与SOMj匹配，则在下一个循环里面，SIMi与SOM(j+1)匹配，这个过程重复k次。为了让所有SIMs均匀匹配，在每一个帧周期的开始，SIMs和SOMs的匹配序列要移动一个位置。14................................................2.3本章小结本章首先介绍了三级Clos网络在大容量交换机市场的背景以及技术优势，以及Clos网络的各种无阻塞条件。然后，我们提出了一种基于三级Clos网络的多级交换机体系结构，该交换机总体上可分为线卡，IPC，OPC，集中调度器，交换网络，系统时钟分配单元几部分。线卡负责接收从物理层来的数据，对数据进行处理，把数据包分解成等长的信元发送给IPC，IPC中的VOQ先存储待发送的信元，在等到允许信号之后，将信元发送给IPC中的组帧模块，组帧模块再把得到允许的信元加上调度器发送过来的帧头信息，组成数据帧，传送到交换网络。交换网络为128128的Clos网络，需要24片1616的crossbar交换芯片搭建而成，整个网络是可重排无阻塞网络。我们还提出了信元和帧的数据结构，介绍了IPC，OPC的数据处理流程，并且分析了调度时间要求。信元的冲突和选路问题由集中调度器和IPC解决，集中调度器采用分布式的Clos网络调度策略，同时进行端口的匹配和路由选择，具体的调度策略将在后一章介绍。153多级调度策略设计3.1前言上一章提出了三级Clos网络交换机的逻辑结构，其中分组调度器的设计处于核心位置，它负责与线卡和交换网络通信，控制信元的发送和路径，配置交换网络，实现信元的可重排无阻塞传输。在本章里，我们首先介绍了多级调度策略的背景，然后提出一种分组调度器的逻辑结构，接着提出了一种基于帧的双重匹配调度策略，该策略分为模块级匹配和端口级匹配两部分，处理Clos网络中的信元调度和路由分配问题。3.2多级调度策略背景Clos网络的调度可以分解为两个问题：信元调度和路由分配。前者为一个输入信元决定相应的输出端口，后者为一对输入输出匹配端口寻找内部无冲突的路径。寻找一种高吞吐量，低延迟，公平，易实现的三级无缓存Clos调度算法是一个很大的挑战。而且调度算法必须具有很好的扩展性，因为随着交换容量和端口线速的增加，调度方案的仲裁时间要求越来越严格。在文献[23]中作者提出了一种路径交换策略，在这种策略中，根据相应的负载模式，在信元到达之前，预先进行IM与OM之间的路由分配。根据预先分配好的路由，当信元相应的IM和OM之间有空闲的路由时，就可以把信元发送出去。然而路径交换策略假设了负载模式是已知的，但是Internet的流量大部分是面向无连接的。在文献[24]中作者提出了一种分布式静态round-robin调度算法，通过round-robin的方式路由信元。然而，由于这种算法的静态特性，这种算法不能解决不同流量下的问题。最近，一类新式的Clos网络匹配算法(MAC)被提出来[20,21]，以有效的调度决策三级无缓存Clos网络的交换问题。为了缓解严格的仲裁时间限制，MAC基于帧进行操作，每一帧由固定长度个信元组成。由于分布式的处理，输入输出匹配和路由选择是同时在调度模块里进行的，MAC可以提供良好的性能指标而且具有很好的扩展性。然而这种方式的时间复杂度太高，使得帧的尺寸比较大。163.3分组调度器的设计分组调度器在基于多级交换结构的交换机中非常重要，它负责与线卡和交换网络进行通信，根据线卡发送的信元到达信息进行调度和路由分配，并且配置交换网络的状态。然后把匹配结果返回线卡，线卡收到匹配结果后，立即把信元从配置好的交换网络传送到输出端口，交换网络的状态在一帧的发送时间内保持不变。调度器逻辑结构如图3.1所示，分组调度器由k个输入调度模块(SIM)，k个输出调度模块(SOM)组成，每一个都对应于三级Clos网络相应的输入或者输出单元。一个可重置的crosspoint交换结构被用来互连这些SIMs和SOMs，使它们可以相互交换信息，从而分布式的计算端口间匹配和路由分配问题。SIM1SIMk

图3.1

分组调度器

SOM1SOMk由于具有很高的线速和交换容量，为缓解严格的仲裁时间限制，我们对每一帧进行调度，设一帧由r个信元组成，每个信元的传送时隙为T，则发送一帧需要rT的时间。所有输入某个线卡的分组被分解成定长的信元，目的端口相同的数据包存在相同的虚拟输出队列(VOQ)里，在一个VOQ中的某帧，一旦获得分组调度器(PS)发送的grant信号，就被传送到目的端口。在传送每一帧时，交换结构保持交换状态不变一直到该帧传送完毕，且允许在该帧传送完之后改变交换状态。帧的大小r事先由预计调度仲裁时间，从线卡到分组调度器的数据往返时间，以及交换结构的重新配置时间共同决定。17........................调度方案输出端口10000图3.2

000000010010000000100000001000端口匹配矩阵信元调度问题可以归类为二分图匹配问题(端口到端口)，而路由选择可以归类为二分图染色问题（模块到模块）。二分图匹配问题我们在下一章将详细分析，下面我们先分析路由选择问题。OMIM图3.3

2111IM-OM连接矩阵给定一组输入输出端口匹配，在三级无缓存Clos网络中的路由分配问题可以用相应的输入输出单元的二分图染色问题来描述。假设每个交换单元是33的交换单元(n=3)，输入和输出单元数k为2，中间单元数m为3。假设如图3.2所示的匹配矩阵代表找到的交换机端口间匹配，如果输入端口g和输出端口h匹配则矩阵的元素(g,h)为1，没有匹配则为0。如图3.3所示，这个端口匹配矩阵可以转换成一个IM-OM连接矩阵，矩阵元素(i,j)代表从IMi到OMj的信元可以选择的中间单元数目。注意到IM-OM连接矩阵的任意行元素之和，任意列元素之和都不能大于n。如图3.4所示，IM-OM连接矩阵逻辑上等效于一个二分图。18输入端口0输入端口0蓝绿红图3.4

红蓝二分图染色假设每个CM用不同的颜色来标示，例如，CM1用蓝色标示，CM2绿色，CM3红色。给指定的输入输出端口匹配寻找中间单元等效于给相应的IM-OM二分图边沿染色，染色的规则是，任意有共同端点的两条边不能用同一种颜色。图3.4给出了一个IM-OM二分图边沿染色方案。图3.5表示相应的路由分配。IM1

蓝绿

CM1

OM1CM2IM2

红

绿图3.5

CM3路由分配

OM2每一个CM的连接都是一对IM-OM匹配，因此，路由分配问题也可以看作从IM-OM的二分图中寻找m个（CM的单元数）匹配。换句话说，就是把IM-OM连接矩阵分解m个IM-OM匹配矩阵，如图3.6所示。在每一个IM-OM匹配矩阵中，任意行和或者列和是1或者0。在m=n的情况，就是可重排无阻塞的情况下，有许多路由分配算法可以应用于Clos网络，它们可以分为两类：一类是最优算法，可以提供有保证的匹配结果，但是时间复杂度高[25]，实现性差[26]。另一类是启发式算法[27]，例如并行匹配算法，可以保证全部或者大部分路由匹配，而且时间复杂度低。19矩阵分解2111

10100101＋00＋10图3.6

矩阵分解这里简单介绍一下并行匹配算法如何用来进行路由分配。首先把每一个IM的输出链路用Ai来表示(1≤i≤k)，每一个OM的输入链路用Bj表示(1≤j≤k)，如图3.7所示，每一个Ai和Bj包含了m个元素，这些元素表示每一条物理链路的状态，Ai={ai,h,1≤h≤m},Bj={bj,h,1≤h≤m}。ai,h(bj,h)=0表示这条链路没有被占用，否则ai,h(bj,h)=1。要找到一条在IM和OM的路径，只需要在Ai和Bj之中找到一对垂直的0，例如，图4.7表示在Ai和Bj之间有两条有效路径。1

2

3

m-1

mAiBj

11

01

00

11

......

11

00

11匹配图3.7

并行匹配算法

匹配我们根据提出的两级匹配算法[28]，提出了一种基于帧[29]的Clos网络调度方案。该Clos网络调度方案由两级匹配组成：模块级(module-level)和端口级(port-level)，图3.8和图3.13分别指出了模块级匹配和端口级匹配的任务。20图3.8

模块级匹配任务图在模块级，我们根据输入队列的状态决定SIM-SOM的匹配模式。在端口级，负责找到匹配的端口并且为相匹配的端口决定内部路径。对每一帧，模块级匹配决定k'(k'k)对SIM-SOM的匹配，只有相应的IM-OM单元端口才能在端口级参与匹配。在模块级，可以同时处理F个帧的交换，F个帧组成一个超帧(Superframe)，在每一次的模块匹配中同时决定F个帧也就是一个超帧的交换模式。模块级匹配由两步组成：超帧匹配和超帧分解。超帧匹配就是要根据交换机的输入队列状态决定一个超帧矩阵。如图3.9所示，超帧匹配的步骤如下：首先计算出流量矩阵，流量矩阵的元素t(i,j)表示要从IMi到OMj的缓存信元的数目，根据流量矩阵可以得到请求矩阵，请求矩阵的元素r(i,j)表示能从SIMi传送到SOMj的请求数目。然后我们采用EiSLIP算法来仲裁请求矩阵，从而得到超帧矩阵，超帧矩阵的每一元素代表相应的SIM和SOM间的匹配机会。1672

111212010115678

421

131302332222

211

121302132112流量矩阵

图3.9

请求矩阵计算超帧矩阵

超帧矩阵如图3.10所示，超帧矩阵分解采用启发式并行匹配算法来实现，把每个超帧矩阵2124112411分解成Fk'个模块匹配矩阵，每个模块匹配矩阵记录下SIM-SOM的匹配状态，到此模块级匹配完成。一帧内的k`个匹配循环211

121302132112

010

010100000001

001

100001010000

...

100

000100010001超帧矩阵

图3.10

模块匹配矩阵超帧矩阵分解当模块级匹配完成之后，下一个超帧的SIMs和SOMs之间的匹配次序(记录在模块匹配矩阵)就决定了，模块匹配矩阵与SIM-SOM的对应关系如图3.11所示。端口级匹配算法由k'次循环组成，在一个帧时隙之内完成，每一次循环都对应于相应的模块匹配矩阵。在端口级匹配，也分为两步：端口匹配和中间单元(CM)分配。221001000SIM1

SOM1010

010100000001

SIM2SIM3

SOM2SOM3模块匹配矩阵1SIM4SIM1

SOM4SOM1001

100001010000

SIM2SIM3

SOM2SOM3模块匹配矩阵2SIM4

SOM412

图3.11

模块匹配矩阵与SIM-SOM对应关系

53

IM1

OM2

7411OM3

12图3.12

端口匹配例示在端口匹配时，为找到相应IM-OM的匹配端口，我们采用EiSLIP算法。例如，当根据模块匹配矩阵，SIMi与SOMj在一个匹配循环中匹配，则在这个匹配循环的开230000始，SOMj首先发送端口可用信息到SIMi，然后SIMi执行EiSLIP算法进行匹配。图3.12为一次端口匹配的例示。为了提高匹配效率和带宽利用率，同时在SIM中引入优先级仲裁器，在优先级策略下，那些超过r个信元的VOQ的优先级高于那些未满r个信元的VOQ。因此，如果相应的VOQ的队列长度小于r，那些正处于匹配状态的输入输出端口可能失去匹配。另外，为了避免不公平性，设定当队列头HOL(HeadofLine)帧的等待时间超过一个门限值之后，该帧的优先级上升为最高。端口级匹配图3.13

端口级匹配任务图当端口匹配完成之后，必须为信元的路由选择合适的中间级(CM),我们同样采用前述在超帧分解中用到的启发式并行匹配算法来完成CM分配。图3.13为端口级匹配的任务图。模块级匹配和端口级匹配可以用流水线[30]的方式执行，如图3.14所示。每一个超帧由F帧组成，每一帧由r个信元组成。设每一帧的匹配循环次数为k',k'k。r个信元的传输时间必须大于等于k'个匹配循环的匹配时间，所以r不能取很小。在每一个超帧总共有Fk'个匹配循环，因此当前超帧进行端口级匹配时，下一个超帧同时进行模块级匹配，以决定F组每组k'个模块匹配矩阵。24模块级匹配

超帧匹配

超帧

超帧矩阵分解

超帧端口级匹配

帧1

...

帧x

...

帧Fk`个匹配循环数据传输

帧帧(r个信元)传输

……

帧图3.14

流水线匹配方式3.4本章小结本章首先介绍了几种常见的三级Clos网络调度策略，并且分析它们的优缺点。然后提出了一种分组调度器逻辑结构，该结构分为SIM，SOM，一个可重置的Crosspoint交换结构三部分，其中SIM，SOM对应于相应的输入输出单元IM，OM，Crosspoint结构负责SIM，SOM的信息交互。随后，我们分析了Clos网络调度存在的信元调度和路由分配问题，这两种问题可以分别等效于二分图的匹配和二分图的染色问题。在分析了二分图染色问题以及启发式并行匹配算法之后，我们提出了一种基于帧的双重匹配策略，该策略对每一帧进行调度，一帧由固定数目的信元组成。分为两步进行调度，模块级匹配和端口级匹配。模块级匹配由超帧匹配和超帧分解两步组成。而端口级匹配又由端口匹配和CM分配两步组成。其中，超帧匹配和端口匹配需要用到后面一章我们提出的E-iSLIP算法，而超帧分解和CM分配要用到启发式并行匹配算法。模块级匹配的结果决定相应的IM-OM单元参与端口级匹配。该匹配策略可以采用流水线方式执行。254输入排队调度算法设计4.1前言高速路由器一般采用基于定长信元的交换结构，其扩展性和性能分别受排队策略和调度算法的影响。基于输入排队策略的路由器具有良好的可扩展性，但需要有一个好的调度算法支持，才能保证吞吐率和延迟等性能。本章将首先介绍调度算法的基本概念以及性能指标，然后讨论输入排队调度算法，重点放在实际应用广泛的极大匹配类算法，对每一种算法，从技术特点和性能指标两个方面进行比较和分析。最后提出了一种采用竭力服务策略和优先权的基于iSLIP的新算法，该算法能够改善突发流量下的信元延迟性能。4.2调度算法调度算法是一系列规则，它按照一定的服务规则对交换节点的不同输入业务流分别进行调度和服务，使所有输入业务流能够按照预定的方式传输到下一节点。现有的调度算法有很多种，可以根据不同的分类标准进行划分。按服务规则分类，队列调度算法可以分为：先到先服务、循环调度、处理机共享、优先级服务、随机服务等。根据调度算法的调度目标分类，调度算法可以分为基于时延的和基于速率的。根据通信网络环境，又可分为无线环境下的队列调度和有线环境下的队列调度。根据调度算法的工作状态，还可以分为工作保持和分工作保持的。调度算法性能指标主要涉及吞吐量、信元延迟、时延抖动、复杂性和可扩展性几个方面。吞吐量是指单位时间内路由器转发的信元数量。延迟是指信元从到达路由器到离开所经历的时间。我们说一个路由器是稳定的，是指输入队列长度的期望值不能无限增长，如果一个路由器在所有独立的和可允许的到达下都是稳定的，我们说这个路由器能够达到100%的吞吐量。在高速网络中，传输一个信元的时间很短，所以调度算法必须在短时间内完成对信元的调度，这就要求调度算法要简单，易实现。另外，当业务流量增加和线路速率26变化范围较大时，调度算法仍应有效工作，这要求调度算法应该具有良好的扩展性。此外，一个好的调度算法还应具备以下性能：有效性：一个有效的算法在每次匹配中，应当有尽可能多的输入队列得到服务。稳定性：对于给定的可允许的业务类型，我们要求算法在任何时刻每个输入队列的平均长度总是有限长的。公平性：对于一个非空的输入排队，在一个给定的业务类型和调度算法下，不能使有的队列总得不到服务。易实现性：时间复杂度不能太高，在硬件上具有可实现性。4.3几个基本概念(1)阻塞：当到达不同端口的两个以上信元竞争同一内部链路时，即发生内部阻塞，如传统的BANYAN网络就是一个内部有阻塞的网络。当两个以上信元在同一时隙指向同一输出端口时，就会出现输出阻塞，所以必须在交换结构内放置缓冲器，以增加信元时延为代价来消除阻塞。在传统的输入缓冲结构中，在一个信元时隙内当FIFO队列的排头信元参与输出竞争失败后，即时排在它后面的信元指向的输出端口是空闲的，该信元也无法输出，这种想象称为排头阻塞。(2)加速比(speedup)：如果每个输出端口在一个时隙内可同时接收S个信元，就说这种交换结构具有加速功能，S称为加速因子。可通过时分和空分两种方法实现加速，前者指交换结构的内部速率是外部端口的S倍；后者则是为每个输出端口提供S条并行路径。(3)组播(multicast)：组播指的是一个源用户的一个数据分组或信元要同时传送到K个目的用户。显然，当K=1就是点到点连接也称为单播(unicast)，K=N即为广播。如视频分配就是典型的组播业务。组播是ATM交换机和路由器的重要功能之一。(4)性能：通常用三个参数描述信元交换结构的性能：吞吐率(TP)、交换时延(D)和信元丢失率(CL)。TP定义为每输入端口、每时隙成功传送信元到目的地端口的平均数，最大吞吐率(TPm)则是最大负荷下的TP值。D指的是一个信元从进入输入端口到传送到输出端口所经历的平均时间，它由缓冲器平均排队时延和一个信元的27传输时间组成。CL定义为交换结构信元丢失的数目与总到达数目之比，信元丢失是由于阻塞或缓冲器溢出造成的，显然降低CL的一个直接办法就是增加缓冲器的容量。此外，延时抖动也是描述交换结构性能的一个重要指标，它指的是一个信元在交换结构中经历的最大时延和平均时延的差值，通常用差值出现的概率表示：该指标对于实时业务有重要影响。不难看出，一个理想的交换结构应具有尽可能大的TP、较小的时研、信元丢失率和延时抖动。(5)优先级(priority):不同的业务在传送时延和丢失率业务上有不同的要求，如像话音这样的实时业务要求有较小的传送延时，像数据这样的非实时业务则要求有较小的丢失率，而像高质量视频业务则对时延和丢失率均有较高的要求。多媒体业务的不断引入要求交换机和路由器应能处理不同的优先级别以保证不同业务的QoS。(6)业务量模型(traffic)：到达输入端口的业务特性通常用两个随机过程描述：一是信元到达输入端口的随机过程，另一个是信元目的端口地址分布。信元到达的真实过程随着业务种类的不同而变化，在进行交换结构的信能分析时一般采用随机和突发两种业务模型。随机业务模型是假定信元到达输入端口是一个独立同分布Bernoulli过程，即在任意给定的时隙内，信元到达某一输入端口的概率为p,无信元概率为(1-p),（p也称为输入负荷）。描述突发业务的常用模型是on/off模型，这种模型虽然简单但很流行，而且在分析上可行。该模型由交替的活动期和沉默期组成，活动期内产生信元，沉默期不产生信元。on和off被认为是相互独立的，而且这些时间间隔服从几何分布。信元目的端口地址分布有均匀分布（uniform）、非均匀分布（non-uniform）和组播（multicast）分布三种。当每个时隙到达输入端口的信元导读每个输出端口的概率为1/N时，则称为均匀分布，否则就是非均匀分布。热点业务（hot-spot）就是一种非均匀分布，所谓热点业务就是指每个时隙到达的所有信元总有一个固定概率到达一个热点输出端口。若设h表示到达热点端口的概率，则输入负荷p可表示为p=ph+p(1-h),其中ph为指向热点的信元数，目前对交换结构的分析大都采用上述模型。284.4现有的输入排队调度算法我们将现有的调度算法分为最大(无权重)匹配、最大权重匹配、稳定婚姻匹配和确定型调度算法4类[31].其中最大匹配、最大权重匹配和稳定婚姻匹配都是二分图的匹配算法,而确定型调度算法主要基于矩阵分解。二分图G

匹配M1

w11

1

1

12

w21

w12

2

2

2w323

3

3

3w2NwN3N

N

N

N图4.1

输入排队调度算法的二分图描述除了确定型调度算法以外,其他调度算法都把交换结构看成一个二分图G=[V,E](如图4.1所示),这里顶点集合V可以分为两个子集:(1)左顶点子集V1,其元素v1k表示输入端口k；(2)右顶点子集V2,其元素v2k表示输出端口k。边集E表示从输入到输出端口可能的传输(如从v1i到v2j的边表示有信元从输入i到输出j)。边的权重记为wij,它可以表示队列中是否有信元,队列长度或队列头信元的等待时间等信息。当输入i没有到输出j的信元时,wij=0。根据二分图G的边的权重组成的N×N矩阵称为权重矩阵W=[wij]。我们定义时间片t时权重矩阵W(t)=[wij(t)]。二分图G的匹配定义为边集E的子集M,具有性质:M中没有两条边有公共顶点。因此,如果M是一个匹配,那么每一个左顶点最多与M的一条边关联,类似地,每一个右顶点最多与M的一条边关联。这说明一个二分图的匹配满足交换结构的传输限制条件。最大匹配(maximumsizematching,简称MSM)是指边数达到最大,而最大权重匹配(maximumweightmatching,简称MWM)是指边的权重之和达到最大。由于这两种算法具有复杂度高、硬件实现复杂等缺点,在实际应用中,我们一般用极大匹配(maximal29........................matching)近似最大匹配。所谓的极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数或权重。稳定婚姻匹配根据每个信元的优先级别来调度信元。4.5基于最大匹配的算法我们可以直接用二分图的MSM算法解决调度中的匹配问题。目前已知的渐进复杂性最好的该类算法可以达到O(N2.5)[32]。MSM采用1位的队列占用作为边的权重:当队列中有信元时,相应的边的权重为1;否则为0。仿真实验表明[33],MSM在均匀的独立到达下可以实现100%的吞吐率。但其也具有以下缺点:(1)在容许的非均匀通信量下,可能导致不稳定和不公平;(2)在非容许的通信量下,可能导致饿死;(3)算法实现起来过于复杂且运行时间长。在实际应用中,我们一般用启发式算法来解决二分图的匹配问题。这些算法具有实现简单、运算速度快等优点,但只能实现极大匹配。启发式调度算法要经过多次迭代才能找到极大匹配,每次迭代包括3个步骤。在一个时间片开始时,所有的输入和输出都初始化为未匹配,只有那些直到一次迭代结束都未能完成匹配的输入和输出才能留到下一次迭代。这3个步骤是:(1)请求(request):每个未完成匹配的输入端口向它的队列中信元可能到达的输出端口发送请求信号。(2)响应(grant):一个输出端口可能收到多个输入端口发来的请求信号。每个未完成匹配的输出端口从收到的请求中选择一个输入端口并向其发送响应信号。(3)接受(accept):每个未完成匹配的输入端口可能收到多个输出端口的响应信号。输入端口从响应信号中选择一个输出端口并向其发送接受信号。并行迭代匹配(ParallelIterativeMatching,PIM)PIM[34]是由DEC系统研究中心为16端口，1Gbps的AN2交换机开发的，这个算法是iSLIP算法的基础。PIM算法的随机性避免了某些端口的“资源匮缺”性，并减少收敛30于最大基数匹配的迭代次数。一般地说，这里的最大匹配是小于最大基数匹配的，PIM算法企图快速地用多次迭代收敛于最大匹配，算法分三步但执行起来简单。1)请求:每个未匹配的输入端口向每个未匹配的输出端口发送请求；2)授权:如果某个未匹配的输出端口收到一个或多个请求，它随机地以相同概率选取一个请求，发回授权信息；3)接受:如果一个输入端口收到若干授权信息，它也可等可能地随机地选取其中的一个，接受这个连接。PIM算法的特点:1)每次迭代将完成平均3/4个剩余的待连接边，在平均意义下，迭代次数为O(logN)。2)它保证所有请求将被最终授权，没有输入队列会处于“资源匮缺”状态。3)以往做过的连接不被记录。缺点:1)在高速时执行起来比较困难和昂贵，每个仲裁器必须在许多时变集合中使用随机选择。2)可能导致连接的不公平性。3)在单次迭代中不是很好，其吞吐量接近于63%,略高于FIFO交换。虽然算法在若干次迭代后收敛，收敛次数可影响交换操作的速率。基本循环匹配算法(BasesRoundRobinMatching,B-RRM)RRM算法[35]是迭代循环算法中最简单和最直观的算法，它形成一个循环判定的二维数组，信元在每个输入和每个输出由循环调度。RRM算法的性能不是最好的。RRM算法潜在地克服了PIM算法中的两点不足，复杂性与不公平性，它用循环仲裁器代替PIM中的随机仲裁器，比随机判决快，优先级的轮循使算法均匀地分配带宽，也使请求连接更加公平。对于一个NN交换，算法也分三步:1)请求:每个输入端口向所有可能的目的端口发送请求；2)授权:输出端口收到请求后，采用循环优先级调度方法，选择一个最高优先级的请求授权，输出端口向每一个提出请求的输入端口发回通知，通知各输入端口是否被授权，31优先级指针按照模N增加1,新的位置为所授权的输入端口的下一个位置，即刚刚得到服务的输入端的优先级降为最低；3)接受:输入端口收到授权信息后，同样采用循环调度方法，选择优先级最高的授权，表明接受此项连接。优先级指针按照模N增加1，新的位置为所接受的输出端口的下一个位置。RRM算法有以下特性：特性1最低优先级最先连接。特性2没有连接是资源匮缺。特性3在重负下，具有同一输出端口队列有同样的吞吐量。迭代SLIP算法(iterativeSLIP,iSLIP)iSLIP算法[35,

36]入和输出端口。目的是为了有效、公平、快速地匹配一个输入队列调度器的输入端口和输出端口。在每个时隙，采用多次迭代来选择交叉开关的配置，使输入端口和输出端口尽量达到匹配。iSLIP每一次迭代由三步组成，这里设输入端口和输出端口数都为N：Step1：请求每一输入端口为该端口的非空VOQ发送服务请求至输出端。Step2：授权每一输出端口在收到的请求服务的输入端口中，以循环优先级方式选择最接近输出端指针的输入端口，发送允许服务信息至该输入端口。如果允许服务信息在第3步中被接受，在该输出端口指向最高优先级位置的指针g按模N增加，指向该允许服务的输入端口的下一个位置。Step3：接受每一输入端口在收到允许服务的输出端口中，以循环优先级方式选择最接近输入端指针的输出端口，发送接受服务信息至该输出端口。该输入端口指向最高优先级位置的指针a按模N增加，指向该接受服务的输出端口的下一个位置。指针只在第一次迭代后被更新。iSLIP算法由于去掉了指针的同步而具有较好的性能，并且文献[35]证明只需迭代一步即可在均匀流量下获得100%吞吐率。由于链路速率越来越快，导致留给调32是基于极大匹配的一种迭代算法，利用循环优先级仲裁来调度输是基于极大匹配的一种迭代算法，利用循环优先级仲裁来调度输度决策的时间也越来越短。例如，250G的链路速率，若分组长度为500bits，那么留给调度的时间仅有2ns，显然多步迭代在这种高速场合下是不可行的，因此下文提及的iSLIP算法均指迭代一次的iSLIP算法。我们以图4.2作为一个调度实例,说明iSLIP调度算法在一次迭代中的实际调度过程。图中g2、g4是输出端口2、4的Grant仲裁器,a1是输入端口的Accept仲裁器。开始时,所有的输入端口与输出端口是未建立匹配的。输入1L(1,1)=1

g2L(1,2)=4

4

1输入3

3

2

g4L(3,2)=2L(3,4)=1输入4

4

1L(4,4)=34132

a1图4.2

iSLIP调度算法实例

3

21请求

输入端口1和输入端口3各有一个以上的分组向具有分组队列缓冲的输出端口1、2和4发出请求(request)信号,其它端口亦如此。2授权

由于输出端口仲裁器的指针g2=1、g4=1,输出端口1和2都向输入端口1发出Grant信号。同理,输出端口4向输入端口3发出Grant信号。注意,当Grant信号发出后,按照RRM调度算法,只有在第三步中准许信号被输入端口所接受,在输出端口指向最高优先级位置的指针g1、g2、g4才能得到更新,并按模增加，指向下一个接受Request信号的输出端口位置。3接受

未被匹配的输入端口从Grant信号中选择其一。由于这时a1=1,输入端口接受了输出端口1的grant信号,两端口之间的匹配成功后,指针a1按模增加指向输出端口2,这时已匹配的输出端口指针g1和g4随之更新,指向下一个向输入端口发出33Grant信号的位置。注意,未成功匹配的指针g2不更新。同理,输入指针a1按模增加并指向2。在一次迭代结束后,如果仍有未匹配的请求,将在下次迭代中匹配。例如输入端口1与输出端口2或输入端口3与输出端口2将在下一次建立匹配。4.6竭力服务iSLIP算法(ExhaustiveiSLIP,E-iSLIP)E-iSLIP算法是在采用公平匹配策略的iSLIP算法的基础