多級分組交換網(wǎng)絡(luò)中基于負載均衡的調(diào)度算法研究.pdf

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

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

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

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

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

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

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

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

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