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

【參考文獻】

相關期刊論文 前4條

1 戴精科;彭來獻;張邦寧;;一種支持單播與組播混合業(yè)務的高速Crossbar調度算法[J];電子與信息學報;2009年10期

2 徐恪,熊勇強,吳建平;寬帶IP路由器的體系結構分析[J];軟件學報;2000年02期

3 龐斌,賀思敏,高文;高速IP路由器中輸入排隊調度算法綜述[J];軟件學報;2003年05期

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

相關博士學位論文 前2條

1 蔣泳波;高速交換結構多播技術研究[D];西安電子科技大學;2013年

2 夏羽;高性能大容量多級交換結構與調度算法研究[D];西南交通大學;2012年

本文編號：2339605