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

孫 倩 許 都

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

1 引言

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

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

目前對Clos網(wǎng)絡(luò)結(jié)構(gòu)的研究，主要根據(jù)構(gòu)成交換網(wǎng)絡(luò)的交換模塊是否具有緩存能力而分為兩類：無緩存和有緩存Clos交換結(jié)構(gòu)。對于前者，典型的SSS (Space-Space-Space)Clos網(wǎng)絡(luò)已大量應(yīng)用于包交換[5,6]，同時有學(xué)者提出可以將無緩存的Clos網(wǎng)絡(luò)應(yīng)用于數(shù)據(jù)中心網(wǎng)絡(luò)[7]；對于后者，在傳統(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ò)性能。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 級間鏈路繁忙概率分析

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

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

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

方法2 母函數(shù)法

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

令

其中a,b是正整數(shù)，t表示鏈路容量，m表示中間級數(shù)目。求出f1(x)中xB的系數(shù)為C1,f2(x)中xB-t的系數(shù)為C2，則所要求的某個鏈路忙的概率是，空閑的概率：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對鏈路復(fù)用的概率是

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

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

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

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

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

n2條中間級-輸出級鏈路忙的概率：

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

4 仿真及分析

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

Yang模型適用于基于Crossbar的空分Clos網(wǎng)絡(luò)的分析，這類網(wǎng)絡(luò)每一級都不具備時隙調(diào)整能力。圖4是兩種模型下同等配置下的Clos網(wǎng)絡(luò)阻塞率分析結(jié)果。從圖中的分析結(jié)果可以看出，基于Crossbar的空分 Clos網(wǎng)絡(luò)的阻塞率明顯高于基于 TST的Clos網(wǎng)絡(luò)，同時三級時隙可調(diào)的 Clos網(wǎng)絡(luò)的阻塞率比傳統(tǒng)的線路交換網(wǎng)絡(luò)的阻塞率下降的更快。當(dāng)然這是以犧牲硬件復(fù)雜度為代價的，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é)果的對照圖，鏈路利用率α=0.9；從圖中可以看出阻塞率隨著中間級規(guī)模的增大迅速下降。隨著中間級規(guī)模的增大，阻塞率變小就意味著配通率的增大，重構(gòu)次數(shù)的降低。分析結(jié)果稍大于仿真結(jié)果，也可以說分析模型保守地估計了網(wǎng)絡(luò)的阻塞率；但兩結(jié)果相差不大且保持著相同的趨勢說明分析模塊有著良好的精度。

下面考查鏈路容量t對阻塞率的影響。圖6所示是網(wǎng)絡(luò)C(20,20,20,t),α=0.9，阻塞率隨鏈路容量t的變化圖。圖7所示是網(wǎng)絡(luò) C(20,21,20,t),α=0 .9，阻塞率隨鏈路容量t的變化圖。從兩圖都可以看出，隨著鏈路容量的增加，阻塞率呈下降趨勢。是因?yàn)殡S著鏈路容量t的增加，pslot呈下降趨勢，并且當(dāng)m＞n時，pslot呈下降的更快，比較圖6，圖7，可以得出：當(dāng)m＞n時阻塞率隨鏈路容量下降比m=n時更快，在我們所配置的網(wǎng)絡(luò)中，阻塞率下降為0；即當(dāng)鏈路利用率α=0.9，網(wǎng)絡(luò)C(20,21,20,t)在足夠大的鏈路容量下可以將業(yè)務(wù)全部配通。所以在構(gòu)建交換網(wǎng)絡(luò)時，如果能提供冗余的交換模塊將會極大地降低重排次數(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)中間級規(guī)模m＞n時，阻塞率下降得更快，當(dāng)中間級規(guī)模m=n+d,d是一個很小的非負(fù)整數(shù)；配通率就可以達(dá)到100%。m=n時Clos網(wǎng)絡(luò)是可重排無阻塞網(wǎng)絡(luò)，但重排會引入噪聲和誤碼；在可靠性要求很高的場合，可采用MTS-Clos結(jié)構(gòu)，只需增加少量中間級就使網(wǎng)絡(luò)無阻塞。

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

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

[1]代曉慧.對十二五期間信息通信業(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.