面向數據中心的多級交換網絡性能分析與優化

2018-07-19 12:53:12潘偉濤

計算機工程與設計 2018年7期

高雅，潘偉濤，鄭凌

(1.無錫職業技術學院物聯網技術學院，江蘇無錫 214121；2.西安電子科技大學綜合業務網國家重點實驗室，陜西西安 710071)

0 引言

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

1 交換網絡模型與參數

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

圖1 CBS交換結構

變長分組被切割成定長信元，傳輸一個定長信元所需時間稱為一個時隙。CBS交換網絡的輸入級采用固定的周期性輪轉配置，每n個時隙輪轉一次；中間級和輸出級采用CQ交換單元，各模塊輸出端口采用隨機調度或輪詢調度算法。信元在離開輸出級模塊后進入重排緩存隊列(re-sequencing queue，RQ)。

2 理論分析

2.1 吞吐率性能的統計平均值

由于CBS交換的后兩級模塊均為CQ結構，首先基于馬爾科夫鏈模型計算CQ交換的吞吐率性能的統計平均值，然后根據獲得的結果進一步計算CBS交換的吞吐率性能。

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

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

圖2 基于單個交叉點緩存狀態的馬爾科夫鏈模型

狀態轉移矩陣P是 (B+1)×(B+1) 非負實數方陣，其中的元素pi,j表示交叉點緩存從前一個狀態πi(t-1)轉移到狀態πj(t)的概率，0≤pi,j≤1，0≤i,j≤B。接下來，可通過迭代計算的方式獲得穩態概率的值

(1)

即

S(t)=PS(t-1)

(2)

首先初始緩存為空，即t=0時

π0(0)=1

(3)

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

(4)

由于一個交叉點每個時隙最多到達一個信元，最多離開一個信元，因此對于j>i+1或者j

當i=0時

(5)

(6)

如p0,0反映了交叉點緩存狀態變化的兩種情況，分別是到達一個信元且被調度離開，以及沒有信元到達。p0,1則表示有信元到達，且未被調度的概率。

當1≤i≤B-1時

(7)

(8)

(9)

當i=B時

pB,B-1=d(t)

(10)

pB,B=1-d(t)

(11)

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

(12)

由于輸入業務的均勻性和交換網絡的對稱性，可通過考察同一輸出端口的一列交叉點緩存的性能來表示整個交換網絡的性能[9,10]。當同一個輸出線的所有緩存為空時，該輸出端口不會調度信元。因此歸一化的相對吞吐率TCQ可通過下式計算出

(13)

當t趨于無限，將獲得吞吐率性能的穩定結果。也就是說最終TCQ是CQ交換端口數M，交叉點緩存規模B和輸入負載ρ的函數，表示為TCQ=f(M,B,ρ)。

CBS交換的后兩級交換單元，可以分別看作兩個CQ交換，其中后一個CQ交換的輸入為前一個CQ交換的輸出負載。這里假設進入輸出級模塊的均勻業務是符合Bernoulli i.i.d.過程的。因此CBS交換的相對吞吐率TCBS表示為

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

(14)

2.2 重排緩存規模

亂序程度可通過最大重排緩存時延和平均重排緩存時延這兩個指標來衡量。只有當各路徑上的緩存為有限規模，且信元等待調度的時延存在上限，才能獲得重排緩存時延的上限值。

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

圖3 信元亂序及重排緩存

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

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

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

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

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

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

由于信元除了要等待序列號小于自己的信元到達重排緩存，還需要等待被逐個調度離開重排緩存。因此重排緩存的每個隊列需要容納至少2MCKC+2MOKO個信元才能保證沒有信元在等待重排和調度時被丟棄，即取ω=2MCKC+2MOKO。

由于每個輸出端口需要維護N個重排隊列，因此對于整個多級交換網絡而言，需要的重排緩存規模為2N2(MCKC+MOKO)。

3 仿真驗證

基于OPNET網絡仿真系統，分別仿真了不同中間級模塊和輸出級模塊緩存大小、不同輸入負載ρ、不同交換規模的CBS交換網絡，統計了業務在不同模塊中的時延和吞吐率性能，如中間級模塊、輸出級模塊和重排緩存模塊，以及CBS交換的整體性能，并與理論分析值進行了比較。到達業務為Bernoulli i.i.d.的均勻業務，輸入和輸出都是可允許業務。仿真時長為200 000個時隙。

3.1 緩存分布對性能的影響

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

圖4 不同緩存規模時吞吐率性能的仿真值與理論值

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

圖5 各級模塊的緩存大小對時延性能的影響

3.2 交換規模和業務負載對性能的影響

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

圖6 不同交換規模和輸入負載對性能的影響

3.3 已知重排緩存規模時的優化設置

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