大容量交換機(jī)多級(jí)交換結(jié)構(gòu)及其調(diào)度算法的研究和設(shè)計(jì)

摘要隨著因特網(wǎng)和寬帶通信技術(shù)的高速發(fā)展，因特網(wǎng)的信息流量和設(shè)備的數(shù)量以驚人的速度增長(zhǎng)，同時(shí)傳輸技術(shù)的長(zhǎng)足發(fā)展使得傳輸容量大幅度提高。交換機(jī)和路由器是架構(gòu)因特網(wǎng)的主要互連設(shè)備，因而對(duì)交換機(jī)和路由器提出了更高的要求。高速、高性能的交換機(jī)和路由器是實(shí)現(xiàn)高速骨干網(wǎng)并決定其性能的關(guān)鍵所在。本文首先介紹了三級(jí)Clos網(wǎng)絡(luò)的應(yīng)用以及無(wú)阻塞條件，在此基礎(chǔ)上提出了基于三級(jí)Clos網(wǎng)絡(luò)大容量分組交換機(jī)的體系結(jié)構(gòu)，并且分析了交換機(jī)的數(shù)據(jù)流程，輸入控制器和輸出控制器的幀處理，以及集中調(diào)度器的功能結(jié)構(gòu)。本文詳細(xì)討論了集中調(diào)度器的邏輯結(jié)構(gòu)以及分組調(diào)度策略的設(shè)計(jì)。集中調(diào)度器在交換機(jī)設(shè)計(jì)中處于中心位置，是整個(gè)交換機(jī)協(xié)調(diào)工作的關(guān)鍵。本文提出了一種基于幀的雙重匹配調(diào)度策略，該策略分為模塊級(jí)匹配和端口級(jí)匹配兩部分，采用啟發(fā)式并行匹配算法進(jìn)行路由，采用本文根據(jù)iSLIP輸入排隊(duì)調(diào)度算法提出的E-iSLIP算法進(jìn)行調(diào)度。E-iSLIP算法采用竭力服務(wù)策略和優(yōu)先級(jí)概念，可以改善算法在突發(fā)流量下的性能。在這些設(shè)計(jì)思想的指導(dǎo)下，本文對(duì)E-iSLIP算法進(jìn)行了性能仿真，仿真結(jié)果表明，與iSLIP算法相比，E-iSLIP算法在突發(fā)流量下的性能有明顯改善，在均勻流量下是穩(wěn)定的，而且采用了優(yōu)先級(jí)的E-iSLIP算法比未采用優(yōu)先級(jí)之前具有更好的公平性。關(guān)鍵詞：交換機(jī)，Clos網(wǎng)絡(luò)，調(diào)度，iSLIP，突發(fā)流量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獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除文中已經(jīng)標(biāo)明引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果。對(duì)本文的研究做出貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)到，本聲明的法律結(jié)果由本人承擔(dān)。學(xué)位論文作者簽名：日期：

年

月

日學(xué)位論文版權(quán)使用授權(quán)書(shū)本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留并向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)華中科技大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。保密□，在_____年解密后適用本授權(quán)書(shū)。本論文屬于

不保密□。（請(qǐng)?jiān)谝陨戏娇騼?nèi)打“√”）學(xué)位論文作者簽名：

指導(dǎo)教師簽名：日期：

年

月

日

日期：

年

月

日1緒論1.1太比特路由器的產(chǎn)生及其研究進(jìn)展隨著Internet和寬帶通信技術(shù)的飛速發(fā)展，Internet主機(jī)的數(shù)量正以每?jī)赡暝黾?倍的速度增長(zhǎng)，Internet流量正以每3個(gè)月增加1倍的速度增長(zhǎng)。同時(shí)傳輸技術(shù)的長(zhǎng)足發(fā)展使得傳輸容量大幅度提高。目前，提高系統(tǒng)傳輸容量的最佳技術(shù)是密集波分復(fù)用(DWDM:DenseWavelengthDivisionMultiplexing)和超DWDM(Ultra-denseWDM)技術(shù)，該技術(shù)可在單根光纖上實(shí)現(xiàn)多個(gè)信道復(fù)用，對(duì)該技術(shù)的研究取得了很大進(jìn)步。最近，NEC公司發(fā)布了在單根光纖上實(shí)現(xiàn)最大容量10.92Tbit/s(27340Gb/s)的三波帶(S帶、C帶、L帶)超密集波分復(fù)用光中繼傳輸技術(shù)。因而具有幾百根光纖的一個(gè)光纖管道的容量已經(jīng)達(dá)到拍比特級(jí)(petabit，即1015bit)。光纖和光互聯(lián)技術(shù)的進(jìn)步使網(wǎng)絡(luò)帶寬容量擴(kuò)大了10000倍[1]，但僅有傳輸帶寬的增加是不夠的，電子技術(shù)的發(fā)展沒(méi)能跟上光技術(shù)的發(fā)展步伐，交換機(jī)/路由器的帶寬只增加了10倍[1]，不能有效地利用DWDM技術(shù)所創(chuàng)造的巨大原始帶寬。為了使網(wǎng)絡(luò)性能全面提高，需要Internet中的“立交橋”—路由器工作得更快，而傳統(tǒng)的路由器已經(jīng)無(wú)法滿足組建高速骨干網(wǎng)絡(luò)的需求，發(fā)展太比特路由器越來(lái)越受到人們的重視。太比特路由器技術(shù)是一個(gè)很新的研究熱點(diǎn)，因此，目前發(fā)表的研究成果有限，而且大部分發(fā)表在2000年后。最早研究太比特路由器的文獻(xiàn)是Stanford大學(xué)的Dally于1998年發(fā)表的論文[2];，該文的研究成果是第一臺(tái)商用太比特路由器—AviciTSR的理論基礎(chǔ)。國(guó)外研究太比特路由器技術(shù)的單位主要有大學(xué)、路由器產(chǎn)品公司。其中包括:Polytechnic大學(xué)Chao領(lǐng)導(dǎo)的研究小組[3,4]；Washington大學(xué)Turner領(lǐng)導(dǎo)的“TerabitBurstSwitching”項(xiàng)目，是基于光結(jié)構(gòu)的太比特路由器技術(shù)[5];Princeton大學(xué)Wolf領(lǐng)導(dǎo)的研究小組[6];IBM公司的研究小組[7];在Dally教授和McKeown教授領(lǐng)導(dǎo)下，Stanford大學(xué)的“TheOpticalRouter”項(xiàng)目(目標(biāo)是研制出100terabit/s交換容量的路由器)是比較多產(chǎn)的，發(fā)表了較多的研究成果[8-11];另外還有一些文獻(xiàn)，雖然其研究目標(biāo)并不一定針1對(duì)太比特路由器，只要是有關(guān)高速、高性能的交換技術(shù)，都可以將其有益的思想引入到太比特路由器，因?yàn)樘忍芈酚善骷夹g(shù)就是在采用了許多ATM技術(shù)發(fā)展起來(lái)的，所以，研究太比特路由器的單位和專(zhuān)家許多是起步于研究ATM技術(shù)。太比特路由器一般基于電結(jié)構(gòu)、光電混合結(jié)構(gòu)或全光結(jié)構(gòu)，鑒于現(xiàn)在和未來(lái)幾年的光電技術(shù)水平，目前光電混合結(jié)構(gòu)是比較經(jīng)濟(jì)、合理、可行的，如:Stanford大學(xué)的“TheOpticalRouter”項(xiàng)目研制的太比特路由器就是基于光電混合結(jié)構(gòu)。從長(zhǎng)遠(yuǎn)看，全光結(jié)構(gòu)的太比特路由器將是必然的發(fā)展趨勢(shì)。太比特路由器技術(shù)的研究工作近兩年在國(guó)內(nèi)才開(kāi)始。研究單位及學(xué)術(shù)帶頭人包括清華大學(xué)的吳建平教授、解放軍理工大學(xué)鄭少仁教授和中科院沈陽(yáng)計(jì)算所欒貴興教授等。目前國(guó)際上成熟的太比特路由器不是很多，Avici,Nexabit(現(xiàn)已被Lucent公司收購(gòu))和Pluris是在研制太比特路由器方面領(lǐng)先的三家公司。典型的產(chǎn)品有AviciTSR,LucentNX64000和PlurisTNR。此外，Cisco公司、Juniper公司、charlotte等公司都提出了自己的太比特路由器研制計(jì)劃。我國(guó)目前尚沒(méi)有太比特路由器產(chǎn)品，但是，在2002年，國(guó)家863計(jì)劃中提出了建設(shè)“高性能寬帶信息示范網(wǎng)(3Tnet)”的研制計(jì)劃，該高性能寬帶信息示范網(wǎng)(3Tnet)集成了太比特高速光傳輸、太比特智能光網(wǎng)絡(luò)、太比特IP路由器和太比特應(yīng)用支撐環(huán)境。其中的分項(xiàng)研究課題就有:太比特路由器研制計(jì)劃，目前正在由清華大學(xué)為主體實(shí)施攻關(guān)。總體上來(lái)說(shuō)，國(guó)內(nèi)的研究成果還停留在理論階段。太比特路由器向著路由器群集、分布式、可擴(kuò)展方向發(fā)展。串行高速和光交換技術(shù)將在交換陣列中采用，光纖背板將取代電子背板;太比特路由器通過(guò)冗余備用模塊來(lái)提高系統(tǒng)的可靠性;ASIC技術(shù)的普遍使用將大大提高路由的轉(zhuǎn)發(fā)能力，越來(lái)越多地使用基于硬件的交換和分組轉(zhuǎn)發(fā)引擎;接口速率也將會(huì)越來(lái)越高，可直接支持全光網(wǎng)絡(luò)的互連?？傊?，未來(lái)的太比特路由器將會(huì)向著超高速、高帶寬、光纖化、智能安全化和易擴(kuò)展方向發(fā)展。21.2太比特路由器關(guān)鍵技術(shù)的研究現(xiàn)狀太比特路由器交換結(jié)構(gòu)的研究現(xiàn)狀交換結(jié)構(gòu)的應(yīng)用很廣，在交換系統(tǒng)、多處理器系統(tǒng)、交換機(jī)和路由器中都有應(yīng)用。路由器經(jīng)歷了從單處理器到多處理器、從共享總線到交換結(jié)構(gòu)的發(fā)展過(guò)程。交叉開(kāi)關(guān)(crossbar)結(jié)構(gòu)與前幾代的結(jié)構(gòu)相比，其具有易實(shí)現(xiàn)各端口之間的線速無(wú)阻塞互連、能同時(shí)傳輸多個(gè)信元等優(yōu)點(diǎn)，同時(shí)它也較好地解決了IP多播、廣播以及服務(wù)質(zhì)量等問(wèn)題，例如:Stanford大學(xué)研制的TinyTera路由器就是交叉開(kāi)關(guān)結(jié)構(gòu)。因?yàn)檫@些優(yōu)點(diǎn)，傳統(tǒng)路由器和ATM交換機(jī)基本上都采用交叉開(kāi)關(guān)這種結(jié)構(gòu)。但是，由于單級(jí)交換結(jié)構(gòu)(以交叉開(kāi)關(guān)結(jié)構(gòu)為代表)的可擴(kuò)展性差，在太比特路由器中采用多級(jí)交換結(jié)構(gòu)來(lái)提高可擴(kuò)展性是很有必要的。多級(jí)交換結(jié)構(gòu)常見(jiàn)的是Banyan結(jié)構(gòu)，在Banyan結(jié)構(gòu)的基礎(chǔ)又?jǐn)U展出Clos、Benes、Batcher-Banyan等交換結(jié)構(gòu)[12]?，F(xiàn)有的太比特路由器大部分采用多級(jí)交換結(jié)構(gòu)。太比特路由器要求可以支持?jǐn)?shù)百個(gè)端口，這些線卡不可能全部安裝在一個(gè)機(jī)架上，因此就需要一種全新的分布式交換系統(tǒng)，它能夠支持分裝在多個(gè)機(jī)架上的幾百個(gè)線卡，允許線卡與交換單元在物理上分離，使它們工作起來(lái)邏輯上如同一個(gè)完整的路由器。太比特路由器研制的核心問(wèn)題之一是分布式無(wú)阻塞交換體系結(jié)構(gòu)。交換網(wǎng)絡(luò)不僅要支持機(jī)架內(nèi)線卡之間的高速交換，還要支持機(jī)架間的選路與交換。同時(shí)，還要保持各條鏈路之間的流量均衡，以實(shí)現(xiàn)無(wú)阻塞交換。目前，國(guó)外產(chǎn)品機(jī)架間的互連都采用多級(jí)或多維交換結(jié)構(gòu)。這些擴(kuò)展方式以往大多應(yīng)用于巨型計(jì)算機(jī)中。如何采用這種互連結(jié)構(gòu)實(shí)現(xiàn)太比特路由器系統(tǒng)的無(wú)阻塞交換，保證各端口之間數(shù)據(jù)傳輸?shù)墓叫院透麈溌飞狭髁康木庑裕潜仨毠タ说募夹g(shù)難點(diǎn)。目前采用得較多的結(jié)構(gòu)是多維交換結(jié)構(gòu)，例如，在AviciTSR中采用的是三維圓環(huán)面(torus)交換結(jié)構(gòu)。在PlurisTNR中采用的是超立方體(hypercube)結(jié)構(gòu)，采用這種3結(jié)構(gòu)可以提供高吞吐率，同時(shí)可以提供組播、廣播服務(wù)，并保證服務(wù)質(zhì)量。在HyperChipPBR-1280中采用的是多維超立方體結(jié)構(gòu)?，F(xiàn)在的太比特路由器經(jīng)常用交叉開(kāi)關(guān)作為基本元素，按某種拓?fù)浣Y(jié)構(gòu)組成多級(jí)交換結(jié)構(gòu)，構(gòu)成一個(gè)太比特路由器的機(jī)架;又采用多維交換結(jié)構(gòu)(如:超立方體結(jié)構(gòu))在機(jī)架間互連，構(gòu)成完整的太比特路由器。太比特路由器分組調(diào)度策略的研究現(xiàn)狀及發(fā)展趨勢(shì)路由器的內(nèi)部調(diào)度和分組快速處理技術(shù)己經(jīng)成為太比特路由器的核心技術(shù)。如何在太比特路由器內(nèi)部提供更有效的調(diào)度算法就成為了目前網(wǎng)絡(luò)技術(shù)研究領(lǐng)域的一個(gè)熱點(diǎn)。在分布式的路由器體系結(jié)構(gòu)中，為了調(diào)度的需要應(yīng)該采用一定的分組緩沖策略，也稱為分組排隊(duì)策略。一般來(lái)說(shuō)路由器轉(zhuǎn)發(fā)子系統(tǒng)中的隊(duì)列管理按其所處位置可以有三種方式:輸入隊(duì)列(IQ,InputQueue);輸出隊(duì)列(OQ,OutputQueue);組合輸入輸出隊(duì)列(CIOQ,CombinedInputandOutputQueues)。傳統(tǒng)的路由器一般基于輸出排隊(duì)，在這種結(jié)構(gòu)下，到達(dá)輸入端口的信元馬上被交換到相應(yīng)的輸出端口。OQ的優(yōu)點(diǎn)是能夠提供最優(yōu)的吞吐量和延遲控制，其調(diào)度算法在理論上已得到深入的研究，實(shí)現(xiàn)簡(jiǎn)單。但為了保證OQ的正常運(yùn)行，交換結(jié)構(gòu)的內(nèi)部帶寬和輸出隊(duì)列的存儲(chǔ)器訪問(wèn)速率必須是輸入端口鏈路速率的N倍(N是輸入端口數(shù)，如果輸入速率不同，則為端口速率之和)，即要求N倍的加速比，隨著鏈路速率或端口數(shù)的增加，在現(xiàn)有的工藝水平下很難實(shí)現(xiàn)高速的基于OQ的交換結(jié)構(gòu)。為了克服OQ結(jié)構(gòu)的可擴(kuò)展性問(wèn)題，人們又考慮采用輸入排隊(duì)。到達(dá)的信元首先被保存在輸入端口的緩沖區(qū)中，然后通過(guò)調(diào)度算法決定信元何時(shí)通過(guò)交換結(jié)構(gòu)傳送到輸出端口。IQ的優(yōu)點(diǎn)是不需要加速比，但是存在鏈頭阻塞問(wèn)題(HOL,headoflineblocking):如果隊(duì)列鏈頭的信元被阻塞，同隊(duì)列到其他輸出端口的信元就不能被轉(zhuǎn)發(fā)。研究表明，當(dāng)端口數(shù)較多時(shí)，在所有輸出均勻分布的Bernoulli到達(dá)下，IQ只能達(dá)到58.6%的吞吐率[13]。解決輸入排隊(duì)鏈頭阻塞問(wèn)題的一種簡(jiǎn)單方案是虛擬輸出排隊(duì)(VOQ,virtualoutputqueuing)[14]，在這種結(jié)構(gòu)下，每個(gè)輸入端口為每個(gè)輸出設(shè)置一個(gè)隊(duì)列，從4而消除了鏈頭阻塞并保持加速比為1。理論研究和仿真實(shí)驗(yàn)都表明，一個(gè)采用最大權(quán)重匹配調(diào)度算法的VOQ路由器可以到達(dá)100%的吞吐率。但是，VOQ路由器的一個(gè)不足是很難提供QoS(QualityofService)保證，原因在于信元的轉(zhuǎn)發(fā)不僅與輸入端口的通信量有關(guān)，而且受調(diào)度算法的影響。提高VOQ路由器性能的一種方法是利用加速比，這需要在輸入和輸出端口都設(shè)置緩沖區(qū)。這種結(jié)構(gòu)稱為組合輸入/輸出排隊(duì)(CIOQ)。研究表明[14]，加速比為2的CIOQ路由器能夠完全仿真一個(gè)OQ路由器。這樣，可以利用CIOQ繼承OQ的吞吐率和延遲特性。但是，要在CIOQ路由器中實(shí)現(xiàn)QoS保證，關(guān)鍵在于設(shè)計(jì)一個(gè)有效的配置交換結(jié)構(gòu)的調(diào)度算法。如何基于流進(jìn)行支持服務(wù)質(zhì)量的調(diào)度將是調(diào)度算法的進(jìn)一步的研究方向。目前，太比特路由器一般采用輸入排隊(duì)(虛擬輸出排隊(duì))或組合輸入/輸出排隊(duì)結(jié)構(gòu)。高速路由器根據(jù)體系結(jié)構(gòu)的不同可分為集中式和分布式兩種。集中式的優(yōu)點(diǎn)是調(diào)度方案簡(jiǎn)單、易于實(shí)施，但是，很難在一個(gè)短的時(shí)間片內(nèi)實(shí)現(xiàn)調(diào)度。分布式的路由器由多個(gè)并行的帶獨(dú)立調(diào)度器的交換結(jié)構(gòu)組成，一個(gè)負(fù)載平衡算法將每個(gè)輸入端口的信元發(fā)送到某個(gè)交換結(jié)構(gòu)，然后由交換結(jié)構(gòu)決定何時(shí)轉(zhuǎn)發(fā)信元到輸出端口，分布式結(jié)構(gòu)的最大優(yōu)點(diǎn)是降低了交換結(jié)構(gòu)的輸入/輸出鏈路速率，從而增大了時(shí)間片，因此可以使用復(fù)雜的調(diào)度算法?，F(xiàn)有的采用分布式結(jié)構(gòu)的路由器包括ADSA[6]和PPS(parallelpacketswitch)[15]。與PPS相比，ADSA具有算法簡(jiǎn)單和控制信息少的優(yōu)點(diǎn)，但這種分布式結(jié)構(gòu)性能需要在實(shí)際網(wǎng)絡(luò)環(huán)境中做進(jìn)一步的測(cè)試，其負(fù)載平衡算法也需要深入研究。Chang等人最近提出了一個(gè)新穎的實(shí)現(xiàn)較簡(jiǎn)單的負(fù)載平衡兩級(jí)交換結(jié)構(gòu)(LB-BvN,loadbalancedBirkhof-vonNeuman)及其調(diào)度算法[16]，不僅能夠達(dá)到100%的吞吐率及保證延遲限度，而且不需要大于1的加速比和復(fù)雜的調(diào)度算法，可以應(yīng)用于電子交換結(jié)構(gòu)和光交換結(jié)構(gòu)的太比特路由器中。但是該調(diào)度算法的缺點(diǎn)是有可能造成信元失序，雖然Chang等人又提出基于FCFS(firstcomefirstserved)和EDF(earliestdeadlinefirst)的調(diào)度算法[17]，來(lái)解決其信元失序問(wèn)題，但是FCFS要求在第2級(jí)輸入前增加復(fù)雜的抖動(dòng)控制機(jī)制，EDF要從第2級(jí)輸入隊(duì)列中找出時(shí)戳最小的信元，都不容易實(shí)現(xiàn)。5針對(duì)該交換結(jié)構(gòu)，需要人們深入研究，提出較好解決信元失序的調(diào)度算法。未來(lái)的太比特路由器調(diào)度算法首先要適應(yīng)網(wǎng)絡(luò)帶寬的快速增長(zhǎng)，具有良好的可擴(kuò)展性和性能，不能成為網(wǎng)絡(luò)傳輸?shù)钠款i，同時(shí)，在延遲、公平性和服務(wù)類(lèi)型的多樣化等方面也要有較好的保證。1.3本課題的研究目的、意義和本文主要內(nèi)容本文課題的目標(biāo)就是光電混合大容量交換機(jī)研制開(kāi)發(fā)項(xiàng)目的第一階段，即利用線速1Gb/s的1616crossbar交換芯片開(kāi)發(fā)基于多級(jí)交換網(wǎng)絡(luò)的128128Gb/s大容量交換機(jī)。本文研究基于多級(jí)交換網(wǎng)絡(luò)的大容量交換機(jī)的體系結(jié)構(gòu)及分組調(diào)度策略，以及交換機(jī)的輸入排隊(duì)調(diào)度算法。全文組織結(jié)構(gòu)及主要內(nèi)容如下：第一章簡(jiǎn)要介紹太比特路由器的產(chǎn)生及國(guó)內(nèi)外研究現(xiàn)狀，并對(duì)太比特路由器的新功能以及研究現(xiàn)狀進(jìn)行了描述，指出分組調(diào)度策略在太比特路由器研究中的重要意義。第二章提出了基于三級(jí)Clos網(wǎng)絡(luò)的多級(jí)交換機(jī)體系結(jié)構(gòu)，并且對(duì)數(shù)據(jù)流程以及各個(gè)模塊的功能進(jìn)行了介紹。第三章分析了集中調(diào)度器的邏輯結(jié)構(gòu)，提出了一種基于幀的雙重匹配調(diào)度策略，用于解決三級(jí)Clos網(wǎng)絡(luò)的信元調(diào)度和路由分配問(wèn)題。第四章介紹調(diào)度算法的相關(guān)概念以及現(xiàn)有的輸入排隊(duì)調(diào)度算法的調(diào)度規(guī)則，并提出一種采用竭力服務(wù)策略的輸入排隊(duì)調(diào)度算法E-iSLIP算法。第五章對(duì)提出的輸入排隊(duì)調(diào)度算法E-iSLIP進(jìn)行性能仿真及分析。第六章對(duì)本論文進(jìn)行了總結(jié)并探討課題下一步的工作。62多級(jí)交換機(jī)系統(tǒng)結(jié)構(gòu)設(shè)計(jì)2.1前言交換結(jié)構(gòu)的選取對(duì)路由器的性能有很大的影響，由于多級(jí)交換結(jié)構(gòu)良好的擴(kuò)展性，目前的大容量路由器和交換機(jī)多采用基于多級(jí)交換網(wǎng)絡(luò)的交換結(jié)構(gòu)，例如Bayern，Benes，Clos網(wǎng)絡(luò)等都在交換結(jié)構(gòu)設(shè)計(jì)中發(fā)揮了重要作用。本章提出用三級(jí)Clos網(wǎng)絡(luò)構(gòu)造大容量交換機(jī)的方案，首先提出了基于三級(jí)Clos網(wǎng)絡(luò)的多級(jí)交換機(jī)體系結(jié)構(gòu)，然后分別分析了交換機(jī)的數(shù)據(jù)包流程，信元和幀的數(shù)據(jù)格式，輸入控制模塊和輸出控制模塊中的幀處理過(guò)程，以及集中調(diào)度器的邏輯結(jié)構(gòu)。2.2多級(jí)交換機(jī)體系結(jié)構(gòu)網(wǎng)絡(luò)交換背景三級(jí)Clos網(wǎng)絡(luò)[18]是采用基本交換單元來(lái)搭建大型交換結(jié)構(gòu)的最常用的拓?fù)洹los網(wǎng)絡(luò)可以用來(lái)有效實(shí)現(xiàn)低延遲，高帶寬，面向連接的ATM交換。Clos類(lèi)型的交換結(jié)構(gòu)還有經(jīng)濟(jì)和技術(shù)上的吸引力。根據(jù)他們的內(nèi)在容錯(cuò)和多徑路由的特性，是提供可靠的寬帶交換的非常有吸引力的一個(gè)選擇。三級(jí)Clos網(wǎng)絡(luò)由于其模塊化和可擴(kuò)展性被廣泛用于商用多處理器互連網(wǎng)絡(luò)和交換陣列。例如IBMGF-11并行系統(tǒng)Memphis交換機(jī)，NEC的ATOM，Hitachi的超級(jí)分布式交換系統(tǒng)OPTIMA，和TORUS電光混合T比特交換機(jī)----ATMOS光交換機(jī)，Lucent的Atlanta套片，Myrinet的Myrinet-2000系列光纖通道交換機(jī)等等。分組交換三級(jí)Clos網(wǎng)絡(luò)目前流行兩種結(jié)構(gòu)，SSS(Space-Space-Space,S3)結(jié)構(gòu)采用無(wú)緩存的空分交換單元實(shí)現(xiàn)。MSM(Memory-Space-Memory)結(jié)構(gòu)采用第一級(jí)和第三級(jí)為共享緩存單元，第二級(jí)為無(wú)緩存空分交換單元實(shí)現(xiàn)。我們提出的是采用SSS結(jié)構(gòu)的Clos網(wǎng)絡(luò)。7欲將任意一個(gè)輸入單元的輸入端連向任意一個(gè)輸出單元的的輸出端時(shí)，有的多級(jí)互連網(wǎng)絡(luò)會(huì)產(chǎn)生阻塞，有的則不會(huì)產(chǎn)生阻塞。對(duì)于產(chǎn)生阻塞的多級(jí)互連網(wǎng)絡(luò)，有的可以通過(guò)重新調(diào)整現(xiàn)有的連接而避免之，有的則不能。多級(jí)互連網(wǎng)絡(luò)處于阻塞狀態(tài)是指對(duì)于存在空閑的輸入級(jí)輸入端點(diǎn)和輸出級(jí)輸出端點(diǎn)時(shí)，多級(jí)互連網(wǎng)絡(luò)找不到一條空閑的鏈路將它們連接起來(lái)。根據(jù)阻塞情況的不同可以將Clos型多級(jí)互連網(wǎng)絡(luò)細(xì)分為以下三種:(1)嚴(yán)格無(wú)阻塞Clos型多級(jí)互連網(wǎng)絡(luò)是指多級(jí)互連網(wǎng)絡(luò)不管處于什么狀態(tài)，對(duì)于任意的空閑輸入級(jí)輸入端點(diǎn)和輸出級(jí)輸出端點(diǎn)，總存在空閑的鏈路將它們連接起來(lái)。而不需調(diào)整多級(jí)互連網(wǎng)絡(luò)中己建立起來(lái)的連接。(2)廣義無(wú)阻塞Clos型多級(jí)互連網(wǎng)絡(luò)是指多級(jí)互連網(wǎng)絡(luò)中存在發(fā)生阻塞的可能性，但是可以通過(guò)路由控制算法避免阻塞的發(fā)生，且不必重新調(diào)整多級(jí)互連網(wǎng)絡(luò)中已建立起來(lái)的連接。(3)可重排無(wú)阻塞Clos型多級(jí)互連網(wǎng)絡(luò)是指多級(jí)互連網(wǎng)絡(luò)發(fā)生阻塞時(shí)，通過(guò)路由控制算法重新調(diào)整現(xiàn)有的連接,從而在輸入級(jí)輸入端和輸出級(jí)輸出端之間，找到一條空閑的鏈路建立起連接。對(duì)于以上三種不同類(lèi)型的Clos多級(jí)互連網(wǎng)絡(luò)，其體系結(jié)構(gòu)是不同的。在此給出三級(jí)Clos型互連網(wǎng)絡(luò)在各種情況下的無(wú)阻塞的條件:(1)對(duì)三級(jí)Clos網(wǎng)絡(luò)C(m,n,k)，如果m≥2n?1，則此網(wǎng)絡(luò)是嚴(yán)格無(wú)阻塞的，即只要一條連接的起點(diǎn)和終點(diǎn)是空閑的，任意時(shí)刻都可以在交換結(jié)構(gòu)中建立這條連接而不影響網(wǎng)絡(luò)中已經(jīng)建立的連接。(2)如果m≥3n/2，則此多級(jí)互連網(wǎng)絡(luò)是廣義無(wú)阻塞的。(3)如果m≥n，則此網(wǎng)絡(luò)是可重排無(wú)阻塞的，即只要一條連接的起點(diǎn)和終點(diǎn)是空閑的，任意時(shí)刻都可以在交換結(jié)構(gòu)中直接或?qū)σ延械倪B接重選路由來(lái)建立這條連接。以上是適用于電路交換的三級(jí)Clos網(wǎng)絡(luò)的無(wú)阻塞條件。對(duì)于分組交換結(jié)構(gòu)，如果將每個(gè)內(nèi)部信元視為一個(gè)呼叫，以信元為單位進(jìn)行路由選擇。在信元到達(dá)之前建立通路，在信元過(guò)去后釋放該連接，則上述結(jié)論也適用于分組交換的三級(jí)Clos網(wǎng)絡(luò)。由以上的條件可以看出，如果中間級(jí)交換單元的數(shù)量越少，則多級(jí)互連網(wǎng)絡(luò)產(chǎn)生8阻塞的可能性就越大，因此，就越要求優(yōu)良的路由控制算法來(lái)實(shí)現(xiàn)無(wú)阻塞的連接。對(duì)于多級(jí)互連網(wǎng)絡(luò)而言，我們總希望使用最少的交換單元來(lái)實(shí)現(xiàn)連接。這樣可以降低成本。由于在輸入、輸出交換單元數(shù)，和輸入交換單元的輸入端口、輸出交換單元的輸出端口數(shù)在相對(duì)固定的情況下。唯有減少中間交換單元數(shù)來(lái)降低成本。這就意味著必須提高路由控制算法的復(fù)雜度來(lái)避免發(fā)生阻塞。從以上的三種阻塞情況來(lái)看，可重排無(wú)阻塞多級(jí)互連網(wǎng)絡(luò)所需要的中間級(jí)交換單元數(shù)最少，所以我們以下將研究基于三級(jí)可重排無(wú)阻塞Clos型互連網(wǎng)絡(luò)的交換機(jī)體系結(jié)構(gòu)。多級(jí)交換機(jī)系統(tǒng)結(jié)構(gòu)PS請(qǐng)求允許

IPC

幀頭信息SwitchFabric

OPC1Gb/s

LC

VOQ

FA

FD

FIFO

LC

1Gb/sIMCMOM系統(tǒng)時(shí)鐘PS：集中調(diào)度器LC：線卡IPC：輸入控制器

OPC：輸出控制器VOQ：虛擬輸出隊(duì)列FIFO：先入先出隊(duì)列

FD：解幀模塊FA：組幀模塊IM：輸入單元

CM：中間單元OM：輸出單元SwitchFabric：交換結(jié)構(gòu)圖2.1

多級(jí)交換機(jī)系統(tǒng)結(jié)構(gòu)如圖2.1所示是多級(jí)交換機(jī)的系統(tǒng)結(jié)構(gòu)[19-22]，基本模塊包括線卡（linecard），輸入端口控制器（IPC，inputportcontroller），輸出端口控制器（OPC，outputportcontroller），交換結(jié)構(gòu)(switchfabric)，集中調(diào)度器（PS，centralizedpacketscheduler），系統(tǒng)時(shí)鐘分配單元（systemclockdistributionunit）。交換結(jié)構(gòu)是三級(jí)Clos網(wǎng)絡(luò)結(jié)構(gòu)，9................................................由輸入交換單元（IM,inputswitchmodule），中間交換單元（CM，centralswitchmodule），輸出交換單元（OM，outputswitchmodule）組成，每個(gè)交換單元都是crossbar交換芯片。我們假設(shè)交換網(wǎng)絡(luò)規(guī)模為128128(128個(gè)輸入端，128個(gè)輸出端)，交換單元為1616的交換芯片，則根據(jù)可重排無(wú)阻塞條件，IM，CM，OM的數(shù)目分別為8，8，8，若輸入和輸出端口線速為1Gb/s，則可以達(dá)到128Gb/s的交換容量。所有的輸入數(shù)據(jù)包都在線卡中分解成等長(zhǎng)的信元，存在線卡緩存中。所有的信元都在IPC和OPC中緩存，中間的交換結(jié)構(gòu)是無(wú)緩存的。IPC上的虛擬輸出隊(duì)列(VOQ,virtualoutputqueue)和集中調(diào)度器為交換機(jī)提供沖突解決。在輸入端，輸入數(shù)據(jù)包緩存在線卡中，然后被分割成信元并且根據(jù)目的端口存入相應(yīng)的VOQ中，相同目的端口的信元存在同一個(gè)VOQ。IPC上的VOQ作為線卡上VOQ緩存結(jié)構(gòu)的“鏡像”，只要能保持信元在線卡和IPC之間的流動(dòng)，IPC上的VOQ相比線卡上對(duì)應(yīng)的“鏡像”VOQ就可以小得多。在信元發(fā)送給目的端口線卡之前，OPC中的緩存用來(lái)存儲(chǔ)這些信元。在輸出端口線卡中有虛擬輸入隊(duì)列（VIQ，virtualinputqueue）用來(lái)緩存從交換結(jié)構(gòu)傳來(lái)的信元，把它們重組成數(shù)據(jù)包。集中調(diào)度器幀載荷

幀頭

交換網(wǎng)絡(luò)輸入信元

r

組幀

幀頭

幀

r解幀

FIFO

輸出信元VOQ輸入控制器

k

m

k

輸出控制器圖2.2

數(shù)據(jù)流程圖圖2.2表示了數(shù)據(jù)是如何流經(jīng)系統(tǒng)的。在輸入端口線卡中，不定長(zhǎng)的數(shù)據(jù)包被分割成定長(zhǎng)為64B的信元（包括信元頭開(kāi)銷(xiāo)），然后把信元從線卡發(fā)給IPC，在IPC中，每一個(gè)VOQ都采用并行緩存結(jié)構(gòu)，使得每次同時(shí)可以讀取r個(gè)信元。這r個(gè)信元在IPC里面的組幀模塊中組成一幀。當(dāng)線卡端口速率為1Gb/s時(shí)，一個(gè)信元時(shí)隙為T(mén)=10512ns，假設(shè)r=8，則每一幀的周期為f=rT=4096ns。在交換網(wǎng)絡(luò)的每一級(jí)，相應(yīng)的幀頭被提取出來(lái)進(jìn)行處理，控制交換單元。由于集中調(diào)度器已經(jīng)解決了競(jìng)爭(zhēng)沖突，在交換網(wǎng)絡(luò)的每一級(jí)，通過(guò)選擇交換單元相應(yīng)的輸出鏈路，數(shù)據(jù)幀可以找到一條合適的路徑通過(guò)交換網(wǎng)絡(luò)。當(dāng)幀到達(dá)目標(biāo)OPC后，通過(guò)OPC解幀模塊，幀被分解成相應(yīng)的r個(gè)信元，然后OPC把信元發(fā)給線卡。載荷

圖2.3

入端口出端口數(shù)據(jù)結(jié)構(gòu)圖

有效位圖2.3描述了在交換每一級(jí)的數(shù)據(jù)結(jié)構(gòu)。每一個(gè)輸入信元的載荷前面都包含兩個(gè)頭部域，OL表示信元的輸出端口號(hào)，IL表示信元的輸入端口號(hào)。信元頭部的有效位表示信元是否有效。如果是NN的三級(jí)Clos交換網(wǎng)絡(luò)C(m,n,k)，則信元頭部長(zhǎng)度為1+log2N+log2Nbits，N=128，則信元頭部大小為15bits。幀的頭部域包含CM號(hào)，OM號(hào)，輸出端口號(hào)，有效位四部分，幀的頭部長(zhǎng)度為1+log2k+log2m+log2nbits，因?yàn)閙=n=k=8，所以幀的頭部長(zhǎng)度為10bits。有效位表示幀是否包含有效信元。圖2.4描述了信元如何經(jīng)過(guò)IPC。數(shù)據(jù)包A來(lái)自輸入端口1，要到目的端口1。在到達(dá)IPC之前，A已經(jīng)被分割成定長(zhǎng)的信元，存在相應(yīng)的線卡中。在這個(gè)例子里，A被分解成16個(gè)信元（A0到A15），所有的信元都以輪轉(zhuǎn)方式存在r(r=8)個(gè)幀緩存中。11FM1A8

A0

1N選擇器A15

A8

A7

A0

A11

FM4

A3

1

TA8

TA0

組幀

F2

F1NA15

A7FM8

F2

F1A15

A7

1N

IPC圖2.4

IPC中的幀處理信元到達(dá)IPC中的幀緩存，立即發(fā)送請(qǐng)求信號(hào)給集中調(diào)度器。若是128128的交換規(guī)模，則每個(gè)IPC在每個(gè)時(shí)隙發(fā)送給集中調(diào)度器的信息為2log2128=14bits。設(shè)集中調(diào)度器與IPC的通信總線位寬為20bits，頻率62.5MHZ，則發(fā)送14bits信息大約需要15ns，發(fā)送128個(gè)端口的請(qǐng)求信息約需要3個(gè)信元周期T。調(diào)度器返回給IPC組幀模塊的幀頭信息為10bits，通過(guò)總線傳送約需要15ns，發(fā)送給128個(gè)端口同樣需要3個(gè)信元周期T，因?yàn)槲覀兊恼{(diào)度方式是基于幀調(diào)度，每一幀有8個(gè)信元，所以總共留給調(diào)度器的調(diào)度時(shí)間為2個(gè)T，即1024ns。集中調(diào)度器采用基于幀的雙重匹配策略進(jìn)行調(diào)度，再把允許信號(hào)返回給允許發(fā)送的IPC，A0到A7組成第一幀，A8到A15組成第二幀。圖2.5描述了數(shù)據(jù)幀如何在OPC中進(jìn)行處理以及在線卡中如何將信元重組成數(shù)據(jù)包。幀首先在解幀模塊被拆成信元，然后根據(jù)信元頭，在第一個(gè)幀周期，A0到A7進(jìn)入OPC緩存中的8個(gè)FIFOs，在第二個(gè)幀周期，A8到A15進(jìn)入相同的8個(gè)FIFOs。然后將這些信元從FIFO中讀到線卡。線卡中的VIQ將信元重組成數(shù)據(jù)包A。12....................................選擇器F2

F1

解幀

TA8

TA0

FIFOsA8A0A11A3

A15...A8線卡1

包A

A7...A0A15F2

A7F1

A15

A7OPC1圖2.5

OPC中的幀處理為了保持時(shí)鐘同步，一個(gè)系統(tǒng)幀時(shí)鐘將提供給系統(tǒng)的各個(gè)模塊。每一個(gè)交換動(dòng)作，包括讀寫(xiě)緩存，拆組數(shù)據(jù)幀，都要根據(jù)相同的幀時(shí)鐘信號(hào)同步。還有一個(gè)基準(zhǔn)時(shí)鐘用來(lái)進(jìn)行比特同步，該時(shí)鐘頻率1GHZ。集中調(diào)度器的結(jié)構(gòu)如圖2.6所示，它由k個(gè)SIMs和k個(gè)SOMs組成，每一個(gè)對(duì)應(yīng)于三級(jí)Clos網(wǎng)絡(luò)相應(yīng)的IM和OM。每一個(gè)SIM都有n個(gè)輸入端口仲裁器（IPAs），有n個(gè)虛擬輸出端口仲裁器（VOPAs），每個(gè)虛擬輸出端口仲裁器對(duì)應(yīng)于相應(yīng)的OM的一個(gè)輸出端口。每一個(gè)SIM有一個(gè)輸入模塊仲裁器（IMA），每一個(gè)SOM有一個(gè)輸出模塊仲裁器（OMA）。一個(gè)可重新匹配的crosspoint交換芯片用來(lái)連接這些SIMs和SOMs。每一個(gè)輸入線卡（ILC）有N個(gè)VOQs，每一個(gè)VOQ對(duì)應(yīng)于一個(gè)輸出端口。一個(gè)計(jì)數(shù)器C(i,j)用來(lái)記錄相應(yīng)的VOQ(i,j)的信元數(shù)目。13............SIM1線卡1

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

IPA(1,1)

VOPA(1,1)

Crosspoint交換片

SOM1信元到達(dá)信息

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信元到達(dá)信息

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

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

IPA(k,n)

IMAkVOPA(k,n)

OMAkSIM：輸入單元調(diào)度模塊SOM：輸出單元調(diào)度模塊C(i,j)：計(jì)數(shù)器

OMA：輸出單元仲裁器IPA：輸入端口仲裁器IMA：輸入單元仲裁器VOPA：虛擬輸出端口仲裁器圖2.6

調(diào)度器結(jié)構(gòu)圖在每一次匹配循環(huán)的開(kāi)始，每一個(gè)SOM發(fā)送m+2nbits信息給相應(yīng)的SIM，其中mbits表示對(duì)應(yīng)OM的m條輸入鏈路的狀態(tài)，2nbits表示對(duì)應(yīng)OM的n個(gè)輸出端口的狀態(tài)。每一個(gè)輸出端口有四種可能的狀態(tài)：00表示輸出端口未占用，01表示輸出端口在上一幀的周期里占用，占用優(yōu)先級(jí)為低。10表示輸出端口在上一幀的周期里占用，占用優(yōu)先級(jí)為高。11表示輸出端口在這個(gè)幀周期里已經(jīng)占用。假定SIMs和SOMs的匹配序列已經(jīng)決定，例如，在一個(gè)循環(huán)里，SIMi與SOMj匹配，則在下一個(gè)循環(huán)里面，SIMi與SOM(j+1)匹配，這個(gè)過(guò)程重復(fù)k次。為了讓所有SIMs均勻匹配，在每一個(gè)幀周期的開(kāi)始，SIMs和SOMs的匹配序列要移動(dòng)一個(gè)位置。14................................................2.3本章小結(jié)本章首先介紹了三級(jí)Clos網(wǎng)絡(luò)在大容量交換機(jī)市場(chǎng)的背景以及技術(shù)優(yōu)勢(shì)，以及Clos網(wǎng)絡(luò)的各種無(wú)阻塞條件。然后，我們提出了一種基于三級(jí)Clos網(wǎng)絡(luò)的多級(jí)交換機(jī)體系結(jié)構(gòu)，該交換機(jī)總體上可分為線卡，IPC，OPC，集中調(diào)度器，交換網(wǎng)絡(luò)，系統(tǒng)時(shí)鐘分配單元幾部分。線卡負(fù)責(zé)接收從物理層來(lái)的數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行處理，把數(shù)據(jù)包分解成等長(zhǎng)的信元發(fā)送給IPC，IPC中的VOQ先存儲(chǔ)待發(fā)送的信元，在等到允許信號(hào)之后，將信元發(fā)送給IPC中的組幀模塊，組幀模塊再把得到允許的信元加上調(diào)度器發(fā)送過(guò)來(lái)的幀頭信息，組成數(shù)據(jù)幀，傳送到交換網(wǎng)絡(luò)。交換網(wǎng)絡(luò)為128128的Clos網(wǎng)絡(luò)，需要24片1616的crossbar交換芯片搭建而成，整個(gè)網(wǎng)絡(luò)是可重排無(wú)阻塞網(wǎng)絡(luò)。我們還提出了信元和幀的數(shù)據(jù)結(jié)構(gòu)，介紹了IPC，OPC的數(shù)據(jù)處理流程，并且分析了調(diào)度時(shí)間要求。信元的沖突和選路問(wèn)題由集中調(diào)度器和IPC解決，集中調(diào)度器采用分布式的Clos網(wǎng)絡(luò)調(diào)度策略，同時(shí)進(jìn)行端口的匹配和路由選擇，具體的調(diào)度策略將在后一章介紹。153多級(jí)調(diào)度策略設(shè)計(jì)3.1前言上一章提出了三級(jí)Clos網(wǎng)絡(luò)交換機(jī)的邏輯結(jié)構(gòu)，其中分組調(diào)度器的設(shè)計(jì)處于核心位置，它負(fù)責(zé)與線卡和交換網(wǎng)絡(luò)通信，控制信元的發(fā)送和路徑，配置交換網(wǎng)絡(luò)，實(shí)現(xiàn)信元的可重排無(wú)阻塞傳輸。在本章里，我們首先介紹了多級(jí)調(diào)度策略的背景，然后提出一種分組調(diào)度器的邏輯結(jié)構(gòu)，接著提出了一種基于幀的雙重匹配調(diào)度策略，該策略分為模塊級(jí)匹配和端口級(jí)匹配兩部分，處理Clos網(wǎng)絡(luò)中的信元調(diào)度和路由分配問(wèn)題。3.2多級(jí)調(diào)度策略背景Clos網(wǎng)絡(luò)的調(diào)度可以分解為兩個(gè)問(wèn)題：信元調(diào)度和路由分配。前者為一個(gè)輸入信元決定相應(yīng)的輸出端口，后者為一對(duì)輸入輸出匹配端口尋找內(nèi)部無(wú)沖突的路徑。尋找一種高吞吐量，低延遲，公平，易實(shí)現(xiàn)的三級(jí)無(wú)緩存Clos調(diào)度算法是一個(gè)很大的挑戰(zhàn)。而且調(diào)度算法必須具有很好的擴(kuò)展性，因?yàn)殡S著交換容量和端口線速的增加，調(diào)度方案的仲裁時(shí)間要求越來(lái)越嚴(yán)格。在文獻(xiàn)[23]中作者提出了一種路徑交換策略，在這種策略中，根據(jù)相應(yīng)的負(fù)載模式，在信元到達(dá)之前，預(yù)先進(jìn)行IM與OM之間的路由分配。根據(jù)預(yù)先分配好的路由，當(dāng)信元相應(yīng)的IM和OM之間有空閑的路由時(shí)，就可以把信元發(fā)送出去。然而路徑交換策略假設(shè)了負(fù)載模式是已知的，但是Internet的流量大部分是面向無(wú)連接的。在文獻(xiàn)[24]中作者提出了一種分布式靜態(tài)round-robin調(diào)度算法，通過(guò)round-robin的方式路由信元。然而，由于這種算法的靜態(tài)特性，這種算法不能解決不同流量下的問(wèn)題。最近，一類(lèi)新式的Clos網(wǎng)絡(luò)匹配算法(MAC)被提出來(lái)[20,21]，以有效的調(diào)度決策三級(jí)無(wú)緩存Clos網(wǎng)絡(luò)的交換問(wèn)題。為了緩解嚴(yán)格的仲裁時(shí)間限制，MAC基于幀進(jìn)行操作，每一幀由固定長(zhǎng)度個(gè)信元組成。由于分布式的處理，輸入輸出匹配和路由選擇是同時(shí)在調(diào)度模塊里進(jìn)行的，MAC可以提供良好的性能指標(biāo)而且具有很好的擴(kuò)展性。然而這種方式的時(shí)間復(fù)雜度太高，使得幀的尺寸比較大。163.3分組調(diào)度器的設(shè)計(jì)分組調(diào)度器在基于多級(jí)交換結(jié)構(gòu)的交換機(jī)中非常重要，它負(fù)責(zé)與線卡和交換網(wǎng)絡(luò)進(jìn)行通信，根據(jù)線卡發(fā)送的信元到達(dá)信息進(jìn)行調(diào)度和路由分配，并且配置交換網(wǎng)絡(luò)的狀態(tài)。然后把匹配結(jié)果返回線卡，線卡收到匹配結(jié)果后，立即把信元從配置好的交換網(wǎng)絡(luò)傳送到輸出端口，交換網(wǎng)絡(luò)的狀態(tài)在一幀的發(fā)送時(shí)間內(nèi)保持不變。調(diào)度器邏輯結(jié)構(gòu)如圖3.1所示，分組調(diào)度器由k個(gè)輸入調(diào)度模塊(SIM)，k個(gè)輸出調(diào)度模塊(SOM)組成，每一個(gè)都對(duì)應(yīng)于三級(jí)Clos網(wǎng)絡(luò)相應(yīng)的輸入或者輸出單元。一個(gè)可重置的crosspoint交換結(jié)構(gòu)被用來(lái)互連這些SIMs和SOMs，使它們可以相互交換信息，從而分布式的計(jì)算端口間匹配和路由分配問(wèn)題。SIM1SIMk

圖3.1

分組調(diào)度器

SOM1SOMk由于具有很高的線速和交換容量，為緩解嚴(yán)格的仲裁時(shí)間限制，我們對(duì)每一幀進(jìn)行調(diào)度，設(shè)一幀由r個(gè)信元組成，每個(gè)信元的傳送時(shí)隙為T(mén)，則發(fā)送一幀需要rT的時(shí)間。所有輸入某個(gè)線卡的分組被分解成定長(zhǎng)的信元，目的端口相同的數(shù)據(jù)包存在相同的虛擬輸出隊(duì)列(VOQ)里，在一個(gè)VOQ中的某幀，一旦獲得分組調(diào)度器(PS)發(fā)送的grant信號(hào)，就被傳送到目的端口。在傳送每一幀時(shí)，交換結(jié)構(gòu)保持交換狀態(tài)不變一直到該幀傳送完畢，且允許在該幀傳送完之后改變交換狀態(tài)。幀的大小r事先由預(yù)計(jì)調(diào)度仲裁時(shí)間，從線卡到分組調(diào)度器的數(shù)據(jù)往返時(shí)間，以及交換結(jié)構(gòu)的重新配置時(shí)間共同決定。17........................調(diào)度方案輸出端口10000圖3.2

000000010010000000100000001000端口匹配矩陣信元調(diào)度問(wèn)題可以歸類(lèi)為二分圖匹配問(wèn)題(端口到端口)，而路由選擇可以歸類(lèi)為二分圖染色問(wèn)題（模塊到模塊）。二分圖匹配問(wèn)題我們?cè)谙乱徽聦⒃敿?xì)分析，下面我們先分析路由選擇問(wèn)題。OMIM圖3.3

2111IM-OM連接矩陣給定一組輸入輸出端口匹配，在三級(jí)無(wú)緩存Clos網(wǎng)絡(luò)中的路由分配問(wèn)題可以用相應(yīng)的輸入輸出單元的二分圖染色問(wèn)題來(lái)描述。假設(shè)每個(gè)交換單元是33的交換單元(n=3)，輸入和輸出單元數(shù)k為2，中間單元數(shù)m為3。假設(shè)如圖3.2所示的匹配矩陣代表找到的交換機(jī)端口間匹配，如果輸入端口g和輸出端口h匹配則矩陣的元素(g,h)為1，沒(méi)有匹配則為0。如圖3.3所示，這個(gè)端口匹配矩陣可以轉(zhuǎn)換成一個(gè)IM-OM連接矩陣，矩陣元素(i,j)代表從IMi到OMj的信元可以選擇的中間單元數(shù)目。注意到IM-OM連接矩陣的任意行元素之和，任意列元素之和都不能大于n。如圖3.4所示，IM-OM連接矩陣邏輯上等效于一個(gè)二分圖。18輸入端口0輸入端口0藍(lán)綠紅圖3.4

紅藍(lán)二分圖染色假設(shè)每個(gè)CM用不同的顏色來(lái)標(biāo)示，例如，CM1用藍(lán)色標(biāo)示，CM2綠色，CM3紅色。給指定的輸入輸出端口匹配尋找中間單元等效于給相應(yīng)的IM-OM二分圖邊沿染色，染色的規(guī)則是，任意有共同端點(diǎn)的兩條邊不能用同一種顏色。圖3.4給出了一個(gè)IM-OM二分圖邊沿染色方案。圖3.5表示相應(yīng)的路由分配。IM1

藍(lán)綠

CM1

OM1CM2IM2

紅

綠圖3.5

CM3路由分配

OM2每一個(gè)CM的連接都是一對(duì)IM-OM匹配，因此，路由分配問(wèn)題也可以看作從IM-OM的二分圖中尋找m個(gè)（CM的單元數(shù)）匹配。換句話說(shuō)，就是把IM-OM連接矩陣分解m個(gè)IM-OM匹配矩陣，如圖3.6所示。在每一個(gè)IM-OM匹配矩陣中，任意行和或者列和是1或者0。在m=n的情況，就是可重排無(wú)阻塞的情況下，有許多路由分配算法可以應(yīng)用于Clos網(wǎng)絡(luò)，它們可以分為兩類(lèi)：一類(lèi)是最優(yōu)算法，可以提供有保證的匹配結(jié)果，但是時(shí)間復(fù)雜度高[25]，實(shí)現(xiàn)性差[26]。另一類(lèi)是啟發(fā)式算法[27]，例如并行匹配算法，可以保證全部或者大部分路由匹配，而且時(shí)間復(fù)雜度低。19矩陣分解2111

10100101＋00＋10圖3.6

矩陣分解這里簡(jiǎn)單介紹一下并行匹配算法如何用來(lái)進(jìn)行路由分配。首先把每一個(gè)IM的輸出鏈路用Ai來(lái)表示(1≤i≤k)，每一個(gè)OM的輸入鏈路用Bj表示(1≤j≤k)，如圖3.7所示，每一個(gè)Ai和Bj包含了m個(gè)元素，這些元素表示每一條物理鏈路的狀態(tài)，Ai={ai,h,1≤h≤m},Bj={bj,h,1≤h≤m}。ai,h(bj,h)=0表示這條鏈路沒(méi)有被占用，否則ai,h(bj,h)=1。要找到一條在IM和OM的路徑，只需要在Ai和Bj之中找到一對(duì)垂直的0，例如，圖4.7表示在Ai和Bj之間有兩條有效路徑。1

2

3

m-1

mAiBj

11

01

00

11

......

11

00

11匹配圖3.7

并行匹配算法

匹配我們根據(jù)提出的兩級(jí)匹配算法[28]，提出了一種基于幀[29]的Clos網(wǎng)絡(luò)調(diào)度方案。該Clos網(wǎng)絡(luò)調(diào)度方案由兩級(jí)匹配組成：模塊級(jí)(module-level)和端口級(jí)(port-level)，圖3.8和圖3.13分別指出了模塊級(jí)匹配和端口級(jí)匹配的任務(wù)。20圖3.8

模塊級(jí)匹配任務(wù)圖在模塊級(jí)，我們根據(jù)輸入隊(duì)列的狀態(tài)決定SIM-SOM的匹配模式。在端口級(jí)，負(fù)責(zé)找到匹配的端口并且為相匹配的端口決定內(nèi)部路徑。對(duì)每一幀，模塊級(jí)匹配決定k'(k'k)對(duì)SIM-SOM的匹配，只有相應(yīng)的IM-OM單元端口才能在端口級(jí)參與匹配。在模塊級(jí)，可以同時(shí)處理F個(gè)幀的交換，F(xiàn)個(gè)幀組成一個(gè)超幀(Superframe)，在每一次的模塊匹配中同時(shí)決定F個(gè)幀也就是一個(gè)超幀的交換模式。模塊級(jí)匹配由兩步組成：超幀匹配和超幀分解。超幀匹配就是要根據(jù)交換機(jī)的輸入隊(duì)列狀態(tài)決定一個(gè)超幀矩陣。如圖3.9所示，超幀匹配的步驟如下：首先計(jì)算出流量矩陣，流量矩陣的元素t(i,j)表示要從IMi到OMj的緩存信元的數(shù)目，根據(jù)流量矩陣可以得到請(qǐng)求矩陣，請(qǐng)求矩陣的元素r(i,j)表示能從SIMi傳送到SOMj的請(qǐng)求數(shù)目。然后我們采用EiSLIP算法來(lái)仲裁請(qǐng)求矩陣，從而得到超幀矩陣，超幀矩陣的每一元素代表相應(yīng)的SIM和SOM間的匹配機(jī)會(huì)。1672

111212010115678

421

131302332222

211

121302132112流量矩陣

圖3.9

請(qǐng)求矩陣計(jì)算超幀矩陣

超幀矩陣如圖3.10所示，超幀矩陣分解采用啟發(fā)式并行匹配算法來(lái)實(shí)現(xiàn)，把每個(gè)超幀矩陣2124112411分解成Fk'個(gè)模塊匹配矩陣，每個(gè)模塊匹配矩陣記錄下SIM-SOM的匹配狀態(tài)，到此模塊級(jí)匹配完成。一幀內(nèi)的k`個(gè)匹配循環(huán)211

121302132112

010

010100000001

001

100001010000

...

100

000100010001超幀矩陣

圖3.10

模塊匹配矩陣超幀矩陣分解當(dāng)模塊級(jí)匹配完成之后，下一個(gè)超幀的SIMs和SOMs之間的匹配次序(記錄在模塊匹配矩陣)就決定了，模塊匹配矩陣與SIM-SOM的對(duì)應(yīng)關(guān)系如圖3.11所示。端口級(jí)匹配算法由k'次循環(huán)組成，在一個(gè)幀時(shí)隙之內(nèi)完成，每一次循環(huán)都對(duì)應(yīng)于相應(yīng)的模塊匹配矩陣。在端口級(jí)匹配，也分為兩步：端口匹配和中間單元(CM)分配。221001000SIM1

SOM1010

010100000001

SIM2SIM3

SOM2SOM3模塊匹配矩陣1SIM4SIM1

SOM4SOM1001

100001010000

SIM2SIM3

SOM2SOM3模塊匹配矩陣2SIM4

SOM412

圖3.11

模塊匹配矩陣與SIM-SOM對(duì)應(yīng)關(guān)系

53

IM1

OM2

7411OM3

12圖3.12

端口匹配例示在端口匹配時(shí)，為找到相應(yīng)IM-OM的匹配端口，我們采用EiSLIP算法。例如，當(dāng)根據(jù)模塊匹配矩陣，SIMi與SOMj在一個(gè)匹配循環(huán)中匹配，則在這個(gè)匹配循環(huán)的開(kāi)230000始，SOMj首先發(fā)送端口可用信息到SIMi，然后SIMi執(zhí)行EiSLIP算法進(jìn)行匹配。圖3.12為一次端口匹配的例示。為了提高匹配效率和帶寬利用率，同時(shí)在SIM中引入優(yōu)先級(jí)仲裁器，在優(yōu)先級(jí)策略下，那些超過(guò)r個(gè)信元的VOQ的優(yōu)先級(jí)高于那些未滿r個(gè)信元的VOQ。因此，如果相應(yīng)的VOQ的隊(duì)列長(zhǎng)度小于r，那些正處于匹配狀態(tài)的輸入輸出端口可能失去匹配。另外，為了避免不公平性，設(shè)定當(dāng)隊(duì)列頭HOL(HeadofLine)幀的等待時(shí)間超過(guò)一個(gè)門(mén)限值之后，該幀的優(yōu)先級(jí)上升為最高。端口級(jí)匹配圖3.13

端口級(jí)匹配任務(wù)圖當(dāng)端口匹配完成之后，必須為信元的路由選擇合適的中間級(jí)(CM),我們同樣采用前述在超幀分解中用到的啟發(fā)式并行匹配算法來(lái)完成CM分配。圖3.13為端口級(jí)匹配的任務(wù)圖。模塊級(jí)匹配和端口級(jí)匹配可以用流水線[30]的方式執(zhí)行，如圖3.14所示。每一個(gè)超幀由F幀組成，每一幀由r個(gè)信元組成。設(shè)每一幀的匹配循環(huán)次數(shù)為k',k'k。r個(gè)信元的傳輸時(shí)間必須大于等于k'個(gè)匹配循環(huán)的匹配時(shí)間，所以r不能取很小。在每一個(gè)超幀總共有Fk'個(gè)匹配循環(huán)，因此當(dāng)前超幀進(jìn)行端口級(jí)匹配時(shí)，下一個(gè)超幀同時(shí)進(jìn)行模塊級(jí)匹配，以決定F組每組k'個(gè)模塊匹配矩陣。24模塊級(jí)匹配

超幀匹配

超幀

超幀矩陣分解

超幀端口級(jí)匹配

幀1

...

幀x

...

幀F(xiàn)k`個(gè)匹配循環(huán)數(shù)據(jù)傳輸

幀幀(r個(gè)信元)傳輸

……

幀圖3.14

流水線匹配方式3.4本章小結(jié)本章首先介紹了幾種常見(jiàn)的三級(jí)Clos網(wǎng)絡(luò)調(diào)度策略，并且分析它們的優(yōu)缺點(diǎn)。然后提出了一種分組調(diào)度器邏輯結(jié)構(gòu)，該結(jié)構(gòu)分為SIM，SOM，一個(gè)可重置的Crosspoint交換結(jié)構(gòu)三部分，其中SIM，SOM對(duì)應(yīng)于相應(yīng)的輸入輸出單元IM，OM，Crosspoint結(jié)構(gòu)負(fù)責(zé)SIM，SOM的信息交互。隨后，我們分析了Clos網(wǎng)絡(luò)調(diào)度存在的信元調(diào)度和路由分配問(wèn)題，這兩種問(wèn)題可以分別等效于二分圖的匹配和二分圖的染色問(wèn)題。在分析了二分圖染色問(wèn)題以及啟發(fā)式并行匹配算法之后，我們提出了一種基于幀的雙重匹配策略，該策略對(duì)每一幀進(jìn)行調(diào)度，一幀由固定數(shù)目的信元組成。分為兩步進(jìn)行調(diào)度，模塊級(jí)匹配和端口級(jí)匹配。模塊級(jí)匹配由超幀匹配和超幀分解兩步組成。而端口級(jí)匹配又由端口匹配和CM分配兩步組成。其中，超幀匹配和端口匹配需要用到后面一章我們提出的E-iSLIP算法，而超幀分解和CM分配要用到啟發(fā)式并行匹配算法。模塊級(jí)匹配的結(jié)果決定相應(yīng)的IM-OM單元參與端口級(jí)匹配。該匹配策略可以采用流水線方式執(zhí)行。254輸入排隊(duì)調(diào)度算法設(shè)計(jì)4.1前言高速路由器一般采用基于定長(zhǎng)信元的交換結(jié)構(gòu)，其擴(kuò)展性和性能分別受排隊(duì)策略和調(diào)度算法的影響?；谳斎肱抨?duì)策略的路由器具有良好的可擴(kuò)展性，但需要有一個(gè)好的調(diào)度算法支持，才能保證吞吐率和延遲等性能。本章將首先介紹調(diào)度算法的基本概念以及性能指標(biāo)，然后討論輸入排隊(duì)調(diào)度算法，重點(diǎn)放在實(shí)際應(yīng)用廣泛的極大匹配類(lèi)算法，對(duì)每一種算法，從技術(shù)特點(diǎn)和性能指標(biāo)兩個(gè)方面進(jìn)行比較和分析。最后提出了一種采用竭力服務(wù)策略和優(yōu)先權(quán)的基于iSLIP的新算法，該算法能夠改善突發(fā)流量下的信元延遲性能。4.2調(diào)度算法調(diào)度算法是一系列規(guī)則，它按照一定的服務(wù)規(guī)則對(duì)交換節(jié)點(diǎn)的不同輸入業(yè)務(wù)流分別進(jìn)行調(diào)度和服務(wù)，使所有輸入業(yè)務(wù)流能夠按照預(yù)定的方式傳輸?shù)较乱还?jié)點(diǎn)?，F(xiàn)有的調(diào)度算法有很多種，可以根據(jù)不同的分類(lèi)標(biāo)準(zhǔn)進(jìn)行劃分。按服務(wù)規(guī)則分類(lèi)，隊(duì)列調(diào)度算法可以分為：先到先服務(wù)、循環(huán)調(diào)度、處理機(jī)共享、優(yōu)先級(jí)服務(wù)、隨機(jī)服務(wù)等。根據(jù)調(diào)度算法的調(diào)度目標(biāo)分類(lèi)，調(diào)度算法可以分為基于時(shí)延的和基于速率的。根據(jù)通信網(wǎng)絡(luò)環(huán)境，又可分為無(wú)線環(huán)境下的隊(duì)列調(diào)度和有線環(huán)境下的隊(duì)列調(diào)度。根據(jù)調(diào)度算法的工作狀態(tài)，還可以分為工作保持和分工作保持的。調(diào)度算法性能指標(biāo)主要涉及吞吐量、信元延遲、時(shí)延抖動(dòng)、復(fù)雜性和可擴(kuò)展性幾個(gè)方面。吞吐量是指單位時(shí)間內(nèi)路由器轉(zhuǎn)發(fā)的信元數(shù)量。延遲是指信元從到達(dá)路由器到離開(kāi)所經(jīng)歷的時(shí)間。我們說(shuō)一個(gè)路由器是穩(wěn)定的，是指輸入隊(duì)列長(zhǎng)度的期望值不能無(wú)限增長(zhǎng)，如果一個(gè)路由器在所有獨(dú)立的和可允許的到達(dá)下都是穩(wěn)定的，我們說(shuō)這個(gè)路由器能夠達(dá)到100%的吞吐量。在高速網(wǎng)絡(luò)中，傳輸一個(gè)信元的時(shí)間很短，所以調(diào)度算法必須在短時(shí)間內(nèi)完成對(duì)信元的調(diào)度，這就要求調(diào)度算法要簡(jiǎn)單，易實(shí)現(xiàn)。另外，當(dāng)業(yè)務(wù)流量增加和線路速率26變化范圍較大時(shí)，調(diào)度算法仍應(yīng)有效工作，這要求調(diào)度算法應(yīng)該具有良好的擴(kuò)展性。此外，一個(gè)好的調(diào)度算法還應(yīng)具備以下性能：有效性：一個(gè)有效的算法在每次匹配中，應(yīng)當(dāng)有盡可能多的輸入隊(duì)列得到服務(wù)。穩(wěn)定性：對(duì)于給定的可允許的業(yè)務(wù)類(lèi)型，我們要求算法在任何時(shí)刻每個(gè)輸入隊(duì)列的平均長(zhǎng)度總是有限長(zhǎng)的。公平性：對(duì)于一個(gè)非空的輸入排隊(duì)，在一個(gè)給定的業(yè)務(wù)類(lèi)型和調(diào)度算法下，不能使有的隊(duì)列總得不到服務(wù)。易實(shí)現(xiàn)性：時(shí)間復(fù)雜度不能太高，在硬件上具有可實(shí)現(xiàn)性。4.3幾個(gè)基本概念(1)阻塞：當(dāng)?shù)竭_(dá)不同端口的兩個(gè)以上信元競(jìng)爭(zhēng)同一內(nèi)部鏈路時(shí)，即發(fā)生內(nèi)部阻塞，如傳統(tǒng)的BANYAN網(wǎng)絡(luò)就是一個(gè)內(nèi)部有阻塞的網(wǎng)絡(luò)。當(dāng)兩個(gè)以上信元在同一時(shí)隙指向同一輸出端口時(shí)，就會(huì)出現(xiàn)輸出阻塞，所以必須在交換結(jié)構(gòu)內(nèi)放置緩沖器，以增加信元時(shí)延為代價(jià)來(lái)消除阻塞。在傳統(tǒng)的輸入緩沖結(jié)構(gòu)中，在一個(gè)信元時(shí)隙內(nèi)當(dāng)FIFO隊(duì)列的排頭信元參與輸出競(jìng)爭(zhēng)失敗后，即時(shí)排在它后面的信元指向的輸出端口是空閑的，該信元也無(wú)法輸出，這種想象稱為排頭阻塞。(2)加速比(speedup)：如果每個(gè)輸出端口在一個(gè)時(shí)隙內(nèi)可同時(shí)接收S個(gè)信元，就說(shuō)這種交換結(jié)構(gòu)具有加速功能，S稱為加速因子。可通過(guò)時(shí)分和空分兩種方法實(shí)現(xiàn)加速，前者指交換結(jié)構(gòu)的內(nèi)部速率是外部端口的S倍；后者則是為每個(gè)輸出端口提供S條并行路徑。(3)組播(multicast)：組播指的是一個(gè)源用戶的一個(gè)數(shù)據(jù)分組或信元要同時(shí)傳送到K個(gè)目的用戶。顯然，當(dāng)K=1就是點(diǎn)到點(diǎn)連接也稱為單播(unicast)，K=N即為廣播。如視頻分配就是典型的組播業(yè)務(wù)。組播是ATM交換機(jī)和路由器的重要功能之一。(4)性能：通常用三個(gè)參數(shù)描述信元交換結(jié)構(gòu)的性能：吞吐率(TP)、交換時(shí)延(D)和信元丟失率(CL)。TP定義為每輸入端口、每時(shí)隙成功傳送信元到目的地端口的平均數(shù)，最大吞吐率(TPm)則是最大負(fù)荷下的TP值。D指的是一個(gè)信元從進(jìn)入輸入端口到傳送到輸出端口所經(jīng)歷的平均時(shí)間，它由緩沖器平均排隊(duì)時(shí)延和一個(gè)信元的27傳輸時(shí)間組成。CL定義為交換結(jié)構(gòu)信元丟失的數(shù)目與總到達(dá)數(shù)目之比，信元丟失是由于阻塞或緩沖器溢出造成的，顯然降低CL的一個(gè)直接辦法就是增加緩沖器的容量。此外，延時(shí)抖動(dòng)也是描述交換結(jié)構(gòu)性能的一個(gè)重要指標(biāo)，它指的是一個(gè)信元在交換結(jié)構(gòu)中經(jīng)歷的最大時(shí)延和平均時(shí)延的差值，通常用差值出現(xiàn)的概率表示：該指標(biāo)對(duì)于實(shí)時(shí)業(yè)務(wù)有重要影響。不難看出，一個(gè)理想的交換結(jié)構(gòu)應(yīng)具有盡可能大的TP、較小的時(shí)研、信元丟失率和延時(shí)抖動(dòng)。(5)優(yōu)先級(jí)(priority):不同的業(yè)務(wù)在傳送時(shí)延和丟失率業(yè)務(wù)上有不同的要求，如像話音這樣的實(shí)時(shí)業(yè)務(wù)要求有較小的傳送延時(shí)，像數(shù)據(jù)這樣的非實(shí)時(shí)業(yè)務(wù)則要求有較小的丟失率，而像高質(zhì)量視頻業(yè)務(wù)則對(duì)時(shí)延和丟失率均有較高的要求。多媒體業(yè)務(wù)的不斷引入要求交換機(jī)和路由器應(yīng)能處理不同的優(yōu)先級(jí)別以保證不同業(yè)務(wù)的QoS。(6)業(yè)務(wù)量模型(traffic)：到達(dá)輸入端口的業(yè)務(wù)特性通常用兩個(gè)隨機(jī)過(guò)程描述：一是信元到達(dá)輸入端口的隨機(jī)過(guò)程，另一個(gè)是信元目的端口地址分布。信元到達(dá)的真實(shí)過(guò)程隨著業(yè)務(wù)種類(lèi)的不同而變化，在進(jìn)行交換結(jié)構(gòu)的信能分析時(shí)一般采用隨機(jī)和突發(fā)兩種業(yè)務(wù)模型。隨機(jī)業(yè)務(wù)模型是假定信元到達(dá)輸入端口是一個(gè)獨(dú)立同分布Bernoulli過(guò)程，即在任意給定的時(shí)隙內(nèi)，信元到達(dá)某一輸入端口的概率為p,無(wú)信元概率為(1-p),（p也稱為輸入負(fù)荷）。描述突發(fā)業(yè)務(wù)的常用模型是on/off模型，這種模型雖然簡(jiǎn)單但很流行，而且在分析上可行。該模型由交替的活動(dòng)期和沉默期組成，活動(dòng)期內(nèi)產(chǎn)生信元，沉默期不產(chǎn)生信元。on和off被認(rèn)為是相互獨(dú)立的，而且這些時(shí)間間隔服從幾何分布。信元目的端口地址分布有均勻分布（uniform）、非均勻分布（non-uniform）和組播（multicast）分布三種。當(dāng)每個(gè)時(shí)隙到達(dá)輸入端口的信元導(dǎo)讀每個(gè)輸出端口的概率為1/N時(shí)，則稱為均勻分布，否則就是非均勻分布。熱點(diǎn)業(yè)務(wù)（hot-spot）就是一種非均勻分布，所謂熱點(diǎn)業(yè)務(wù)就是指每個(gè)時(shí)隙到達(dá)的所有信元總有一個(gè)固定概率到達(dá)一個(gè)熱點(diǎn)輸出端口。若設(shè)h表示到達(dá)熱點(diǎn)端口的概率，則輸入負(fù)荷p可表示為p=ph+p(1-h),其中ph為指向熱點(diǎn)的信元數(shù)，目前對(duì)交換結(jié)構(gòu)的分析大都采用上述模型。284.4現(xiàn)有的輸入排隊(duì)調(diào)度算法我們將現(xiàn)有的調(diào)度算法分為最大(無(wú)權(quán)重)匹配、最大權(quán)重匹配、穩(wěn)定婚姻匹配和確定型調(diào)度算法4類(lèi)[31].其中最大匹配、最大權(quán)重匹配和穩(wěn)定婚姻匹配都是二分圖的匹配算法,而確定型調(diào)度算法主要基于矩陣分解。二分圖G

匹配M1

w11

1

1

12

w21

w12

2

2

2w323

3

3

3w2NwN3N

N

N

N圖4.1

輸入排隊(duì)調(diào)度算法的二分圖描述除了確定型調(diào)度算法以外,其他調(diào)度算法都把交換結(jié)構(gòu)看成一個(gè)二分圖G=[V,E](如圖4.1所示),這里頂點(diǎn)集合V可以分為兩個(gè)子集:(1)左頂點(diǎn)子集V1,其元素v1k表示輸入端口k；(2)右頂點(diǎn)子集V2,其元素v2k表示輸出端口k。邊集E表示從輸入到輸出端口可能的傳輸(如從v1i到v2j的邊表示有信元從輸入i到輸出j)。邊的權(quán)重記為wij,它可以表示隊(duì)列中是否有信元,隊(duì)列長(zhǎng)度或隊(duì)列頭信元的等待時(shí)間等信息。當(dāng)輸入i沒(méi)有到輸出j的信元時(shí),wij=0。根據(jù)二分圖G的邊的權(quán)重組成的N×N矩陣稱為權(quán)重矩陣W=[wij]。我們定義時(shí)間片t時(shí)權(quán)重矩陣W(t)=[wij(t)]。二分圖G的匹配定義為邊集E的子集M,具有性質(zhì):M中沒(méi)有兩條邊有公共頂點(diǎn)。因此,如果M是一個(gè)匹配,那么每一個(gè)左頂點(diǎn)最多與M的一條邊關(guān)聯(lián),類(lèi)似地,每一個(gè)右頂點(diǎn)最多與M的一條邊關(guān)聯(lián)。這說(shuō)明一個(gè)二分圖的匹配滿足交換結(jié)構(gòu)的傳輸限制條件。最大匹配(maximumsizematching,簡(jiǎn)稱MSM)是指邊數(shù)達(dá)到最大,而最大權(quán)重匹配(maximumweightmatching,簡(jiǎn)稱MWM)是指邊的權(quán)重之和達(dá)到最大。由于這兩種算法具有復(fù)雜度高、硬件實(shí)現(xiàn)復(fù)雜等缺點(diǎn),在實(shí)際應(yīng)用中,我們一般用極大匹配(maximal29........................matching)近似最大匹配。所謂的極大匹配是指在當(dāng)前已完成的匹配下,無(wú)法再通過(guò)增加未完成匹配的邊的方式來(lái)增加匹配的邊數(shù)或權(quán)重。穩(wěn)定婚姻匹配根據(jù)每個(gè)信元的優(yōu)先級(jí)別來(lái)調(diào)度信元。4.5基于最大匹配的算法我們可以直接用二分圖的MSM算法解決調(diào)度中的匹配問(wèn)題。目前已知的漸進(jìn)復(fù)雜性最好的該類(lèi)算法可以達(dá)到O(N2.5)[32]。MSM采用1位的隊(duì)列占用作為邊的權(quán)重:當(dāng)隊(duì)列中有信元時(shí),相應(yīng)的邊的權(quán)重為1;否則為0。仿真實(shí)驗(yàn)表明[33],MSM在均勻的獨(dú)立到達(dá)下可以實(shí)現(xiàn)100%的吞吐率。但其也具有以下缺點(diǎn):(1)在容許的非均勻通信量下,可能導(dǎo)致不穩(wěn)定和不公平;(2)在非容許的通信量下,可能導(dǎo)致餓死;(3)算法實(shí)現(xiàn)起來(lái)過(guò)于復(fù)雜且運(yùn)行時(shí)間長(zhǎng)。在實(shí)際應(yīng)用中,我們一般用啟發(fā)式算法來(lái)解決二分圖的匹配問(wèn)題。這些算法具有實(shí)現(xiàn)簡(jiǎn)單、運(yùn)算速度快等優(yōu)點(diǎn),但只能實(shí)現(xiàn)極大匹配。啟發(fā)式調(diào)度算法要經(jīng)過(guò)多次迭代才能找到極大匹配,每次迭代包括3個(gè)步驟。在一個(gè)時(shí)間片開(kāi)始時(shí),所有的輸入和輸出都初始化為未匹配,只有那些直到一次迭代結(jié)束都未能完成匹配的輸入和輸出才能留到下一次迭代。這3個(gè)步驟是:(1)請(qǐng)求(request):每個(gè)未完成匹配的輸入端口向它的隊(duì)列中信元可能到達(dá)的輸出端口發(fā)送請(qǐng)求信號(hào)。(2)響應(yīng)(grant):一個(gè)輸出端口可能收到多個(gè)輸入端口發(fā)來(lái)的請(qǐng)求信號(hào)。每個(gè)未完成匹配的輸出端口從收到的請(qǐng)求中選擇一個(gè)輸入端口并向其發(fā)送響應(yīng)信號(hào)。(3)接受(accept):每個(gè)未完成匹配的輸入端口可能收到多個(gè)輸出端口的響應(yīng)信號(hào)。輸入端口從響應(yīng)信號(hào)中選擇一個(gè)輸出端口并向其發(fā)送接受信號(hào)。并行迭代匹配(ParallelIterativeMatching,PIM)PIM[34]是由DEC系統(tǒng)研究中心為16端口，1Gbps的AN2交換機(jī)開(kāi)發(fā)的，這個(gè)算法是iSLIP算法的基礎(chǔ)。PIM算法的隨機(jī)性避免了某些端口的“資源匱缺”性，并減少收斂30于最大基數(shù)匹配的迭代次數(shù)。一般地說(shuō)，這里的最大匹配是小于最大基數(shù)匹配的，PIM算法企圖快速地用多次迭代收斂于最大匹配，算法分三步但執(zhí)行起來(lái)簡(jiǎn)單。1)請(qǐng)求:每個(gè)未匹配的輸入端口向每個(gè)未匹配的輸出端口發(fā)送請(qǐng)求；2)授權(quán):如果某個(gè)未匹配的輸出端口收到一個(gè)或多個(gè)請(qǐng)求，它隨機(jī)地以相同概率選取一個(gè)請(qǐng)求，發(fā)回授權(quán)信息；3)接受:如果一個(gè)輸入端口收到若干授權(quán)信息，它也可等可能地隨機(jī)地選取其中的一個(gè)，接受這個(gè)連接。PIM算法的特點(diǎn):1)每次迭代將完成平均3/4個(gè)剩余的待連接邊，在平均意義下，迭代次數(shù)為O(logN)。2)它保證所有請(qǐng)求將被最終授權(quán)，沒(méi)有輸入隊(duì)列會(huì)處于“資源匱缺”狀態(tài)。3)以往做過(guò)的連接不被記錄。缺點(diǎn):1)在高速時(shí)執(zhí)行起來(lái)比較困難和昂貴，每個(gè)仲裁器必須在許多時(shí)變集合中使用隨機(jī)選擇。2)可能導(dǎo)致連接的不公平性。3)在單次迭代中不是很好，其吞吐量接近于63%,略高于FIFO交換。雖然算法在若干次迭代后收斂，收斂次數(shù)可影響交換操作的速率?；狙h(huán)匹配算法(BasesRoundRobinMatching,B-RRM)RRM算法[35]是迭代循環(huán)算法中最簡(jiǎn)單和最直觀的算法，它形成一個(gè)循環(huán)判定的二維數(shù)組，信元在每個(gè)輸入和每個(gè)輸出由循環(huán)調(diào)度。RRM算法的性能不是最好的。RRM算法潛在地克服了PIM算法中的兩點(diǎn)不足，復(fù)雜性與不公平性，它用循環(huán)仲裁器代替PIM中的隨機(jī)仲裁器，比隨機(jī)判決快，優(yōu)先級(jí)的輪循使算法均勻地分配帶寬，也使請(qǐng)求連接更加公平。對(duì)于一個(gè)NN交換，算法也分三步:1)請(qǐng)求:每個(gè)輸入端口向所有可能的目的端口發(fā)送請(qǐng)求；2)授權(quán):輸出端口收到請(qǐng)求后，采用循環(huán)優(yōu)先級(jí)調(diào)度方法，選擇一個(gè)最高優(yōu)先級(jí)的請(qǐng)求授權(quán)，輸出端口向每一個(gè)提出請(qǐng)求的輸入端口發(fā)回通知，通知各輸入端口是否被授權(quán)，31優(yōu)先級(jí)指針按照模N增加1,新的位置為所授權(quán)的輸入端口的下一個(gè)位置，即剛剛得到服務(wù)的輸入端的優(yōu)先級(jí)降為最低；3)接受:輸入端口收到授權(quán)信息后，同樣采用循環(huán)調(diào)度方法，選擇優(yōu)先級(jí)最高的授權(quán)，表明接受此項(xiàng)連接。優(yōu)先級(jí)指針按照模N增加1，新的位置為所接受的輸出端口的下一個(gè)位置。RRM算法有以下特性：特性1最低優(yōu)先級(jí)最先連接。特性2沒(méi)有連接是資源匱缺。特性3在重負(fù)下，具有同一輸出端口隊(duì)列有同樣的吞吐量。迭代SLIP算法(iterativeSLIP,iSLIP)iSLIP算法[35,

36]入和輸出端口。目的是為了有效、公平、快速地匹配一個(gè)輸入隊(duì)列調(diào)度器的輸入端口和輸出端口。在每個(gè)時(shí)隙，采用多次迭代來(lái)選擇交叉開(kāi)關(guān)的配置，使輸入端口和輸出端口盡量達(dá)到匹配。iSLIP每一次迭代由三步組成，這里設(shè)輸入端口和輸出端口數(shù)都為N：Step1：請(qǐng)求每一輸入端口為該端口的非空VOQ發(fā)送服務(wù)請(qǐng)求至輸出端。Step2：授權(quán)每一輸出端口在收到的請(qǐng)求服務(wù)的輸入端口中，以循環(huán)優(yōu)先級(jí)方式選擇最接近輸出端指針的輸入端口，發(fā)送允許服務(wù)信息至該輸入端口。如果允許服務(wù)信息在第3步中被接受，在該輸出端口指向最高優(yōu)先級(jí)位置的指針g按模N增加，指向該允許服務(wù)的輸入端口的下一個(gè)位置。Step3：接受每一輸入端口在收到允許服務(wù)的輸出端口中，以循環(huán)優(yōu)先級(jí)方式選擇最接近輸入端指針的輸出端口，發(fā)送接受服務(wù)信息至該輸出端口。該輸入端口指向最高優(yōu)先級(jí)位置的指針a按模N增加，指向該接受服務(wù)的輸出端口的下一個(gè)位置。指針只在第一次迭代后被更新。iSLIP算法由于去掉了指針的同步而具有較好的性能，并且文獻(xiàn)[35]證明只需迭代一步即可在均勻流量下獲得100%吞吐率。由于鏈路速率越來(lái)越快，導(dǎo)致留給調(diào)32是基于極大匹配的一種迭代算法，利用循環(huán)優(yōu)先級(jí)仲裁來(lái)調(diào)度輸是基于極大匹配的一種迭代算法，利用循環(huán)優(yōu)先級(jí)仲裁來(lái)調(diào)度輸度決策的時(shí)間也越來(lái)越短。例如，250G的鏈路速率，若分組長(zhǎng)度為500bits，那么留給調(diào)度的時(shí)間僅有2ns，顯然多步迭代在這種高速場(chǎng)合下是不可行的，因此下文提及的iSLIP算法均指迭代一次的iSLIP算法。我們以圖4.2作為一個(gè)調(diào)度實(shí)例,說(shuō)明iSLIP調(diào)度算法在一次迭代中的實(shí)際調(diào)度過(guò)程。圖中g(shù)2、g4是輸出端口2、4的Grant仲裁器,a1是輸入端口的Accept仲裁器。開(kāi)始時(shí),所有的輸入端口與輸出端口是未建立匹配的。輸入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調(diào)度算法實(shí)例

3

21請(qǐng)求

輸入端口1和輸入端口3各有一個(gè)以上的分組向具有分組隊(duì)列緩沖的輸出端口1、2和4發(fā)出請(qǐng)求(request)信號(hào),其它端口亦如此。2授權(quán)

由于輸出端口仲裁器的指針g2=1、g4=1,輸出端口1和2都向輸入端口1發(fā)出Grant信號(hào)。同理,輸出端口4向輸入端口3發(fā)出Grant信號(hào)。注意,當(dāng)Grant信號(hào)發(fā)出后,按照RRM調(diào)度算法,只有在第三步中準(zhǔn)許信號(hào)被輸入端口所接受,在輸出端口指向最高優(yōu)先級(jí)位置的指針g1、g2、g4才能得到更新,并按模增加，指向下一個(gè)接受Request信號(hào)的輸出端口位置。3接受

未被匹配的輸入端口從Grant信號(hào)中選擇其一。由于這時(shí)a1=1,輸入端口接受了輸出端口1的grant信號(hào),兩端口之間的匹配成功后,指針a1按模增加指向輸出端口2,這時(shí)已匹配的輸出端口指針g1和g4隨之更新,指向下一個(gè)向輸入端口發(fā)出33Grant信號(hào)的位置。注意,未成功匹配的指針g2不更新。同理,輸入指針a1按模增加并指向2。在一次迭代結(jié)束后,如果仍有未匹配的請(qǐng)求,將在下次迭代中匹配。例如輸入端口1與輸出端口2或輸入端口3與輸出端口2將在下一次建立匹配。4.6竭力服務(wù)iSLIP算法(ExhaustiveiSLIP,E-iSLIP)E-iSLIP算法是在采用公平匹配策略的iSLIP算法的基礎(chǔ)