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

1、網(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ī)架供電、芯片面積、端口密度等),無法做到更大容量。采用小型的交換模塊搭建大容量的多級(jí)交換網(wǎng)絡(luò),可以避免上述問題

2、。這其中三級(jí)Clos交換網(wǎng)絡(luò)由于模塊化、可擴(kuò)展、無內(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í)間通信開銷大、多路徑均衡負(fù)載時(shí)信元發(fā)生亂序、缺乏對(duì)多播業(yè)務(wù)的支持等問題。在Clos交換網(wǎng)絡(luò)中,一對(duì)輸入輸出端口之間存在多條中間路徑,如何有效地在這多條路徑中均衡業(yè)務(wù)以便獲得高吞吐率性能,但同時(shí)又不引起亂序問題和增加復(fù)雜度,這一點(diǎn)需要

3、深入研究。同樣是均衡負(fù)載,兩級(jí)負(fù)載均衡交換雖然與單級(jí)Crossbar交換網(wǎng)絡(luò)一樣,存在端口數(shù)目限制的問題,但是其在簡(jiǎn)化調(diào)度過程、提供穩(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ò)的亂序問題。MMM結(jié)構(gòu)Clos交換網(wǎng)絡(luò)中間級(jí)緩存的存在緩解了輸出端口的沖突,但是當(dāng)不同路徑上的緩存隊(duì)列長(zhǎng)度不一致時(shí),會(huì)引起輸

4、出端口信元亂序。傳統(tǒng)的按序調(diào)度算法或者引入復(fù)雜的匹配調(diào)度過程,或者需要逐信元反饋流控信息,限制了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í)模塊,通過使信元經(jīng)過的中間級(jí)緩存隊(duì)列長(zhǎng)度一致來保證信元不發(fā)生亂序。一幀信元的數(shù)目與中間級(jí)模

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

6、的多播調(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ù)制

7、扇出機(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ò)一種分布

8、式加權(quán)匹配調(diào)度算法(DWMD),具有復(fù)雜度低、級(jí)間通信開銷小、匹配效率高的優(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),但既沒有引起信元亂序,也沒有增加通信開銷。仿真結(jié)果表明,分布式加權(quán)匹配調(diào)度算法在多種

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