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ò)；組播；路由算法；扇出

Abstract:Fan-outmechanismwouldaffect the blocking probability of the three-stage Clos network, the time complexity of the algorithm and network costs. Good fan-out approach can give full play to the multicast capacity of the network. According to the output-stage fan-out, middle-stage fan-out, and input-stage fan-out mechanisms, multicast algorithms include Input Fan-out Multicast Algorithm (IFMA), Lazy Fan-out Multicast Algorithm (LFMA), Split Fan-out Multicast Algorithm (SFMA), and Central Module First Fan-out Multicast Algorithm (CMFFMA). Comparing the analyses of these four algorithms, this article proposes a routing scheme in which different businesses use different algorithms. Bundled traffic can adopt CMFFMA, and incremental traffic can route from output-stage through middle-stage to input-stage fan-out. Therefore, the blocking probability can be effectively reduced.

Keywords:Closnetwork;multicast; routing algorithm; fan out

隨著寬帶技術(shù)的不斷發(fā)展，視頻點(diǎn)播、遠(yuǎn)程教學(xué)、新聞發(fā)布、網(wǎng)絡(luò)電視等業(yè)務(wù)成為新一輪運(yùn)營(yíng)競(jìng)爭(zhēng)的焦點(diǎn)，它們的特點(diǎn)是，信息由一個(gè)服務(wù)器向大量的客戶端發(fā)布。組播技術(shù)非常適合這類業(yè)務(wù)，并具有如下優(yōu)點(diǎn)：服務(wù)器不必知道某個(gè)客戶端是否存在，它只負(fù)責(zé)按多播地址將媒體流發(fā)送出去，即使有成千上萬(wàn)個(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)的傳輸，廣播業(yè)務(wù)是指在傳送網(wǎng)中把待轉(zhuǎn)發(fā)的一個(gè)消息從源節(jié)點(diǎn)轉(zhuǎn)發(fā)到傳送網(wǎng)的全部輸出端口上，而組播業(yè)務(wù)是則把消息轉(zhuǎn)發(fā)到傳送網(wǎng)中的一組輸出端口上。從廣義上來(lái)講，單播和廣播是組播的一個(gè)特例。

根據(jù)組播請(qǐng)求的多個(gè)目的輸出端口的產(chǎn)生時(shí)間，可以把組播分為兩類[3]：第一類是固定扇出業(yè)務(wù)，所有的目的輸出端口是在請(qǐng)求一開(kāi)始就確定；第二類是遞增業(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ò)自提出以來(lái)[4]由于其低成本、易大規(guī)模實(shí)現(xiàn)，在交換設(shè)備中得到了廣泛的應(yīng)用。

圖1為一個(gè)對(duì)稱的三級(jí)Clos網(wǎng)絡(luò)，用n表示輸入輸出模塊的端口數(shù)量，N表示總的輸入端口數(shù)，f表示扇出值，m表示中間模塊的數(shù)量，r表示輸入和輸出模塊的數(shù)量，則一個(gè)三級(jí)Clos網(wǎng)絡(luò)可以表示為C(n, m, r)。如果用Ip表示輸入端口，Pi表示輸出端口，那么一個(gè)組播請(qǐng)求可表示為(Ip：P1，P2……Pk)。對(duì)稱的三級(jí)Clos網(wǎng)絡(luò)在任意級(jí)有扇出功能的組播嚴(yán)格無(wú)阻塞的條件為m≥min{(n -1)f +n,(N -1)f,N }[5]，而且對(duì)于任意一個(gè)組播嚴(yán)格無(wú)阻塞網(wǎng)絡(luò)，需要的開(kāi)關(guān)數(shù)最少為O(N 2)[6]，但是在實(shí)際應(yīng)用中并不需要達(dá)到嚴(yán)格無(wú)阻塞就可以有很好的性能。

1.1Clos網(wǎng)絡(luò)扇出機(jī)制

對(duì)于三級(jí)Clos網(wǎng)絡(luò)，不同的扇出機(jī)制不但影響Clos網(wǎng)絡(luò)的阻塞率，而且影響算法的時(shí)間復(fù)雜度及網(wǎng)絡(luò)成本，因此選擇好的扇出方式才能充分發(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)過(guò)一個(gè)中間模塊，否則有多少輸出端口就需要經(jīng)過(guò)多少個(gè)中間模塊，在三級(jí)Clos網(wǎng)絡(luò)中路由分配主要就是中間級(jí)模塊的分配，因此必須降低對(duì)中間級(jí)模塊的需求，而第三級(jí)扇出可以降低對(duì)中間級(jí)模塊的要求，所以采用第三級(jí)扇出可以有效的降低阻塞率，這樣我們就可以將一個(gè)組播請(qǐng)求由原來(lái)的端口表示(Ip：{P1，P2……Pk})轉(zhuǎn)化成模塊表示(I：{O1，O2   Ok})，其中I表示輸入模塊，Oi表示輸出模塊。

(2)中間級(jí)扇出

中間級(jí)扇出指中間級(jí)的模塊具有扇出功能。假如第一級(jí)沒(méi)有扇出功能，那么所有組播分支只能在一個(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)行處理，這樣可以利用單播中成熟的算法來(lái)進(jìn)行處理，實(shí)現(xiàn)簡(jiǎn)單，而且可以降低內(nèi)部阻塞率。但是由于每個(gè)組播請(qǐng)求只在第一級(jí)扇出，因此需要大量的中間模塊，容易出現(xiàn)外部阻塞問(wèn)題。