支持多時(shí)隙業(yè)務(wù)的MTS-Clos網(wǎng)絡(luò)結(jié)構(gòu)及其建模分析

孫 倩 許 都

(電子科技大學(xué)寬帶光纖傳感與通信教育部重點(diǎn)實(shí)驗(yàn)室 成都 611731)

1 引言

隨著網(wǎng)絡(luò)業(yè)務(wù)融合、移動(dòng)應(yīng)用、物聯(lián)網(wǎng)、云計(jì)算等新興戰(zhàn)略產(chǎn)業(yè)的發(fā)展，信息網(wǎng)絡(luò)基礎(chǔ)設(shè)施加速向?qū)拵诤?、泛在智能方向演進(jìn)。IP技術(shù)作為承載網(wǎng)的必然選擇，需要滿足高帶寬、多樣化的數(shù)據(jù)、語(yǔ)音、視頻等大量融合業(yè)務(wù)的傳輸與交換壓力[1]。特別是在核心網(wǎng)部分，IP網(wǎng)絡(luò)的流量和規(guī)模的膨脹發(fā)展，必然使得系統(tǒng)容量、端口速率等方面性能的提升成為急需解決的問(wèn)題。

當(dāng)交叉連接容量較大時(shí)，Clos矩陣[2,3]需要控制的交叉結(jié)點(diǎn)數(shù)量比平方矩陣(即Crossbar)大為減少[4]。同時(shí)，若Clos矩陣的中間級(jí)設(shè)為固定容量，則當(dāng)需要擴(kuò)容時(shí)僅需擴(kuò)大輸入級(jí)和輸出級(jí)的容量即可。這在很大程度上滿足了容量平滑增長(zhǎng)的要求，因此Clos矩陣是目前交叉連接設(shè)備的主流應(yīng)用矩陣。

目前對(duì)Clos網(wǎng)絡(luò)結(jié)構(gòu)的研究，主要根據(jù)構(gòu)成交換網(wǎng)絡(luò)的交換模塊是否具有緩存能力而分為兩類：無(wú)緩存和有緩存Clos交換結(jié)構(gòu)。對(duì)于前者，典型的SSS (Space-Space-Space)Clos網(wǎng)絡(luò)已大量應(yīng)用于包交換[5,6]，同時(shí)有學(xué)者提出可以將無(wú)緩存的Clos網(wǎng)絡(luò)應(yīng)用于數(shù)據(jù)中心網(wǎng)絡(luò)[7]；對(duì)于后者，在傳統(tǒng)共享緩存MMM(Memory-Memory-Memory)Clos結(jié)構(gòu)的基礎(chǔ)上，文獻(xiàn)[8]在近期提出了MMeM結(jié)構(gòu)，以克服MMM結(jié)構(gòu)下的隊(duì)頭阻塞[8]。此外，文獻(xiàn)[9]從理論和仿真方面研究了SMM(Space-Memory-Memory)Clos網(wǎng)絡(luò)在高速突發(fā)業(yè)務(wù)下的網(wǎng)絡(luò)性能。

對(duì)于一個(gè)交換結(jié)構(gòu)，其在一定網(wǎng)絡(luò)資源或規(guī)模下的阻塞率是其交換性能的關(guān)鍵表征參數(shù)。針對(duì)Clos交換結(jié)構(gòu)，經(jīng)典的概率分析模型有Lee模型[10]，Jacobaeus模型[11]和Yang模型[12]，這3個(gè)模型都是用來(lái)計(jì)算在隨機(jī)選路策略下三級(jí)Clos網(wǎng)絡(luò)的阻塞概率。其中Yang模型由于考慮了級(jí)間鏈路復(fù)用，故此其分析結(jié)果更為精確。 此外，文獻(xiàn)[13]利用了類似的分析方法，對(duì)Clos網(wǎng)絡(luò)的多播阻塞率進(jìn)行了深入的研究。

不同于傳統(tǒng)的Clos網(wǎng)絡(luò)，本文提出一種應(yīng)用于多時(shí)隙業(yè)務(wù)的三級(jí)Clos網(wǎng)絡(luò)，并對(duì)其阻塞性能進(jìn)行理論和仿真研究。多時(shí)隙業(yè)務(wù)是指輸入模塊接收的主要是SONET/SDH或OTN的數(shù)據(jù)流，此類數(shù)據(jù)流的特點(diǎn)是：高等級(jí)的數(shù)字信號(hào)系列可通過(guò)將低速率等級(jí)的模塊通過(guò)字節(jié)間插復(fù)用而成。同時(shí)，近期VLSI設(shè)計(jì)技術(shù)與半導(dǎo)體工藝水平的發(fā)展，也使得MTS-Clos(Multiple Time Slot Clos network)結(jié)構(gòu)的可實(shí)現(xiàn)性問(wèn)題得以解決，如Velio公司的VC2002芯片即可高密度地實(shí)現(xiàn)快速時(shí)隙交叉。針對(duì)這種多時(shí)隙多級(jí)Clos網(wǎng)絡(luò)結(jié)構(gòu)，目前尚沒有較為嚴(yán)格的理論分析模型可供參考，這使得基于傳統(tǒng)分析結(jié)論所進(jìn)行的工程應(yīng)用設(shè)計(jì)具有一定的盲目性。

本文第2節(jié)將給出基于多時(shí)隙交換的三級(jí)Clos網(wǎng)絡(luò)結(jié)構(gòu)MTS-Clos；在第3節(jié)對(duì)多時(shí)隙環(huán)境下的三級(jí)Clos網(wǎng)絡(luò)阻塞率分析模型進(jìn)行論述；第4節(jié)是數(shù)值仿真結(jié)果及分析計(jì)論；最后是結(jié)論。

2 基于TST的三級(jí)Clos結(jié)構(gòu)

傳統(tǒng)的三級(jí)對(duì)稱Clos交換結(jié)構(gòu)如圖1所示，其中一、三級(jí)是r個(gè)n×m的交換模塊，中間級(jí)是m個(gè)r×r的交換單元。根據(jù)網(wǎng)絡(luò)的阻塞特性可將其分為3類[4]，當(dāng)滿足m≥ 2n- 1時(shí)，是嚴(yán)格無(wú)阻塞網(wǎng)絡(luò)；當(dāng)滿足m≥n時(shí)，是可重排無(wú)阻塞網(wǎng)絡(luò)；第三是廣義無(wú)阻塞網(wǎng)絡(luò)。明顯地，嚴(yán)格無(wú)阻塞條件下的網(wǎng)絡(luò)硬件實(shí)現(xiàn)代價(jià)很高，這使得實(shí)際應(yīng)用中可重排無(wú)阻塞網(wǎng)絡(luò)成為首選。這類網(wǎng)絡(luò)中業(yè)務(wù)尋徑的性能主要決定于路由算法，而目前應(yīng)用中的路由算法普遍存在重排次數(shù)多、重排路徑長(zhǎng)等缺點(diǎn)。

鑒于此，我們提出一種新的結(jié)構(gòu)：即每一級(jí)不再是簡(jiǎn)單的空分結(jié)構(gòu)或是共享緩存交換結(jié)構(gòu)，而是由具有時(shí)分和空分功能的 TST(Time-Space-Time)構(gòu)成，我們稱具有n個(gè)輸入、m輸出端口，鏈路容量是t的TST的交叉規(guī)模是nt×mt。圖2是4個(gè)輸入端口，鏈路容量是4時(shí)隙的TST。圖中每個(gè)字母代表一個(gè)顆粒，即 SONET/SDH中的低速信號(hào)。由于低速信號(hào)是以字節(jié)間插方式復(fù)用進(jìn)高速信號(hào)的幀結(jié)構(gòu)中的，這樣低速信號(hào)在高速信號(hào)里的位置是固定的、有規(guī)律性，也就是有可預(yù)見性。這樣就能從高速信號(hào)中直接插/分出低速信號(hào)。

圖1 三級(jí)Clos網(wǎng)絡(luò)C(n,m,r)

MTS-Clos交換網(wǎng)絡(luò)結(jié)構(gòu)C(m,n,r,t)是如下結(jié)構(gòu)：輸入、輸出級(jí)是由r個(gè)交叉規(guī)模nt×mt的TST；中間級(jí)是m個(gè)交叉規(guī)模rt×rt的TST，如圖3所示。輸入級(jí)模塊可將大顆粒業(yè)務(wù)拆分成小顆粒(基本顆粒)，如將任意 STM-N的業(yè)務(wù)請(qǐng)求拆分成 STM-1請(qǐng)求，在網(wǎng)絡(luò)中獨(dú)立尋路，然后在輸出級(jí)模塊進(jìn)行時(shí)隙整合，恢復(fù)為原始大顆粒業(yè)務(wù)輸出。

3 多時(shí)隙環(huán)境下的阻塞率分析模型

現(xiàn)有的分析模型主要針對(duì)傳統(tǒng)的不具有多時(shí)隙交叉能力的 Clos網(wǎng)絡(luò)進(jìn)行阻塞率分析，在此基礎(chǔ)上，本節(jié)中對(duì)分析多時(shí)隙環(huán)境下MTS-Clos網(wǎng)絡(luò)的阻塞率進(jìn)行研究。

3.1 假設(shè)與符號(hào)定義

圖3 由TST構(gòu)成三級(jí)Clos交換網(wǎng)絡(luò)

定義1 如圖3所示網(wǎng)絡(luò)，所有模塊(輸入級(jí)、中間級(jí)、輸出級(jí))都具有時(shí)隙交叉能力。設(shè)鏈路容量為t時(shí)隙，定義這樣的網(wǎng)絡(luò)為MTS-C(m,n,r,t)。

定義2 輸入級(jí)第g個(gè)模塊的輸入端口定義為Ig={ig,i|i∈ { 1,…,n}}，其中g(shù)∈ { 1,…,r}。輸出級(jí)第h個(gè)模塊的輸出端口定義為Oh={oh,j|j∈ { 1,…,n}}，其中h∈ { 1,…,r}。

定義3 輸入級(jí)第g個(gè)模塊的第i個(gè)端口到輸出級(jí)第h個(gè)模塊的第j個(gè)端口的請(qǐng)求定義為C(ig,i,oh,j)。

定義4 請(qǐng)求C(ig,i,oh,j)到達(dá)之前，Ig模塊n1條鏈路忙，Oh模塊n2條鏈路忙。設(shè)n1,n2中有k對(duì)鏈路共用中間級(jí)，則稱為k-鏈路復(fù)用(k- overlapped)。

假設(shè) 1 每條鏈路繁忙的事件是相互獨(dú)立的。當(dāng)業(yè)務(wù)負(fù)荷不是很高、網(wǎng)絡(luò)規(guī)模較大時(shí)，該假設(shè)近似成立。

假設(shè) 2 每個(gè)時(shí)隙可以被隨機(jī)地分配到有空閑的中間級(jí)鏈路上，即負(fù)載均勻分布在所有鏈路上。設(shè)pslot∈[0,1]是級(jí)間鏈路忙的概率，qslot=1-pslot是級(jí)間鏈路空閑的概率。

假設(shè) 3 輸入級(jí)-中間級(jí)忙的鏈路與中間級(jí)-輸出級(jí)忙的鏈路，其概率分布函數(shù)服從二項(xiàng)式分布。

假設(shè) 4 外部輸入/輸出鏈路和內(nèi)部交叉鏈路的容量都是t個(gè)時(shí)隙，且交叉業(yè)務(wù)的帶寬需求是基本帶寬單元的倍數(shù)。帶寬需求β(1 ≤β≤t)個(gè)時(shí)隙的業(yè)務(wù)用β表示，定義β為交叉業(yè)務(wù)的倍數(shù)因子。假設(shè)當(dāng)前共有s個(gè)業(yè)務(wù)請(qǐng)求，第i請(qǐng)求的倍數(shù)因子是βi(1 ≤i≤s)。定義α為外部鏈路利用率。則α=

3.2 級(jí)間鏈路繁忙概率分析

方法1 求取方程整數(shù)解向量的個(gè)數(shù)

這種方法物理意義明確：方程1表示B個(gè)基本時(shí)隙需求，被隨機(jī)地分配在m條容量是t的鏈路上，其整數(shù)解向量的個(gè)數(shù)C1是B個(gè)基本時(shí)隙的選路方式。方程2表示B-t個(gè)基本時(shí)隙需求，被隨機(jī)地分配在m-1條容量是t的鏈路上。整數(shù)解向量的個(gè)數(shù)C2是B-t個(gè)基本時(shí)隙的選路方式。綜合上述兩式，則某條鏈路忙的概率是

上述兩方程可以用貪婪算法求解，但其運(yùn)算量與m成指數(shù)倍關(guān)系，當(dāng)m較大時(shí)，運(yùn)算量大，求解困難。

方法2 母函數(shù)法

假設(shè)存在m種物品，每個(gè)物品的個(gè)數(shù)都是t，這m種物品分別為x1,x2,…,xm；重集Q1={t?x1,t?x2,…,t?xm}。則上述方程1解向量的個(gè)數(shù)是求重集Q1的B排列數(shù)。由于每種物品最多可以選t種，故母函數(shù)是：f(x)=(1 +x+x2+…+xt)m。

令

其中a,b是正整數(shù)，t表示鏈路容量，m表示中間級(jí)數(shù)目。求出f1(x)中xB的系數(shù)為C1,f2(x)中xB-t的系數(shù)為C2，則所要求的某個(gè)鏈路忙的概率是，空閑的概率：qslot=1 -pslot。

3.3 網(wǎng)絡(luò)MTS-Clos(m,n,r,t)的阻塞率

引理1 滿足假設(shè)1,2,3,4，給定事件n1,n2，在MTS-Clos(m,n,r,t)中k對(duì)鏈路復(fù)用的概率是

其中k是鏈路復(fù)用的對(duì)數(shù)。

證明 在傳統(tǒng)Clos網(wǎng)絡(luò)中，此引理在文獻(xiàn)[12]已給出證明方法，實(shí)際上，在MTS-Clos(m,n,r,t)中的證明方法相同。

給定事件n1,n2,k對(duì)鏈路復(fù)用，則請(qǐng)求不被阻塞的條件是：n1+n2-k＜m。注意到k的值應(yīng)小于輸入模塊中忙的鏈路(n1)和輸出模塊中忙的鏈路(n2)，因此：k≤min {n1,n2}。因此，給定事件n1,n2，請(qǐng)求C(ig,i,oh,j)不被阻塞的概率是

根據(jù)假設(shè)1，

下面計(jì)算 P r{n1}和 P r{n2}，由假設(shè)2，假設(shè)3在網(wǎng)絡(luò)MTS-C(m,n,r,t)中，n1條輸入級(jí)-中間級(jí)鏈路忙的概率是：，但由于最多由n-1條輸入級(jí)-中間級(jí)鏈路忙，我們可得出更準(zhǔn)確的概率：

n2條中間級(jí)-輸出級(jí)鏈路忙的概率：

由式(6)-式(9)中，我們可以得出請(qǐng)求C(ig,i,oh,j)不被阻塞的概率為

4 仿真及分析

仿真平臺(tái)采用VC++編寫，網(wǎng)絡(luò)C(m,n,r,t)的所有參數(shù)均可配置，主要由業(yè)務(wù)生成模塊和業(yè)務(wù)處理模塊構(gòu)成。業(yè)務(wù)生成模塊用于生成合法業(yè)務(wù)請(qǐng)求，然后由業(yè)務(wù)處理模塊按照隨機(jī)策略分配中間級(jí)，如若不能配通，即計(jì)為一次阻塞。

Yang模型適用于基于Crossbar的空分Clos網(wǎng)絡(luò)的分析，這類網(wǎng)絡(luò)每一級(jí)都不具備時(shí)隙調(diào)整能力。圖4是兩種模型下同等配置下的Clos網(wǎng)絡(luò)阻塞率分析結(jié)果。從圖中的分析結(jié)果可以看出，基于Crossbar的空分 Clos網(wǎng)絡(luò)的阻塞率明顯高于基于 TST的Clos網(wǎng)絡(luò)，同時(shí)三級(jí)時(shí)隙可調(diào)的 Clos網(wǎng)絡(luò)的阻塞率比傳統(tǒng)的線路交換網(wǎng)絡(luò)的阻塞率下降的更快。當(dāng)然這是以犧牲硬件復(fù)雜度為代價(jià)的，Yang模型所適用的是空分的Clos網(wǎng)絡(luò)，這類網(wǎng)絡(luò)硬件復(fù)雜度比文中所提的基于TST的Clos網(wǎng)絡(luò)要小。

圖5是網(wǎng)絡(luò)C(m,20,20,4)的仿真結(jié)果和分析結(jié)果的對(duì)照?qǐng)D，鏈路利用率α=0.9；從圖中可以看出阻塞率隨著中間級(jí)規(guī)模的增大迅速下降。隨著中間級(jí)規(guī)模的增大，阻塞率變小就意味著配通率的增大，重構(gòu)次數(shù)的降低。分析結(jié)果稍大于仿真結(jié)果，也可以說(shuō)分析模型保守地估計(jì)了網(wǎng)絡(luò)的阻塞率；但兩結(jié)果相差不大且保持著相同的趨勢(shì)說(shuō)明分析模塊有著良好的精度。

下面考查鏈路容量t對(duì)阻塞率的影響。圖6所示是網(wǎng)絡(luò)C(20,20,20,t),α=0.9，阻塞率隨鏈路容量t的變化圖。圖7所示是網(wǎng)絡(luò) C(20,21,20,t),α=0 .9，阻塞率隨鏈路容量t的變化圖。從兩圖都可以看出，隨著鏈路容量的增加，阻塞率呈下降趨勢(shì)。是因?yàn)殡S著鏈路容量t的增加，pslot呈下降趨勢(shì)，并且當(dāng)m＞n時(shí)，pslot呈下降的更快，比較圖6，圖7，可以得出：當(dāng)m＞n時(shí)阻塞率隨鏈路容量下降比m=n時(shí)更快，在我們所配置的網(wǎng)絡(luò)中，阻塞率下降為0；即當(dāng)鏈路利用率α=0.9，網(wǎng)絡(luò)C(20,21,20,t)在足夠大的鏈路容量下可以將業(yè)務(wù)全部配通。所以在構(gòu)建交換網(wǎng)絡(luò)時(shí)，如果能提供冗余的交換模塊將會(huì)極大地降低重排次數(shù)。

圖4 兩種模型下的Clos網(wǎng)絡(luò)阻塞率分析結(jié)果

圖5 網(wǎng)絡(luò)C(m,20,20,4)的仿真與分析結(jié)果

圖6 網(wǎng)絡(luò)C(20,20,20,t)阻塞率隨t變化圖

5 結(jié)論

本文所提出的基于TST的Clos網(wǎng)絡(luò)，與基于Crossbar的空分 Clos網(wǎng)絡(luò)相比雖然在構(gòu)成上略為復(fù)雜，但在相同的網(wǎng)絡(luò)規(guī)模下，基于TST的Clos網(wǎng)絡(luò)的阻塞率更低；尤其特別的是當(dāng)中間級(jí)規(guī)模m＞n時(shí)，阻塞率下降得更快，當(dāng)中間級(jí)規(guī)模m=n+d,d是一個(gè)很小的非負(fù)整數(shù)；配通率就可以達(dá)到100%。m=n時(shí)Clos網(wǎng)絡(luò)是可重排無(wú)阻塞網(wǎng)絡(luò)，但重排會(huì)引入噪聲和誤碼；在可靠性要求很高的場(chǎng)合，可采用MTS-Clos結(jié)構(gòu)，只需增加少量中間級(jí)就使網(wǎng)絡(luò)無(wú)阻塞。

本文通過(guò)理論分析和仿真實(shí)驗(yàn)證明了 MTSClos網(wǎng)絡(luò)的阻塞率與鏈路容量成負(fù)相關(guān)：輸入鏈路容量和級(jí)間鏈路容量同時(shí)增加時(shí)，網(wǎng)絡(luò)的阻塞率隨之降低。該性質(zhì)是基于Crossbar的Clos網(wǎng)絡(luò)所不具備。

圖7 網(wǎng)絡(luò)C(20,21,20,t)阻塞率隨t變化圖

[1]代曉慧.對(duì)十二五期間信息通信業(yè)發(fā)展的思考[OL].www.c114.net/topic/2561/a570678.html,2010.12.

[2]Clos C.A study of non-blocking switching networks[J].The Bell System Technical Journal,1953,32(3): 406-424.

[3]Chao H J and Liu B.High Performance Switches and Routers[M].New Jersey: Wiley-IEEE Press,2007: 382-408.

[4]Benes V E.Mathematical Theory of Connecting Networks and Telephone Traffic[M].New York: Academic Press,1965:53-65.

[5]Dorren H J,Calabretta N,and Raz O.A 3-stage CLOS architecture for high-throughput optical packet switching[C].Communications and Photonics Conference and Exhibition(ACP),Shanghai,China,Nov.2-6,2009: 1-6.

[6]Oki Eiji,Kitsuwan Nattapong,and Rojas-Cessa R.Analysis of space-space-space Clos-network packet switch[C].2009 Proceedings of 18th International Conference on Computer Communications and Networks,San Francisco,CA,USA,Aug.3-6,2009: 1-6.

[7]Chao H J and Kang Xi.Bufferless optical Clos switches for data centers[C].Optical Fiber Communication Conference and Exposition (OFC/NFOEC),Los Angeles,CA,USA,March 6-10,2011: 1-3.

[8]Dong Zi-qian and Rojas-Cessa R.Non-blocking memorymemory-memory Clos-network packet switch[C].Sarnoff Symposium,Princeton,NJ,USA,2011: 1-5.

[9]Ruepp S,Rytlig A,and Manolova A V.Performance evaluation of 100 Gigabit Ethernet switches under bursty traffic[C].Optical Network Design and Modeling (ONDM),Bologna,Italy,Feb.8-10,2011: 1-6.

[10]Lee C Y.Analysis of switching networks[J].The Bell System Technical Journal,1955,34(6): 1287-1315.

[11]Jacobaeus C.A study of congestion in link system[J].Ericsson Techniques,1950,51(3): 1-68.

[12]Yang Y.An analytical model on network blocking probability[J].IEEE Communications Letters,1997,1(5):143-145.

[13]Pattavina A and Tesei G L.Modeling the blocking behavior of multicast Clos networks[C].INFOCOM 2003.Twenty-Second Annual Joint Conference of the IEEE Computer and Communications,IEEE Societies,San Francisco,CA,USA,2003,Vol.1: 756-763.