多級分組交換網絡中基于負載均衡的調度算法研究.pdf

1、網絡的高速發(fā)展特別是新一代數據中心及云計算應用的出現,對構建互聯(lián)網基礎架構的交換機和路由器提出了更高要求。作為網絡設備核心的交換架構,需要向更大容量、更優(yōu)性能、更好的可擴展性和更精細的QoS保障等方向發(fā)展,以滿足不斷涌現的各種新型業(yè)務和應用。單級Crossbar交換網絡是目前核心路由器主流交換網絡結構,但是受工程實現的限制(如機架供電、芯片面積、端口密度等),無法做到更大容量。采用小型的交換模塊搭建大容量的多級交換網絡,可以避免上述問題

2、。這其中三級Clos交換網絡由于模塊化、可擴展、無內部阻塞的優(yōu)點獲得廣泛關注。
　　目前針對三級Clos交換網絡調度算法的研究是對單級Crossbar交換網絡研究成果的簡單推廣,存在調度算法復雜度高、級間通信開銷大、多路徑均衡負載時信元發(fā)生亂序、缺乏對多播業(yè)務的支持等問題。在Clos交換網絡中,一對輸入輸出端口之間存在多條中間路徑,如何有效地在這多條路徑中均衡業(yè)務以便獲得高吞吐率性能,但同時又不引起亂序問題和增加復雜度,這一點需要

3、深入研究。同樣是均衡負載,兩級負載均衡交換雖然與單級Crossbar交換網絡一樣,存在端口數目限制的問題,但是其在簡化調度過程、提供穩(wěn)定吞吐率性能等方面的優(yōu)勢仍然值得借鑒。因此本文基于負載均衡的思想,對不同結構三級Clos網絡調度算法的關鍵技術進行了研究。主要創(chuàng)新點包括:
　　1.研究了各級帶緩存Clos網絡的亂序問題。MMM結構Clos交換網絡中間級緩存的存在緩解了輸出端口的沖突,但是當不同路徑上的緩存隊列長度不一致時,會引起輸

4、出端口信元亂序。傳統(tǒng)的按序調度算法或者引入復雜的匹配調度過程,或者需要逐信元反饋流控信息,限制了MMM交換的可擴展性,并且這些算法均不能達到100％吞吐率。本文提出了兩種基于填補幀技術的按序調度算法(EPF算法和FIM3算法),具有復雜度低、靈活性高的優(yōu)點,可在按序調度的同時提供100%吞吐率性能。所提調度算法將到達業(yè)務逐流逐幀均勻分布到所有中間級模塊,通過使信元經過的中間級緩存隊列長度一致來保證信元不發(fā)生亂序。一幀信元的數目與中間級模

5、塊數目相等。為避免低負載隊列的饑餓問題,不滿一幀的隊列可通過填補空信元的方式獲得發(fā)送機會。EPF算法在輸入和輸出級交換模塊采用周期確定性輪轉配置,不需要執(zhí)行調度算法。在此基礎上,FIM3算法在輸出級采用交叉點緩存交換結構,結合最老信元優(yōu)先調度算法,進一步改善了低負載時算法的時延性能。理論分析和仿真驗證結果均表明在可允許業(yè)務下,所提算法無亂序、同時可提供100%的吞吐率性能。
　　2.研究了各級帶緩存Clos網絡的多播支持問題?，F有

6、的多播調度算法在中間級和輸出級采用輸入排隊FIFO結構,其吞吐率性能受多播隊頭阻塞影響較大;并且,以分組為粒度的調度雖然避免了分組內信元的亂序,但未能消除分組間的亂序,且總的亂序程度未被有效降低。盡管已有大量按序單播調度算法,但是考慮到多播業(yè)務扇出分布的特點,難以采用逐流業(yè)務均衡。本文提出了一種基于填補幀技術的多播調度算法(FMClos),具有較高的吞吐率和較低的亂序比例。該調度算法以信元為調度粒度,多播信元在輸入級和輸出級采用地址復制

7、扇出機制進行入隊操作,消除多播隊頭阻塞影響,提高了交換網絡的吞吐率。所提算法輸入級和中間級基于輸出模塊排隊并進行逐幀調度,結合中間級模塊采用的交叉點帶緩存Crossbar交換單元,有效地控制了信元亂序影響的范圍。仿真結果表明,所提多播調度算法的吞吐率性能接近100%,并且相比已有的多播調度算法,其亂序比例以及重排所需時延被大幅降低。
　　3.研究了輸入輸出級帶緩存Clos網絡的加權匹配調度算法,提出了MSM結構Clos網絡一種分布

8、式加權匹配調度算法(DWMD),具有復雜度低、級間通信開銷小、匹配效率高的優(yōu)點。在分布式加權匹配調度算法中,每個輸入模塊將請求令牌均衡到所有中間級模塊。各中間級模塊依據本地維護的虛擬令牌計數器值執(zhí)行基于權重的匹配算法,如啟發(fā)式的加權匹配或隨機化的加權匹配,不需要了解全局請求信息或其它中間級模塊的匹配信息。該調度算法繼承了負載均衡交換和加權匹配算法的優(yōu)點,但既沒有引起信元亂序,也沒有增加通信開銷。仿真結果表明,分布式加權匹配調度算法在多種

9、業(yè)務類型下均可達到100%吞吐率,并且相比已有的加權匹配調度算法,新算法具有更高的匹配效率。
　　4.研究了輸入輸出級帶緩存Clos網絡的多播支持問題,提出了一種基于靜態(tài)輪詢的單多播集成調度算法(MUSRRD)。所提算法對單多播信元分開入隊,隔離了兩種業(yè)務之間的影響;且多播信元在輸入級基于輸出模塊地址復制扇出入隊,消除了多播排頭阻塞。由于該單多播集成調度算法不增加模塊間調度信息,因此在靜態(tài)輪詢單播調度算法的基礎上,只需對輸入模塊內