面向數(shù)據(jù)中心的多級(jí)交換網(wǎng)絡(luò)性能分析與優(yōu)化

高 雅，潘偉濤，鄭 凌

(1.無(wú)錫職業(yè)技術(shù)學(xué)院 物聯(lián)網(wǎng)技術(shù)學(xué)院，江蘇 無(wú)錫 214121；2.西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071)

0 引 言

Clos結(jié)構(gòu)多級(jí)交換網(wǎng)絡(luò)由于其模塊化、可擴(kuò)展的特點(diǎn)，成為數(shù)據(jù)中心交換網(wǎng)絡(luò)的重要解決方案[1]。在Clos交換網(wǎng)絡(luò)的中間級(jí)設(shè)置緩存，如中間級(jí)和輸出級(jí)有緩存交換(space-memory-memory，SMM)或各級(jí)有緩存交換(memory-memory-memory，MMM)，能夠有效避免各級(jí)無(wú)緩存交換或輸入輸出級(jí)有緩存交換[2]中復(fù)雜的匹配調(diào)度和緩存加速問(wèn)題，具有更加靈活的可擴(kuò)展性。然而，中間級(jí)緩存的存在會(huì)引起輸出端口信元亂序，可通過(guò)復(fù)雜的背壓反饋[3]、逐幀調(diào)度[4,5]、模擬輸出排隊(duì)交換[6,7]等方法控制亂序信元產(chǎn)生，或者在輸出端口進(jìn)行亂序重排[8]。從已有文獻(xiàn)的研究成果可看出，增加各級(jí)模塊的緩存大小能夠提高吞吐率，但同時(shí)會(huì)加劇亂序程度。各級(jí)模塊的緩存大小具體如何影響交換網(wǎng)絡(luò)的吞吐率和時(shí)延性能，最大重排時(shí)延以及重排緩存的規(guī)模受哪些參數(shù)影響，給定重排緩存規(guī)模時(shí)各級(jí)模塊內(nèi)的緩存大小如何設(shè)置以獲得最優(yōu)性能等問(wèn)題仍未解決。本文對(duì)以SMM結(jié)構(gòu)為代表的中間級(jí)有緩存的Clos交換網(wǎng)絡(luò)(central-stage buffered switch，CBS)的性能進(jìn)行了研究。通過(guò)理論分析和仿真驗(yàn)證的方法研究了中間級(jí)和輸出級(jí)緩存規(guī)模對(duì)CBS交換吞吐率和時(shí)延性能的影響，給出了定性和定量的分析。同時(shí)，推導(dǎo)了最大重排時(shí)延以及重排所需緩存大小，并比較了不同緩存配置下的平均重排緩存時(shí)延性能，得到有限條件約束下性能最優(yōu)時(shí)的配置參數(shù)。

1 交換網(wǎng)絡(luò)模型與參數(shù)

圖1所示為中間級(jí)有緩存的Clos交換網(wǎng)絡(luò)。第一級(jí)有k個(gè)輸入模塊(input module，IM)，每個(gè)輸入模塊為n×m的無(wú)緩存Crossbar交換單元，其中k=N/n，N為交換網(wǎng)絡(luò)端口數(shù)。第二級(jí)為m個(gè)中間級(jí)模塊(central module，CM)，每個(gè)CM為k×k的交叉點(diǎn)有緩存Crossbar交換(crosspoint-queued，CQ)，來(lái)自IM(i)到達(dá)CM(r)目的模塊為OM(j)的信元入隊(duì)XBC(r,i,j)。第三級(jí)為k個(gè)輸出級(jí)模塊(output module，OM)，每個(gè)OM為m×n的CQ交換，經(jīng)由CM(r)到達(dá)OM(j)需去往第h+1個(gè)輸出端口的信元入隊(duì)XBO(j,r,h)。CM和OM中交叉點(diǎn)緩存規(guī)模分別為KC和KO。其中0≤i,j≤k-1，0≤r≤m-1，0≤h≤n-1。通常將上述Clos網(wǎng)絡(luò)記為C(m,n,k)。為討論方便，取m=n=MO，同時(shí)令k=MC。

圖1 CBS交換結(jié)構(gòu)

變長(zhǎng)分組被切割成定長(zhǎng)信元，傳輸一個(gè)定長(zhǎng)信元所需時(shí)間稱(chēng)為一個(gè)時(shí)隙。CBS交換網(wǎng)絡(luò)的輸入級(jí)采用固定的周期性輪轉(zhuǎn)配置，每n個(gè)時(shí)隙輪轉(zhuǎn)一次；中間級(jí)和輸出級(jí)采用CQ交換單元，各模塊輸出端口采用隨機(jī)調(diào)度或輪詢調(diào)度算法。信元在離開(kāi)輸出級(jí)模塊后進(jìn)入重排緩存隊(duì)列(re-sequencing queue，RQ)。

2 理論分析

2.1 吞吐率性能的統(tǒng)計(jì)平均值

由于CBS交換的后兩級(jí)模塊均為CQ結(jié)構(gòu)，首先基于馬爾科夫鏈模型計(jì)算CQ交換的吞吐率性能的統(tǒng)計(jì)平均值，然后根據(jù)獲得的結(jié)果進(jìn)一步計(jì)算CBS交換的吞吐率性能。

令M為CQ交換的端口數(shù)，B為一個(gè)交叉點(diǎn)緩存可容納的信元數(shù)。每個(gè)時(shí)隙的開(kāi)始為信元到達(dá)階段，隨后為調(diào)度離開(kāi)階段。由輸入端口g到達(dá)需去往輸出端口h的信元，緩存在交叉點(diǎn)Qg,h；若緩存已滿，則該信元被丟棄。在一列交叉點(diǎn)緩存中，即{Qg,h|0≤g≤M-1}， 輸出端口h隨機(jī)選擇一個(gè)非空緩存進(jìn)行調(diào)度。定義d(t)為一個(gè)交叉點(diǎn)緩存被調(diào)度的概率。在Bernoulli i.i.d。均勻到達(dá)業(yè)務(wù)下建立CQ交換模型，每個(gè)時(shí)隙每個(gè)輸入端口有信元到達(dá)的概率為ρ，每個(gè)交叉點(diǎn)緩存有信元到達(dá)的概率為ρ/M。

令πj(t)表示在第t個(gè)時(shí)隙結(jié)束時(shí)交叉點(diǎn)緩存Qg,h包含j個(gè)信元的穩(wěn)態(tài)概率，如圖2所示。由于每個(gè)交叉點(diǎn)緩存有B+1個(gè)狀態(tài)，將這B+1個(gè)穩(wěn)態(tài)概率表示成列向量S(t)，即S(t)=(π0(t),π1(t),…,πB(t))T。 假設(shè)被觀察緩存的狀態(tài)只依賴(lài)于其前一個(gè)時(shí)隙的狀態(tài)。

圖2 基于單個(gè)交叉點(diǎn)緩存狀態(tài)的馬爾科夫鏈模型

狀態(tài)轉(zhuǎn)移矩陣P是 (B+1)×(B+1) 非負(fù)實(shí)數(shù)方陣，其中的元素pi,j表示交叉點(diǎn)緩存從前一個(gè)狀態(tài)πi(t-1)轉(zhuǎn)移到狀態(tài)πj(t)的概率，0≤pi,j≤1，0≤i,j≤B。接下來(lái)，可通過(guò)迭代計(jì)算的方式獲得穩(wěn)態(tài)概率的值

(1)

即

S(t)=PS(t-1)

(2)

首先初始緩存為空，即t=0時(shí)

π0(0)=1

(3)

πj(0)=0，1≤j≤B

(4)

由于一個(gè)交叉點(diǎn)每個(gè)時(shí)隙最多到達(dá)一個(gè)信元，最多離開(kāi)一個(gè)信元，因此對(duì)于j>i+1或者j

當(dāng)i=0時(shí)

(5)

(6)

如p0,0反映了交叉點(diǎn)緩存狀態(tài)變化的兩種情況，分別是到達(dá)一個(gè)信元且被調(diào)度離開(kāi)，以及沒(méi)有信元到達(dá)。p0,1則表示有信元到達(dá)，且未被調(diào)度的概率。

當(dāng)1≤i≤B-1時(shí)

(7)

(8)

(9)

當(dāng)i=B時(shí)

pB,B-1=d(t)

(10)

pB,B=1-d(t)

(11)

為簡(jiǎn)化離開(kāi)狀態(tài)的模型，假設(shè)同一個(gè)輸出鏈路的交叉點(diǎn)緩存具有相同的狀態(tài)分布。非空交叉點(diǎn)緩存被調(diào)度的概率d(t)與同一個(gè)輸出線上其它緩存的狀態(tài)相關(guān)。若除外還有i-1個(gè)非空緩存，則該緩存能夠發(fā)送隊(duì)首信元的概率為1/i。而一個(gè)緩存在調(diào)度期間為空的概率為π0(t-1)(1-ρ/M)。 基于上述描述以及全概率公式[9]，離開(kāi)概率表示為

(12)

由于輸入業(yè)務(wù)的均勻性和交換網(wǎng)絡(luò)的對(duì)稱(chēng)性，可通過(guò)考察同一輸出端口的一列交叉點(diǎn)緩存的性能來(lái)表示整個(gè)交換網(wǎng)絡(luò)的性能[9,10]。當(dāng)同一個(gè)輸出線的所有緩存為空時(shí)，該輸出端口不會(huì)調(diào)度信元。因此歸一化的相對(duì)吞吐率TCQ可通過(guò)下式計(jì)算出

(13)

當(dāng)t趨于無(wú)限，將獲得吞吐率性能的穩(wěn)定結(jié)果。也就是說(shuō)最終TCQ是CQ交換端口數(shù)M，交叉點(diǎn)緩存規(guī)模B和輸入負(fù)載ρ的函數(shù)，表示為T(mén)CQ=f(M,B,ρ)。

CBS交換的后兩級(jí)交換單元，可以分別看作兩個(gè)CQ交換，其中后一個(gè)CQ交換的輸入為前一個(gè)CQ交換的輸出負(fù)載。這里假設(shè)進(jìn)入輸出級(jí)模塊的均勻業(yè)務(wù)是符合Bernoulli i.i.d.過(guò)程的。因此CBS交換的相對(duì)吞吐率TCBS表示為

TCBS=TCM·TOM=
f(MC,KC,ρ)·f(MO,KO,ρf(MC,KC,ρ))

(14)

2.2 重排緩存規(guī)模

亂序程度可通過(guò)最大重排緩存時(shí)延和平均重排緩存時(shí)延這兩個(gè)指標(biāo)來(lái)衡量。只有當(dāng)各路徑上的緩存為有限規(guī)模，且信元等待調(diào)度的時(shí)延存在上限，才能獲得重排緩存時(shí)延的上限值。

定義來(lái)自IM(i)的第g+1個(gè)輸入端口需要去往OM(j) 的第h+1個(gè)輸出端口的一系列信元為流(i,g,j,h)。CQ交換的各輸出端口采用輪詢調(diào)度算法。圖3(a)給出了與流(i,g,j,h)相關(guān)的多條路徑上的信元緩存及調(diào)度情況。同一個(gè)流的連續(xù)信元在多條路徑上經(jīng)歷時(shí)延不一致會(huì)產(chǎn)生亂序。

圖3 信元亂序及重排緩存

在CBS交換中，假設(shè)信元最快在1個(gè)時(shí)隙內(nèi)經(jīng)過(guò)輸入級(jí)模塊、中間級(jí)模塊和輸出級(jí)模塊，以及重排緩存模塊，進(jìn)入輸出鏈路。如圖中信元2，在由輸入級(jí)模塊輪轉(zhuǎn)到CM(1) 后緊接著被調(diào)度去往輸出級(jí)模塊，并在輸出級(jí)模塊獲得同樣的待遇。由于早于信元2的信元1還未到達(dá)輸出端口，因此信元2只能在重排緩存模塊中等待。而信元1進(jìn)入中間級(jí)后，需要至多等待MCKC個(gè)時(shí)隙才能被調(diào)度，進(jìn)入輸出級(jí)模塊后，同樣需要等待MOKO個(gè)時(shí)隙。此時(shí)信元2已在重排隊(duì)列中等待MCKC+MOKO-1個(gè)時(shí)隙。也就是說(shuō)最差情況下重排時(shí)延為MCKC+MOKO個(gè)時(shí)隙。

CBS交換的輸出端口設(shè)置有逐流重排緩存，每個(gè)重排緩存由一個(gè)可容納w個(gè)信元的圓形隊(duì)列實(shí)現(xiàn)[11]。重排緩存維護(hù)一個(gè)指針，用于記錄下一個(gè)期待接收的按序信元的序列號(hào)。具體工作流程如下：

(1)新到達(dá)的信元將按照序列號(hào)(sequence number，SN)取模的方式(即：SNmodw)被安置到相應(yīng)位置，如圖3(b)中信元4被安排在緩存4號(hào)位。

(2)若新到達(dá)的信元恰好是指針指向位置的被期待信元，則該信元將被調(diào)度發(fā)往輸出線卡，如圖中指針指向位置需要等待信元1，而信元2已經(jīng)緩存在重排緩存模塊中。同時(shí)按序指針更新至下一位。

(3)若指針指向位置已有信元到達(dá)，表明該信元也是按序的，將隨著按序指針的更新逐個(gè)發(fā)送出去。

(4)最終，按序指針將指向被期待的空信元位置。

由于信元除了要等待序列號(hào)小于自己的信元到達(dá)重排緩存，還需要等待被逐個(gè)調(diào)度離開(kāi)重排緩存。因此重排緩存的每個(gè)隊(duì)列需要容納至少2MCKC+2MOKO個(gè)信元才能保證沒(méi)有信元在等待重排和調(diào)度時(shí)被丟棄，即取ω=2MCKC+2MOKO。

由于每個(gè)輸出端口需要維護(hù)N個(gè)重排隊(duì)列，因此對(duì)于整個(gè)多級(jí)交換網(wǎng)絡(luò)而言，需要的重排緩存規(guī)模為2N2(MCKC+MOKO)。

3 仿真驗(yàn)證

基于OPNET網(wǎng)絡(luò)仿真系統(tǒng)，分別仿真了不同中間級(jí)模塊和輸出級(jí)模塊緩存大小、不同輸入負(fù)載ρ、不同交換規(guī)模的CBS交換網(wǎng)絡(luò)，統(tǒng)計(jì)了業(yè)務(wù)在不同模塊中的時(shí)延和吞吐率性能，如中間級(jí)模塊、輸出級(jí)模塊和重排緩存模塊，以及CBS交換的整體性能，并與理論分析值進(jìn)行了比較。到達(dá)業(yè)務(wù)為Bernoulli i.i.d.的均勻業(yè)務(wù)，輸入和輸出都是可允許業(yè)務(wù)。仿真時(shí)長(zhǎng)為200 000個(gè)時(shí)隙。

3.1 緩存分布對(duì)性能的影響

圖4比較了ρ=1時(shí)C(4,4,4)的CBS交換吞吐率性能的仿真值和理論值。中間級(jí)和輸出級(jí)模塊的歸一化相對(duì)吞吐率，理論值均略高于仿真值，總吞吐率ThCBS累積了這部分誤差，最大誤差約為2.70%(發(fā)生在KC=4，KO=4時(shí))，但總體趨勢(shì)一致。CBS交換的吞吐率ThCBS不會(huì)超過(guò)中間級(jí)和輸出級(jí)模塊吞吐率的最低值。單獨(dú)提高中間級(jí)和輸出級(jí)模塊的緩存大小，ThCBS提高。對(duì)于給定的KO，ThOM隨著KC的增加而降低。這是因?yàn)橹虚g級(jí)模塊可緩存的信元越多，吞吐率性能提高，則進(jìn)入輸出級(jí)模塊的業(yè)務(wù)量越大，丟包率提高。

圖4 不同緩存規(guī)模時(shí)吞吐率性能的仿真值與理論值

如圖5所示，信元在中間級(jí)模塊、輸出級(jí)模塊和重排緩存模塊中經(jīng)歷的時(shí)延被分別統(tǒng)計(jì)，共同組成信元的端到端時(shí)延。隨著KC的增大，信元在中間級(jí)模塊中的時(shí)延、重排時(shí)延增加，并造成端到端時(shí)延呈線性增加。相比而言，輸出級(jí)模塊中緩存規(guī)模的增加，不會(huì)對(duì)中間級(jí)模塊中的時(shí)延產(chǎn)生影響，且輸出級(jí)模塊和重排緩存模塊中的時(shí)延增幅遠(yuǎn)低于前一種情況。由此可看出，緩存在中間級(jí)和輸出級(jí)模塊中不同的數(shù)量會(huì)影響到平均重排時(shí)延的大小，并影響到端到端的時(shí)延。在最大重排緩存時(shí)延MCKC+MOKO相等的條件下，KO較大的平均端到端時(shí)延較小。如圖5所示，KC=64，KO=4時(shí)的端到端時(shí)延要遠(yuǎn)高于KC=4，KO=64時(shí)的端到端時(shí)延。

圖5 各級(jí)模塊的緩存大小對(duì)時(shí)延性能的影響

3.2 交換規(guī)模和業(yè)務(wù)負(fù)載對(duì)性能的影響

為比較不同交換規(guī)模對(duì)吞吐率和時(shí)延性能的影響，分別仿真了C(4,4,4)和C(8,8,8)的CBS交換在不同緩存規(guī)模時(shí)吞吐率和時(shí)延性能隨輸入負(fù)載變化的情況。時(shí)延和吞吐率性能隨著交換規(guī)模的增加均有所提高。從圖6可看出對(duì)于KC=1且KO=1的CBS交換網(wǎng)絡(luò)，增加輸出級(jí)模塊中的緩存數(shù)目(如：KC=1，KO=4)比增加中間級(jí)模塊中的緩存(如：KC=4，KO=1)能更有效地提高吞吐率，且端到端時(shí)延增量更小。

圖6 不同交換規(guī)模和輸入負(fù)載對(duì)性能的影響

3.3 已知重排緩存規(guī)模時(shí)的優(yōu)化設(shè)置

為考察在給定重排緩存規(guī)模時(shí)，中間級(jí)和輸出級(jí)模塊內(nèi)的緩存大小如何設(shè)置，仿真了在KC+KO=8限制下不同KC和KO組合的CBS交換網(wǎng)絡(luò)，其中N=16，ρ=1。如圖7 所示，從獲得的吞吐率性能看，當(dāng)KC和KO值相近時(shí)，可以獲得吞吐率最高值。而端到端時(shí)延則幾乎是遞增狀態(tài)。中間級(jí)模塊中的時(shí)延隨著KC的增加而線性遞增，而輸出級(jí)模塊中的時(shí)延首先隨著到達(dá)輸出級(jí)模塊的信元增加呈上升趨勢(shì)，最后，由于KO減少，時(shí)延下降。

圖7 給定重排緩存規(guī)模時(shí)緩存大小對(duì)性能的影響

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

各級(jí)模塊的緩存規(guī)模對(duì)時(shí)延和吞吐率性能的作用并非簡(jiǎn)單的線性關(guān)系，緩存的大小和分布，對(duì)交換網(wǎng)絡(luò)的性能具有重要影響。本文基于理論分析和仿真驗(yàn)證的方式研究了多級(jí)交換網(wǎng)絡(luò)各參數(shù)對(duì)性能的影響。得出結(jié)論如下：

(1)各級(jí)模塊中交叉點(diǎn)緩存規(guī)模最小的模塊其吞吐率決定了交換網(wǎng)絡(luò)吞吐率的上限。

(2)增加各級(jí)緩存規(guī)模有利于提高吞吐率，但同時(shí)會(huì)增加端到端時(shí)延，以及所需的重排緩存規(guī)模；其中增加輸出級(jí)模塊的緩存規(guī)模要優(yōu)于增加中間級(jí)模塊的緩存規(guī)模。

(3)中間級(jí)和輸出級(jí)模塊的端口數(shù)以及交叉點(diǎn)緩存的大小共同決定了所需重排緩存的規(guī)模；對(duì)于重排緩存規(guī)模已知的情況，合理設(shè)置中間級(jí)和輸出級(jí)模塊的緩存大小可以達(dá)到吞吐率的最優(yōu)值。

本文的研究為設(shè)計(jì)與實(shí)現(xiàn)面向數(shù)據(jù)中心應(yīng)用的多級(jí)交換網(wǎng)絡(luò)提供了重要的理論依據(jù)。