高 雅 邱智亮 張茂森 黎 軍

①(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 西安 710071)

②(空間微波技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 西安 710100)

1 引言

Internet的持續(xù)爆炸性增長(zhǎng)促進(jìn)了可擴(kuò)展快速交換結(jié)構(gòu)的研究。Clos交換網(wǎng)絡(luò)由于其在模塊化和可擴(kuò)展性方面的潛能，在構(gòu)建大容量多端口交換網(wǎng)絡(luò)的研究中受到越來(lái)越多的關(guān)注。Clos網(wǎng)絡(luò)交換結(jié)構(gòu)可以分為兩類：無(wú)緩存 Clos網(wǎng)絡(luò)和有緩存 Clos網(wǎng)絡(luò)。無(wú)緩存 Clos網(wǎng)絡(luò)，也稱為空分交換結(jié)構(gòu)(Space-Space-Space, SSS)。SSS Clos網(wǎng)絡(luò)的交換模塊設(shè)計(jì)簡(jiǎn)單，但交換時(shí)需要的配置相當(dāng)復(fù)雜[1]，這是由于每個(gè)時(shí)隙在信元傳輸之前都要解決輸出端口競(jìng)爭(zhēng)和路徑選擇的問題。為減少配置時(shí)間，通常在輸入級(jí)和輸出級(jí)模塊設(shè)置緩存。依據(jù)中間級(jí)模塊是否存儲(chǔ)信元，將帶緩存的Clos交換網(wǎng)絡(luò)分為兩類：MSM(Memory-Space-Memory)型 Clos網(wǎng)絡(luò)和MMM型Clos網(wǎng)絡(luò)。MSM Clos網(wǎng)絡(luò)在輸入級(jí)和輸出級(jí)需要緩存加速，交換模塊端口數(shù)越大，需要的緩存加速越高，這將極大限制MSM型Clos交換網(wǎng)絡(luò)的應(yīng)用范圍。MMM型Clos網(wǎng)絡(luò)不需要緩存加速，但是中間級(jí)緩存的存在會(huì)引起輸出端口的信元亂序。亂序轉(zhuǎn)發(fā)就需要在輸出端口進(jìn)行信元重排，這在緩存和分組處理上將帶來(lái)極大消耗。

設(shè)計(jì)一個(gè)按序高效的交換網(wǎng)絡(luò)調(diào)度方案是MMM 交換的研究重點(diǎn)。文獻(xiàn)[2]提出了一種具有信元保序能力的三級(jí)Clos分布式調(diào)度算法——負(fù)載分配并發(fā)式調(diào)度算法。該算法首先按輪詢方式選擇一個(gè)中間級(jí)模塊(Central Module, CM)，然后根據(jù)該CM 的排隊(duì)情況計(jì)算得到本時(shí)隙的調(diào)度匹配，并將結(jié)果廣播給其它CM。這種方式下要求CM間有總線相連，通信開銷較大。輸出級(jí)模塊(Output Module,OM)采用迭代式最早信元順序輸出調(diào)度算法，計(jì)算和通信代價(jià)比較高。TrueWay[3]是一種多平面MMM交換，可提供信元按序傳遞。該交換采用散列(hashing)函數(shù)為每個(gè)流選擇平面和中間模塊，這樣一個(gè)流的信元遵循同一條路徑。但是為達(dá)到較高性能，TrueWay需要1.6倍的緩存加速。MMM-IM算法[4]在信元進(jìn)入輸入模塊(Input Module, IM)后加時(shí)間戳，分組選擇CM是依據(jù)逐流設(shè)置的指針，以保證每個(gè)流均勻分布到中間級(jí)各模塊。一個(gè)流的前一個(gè)分組離開CM時(shí)，需要向IM反饋流信息，這樣同一個(gè)流的下一個(gè)分組才能發(fā)送到 CM。由于算法維序是通過(guò)逐分組反饋，復(fù)雜度較高，并且達(dá)不到100%吞吐率。

同樣存在分組亂序問題的是基于負(fù)載均衡的兩級(jí)交換結(jié)構(gòu)。至文獻(xiàn)[5]首次提出負(fù)載均衡交換的概念，這一領(lǐng)域獲得了大量的關(guān)注[6-12]。典型的負(fù)載均衡交換包含兩級(jí)：輸入級(jí)用于均衡負(fù)載，將到達(dá)的業(yè)務(wù)轉(zhuǎn)換成均勻業(yè)務(wù)，中間級(jí)用于交換均勻業(yè)務(wù)。兩級(jí)交換的連接模式都是確定性和周期性的。負(fù)載均衡交換分組保序算法中具有代表性的就是基于幀的一類算法[6-8]。UFS[6](Uniform Frame Spreading)算法采用逐幀轉(zhuǎn)發(fā)的概念，一幀由N個(gè)連續(xù)的屬于同一個(gè)流的信元組成。如果每個(gè)輸入端口的信元都按幀的方式，在N個(gè)連續(xù)的時(shí)槽內(nèi)被順序轉(zhuǎn)發(fā)到各個(gè)對(duì)應(yīng)的VOQ(Virtual Output Queue)中，則每個(gè)中間級(jí)對(duì)應(yīng)的 VOQ的隊(duì)長(zhǎng)都相等，從而同一個(gè)幀的分組在中間級(jí)所經(jīng)歷的時(shí)延也相同。但是在中低負(fù)載下，一個(gè) VOQ可能需要等待較長(zhǎng)時(shí)間才能構(gòu)成一個(gè)幀，因此UFS算法的時(shí)延性能較差。在此基礎(chǔ)上，為減小低負(fù)載時(shí)分組時(shí)延，文獻(xiàn)[7]提出了滿幀填補(bǔ)(Padded Frame, PF)算法。其思想是在VOQ沒有滿幀時(shí)，增加“填充分組”湊成滿幀，這樣可減少業(yè)務(wù)量較少的隊(duì)列成幀的時(shí)間，代價(jià)是需要使用額外的帶寬來(lái)轉(zhuǎn)發(fā)填充分組。

由于MMM交換天然存在多條路徑，結(jié)合負(fù)載均衡交換的思想，本文提出了一種基于滿幀填補(bǔ)的MMM Clos網(wǎng)絡(luò)按序分組交換算法：PF擴(kuò)展算法(EPF)。與傳統(tǒng)兩級(jí)負(fù)載均衡交換一幀長(zhǎng)度為N不同，EPF算法里一幀長(zhǎng)度為M，其中M為中間級(jí)模塊數(shù)目。相比于滿幀填補(bǔ)算法(PF), EPF算法構(gòu)成滿幀所需的分組數(shù)目減少，時(shí)延性能得到進(jìn)一步改善。另外，由于填充分組的產(chǎn)生會(huì)增加中間級(jí)輸入端口的分組到達(dá)率，本文證明了若控制填充分組的數(shù)量，交換網(wǎng)絡(luò)仍能保持穩(wěn)定。

2 基于幀填補(bǔ)的Clos網(wǎng)絡(luò)按序分組傳輸

MMM Clos交換網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。輸入級(jí)有k個(gè)輸入模塊(IM)，每個(gè)IM為n×m的輸入排隊(duì)交換結(jié)構(gòu)，其中k=N/n,N為整個(gè)交換網(wǎng)絡(luò)規(guī)模。中間級(jí)有m個(gè)中間模塊(CM)，每個(gè)CM為k×k的交叉點(diǎn)帶緩存 Crossbar。輸出級(jí)有k個(gè)輸出模塊(OM)，每個(gè)OM為m×n的輸入排隊(duì)交換結(jié)構(gòu)。通常將上述Clos網(wǎng)絡(luò)記為C(m,n,k)。為討論方便，取m=n=k=M。所有到達(dá)變長(zhǎng)分組均被切割成定長(zhǎng)信元，簡(jiǎn)稱為分組，最后在輸出端口進(jìn)行重組。交換網(wǎng)絡(luò)傳輸一個(gè)定長(zhǎng)信元所需要的時(shí)間定義為一個(gè)時(shí)隙。

圖1 MMM Clos網(wǎng)絡(luò)交換結(jié)構(gòu)

為避免填充分組的產(chǎn)生加劇中間級(jí)緩存的積壓狀態(tài)，設(shè)置閾值TC，當(dāng)中間級(jí)緩存超過(guò)TC時(shí)，便不再產(chǎn)生填充分組，也就是說(shuō)，此時(shí)輸入級(jí)輸入只可調(diào)度滿幀分組。

EPF算法中填充分組的產(chǎn)生由IM模塊的各輸入端口調(diào)度器控制，CM和OM分別為自路由模式、各級(jí)模塊分布式操作。下面分別介紹各級(jí)模塊中算法的執(zhí)行過(guò)程。

2.1 輸入級(jí)模塊

每個(gè)輸入端口有N個(gè)VOQ隊(duì)列，對(duì)應(yīng)交換網(wǎng)絡(luò)的N個(gè)輸出端口。由輸入端口IP(i,g)去往輸出端口OP(j,h)的信元入隊(duì)VOQ(i,g,j,h)。輸入級(jí)模塊內(nèi)，當(dāng)j=(i+t)%M時(shí)，輸入端口i在時(shí)隙t與輸出端口j相連。

輸入端口發(fā)送隊(duì)列的選擇：

(1)每M個(gè)時(shí)隙，每個(gè)輸入端口以輪詢方式在VOQ(i,g,j,h)中尋找滿幀隊(duì)列。

(2)若不存在這樣的 VOQ，則在非空隊(duì)列中尋找最長(zhǎng)隊(duì)列。不失一般性，假設(shè)對(duì)于輸入端口IP(i,g),VOQ(i,g,j′,h′)是最長(zhǎng)隊(duì)列，L′為CM(0)中CQ(i,0,j′,h′)的長(zhǎng)度。進(jìn)行下面的判斷，若L′＜TC，則調(diào)度VOQ(i,g,j′,h′)，否則，不調(diào)度。之所以取CM(0)的隊(duì)列狀態(tài)是因?yàn)?IM 將業(yè)務(wù)均勻擴(kuò)展，每幀時(shí)隙結(jié)束時(shí)各中間級(jí)的隊(duì)列狀態(tài)一致。

輸入端口將選中隊(duì)列的分組發(fā)送到中間模塊，并始終從CM(0)開始，隨后按照遞增的方式，直到CM(M-1)。當(dāng)服務(wù)一個(gè)非滿幀時(shí)，若沒有分組，則發(fā)送一個(gè)填充分組；否則，發(fā)送存儲(chǔ)的分組。幀長(zhǎng)為F的非滿幀，0＜F＜M，需插入M-F個(gè)填充分組。

2.2 中間級(jí)模塊

由IM(i)經(jīng)由CM(r)去往OP(j,h)的信元，進(jìn)入交叉點(diǎn)緩存CQ(i,r,j,h)，如圖 2。每個(gè)輸出端口一個(gè)調(diào)度器，在一個(gè)幀時(shí)隙中，依次調(diào)度去往OM不同輸出端口的分組。如：每一幀時(shí)隙的第k個(gè)時(shí)隙(1≤k≤M)，在CQ(i,r,j,k-1)(其中0≤i≤M-1)中以最早信元優(yōu)先(Oldest Cell First, OCF)方式選擇一個(gè)去往OP(j,k-1)的分組。若相應(yīng)的隊(duì)列中均沒有分組，則不發(fā)送。由于CM間相互獨(dú)立，為保證各CM調(diào)度結(jié)果一致，啟動(dòng)時(shí)需要依次錯(cuò)開時(shí)隙。

2.3 輸出級(jí)模塊

每個(gè)輸入端口有M個(gè)VOPQ(Virtual Output Port Queue)，對(duì)應(yīng)M個(gè)輸出端口。由輸入端口r去往輸出端口h的信元，入隊(duì)VOPQ(r,j,h)。輸出級(jí)模塊內(nèi)，若r滿足r=(h+t)%M，輸入端口r在時(shí)隙t與輸出端口h相連。這種配置方式保證每個(gè)輸出端口在讀取數(shù)據(jù)時(shí)，由CM(0)開始，并遞增到CM(M-1)。輸出端口接收到真分組，則將分組發(fā)送往輸出線卡，若是填充分組，則丟棄。

3 算法穩(wěn)定性及復(fù)雜度分析

3.1 穩(wěn)定性

下面通過(guò)對(duì)采用EPF算法的MMM交換和理想輸出排隊(duì)(OQ)交換進(jìn)行比較，證明 EPF算法可達(dá)100%吞吐率。其中，OQ交換在實(shí)現(xiàn)時(shí)輸出端口需要N倍緩存加速，而EPF算法沒有緩存加速的要求。

引理1對(duì)于一個(gè)工作守恒(work-conserving)服務(wù)器，令A(yù)(t)和D(t)分別表示截止時(shí)刻t到達(dá)和離開分組的累積和，服務(wù)器每時(shí)隙服務(wù)一個(gè)分組。則對(duì)于任意t≥0，有

引理1在文獻(xiàn)[13]中有證明。

定理1不管是何種業(yè)務(wù)到達(dá)過(guò)程，EPF算法具有與理想輸出排隊(duì)交換相同的吞吐率。

證明不失一般性，假設(shè)只有輸出端口k，且t=0 時(shí)隊(duì)列中沒有分組。定義下面的變量：

Ak(t)(Bk(t))：在t時(shí)刻，MMM交換的輸入級(jí)(中間級(jí))輸入端口去往目的端口k的累積到達(dá)分組數(shù)。

Ck(t)：時(shí)刻t時(shí)，MMM交換的輸出級(jí)輸出端口k的累積離開分組數(shù)。

圖2 CM(r)交換單元隊(duì)列結(jié)構(gòu)

由于離開分組的累積數(shù)目不大于到達(dá)分組的累積數(shù)目，很容易得到

觀察每個(gè)輸入，從滿幀的最后一個(gè)分組到達(dá)時(shí)刻開始直到下一次這個(gè) VOQ被調(diào)度，可能有至多M-1個(gè)時(shí)隙。另外，每個(gè)時(shí)隙只有一個(gè)輸入端口可以發(fā)送分組到第 1個(gè)中間輸入，因此一個(gè) VOQ隊(duì)列從被調(diào)度到實(shí)際得到服務(wù)，經(jīng)歷的最大時(shí)延為M-1個(gè)時(shí)隙。

首先證明輸入級(jí)輸入隊(duì)列的隊(duì)長(zhǎng)是有界的。注意每個(gè)輸入最多有N(M-1)個(gè)分組沒有滿幀。而一個(gè)滿幀的出現(xiàn)使得輸入端口開始服務(wù)分組(時(shí)延界為M-1+M-1=2M-2)；因此，每個(gè)輸入的最大分組數(shù)為N(M-1)+2M-2=MN-N+2M-2，開始服務(wù)后這個(gè)數(shù)目不會(huì)再增加。從而，所有輸入最多有N(MN-N+2M-2)=MN2-N2+2MN-2N個(gè)分組去往輸出端口k。令C1=MN2-N2+2MN-2N，則

現(xiàn)在證明若輸入過(guò)程由Bk(t)給出，則后兩級(jí)交換與理想工作守恒服務(wù)器的累計(jì)離開分組數(shù)的差別是有限的；再結(jié)合式(2)，可得出這樣的結(jié)論：在輸入由Ak(t)給出時(shí)，采用EPF算法的MMM交換和理想OQ交換在服務(wù)上的區(qū)別是有限的。

以每一幀時(shí)隙為單位，觀察后兩級(jí)緩存狀態(tài)。以IM(i)為例，若CM(0)的第i個(gè)輸入去往輸出端口k的分組數(shù)目不大于TC-1，則IM(i)的每個(gè)輸入將有機(jī)會(huì)在接下來(lái)M個(gè)時(shí)隙內(nèi)發(fā)送M個(gè)分組(真分組或填充分組)去往中間級(jí)。而CM在接下來(lái)M個(gè)時(shí)隙中，每個(gè)輸出端口至少離開1個(gè)分組。因此對(duì)于經(jīng)過(guò)相同CM去往輸出端口k的分組，在這一幀時(shí)隙內(nèi)增加M2-1個(gè)，結(jié)果為(TC-1)M+M2-1。因而這一幀時(shí)隙結(jié)束時(shí)，經(jīng)過(guò)M個(gè)CM去往k的積壓分組數(shù)目為M3+(TC-1)M2-M。令C2=M3+(TC-1)M2-M。這意味著當(dāng)(t)≥C2時(shí)，交換將只發(fā)送滿幀到中間模塊。

在每個(gè)時(shí)刻t, MMM交換只可能是下面兩種狀態(tài)：

因此，由式(1)，引理1和式(2)，有

并且由于OQ交換可以模擬單位交換能力的工作守恒服務(wù)器，存在

因此，對(duì)于式(3)有

進(jìn)入式(4)的唯一路徑是經(jīng)過(guò)式(3)，當(dāng)?shù)竭_(dá)新狀態(tài)的第1個(gè)時(shí)隙，式(5)仍然成立。這之后，輸入級(jí)交換不再產(chǎn)生填充分組，只服務(wù)中間級(jí)和輸出級(jí)隊(duì)列中剩下的分組。因此經(jīng)過(guò)M個(gè)CM去往k的填充分組總數(shù)至多為(M.2+TC.M.-M.-1)(M.-1)。定義C3=M.3+(TC-1)M.2-TC.M+1。

因此，對(duì)于滿足式(4)的任何時(shí)刻，采用引理1和式(2)：

從而

綜合式(6)和式(7)，EPF算法與理想OQ交換在服務(wù)的分組數(shù)目上相差常數(shù)個(gè)，可得出結(jié)論：不管是何種到達(dá)過(guò)程，采用EPF算法的MMM交換與理想OQ交換具有相同吞吐率。 證畢

3.2 復(fù)雜度

輸入級(jí)和輸出級(jí)交換網(wǎng)絡(luò)按照固定周期性的配置輪轉(zhuǎn)，與傳統(tǒng)負(fù)載均衡交換類似，只是輪轉(zhuǎn)周期由兩級(jí)交換網(wǎng)絡(luò)的N減小為M，時(shí)間復(fù)雜度為O(1)。

輸入級(jí)模塊選擇發(fā)送隊(duì)列時(shí)，每輸入端口首先需要在N個(gè)VOQ中輪詢滿幀分組，輪詢尋找的時(shí)間復(fù)雜度為O(lgN)。若沒有滿幀，則需要尋找最長(zhǎng)非空隊(duì)列。采用比較樹電路來(lái)實(shí)現(xiàn)，將會(huì)產(chǎn)生O(lgN)的門時(shí)延。接下來(lái)需要判定L′＜TC是否滿足。實(shí)際上IM不需要知道L′的值，只需要知道閾值是否達(dá)到。由于只有CM(0)更新L′值，所有輸入模塊需要能夠訪問該值，因此線卡之間的通信僅需要一個(gè)共享總線，廣播M×N比特矢量，表示是否閾值已達(dá)到。這個(gè)實(shí)時(shí)讀取需要O(1)時(shí)間。由于每幀只需一次更新，線卡之間的通信以線速的1/M發(fā)生。

中間級(jí)輸出端口調(diào)度器需要在M個(gè)隊(duì)列中以O(shè)CF方式選擇一個(gè)分組發(fā)送，采用比較樹電路來(lái)實(shí)現(xiàn)，將產(chǎn)生O(lgM)的門時(shí)延。

綜上，EPF算法最高時(shí)間復(fù)雜度為O(lgN)，比較樹電路最高門時(shí)延為O(lgN)。

4 仿真結(jié)果

本節(jié)基于網(wǎng)絡(luò)仿真系統(tǒng)OPNET對(duì)EPF算法的性能進(jìn)行評(píng)估。對(duì)比項(xiàng)為采用 PF算法的負(fù)載均衡兩級(jí)交換，采用 SRRD[14](Static Round-Robin Dispatching)算法的MSM交換，以及采用MMM-IM算法的 MMM 交換。仿真過(guò)程統(tǒng)計(jì)了各算法在Bernoulli均勻業(yè)務(wù)，突發(fā)均勻業(yè)務(wù)和不均衡業(yè)務(wù)下的性能。輸入和輸出都是可允許業(yè)務(wù)。交換網(wǎng)絡(luò)的規(guī)模為N=16和N=64，對(duì)于Clos網(wǎng)絡(luò)，分別對(duì)應(yīng)C(4,4,4)和C(8,8,8)。每輸入端口的業(yè)務(wù)負(fù)載定義為λ, 0≤λ≤1。則由輸入i去往輸出j的業(yè)務(wù)到達(dá)速率ai,j(0≤ai,j≤1)定義如下：

其中ω為不均衡系數(shù)，0≤ω≤1。Bernoulli均勻業(yè)務(wù)每個(gè)時(shí)隙以λ的概率產(chǎn)生分組，分組目的地址在N個(gè)輸出端口間均勻分布。突發(fā)均勻業(yè)務(wù)由 ON/OFF源來(lái)模擬，突發(fā)長(zhǎng)度服從指數(shù)分布，平均突發(fā)長(zhǎng)度設(shè)置為16，一次突發(fā)中的目的地址相同。

4.1 中間緩存閾值對(duì)性能的影響

為考察閾值TC對(duì)于 EPF算法性能的影響，對(duì)不同負(fù)載下時(shí)延性能與閾值變化的關(guān)系進(jìn)行了仿真。仿真結(jié)果如圖3所示。閾值長(zhǎng)度為0時(shí)只能發(fā)送滿幀分組，因此低負(fù)載業(yè)務(wù)時(shí)延較大，如λ=0.05。對(duì)于中等負(fù)載業(yè)務(wù)，如λ=0.5，時(shí)延隨著閾值的增加呈凹函數(shù)變化。閾值由0增加后，分組等待成幀的時(shí)延減少；閾值繼續(xù)增加，越來(lái)越多的非滿幀得到發(fā)送機(jī)會(huì)，填充分組數(shù)目增加，造成交換網(wǎng)絡(luò)內(nèi)的實(shí)際交換負(fù)載接近滿負(fù)載，時(shí)延增加。選擇合適的閾值，對(duì)交換網(wǎng)絡(luò)的性能有重要影響。從圖3中，交換網(wǎng)絡(luò)C(4,4,4)和C(8,8,8)在TC=2時(shí)中等負(fù)載業(yè)務(wù)具有較小時(shí)延。下面的仿真中若沒有特別說(shuō)明，EPF和PF均取TC=2 。

4.2 填充分組占有比例

為考察輸入級(jí)填充分組的產(chǎn)生與輸入負(fù)載，交換規(guī)模的關(guān)系，統(tǒng)計(jì)了Bernoulli均勻業(yè)務(wù)下處于穩(wěn)定狀態(tài)后，較長(zhǎng)時(shí)間段內(nèi)產(chǎn)生的填充分組數(shù)目。NT和NF分別表示輸出端口處統(tǒng)計(jì)到的真分組和填充分組的數(shù)目，縱坐標(biāo)η=NF(NF+NT)。由圖4可看出，當(dāng)閾值TC增加，更多非滿幀得到發(fā)送機(jī)會(huì)，從而產(chǎn)生更大比例的填充分組。填充比例η最大為(M-1)/M，也就是說(shuō)低負(fù)載時(shí)填充分組的比例隨著CM數(shù)目的增加而增加。在PF算法中，這一比例為(N-1)/N。

4.3 均勻業(yè)務(wù)時(shí)的性能

圖5為Bernoulli均勻業(yè)務(wù)下各方案的端到端時(shí)延性能。由圖5中可以看出，PF算法即使在低負(fù)載下時(shí)延仍然很高。EPF算法時(shí)延低于PF算法，但是比SRRD和MMM-IM算法的時(shí)延高。另外，由于幀長(zhǎng)與交換網(wǎng)絡(luò)規(guī)模有關(guān)，PF算法和EPF算法的時(shí)延隨著交換規(guī)模的增加而大幅增加，SRRD算法和MMM-IM算法則受交換規(guī)模的影響較小。

圖6給出了突發(fā)業(yè)務(wù)下各算法的仿真結(jié)果。對(duì)于PF和EPF方案，一次突發(fā)意味著形成滿幀的概率增大，因此在突發(fā)低負(fù)載時(shí)的性能甚至優(yōu)于Bernoulli均勻業(yè)務(wù)時(shí)的性能。EPF方案受突發(fā)業(yè)務(wù)的影響較小，高負(fù)載時(shí)的時(shí)延性能優(yōu)于其它方案。

4.4 不均勻業(yè)務(wù)時(shí)的性能

圖7為不均勻業(yè)務(wù)下各算法的吞吐率結(jié)果?；谪?fù)載均衡的兩類算法 PF和 EPF，能達(dá)到接近100%的吞吐率。而SRRD算法和MMM-IM算法的最低吞吐率分別為75%和90%。

圖3 不同閾值下的時(shí)延性能

圖4 填充分組占有比例

圖5 Bernoulli均勻業(yè)務(wù)下算法的時(shí)延性能

圖6 突發(fā)業(yè)務(wù)下算法的時(shí)延性能(N=64)

圖7 不均勻業(yè)務(wù)下的吞吐率(N=64)

5 結(jié)束語(yǔ)

本文提出了基于幀填補(bǔ)技術(shù)的MMM Clos網(wǎng)絡(luò)的按序分組交換算法(EPF)，通過(guò)增加填充分組使非滿幀隊(duì)列構(gòu)成滿幀，EPF算法避免了Clos網(wǎng)絡(luò)中分組亂序問題和低負(fù)載下的饑餓問題。EPF算法采用分布式控制，具有復(fù)雜度低，不需要緩存加速的特點(diǎn)。線卡間需要共享的信息以1/M線速的速率交互，不會(huì)對(duì)高速交換的實(shí)現(xiàn)產(chǎn)生重要影響。分析和仿真結(jié)果表明在輸入輸出可允許業(yè)務(wù)下，EPF算法可達(dá)100%吞吐率。但相比于Clos網(wǎng)絡(luò)傳統(tǒng)的調(diào)度算法，EPF算法在均勻業(yè)務(wù)下的時(shí)延較高，設(shè)計(jì)具有更優(yōu)時(shí)延性能的MMM Clos網(wǎng)絡(luò)算法將作為本文的后續(xù)研究工作。

[1]Chao H J, Jing Z G, and Liew S Y. Matching algorithms for three-stage bufferless Clos network switches[J].IEEE Communications Magazine, 2003, 41(10): 46-54.

[2]楊君剛, 鮑民權(quán), 劉增基, 等. 一種具有信元保序能力的Clos網(wǎng)絡(luò)分布式調(diào)度算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(3): 467-475.

Yang Jun-gang, Bao Min-quan, Liu Zeng-ji,et al.. A distributed scheduling algorithm maintaining cells order for three-stage Clos networks [J].Chinese Journal of Computers,2008, 31(3): 467-475.

[3]Chao H J, Jinsoo P, Artan S,et al.. TrueWay: a highly scalable multi-plane multi-stage buffered packet switch [C].Workshop on High Performance Switching and Routing,Hong Kong, 2005: 246-253.

[4]Dong Z Q, Rojas C R, Oki E,et al.. Memory-memorymemory Clos-network packet switches with in-sequence service[C]. Conference on High Performance Switching and Routing, Cartagena, 2011: 121-125.

[5]Chang C S, Lee D S, and Jou Y S. Load balanced Birkhoff-von Neumann switches, Part I: one-stage buffering[J].Computer Communications, 2002, 25(6):611-622.

[6]Keslassy I, Chuang S T, Yu K,et al.. Scaling internet routers using optics[J].Computer Communication Review, 2003,33(4): 189-200.

[7]Jaramillo J J, Milanf F, Srikant R,et al.. Padded frames: a novel algorithm for stable scheduling in load-balanced switches[J].IEEE/ACM Transactions on Networking, 2008,16(5): 1212-1225.

[8]Yu C L, Chang C S, Lee D S,et al.. CR: a load-balanced switch with contention and reservation[J].IEEE/ACM Transactions on Networking, 2009, 17(5): 1659-1671.

[9]Hu B and Yeung K L. Feedback-based scheduling for loadbalanced two-stage switches[J].IEEE/ACM Transactions on Networking, 2010, 18(4): 1077-1090.

[10]Lin B and Keslassy I. The concurrent matching switch architecture[J].IEEE/ACM Transactions on Networking,2010, 18(4): 1330-1343.

[11]申志軍, 曾華燊, 高志江. 一種改進(jìn)的反饋制兩級(jí)交換結(jié)構(gòu)FTSA-2-SS[J]. 電子與信息學(xué)報(bào), 2011, 33(6): 1319-1325.

Shen Zhi-jun, Zeng Hua-shen, and Gao Zhi-jiang. An improved feedback-based two-stage switch architecture using 2-staggered symmetry connection pattern[J].Journal of Electronics&Information Technology, 2011, 33(6):1319-1325.

[12]Shi L, Liu B, Sun C,et al.. Load-balancing multipath switching system with flow slice[J].IEEE Transactions on Computers, 2012, 61(3): 350-365.

[13]Chang C S. Performance Guarantees in Communication Networks[M]. New York: Springer-Verlag, 2000: 6-7.

[14]Konghong P and Hamdi M. Static round-robin dispatching schemes for Clos-network switches[C]. Workshop on High Performance Switching and Routing, Kobe, 2002: 329-333.