基于幀填補的MMM Clos網(wǎng)絡按序分組交換算法

高 雅 邱智亮 張茂森 黎 軍

①(西安電子科技大學綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室 西安 710071)

②(空間微波技術國家重點實驗室 西安 710100)

1 引言

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

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

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

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

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

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

圖1 MMM Clos網(wǎng)絡交換結構

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

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

2.1 輸入級模塊

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

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

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

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

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

2.2 中間級模塊

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

2.3 輸出級模塊

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

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

3.1 穩(wěn)定性

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

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

引理1在文獻[13]中有證明。

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

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

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

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

圖2 CM(r)交換單元隊列結構

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

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

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

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

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

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

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

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

因此，對于式(3)有

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

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

從而

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

3.2 復雜度

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

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

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

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

4 仿真結果

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

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

4.1 中間緩存閾值對性能的影響

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

4.2 填充分組占有比例

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

4.3 均勻業(yè)務時的性能

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

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

4.4 不均勻業(yè)務時的性能

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

圖3 不同閾值下的時延性能

圖4 填充分組占有比例

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

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

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

5 結束語

本文提出了基于幀填補技術的MMM Clos網(wǎng)絡的按序分組交換算法(EPF)，通過增加填充分組使非滿幀隊列構成滿幀，EPF算法避免了Clos網(wǎng)絡中分組亂序問題和低負載下的饑餓問題。EPF算法采用分布式控制，具有復雜度低，不需要緩存加速的特點。線卡間需要共享的信息以1/M線速的速率交互，不會對高速交換的實現(xiàn)產(chǎn)生重要影響。分析和仿真結果表明在輸入輸出可允許業(yè)務下，EPF算法可達100%吞吐率。但相比于Clos網(wǎng)絡傳統(tǒng)的調度算法，EPF算法在均勻業(yè)務下的時延較高，設計具有更優(yōu)時延性能的MMM Clos網(wǎng)絡算法將作為本文的后續(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]楊君剛, 鮑民權, 劉增基, 等. 一種具有信元保序能力的Clos網(wǎng)絡分布式調度算法[J]. 計算機學報, 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]申志軍, 曾華燊, 高志江. 一種改進的反饋制兩級交換結構FTSA-2-SS[J]. 電子與信息學報, 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.