【摘要】：網(wǎng)絡(luò)的高速發(fā)展特別是新一代數(shù)據(jù)中心及云計(jì)算應(yīng)用的出現(xiàn)，對(duì)構(gòu)建互聯(lián)網(wǎng)基礎(chǔ)架構(gòu)的交換機(jī)和路由器提出了更高要求。作為網(wǎng)絡(luò)設(shè)備核心的交換架構(gòu)，需要向更大容量、更優(yōu)性能、更好的可擴(kuò)展性和更精細(xì)的QoS保障等方向發(fā)展，以滿足不斷涌現(xiàn)的各種新型業(yè)務(wù)和應(yīng)用。單級(jí)Crossbar交換網(wǎng)絡(luò)是目前核心路由器主流交換網(wǎng)絡(luò)結(jié)構(gòu)，，但是受工程實(shí)現(xiàn)的限制（如機(jī)架供電、芯片面積、端口密度等），無(wú)法做到更大容量。采用小型的交換模塊搭建大容量的多級(jí)交換網(wǎng)絡(luò)，可以避免上述問(wèn)題。這其中三級(jí)Clos交換網(wǎng)絡(luò)由于模塊化、可擴(kuò)展、無(wú)內(nèi)部阻塞的優(yōu)點(diǎn)獲得廣泛關(guān)注。 目前針對(duì)三級(jí)Clos交換網(wǎng)絡(luò)調(diào)度算法的研究是對(duì)單級(jí)Crossbar交換網(wǎng)絡(luò)研究成果的簡(jiǎn)單推廣，存在調(diào)度算法復(fù)雜度高、級(jí)間通信開(kāi)銷大、多路徑均衡負(fù)載時(shí)信元發(fā)生亂序、缺乏對(duì)多播業(yè)務(wù)的支持等問(wèn)題。在Clos交換網(wǎng)絡(luò)中，一對(duì)輸入輸出端口之間存在多條中間路徑，如何有效地在這多條路徑中均衡業(yè)務(wù)以便獲得高吞吐率性能，但同時(shí)又不引起亂序問(wèn)題和增加復(fù)雜度，這一點(diǎn)需要深入研究。同樣是均衡負(fù)載，兩級(jí)負(fù)載均衡交換雖然與單級(jí)Crossbar交換網(wǎng)絡(luò)一樣，存在端口數(shù)目限制的問(wèn)題，但是其在簡(jiǎn)化調(diào)度過(guò)程、提供穩(wěn)定吞吐率性能等方面的優(yōu)勢(shì)仍然值得借鑒。因此本文基于負(fù)載均衡的思想，對(duì)不同結(jié)構(gòu)三級(jí)Clos網(wǎng)絡(luò)調(diào)度算法的關(guān)鍵技術(shù)進(jìn)行了研究。主要?jiǎng)?chuàng)新點(diǎn)包括： 1.研究了各級(jí)帶緩存Clos網(wǎng)絡(luò)的亂序問(wèn)題。MMM結(jié)構(gòu)Clos交換網(wǎng)絡(luò)中間級(jí)緩存的存在緩解了輸出端口的沖突，但是當(dāng)不同路徑上的緩存隊(duì)列長(zhǎng)度不一致時(shí)，會(huì)引起輸出端口信元亂序。傳統(tǒng)的按序調(diào)度算法或者引入復(fù)雜的匹配調(diào)度過(guò)程，或者需要逐信元反饋流控信息，限制了MMM交換的可擴(kuò)展性，并且這些算法均不能達(dá)到100%吞吐率。本文提出了兩種基于填補(bǔ)幀技術(shù)的按序調(diào)度算法（EPF算法和FIM3算法），具有復(fù)雜度低、靈活性高的優(yōu)點(diǎn)，可在按序調(diào)度的同時(shí)提供100%吞吐率性能。所提調(diào)度算法將到達(dá)業(yè)務(wù)逐流逐幀均勻分布到所有中間級(jí)模塊，通過(guò)使信元經(jīng)過(guò)的中間級(jí)緩存隊(duì)列長(zhǎng)度一致來(lái)保證信元不發(fā)生亂序。一幀信元的數(shù)目與中間級(jí)模塊數(shù)目相等。為避免低負(fù)載隊(duì)列的饑餓問(wèn)題，不滿一幀的隊(duì)列可通過(guò)填補(bǔ)空信元的方式獲得發(fā)送機(jī)會(huì)。EPF算法在輸入和輸出級(jí)交換模塊采用周期確定性輪轉(zhuǎn)配置，不需要執(zhí)行調(diào)度算法。在此基礎(chǔ)上，F(xiàn)IM3算法在輸出級(jí)采用交叉點(diǎn)緩存交換結(jié)構(gòu)，結(jié)合最老信元優(yōu)先調(diào)度算法，進(jìn)一步改善了低負(fù)載時(shí)算法的時(shí)延性能。理論分析和仿真驗(yàn)證結(jié)果均表明在可允許業(yè)務(wù)下，所提算法無(wú)亂序、同時(shí)可提供100%的吞吐率性能。 2.研究了各級(jí)帶緩存Clos網(wǎng)絡(luò)的多播支持問(wèn)題�，F(xiàn)有的多播調(diào)度算法在中間級(jí)和輸出級(jí)采用輸入排隊(duì)FIFO結(jié)構(gòu)，其吞吐率性能受多播隊(duì)頭阻塞影響較大；并且，以分組為粒度的調(diào)度雖然避免了分組內(nèi)信元的亂序，但未能消除分組間的亂序，且總的亂序程度未被有效降低。盡管已有大量按序單播調(diào)度算法，但是考慮到多播業(yè)務(wù)扇出分布的特點(diǎn)，難以采用逐流業(yè)務(wù)均衡。本文提出了一種基于填補(bǔ)幀技術(shù)的多播調(diào)度算法（FMClos），具有較高的吞吐率和較低的亂序比例。該調(diào)度算法以信元為調(diào)度粒度，多播信元在輸入級(jí)和輸出級(jí)采用地址復(fù)制扇出機(jī)制進(jìn)行入隊(duì)操作，消除多播隊(duì)頭阻塞影響，提高了交換網(wǎng)絡(luò)的吞吐率。所提算法輸入級(jí)和中間級(jí)基于輸出模塊排隊(duì)并進(jìn)行逐幀調(diào)度，結(jié)合中間級(jí)模塊采用的交叉點(diǎn)帶緩存Crossbar交換單元，有效地控制了信元亂序影響的范圍。仿真結(jié)果表明，所提多播調(diào)度算法的吞吐率性能接近100%，并且相比已有的多播調(diào)度算法，其亂序比例以及重排所需時(shí)延被大幅降低。 3.研究了輸入輸出級(jí)帶緩存Clos網(wǎng)絡(luò)的加權(quán)匹配調(diào)度算法，提出了MSM結(jié)構(gòu)Clos網(wǎng)絡(luò)一種分布式加權(quán)匹配調(diào)度算法（DWMD），具有復(fù)雜度低、級(jí)間通信開(kāi)銷小、匹配效率高的優(yōu)點(diǎn)。在分布式加權(quán)匹配調(diào)度算法中，每個(gè)輸入模塊將請(qǐng)求令牌均衡到所有中間級(jí)模塊。各中間級(jí)模塊依據(jù)本地維護(hù)的虛擬令牌計(jì)數(shù)器值執(zhí)行基于權(quán)重的匹配算法，如啟發(fā)式的加權(quán)匹配或隨機(jī)化的加權(quán)匹配，不需要了解全局請(qǐng)求信息或其它中間級(jí)模塊的匹配信息。該調(diào)度算法繼承了負(fù)載均衡交換和加權(quán)匹配算法的優(yōu)點(diǎn)，但既沒(méi)有引起信元亂序，也沒(méi)有增加通信開(kāi)銷。仿真結(jié)果表明，分布式加權(quán)匹配調(diào)度算法在多種業(yè)務(wù)類型下均可達(dá)到100%吞吐率，并且相比已有的加權(quán)匹配調(diào)度算法，新算法具有更高的匹配效率。 4.研究了輸入輸出級(jí)帶緩存Clos網(wǎng)絡(luò)的多播支持問(wèn)題，提出了一種基于靜態(tài)輪詢的單多播集成調(diào)度算法（MUSRRD）。所提算法對(duì)單多播信元分開(kāi)入隊(duì)，隔離了兩種業(yè)務(wù)之間的影響；且多播信元在輸入級(jí)基于輸出模塊地址復(fù)制扇出入隊(duì)，消除了多播排頭阻塞。由于該單多播集成調(diào)度算法不增加模塊間調(diào)度信息，因此在靜態(tài)輪詢單播調(diào)度算法的基礎(chǔ)上，只需對(duì)輸入模塊內(nèi)的從判決器進(jìn)行重新設(shè)計(jì)。研究表明，該算法繼承了靜態(tài)輪詢單播調(diào)度算法中指針初始化和更新方式簡(jiǎn)單高效的特點(diǎn)，可提供業(yè)務(wù)類型級(jí)和流級(jí)的公平，并且算法復(fù)雜度低、硬件實(shí)現(xiàn)簡(jiǎn)單。
[Abstract]:......
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP393.05

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 戴精科;彭來(lái)獻(xiàn);張邦寧;;一種支持單播與組播混合業(yè)務(wù)的高速Crossbar調(diào)度算法[J];電子與信息學(xué)報(bào);2009年10期

2 徐恪,熊勇強(qiáng),吳建平;寬帶IP路由器的體系結(jié)構(gòu)分析[J];軟件學(xué)報(bào);2000年02期

3 龐斌,賀思敏,高文;高速IP路由器中輸入排隊(duì)調(diào)度算法綜述[J];軟件學(xué)報(bào);2003年05期

4 陳庶樵;扈紅超;郭云飛;李揮;;一種支持單組播的MCICQ交換結(jié)構(gòu)及其性能仿真[J];系統(tǒng)仿真學(xué)報(bào);2009年13期

相關(guān)博士學(xué)位論文 前2條

1 蔣泳波;高速交換結(jié)構(gòu)多播技術(shù)研究[D];西安電子科技大學(xué);2013年

2 夏羽;高性能大容量多級(jí)交換結(jié)構(gòu)與調(diào)度算法研究[D];西南交通大學(xué);2012年

本文編號(hào)：2339605