Clos網(wǎng)絡(luò)中的組播路由算法

1、Clos網(wǎng)絡(luò)中的組播路由算法摘要：對(duì)于三級(jí)Clos網(wǎng)絡(luò)，扇出機(jī)制會(huì)影響Clos網(wǎng)絡(luò)的阻塞率、算法的時(shí)間復(fù)雜度及網(wǎng)絡(luò)成本，因此選擇好的扇出方式能充分發(fā)揮網(wǎng)絡(luò)的組播能力。根據(jù)輸出級(jí)扇出、中間級(jí)扇出、輸入級(jí)扇出等不同的扇出機(jī)制分類，可將組播算法分為輸入級(jí)扇由算法(IFMA)、最遲扇由算法(LFMA)、切割扇出算法(SFMA)、中間級(jí)優(yōu)先扇出算法(CMFFMA)。在對(duì)4種算法仿真比較的基礎(chǔ)上，文章提出針對(duì)不同的業(yè)務(wù)采用不同的處理方法的路由方案，對(duì)于固定扇出業(yè)務(wù)可采用CMFFMA算法進(jìn)行路由，針對(duì)遞增業(yè)務(wù)采用先輸出級(jí)、再中間級(jí)、最后輸入級(jí)扇出的策略，可有效地降低阻塞率。關(guān)鍵詞：Clos網(wǎng)絡(luò)；組播；路由算

2、法；扇出隨著寬帶技術(shù)的不斷發(fā)展，視頻點(diǎn)播、遠(yuǎn)程教學(xué)、新聞發(fā)布、網(wǎng)絡(luò)電視等業(yè)務(wù)成為新一輪運(yùn)營競爭的焦點(diǎn)，它們的特點(diǎn)是，信息由一個(gè)服務(wù)器向大量的客戶端發(fā)布。組播技術(shù)非常適合這類業(yè)務(wù)，并具有如下優(yōu)點(diǎn)：服務(wù)器不必知道某個(gè)客戶端是否存在，它只負(fù)責(zé)按多播地址將媒體流發(fā)送出去，即使有成千上萬個(gè)客戶端，也僅發(fā)送一份即可；客戶端如果希望接收某媒體流服務(wù)器的數(shù)據(jù)，只需加入該媒體流服務(wù)器播放數(shù)據(jù)使用的組播組即可1。目前智能光網(wǎng)絡(luò)的發(fā)展要求節(jié)點(diǎn)設(shè)備的交叉矩陣具有容量高、快速的端口配置和組播支持能力，組播業(yè)務(wù)根據(jù)目的節(jié)點(diǎn)數(shù)的不同，可以分為單播、組播和廣播3種類型2單播是指待轉(zhuǎn)發(fā)的消息在傳送網(wǎng)中要求實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)的傳輸，廣播

3、業(yè)務(wù)是指在傳送網(wǎng)中把待轉(zhuǎn)發(fā)的一個(gè)消息從源節(jié)點(diǎn)轉(zhuǎn)發(fā)到傳送網(wǎng)的全部輸出端口上，而組播業(yè)務(wù)是則把消息轉(zhuǎn)發(fā)到傳送網(wǎng)中的一組輸出端口上。從廣義上來講，單播和廣播是組播的一個(gè)特例。根據(jù)組播請(qǐng)求的多個(gè)目的輸出端口的產(chǎn)生時(shí)間，可以把組播分為兩類3：第一類是固定扇出業(yè)務(wù)，所有的目的輸出端口是在請(qǐng)求一開始就確定；第二類是遞增業(yè)務(wù)，它的目的端口遞增，是不確定的。1 Clos網(wǎng)絡(luò)的組播業(yè)務(wù)為了支持網(wǎng)絡(luò)中的組播業(yè)務(wù)，網(wǎng)絡(luò)中的核心設(shè)備交換設(shè)備也應(yīng)當(dāng)具有組播功能。Clos網(wǎng)絡(luò)自提出以來4由于其低成本、易大規(guī)模實(shí)現(xiàn)，在交換設(shè)備中得到了廣泛的應(yīng)用。圖1為一個(gè)對(duì)稱的三級(jí)Clos網(wǎng)絡(luò)，用n表示輸入輸出模塊的端口數(shù)量，N表示總的輸入

4、端口數(shù)，f表示扇出值，m表示中間模塊的數(shù)量，r表示輸入和輸出模塊的數(shù)量，則一個(gè)三級(jí)Clos網(wǎng)絡(luò)可以表示為C(n,m,r)。如果用Ip表示輸入端口，Pi表示輸出端口，那么一個(gè)組播請(qǐng)求可表示為(Ip：P1，P2Pk)。對(duì)稱白三級(jí)Clos網(wǎng)絡(luò)在任意級(jí)有扇由功能的組播嚴(yán)格無阻塞的條件為m>min(n-1)f+n,(N-1)f,N5,而且對(duì)于任意一個(gè)組播嚴(yán)格無阻塞網(wǎng)絡(luò)，需要的開關(guān)數(shù)最少為O(N2)6，但是在實(shí)際應(yīng)用中并不需要達(dá)到嚴(yán)格無阻塞就可以有很好的性能。1.1 Clos網(wǎng)絡(luò)扇出機(jī)制對(duì)于三級(jí)Clos網(wǎng)絡(luò)，不同的扇出機(jī)制不但影響Clos網(wǎng)絡(luò)的阻塞率，而且影響算法的時(shí)間復(fù)雜度及網(wǎng)絡(luò)成本，因此選擇好的

5、扇出方式才能充分發(fā)揮網(wǎng)絡(luò)的組播能力。以下將對(duì)Clos網(wǎng)絡(luò)各級(jí)扇出的性能特點(diǎn)進(jìn)行分析。(1) 輸出級(jí)扇出輸出級(jí)扇出指輸出級(jí)模塊具有扇出功能，如果輸出級(jí)具有扇出功能，那么對(duì)于同一個(gè)業(yè)務(wù)源到一個(gè)輸出模塊中的多個(gè)輸出端口只需要經(jīng)過一個(gè)中間模塊，否則有多少輸出端口就需要經(jīng)過多少個(gè)中間模塊，在三級(jí)Clos網(wǎng)絡(luò)中路由分配主要就是中間級(jí)模塊的分配，因此必須降低對(duì)中間級(jí)模塊的需求，而第三級(jí)扇出可以降低對(duì)中間級(jí)模塊的要求，所以采用第三級(jí)扇出可以有效的降低阻塞率，這樣我們就可以將一個(gè)組播請(qǐng)求由原來的端口表示(Ip:P1,P2Pk)轉(zhuǎn)化成模塊表示(I:O1,O2Ok),其中I表示輸入模塊，Oi表示輸出模塊。(2) 中

6、間級(jí)扇出中間級(jí)扇出指中間級(jí)的模塊具有扇出功能。假如第一級(jí)沒有扇出功能，那么所有組播分支只能在一個(gè)中間級(jí)模塊進(jìn)行扇出，因此只有那些滿足所有扇出要求的中間交換單元才可以成功建立連接。所以在組播請(qǐng)求的扇出值很大的情況下，網(wǎng)絡(luò)的阻塞概率將會(huì)急劇上升，但是由于只使用一個(gè)中間模塊，可以避免外部阻塞的發(fā)生。(3) 輸入級(jí)扇出輸入級(jí)扇出指輸入級(jí)模塊具有扇出功能，可以從一個(gè)輸入端口到達(dá)不同的中間級(jí)模塊。如果第三級(jí)有扇出的話，那么組播請(qǐng)求要到達(dá)幾個(gè)輸出級(jí)模塊，就需要占用幾個(gè)中間級(jí)模塊。對(duì)于輸入級(jí)扇出可以將組播分解成不同的單播請(qǐng)求進(jìn)行處理，這樣可以利用單播中成熟的算法來進(jìn)行處理，實(shí)現(xiàn)簡單，而且可以降低內(nèi)部阻塞率。但

7、是由于每個(gè)組播請(qǐng)求只在第一級(jí)扇出，因此需要大量的中間模塊，容易出現(xiàn)外部阻塞問題。1.2 Clos網(wǎng)絡(luò)組播算法介紹Clos網(wǎng)絡(luò)中的組播算法性能主要受扇出機(jī)制的影響，這樣我們就根據(jù)扇出策略的不同將組播算法分為以下幾種。輸入級(jí)扇出算法(IFMA)7是基于輸入級(jí)扇出的算法，其主要思想是通過將一個(gè)扇出值為f的組播請(qǐng)求轉(zhuǎn)化成f個(gè)單播請(qǐng)求，然后按照單播請(qǐng)求的路由算法進(jìn)行路由，這樣在Clos網(wǎng)絡(luò)中每個(gè)組播請(qǐng)求只在輸入級(jí)進(jìn)行扇出，這樣可以將組播業(yè)務(wù)理解為多個(gè)相互獨(dú)立的單播業(yè)務(wù)，這樣就可以利用單播算法中的成熟算法。如圖1中的輸入端口0到輸出端口0、輸出端口4和輸出端口8的組播業(yè)務(wù)采用輸入級(jí)扇出方式，在輸入模塊IM

8、1中完成所有的扇出，分別經(jīng)過中間模塊CM1、CM2和CM3到不同的目的模塊。最遲扇出算法(LFMA)6是基于中間級(jí)扇出的算法，該算法的思想是只有在必須進(jìn)行扇出時(shí)才進(jìn)行扇出，即先在輸出級(jí)扇出再在中間級(jí)扇出。因此對(duì)于每一個(gè)組播請(qǐng)求只使用一個(gè)中間模塊，如圖1中輸入端口2中的請(qǐng)求(2：1，3，7)，只使用了一個(gè)中間模塊CM4。這兩種扇出機(jī)制都存在著自身的局限性，但是又有很強(qiáng)的互補(bǔ)性，因此將兩種扇出相結(jié)合的思想就應(yīng)運(yùn)而出。在三級(jí)Clos網(wǎng)絡(luò)中，內(nèi)部阻塞的產(chǎn)生主要是由于級(jí)間鏈路的競爭，如果沒有第三級(jí)扇出，那么每個(gè)組播請(qǐng)求在一個(gè)輸出模塊的每個(gè)輸出端口都要占用一個(gè)從中間級(jí)到輸出級(jí)的鏈路，否則只需要一個(gè)鏈路。同

9、樣，如果中間級(jí)沒有扇出，那么每一個(gè)子請(qǐng)求都要占用一條輸入模塊到中間模塊之間的鏈路，這樣就會(huì)出現(xiàn)外部阻塞。各種扇出機(jī)制各有優(yōu)缺點(diǎn)，可以結(jié)合使用。在在輸入級(jí)和輸出級(jí)同時(shí)扇出的機(jī)制中又可以根據(jù)不同的分配方式分為切分扇出算法及先中間級(jí)后輸入級(jí)算法兩種。切割扇由算法(SFMA)8是把目的輸由模塊進(jìn)行分組，分組數(shù)g為扇出值F和切割值s的比值向上取整，然后在進(jìn)行路由時(shí)在第一級(jí)就進(jìn)行扇出，即需要在第二級(jí)選擇g個(gè)可用的中間交換單元，然后再在第二級(jí)和中間級(jí)扇出機(jī)制一樣進(jìn)行同樣的處理。如圖1中輸入端口3的請(qǐng)求，如果按照切割算法理解的話其扇出值F為3，切割值s為2，分為兩組，一組通過中間模塊CM1路由，另一組通過中間

10、模塊CM2路由。最后一種算法是中間級(jí)優(yōu)先扇出算法(CMFFMA)9-10，利用盡量少的中間模塊完成扇出，即首先選擇一個(gè)可以建立盡量多扇出的中間單元，建立其到輸出模塊的連接。如果到全部輸出模塊的連接均建立完成則路由成功，否則將余下的尚未完成的連接繼續(xù)按照上一步的方法處理，利用其他中間級(jí)單元的扇出能力完成扇出。例如在圖1中，由于沒有一個(gè)中間模塊能夠滿足輸入端口3的所有扇出請(qǐng)求，因此通過CM1建立其中的兩條，然后再通過CM2建立剩余的連接。通過以上對(duì)扇出的分析，我們可以得到采用先中間級(jí)后輸入級(jí)算法的扇出機(jī)制是最優(yōu)的。與切割扇出機(jī)制相比，它少了盲目性，多了預(yù)先檢測性，可以在第一級(jí)進(jìn)行有目的扇出；與最遲

11、扇出機(jī)制相比，它又有很強(qiáng)的靈活性。1.3 Clos網(wǎng)絡(luò)組播算法仿真(1) 仿真條件采用OPNET軟件對(duì)不同的組播算法進(jìn)行仿真，仿真中的請(qǐng)求是按照占用-空閑源模式產(chǎn)生，即每個(gè)輸入端口有占用和空閑兩種狀態(tài)，占用狀態(tài)表示該輸入端口當(dāng)前存在一個(gè)鏈接，每種狀態(tài)的持續(xù)時(shí)間均服從指數(shù)分布，如果1/以表示占用的平均時(shí)間，1/人表示空閑的持續(xù)時(shí)間，那么在以輸入端的狀態(tài)判斷，網(wǎng)絡(luò)中的負(fù)載p1=1/u/1/u+1/入=入力+入，如果用f表示組播的平均扇出，Pptp表示業(yè)務(wù)中單播的比率，那么網(wǎng)絡(luò)中的實(shí)際負(fù)載p=(Pptp+(1-Pptp)xf)XpIo每個(gè)組播的扇出值按指數(shù)分布產(chǎn)生。(2) 仿真結(jié)果在具有組播業(yè)務(wù)的C

12、los網(wǎng)絡(luò)中網(wǎng)絡(luò)的阻塞率主要受組播業(yè)務(wù)的扇出值、組播比例和中間模塊數(shù)的影響，下面就分別進(jìn)行仿真分析。圖2是4種不同的算法在C(16,16,16)網(wǎng)絡(luò)規(guī)模、0.8負(fù)載以及單播比例為0.5時(shí)的阻塞率隨扇出值變化的曲線圖。從圖2中可以看出隨著扇出值的增加阻塞率會(huì)有所增加，但是當(dāng)扇出值達(dá)到一定值時(shí)，阻塞率將趨于穩(wěn)定，這是因?yàn)樵谪?fù)載固定、輸出級(jí)有扇出的情況下，隨著扇出值的增加請(qǐng)求數(shù)量會(huì)減少。同時(shí)由于輸出級(jí)具有扇出功能，而輸出級(jí)的模塊數(shù)固定，所以當(dāng)扇出值超出一定值后扇出的目的模塊數(shù)不會(huì)有太多的變化，因此在扇出值大于一定范圍后，阻塞則趨于穩(wěn)定。在這幾種算法里CMFFMA的阻塞率最低，因?yàn)樗纳瘸鲰樞蚴窍容敵?/p>

13、級(jí)、再中間級(jí)、最后輸入級(jí)，這樣可以最低限度地節(jié)約網(wǎng)絡(luò)中的鏈路資源，避免阻塞發(fā)生。圖3為C(16,16,16)的Clos網(wǎng)絡(luò)在負(fù)載為0.8時(shí)的阻塞率隨單播比例變化的仿真結(jié)果。從圖3中可以看出隨著單播比例的增加IFMA算法、SFMA和LFMA算法的阻塞率單調(diào)下降，而CMFFMA算法的阻塞率隨著單播比例的變化成拋物線狀，這是因?yàn)檫@兩種算法適宜于組播請(qǐng)求的建立，能夠最大程度的利用已有的空閑資源，因此在單播比例較低時(shí)網(wǎng)絡(luò)的阻塞率比較低，但是隨著單播比例的增加阻塞率會(huì)逐漸增加，當(dāng)?shù)竭_(dá)一定的比例時(shí)阻塞率又隨著單播比例的增加而下降，直到單播比例為1時(shí)，以上幾種算法的阻塞率均達(dá)到一個(gè)固定值。圖4為C(16,16

14、,16)規(guī)模的Clos網(wǎng)絡(luò)在0.8的負(fù)載，平均扇出值為8時(shí)及單播比例為0.5時(shí)各種算法的阻塞率隨中間模塊數(shù)的變化曲線。從圖4中可以看出隨著中間模塊數(shù)的增加，不同算法的阻塞率下降的速度不同，其中LFMA算法和IFMA算法的下降最緩慢，其他兩種算法的下降速度很快；而且在中間模塊數(shù)遠(yuǎn)小于嚴(yán)格無阻塞所需要的中間模塊數(shù)的情況下，Clos網(wǎng)絡(luò)的阻塞率可以下降到很低。從以上分析可知IFMA算法的阻塞率在所有算法中是最高的，這是因?yàn)樵撍惴ú捎幂斎爰?jí)扇出，組播業(yè)務(wù)的扇出均要在輸入級(jí)實(shí)現(xiàn)，這樣會(huì)造成很高的外部阻塞，而且占用的第一級(jí)鏈路數(shù)與第二級(jí)鏈路數(shù)相等。圖5為IFMA算法的阻塞率隨中間模塊數(shù)的變化趨勢，網(wǎng)絡(luò)規(guī)模

15、為C(16,m,16)，平均扇出值為8，負(fù)載為0.8，全組播業(yè)務(wù)。圖5中可以看出內(nèi)部阻塞率較小，故網(wǎng)絡(luò)的整體阻塞率主要由外部阻塞率決定。上面分析了在單、組播業(yè)務(wù)混合的情況下網(wǎng)絡(luò)的整體阻塞率，但是由于單播和組播業(yè)務(wù)的不同，其阻塞率不盡相同，圖6為不同算法隨單播比例變化對(duì)組播業(yè)務(wù)阻塞率的影響。從圖6中可以看出隨著單播比例的增加，組播業(yè)務(wù)的阻塞率單調(diào)遞增。其中，CMFFMA算法的阻塞率最低，這是由于其更好的利用了網(wǎng)絡(luò)中的空閑鏈路資源；IFMA算法采用輸入級(jí)扇出，所以單播比例的增加并沒有影響其可用的鏈路資源的減少，因此阻塞率的增長最慢。2 組播實(shí)現(xiàn)方案在對(duì)組播業(yè)務(wù)及常見算法的比較分析的基礎(chǔ)上，本文設(shè)計(jì)

16、出一種路由方案，針對(duì)不同的業(yè)務(wù)采用不同的處理方法。由于三級(jí)均有扇出的CMFFMA算法的阻塞率最低，因此對(duì)于固定扇出業(yè)務(wù)可以采用該算法進(jìn)行路由。針對(duì)遞增業(yè)務(wù)的特點(diǎn)，同時(shí)為了降低對(duì)鏈路資源的占用，采用先輸出級(jí)、再中間級(jí)、最后輸入級(jí)扇出的策略。由于遞增業(yè)務(wù)是在固定扇出業(yè)務(wù)的基礎(chǔ)上增加的業(yè)務(wù)，因此首先判斷是否可以在固定業(yè)務(wù)已占用的輸出模塊內(nèi)完成扇出，如果路由成功則退出；否則再判斷是否可以通過固定業(yè)務(wù)已經(jīng)占有的中間級(jí)模塊完成路由，如果成功則退出；否則采用輸入模塊進(jìn)行扇出，如果成功則退出；否則返回路由失敗。圖7為采用本方案后的C(16,16,16)規(guī)模的Clos網(wǎng)絡(luò)，在單播比例為0.5、負(fù)載為0.8、平均

17、扇出為8的時(shí)的阻塞率變化圖，其中遞增業(yè)務(wù)比例為遞增業(yè)務(wù)占組播業(yè)務(wù)的比例。由于遞增業(yè)務(wù)均是以單播的形式處理，而且對(duì)于遞增業(yè)務(wù)處理思想與固定組播業(yè)務(wù)類似，首先從輸出模塊進(jìn)行扇出、再中間模塊、最后輸入級(jí)，因此遞增業(yè)務(wù)的阻塞率接近于單播業(yè)務(wù)的阻塞率，而且隨著遞增業(yè)務(wù)量的增加，網(wǎng)絡(luò)的阻塞率無太大變化。3 結(jié)束語隨著單播比例的增加，網(wǎng)絡(luò)中的組播業(yè)務(wù)的阻塞率會(huì)隨之增加。其中，中間級(jí)優(yōu)先扇出算法要求輸入級(jí)和輸出級(jí)都要有扇出功能，充分利用了交叉矩陣中的鏈路資源，因此阻塞率最低。雖然組播嚴(yán)格無阻塞所需要的中間模塊數(shù)很多，但是在實(shí)際的應(yīng)用中并不需要很多就可以達(dá)到很低的阻塞率。而且在相同的條件下，隨著中間級(jí)模塊數(shù)量的

18、增加，輸入級(jí)和輸出級(jí)同時(shí)扇出的算法的阻塞率下降更快。對(duì)于遞增業(yè)務(wù)處理時(shí)可以按照組播扇出的思想進(jìn)行處理，這樣對(duì)整體網(wǎng)絡(luò)中的阻塞率無明顯影響。下一步的工作是將重排算法引入Clos網(wǎng)絡(luò)中的組播業(yè)務(wù)，通過對(duì)已建立的業(yè)務(wù)進(jìn)行重排來降低阻塞率。4 參考文獻(xiàn)1 SUNShutao,HESimin,ZHENGYanfeng,etal.MulticastschedulinginbufferedcrossbarswitcheswithmultipleinputqueuesC/Proceedingsof2005WorkshoponHighPerformanceSwitchingandRouting(HPSR05-1

19、),4M,2a0y0152,HongKong,China.Piscataway,NJ,USA:IEEE,2005:73-77.2 FUHunglin,HWANGFK.On3-stageClosnetworkswithdifferentnonblockingrequirementsontwotypesofcallsJ.JournalofCombinatorialOptimization,2005,9(3):263-266.3 HWANGFK,SHENG-CHYANGL.Onnonblockingmulticastthree-stageClosnetworksJ.IEEE/ACMTransacti

20、onsonNetworking,2000,8(4):535-539.4 CLOSC.Astudyofnon-blockingswitchingnetworkJ.BellSystemTechnicalJournal,1953,32(2):406-424.5 HWANGFK.Asurveyofnooblockingmulticastthree-stageClosnetworksJ.IEEECommunicationsMagazine,2003,41(10):34-37.6 FRIEDMANJ.Alowerboundonstrictlynon-blockingnetworkJ.Combinatorica,1988,8(2):185-188.7 PARKWon-Bae,HENRYL.Owenandellenwinezegura,SONET/SDHmulticastroutingalgorithmsinsymmetricalthreestagenetworksC/ProceedingsofInternationalConferenceonCommunications(ICC'95):Vol3,Jun18-22,1995,Seattle,WA,USA.Piscataway,NJ,USA:IEEE,1995:1912-1917.8 KimDS,DUDingzhu.P