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

關(guān)鍵詞：Clos網(wǎng)絡(luò)；組播；路由算法；扇出

隨著寬帶技術(shù)的不斷發(fā)展，視頻點播、遠程教學(xué)、新聞發(fā)布、網(wǎng)絡(luò)電視等業(yè)務(wù)成為新一輪運營競爭的焦點，它們的特點是，信息由一個服務(wù)器向大量的客戶端發(fā)布。組播技術(shù)非常適合這類業(yè)務(wù)，并具有如下優(yōu)點：服務(wù)器不必知道某個客戶端是否存在，它只負(fù)責(zé)按多播地址將媒體流發(fā)送出去，即使有成千上萬個客戶端，也僅發(fā)送一份即可；客戶端如果希望接收某媒體流服務(wù)器的數(shù)據(jù)，只需加入該媒體流服務(wù)器播放數(shù)據(jù)使用的組播組即可[1]。

目前智能光網(wǎng)絡(luò)的發(fā)展要求節(jié)點設(shè)備的交叉矩陣具有容量高、快速的端口配置和組播支持能力，組播業(yè)務(wù)根據(jù)目的節(jié)點數(shù)的不同，可以分為單播、組播和廣播3種類型[2]。單播是指待轉(zhuǎn)發(fā)的消息在傳送網(wǎng)中要求實現(xiàn)點對點的傳輸，廣播業(yè)務(wù)是指在傳送網(wǎng)中把待轉(zhuǎn)發(fā)的一個消息從源節(jié)點轉(zhuǎn)發(fā)到傳送網(wǎng)的全部輸出端口上，而組播業(yè)務(wù)是則把消息轉(zhuǎn)發(fā)到傳送網(wǎng)中的一組輸出端口上。從廣義上來講，單播和廣播是組播的一個特例。

根據(jù)組播請求的多個目的輸出端口的產(chǎn)生時間，可以把組播分為兩類[3]：第一類是固定扇出業(yè)務(wù)，所有的目的輸出端口是在請求一開始就確定；第二類是遞增業(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ī)模實現(xiàn)，在交換設(shè)備中得到了廣泛的應(yīng)用。

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

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

對于三級Clos網(wǎng)絡(luò)，不同的扇出機制不但影響Clos網(wǎng)絡(luò)的阻塞率，而且影響算法的時間復(fù)雜度及網(wǎng)絡(luò)成本，因此選擇好的扇出方式才能充分發(fā)揮網(wǎng)絡(luò)的組播能力。以下將對Clos網(wǎng)絡(luò)各級扇出的性能特點進行分析。

(1) 輸出級扇出

輸出級扇出指輸出級模塊具有扇出功能，如果輸出級具有扇出功能，那么對于同一個業(yè)務(wù)源到一個輸出模塊中的多個輸出端口只需要經(jīng)過一個中間模塊，否則有多少輸出端口就需要經(jīng)過多少個中間模塊，在三級Clos網(wǎng)絡(luò)中路由分配主要就是中間級模塊的分配，因此必須降低對中間級模塊的需求，而第三級扇出可以降低對中間級模塊的要求，所以采用第三級扇出可以有效的降低阻塞率，這樣我們就可以將一個組播請求由原來的端口表示(Ip：{P1，P2……Pk})轉(zhuǎn)化成模塊表示(I：{O1，O2……Ok})，其中I表示輸入模塊，Oi表示輸出模塊。

(2) 中間級扇出

中間級扇出指中間級的模塊具有扇出功能。假如第一級沒有扇出功能，那么所有組播分支只能在一個中間級模塊進行扇出，因此只有那些滿足所有扇出要求的中間交換單元才可以成功建立連接。所以在組播請求的扇出值很大的情況下，網(wǎng)絡(luò)的阻塞概率將會急劇上升，但是由于只使用一個中間模塊，可以避免外部阻塞的發(fā)生。

(3) 輸入級扇出

輸入級扇出指輸入級模塊具有扇出功能，可以從一個輸入端口到達不同的中間級模塊。如果第三級有扇出的話，那么組播請求要到達幾個輸出級模塊，就需要占用幾個中間級模塊。對于輸入級扇出可以將組播分解成不同的單播請求進行處理，這樣可以利用單播中成熟的算法來進行處理，實現(xiàn)簡單，而且可以降低內(nèi)部阻塞率。但是由于每個組播請求只在第一級扇出，因此需要大量的中間模塊，容易出現(xiàn)外部阻塞問題。

1.2 Clos網(wǎng)絡(luò)組播算法介紹

Clos網(wǎng)絡(luò)中的組播算法性能主要受扇出機制的影響，這樣我們就根據(jù)扇出策略的不同將組播算法分為以下幾種。

輸入級扇出算法(IFMA)[7]是基于輸入級扇出的算法，其主要思想是通過將一個扇出值為f的組播請求轉(zhuǎn)化成f個單播請求，然后按照單播請求的路由算法進行路由，這樣在Clos網(wǎng)絡(luò)中每個組播請求只在輸入級進行扇出，這樣可以將組播業(yè)務(wù)理解為多個相互獨立的單播業(yè)務(wù)，這樣就可以利用單播算法中的成熟算法。如圖1中的輸入端口0到輸出端口0、輸出端口4和輸出端口8的組播業(yè)務(wù)采用輸入級扇出方式，在輸入模塊IM1中完成所有的扇出，分別經(jīng)過中間模塊CM1、CM2和CM3到不同的目的模塊。

最遲扇出算法(LFMA)[6] 是基于中間級扇出的算法，該算法的思想是只有在必須進行扇出時才進行扇出，即先在輸出級扇出再在中間級扇出。因此對于每一個組播請求只使用一個中間模塊，如圖1中輸入端口2中的請求(2：{1，3，7})，只使用了一個中間模塊CM4。

這兩種扇出機制都存在著自身的局限性，但是又有很強的互補性，因此將兩種扇出相結(jié)合的思想就應(yīng)運而出。在三級Clos網(wǎng)絡(luò)中，內(nèi)部阻塞的產(chǎn)生主要是由于級間鏈路的競爭，如果沒有第三級扇出，那么每個組播請求在一個輸出模塊的每個輸出端口都要占用一個從中間級到輸出級的鏈路，否則只需要一個鏈路。同樣，如果中間級沒有扇出，那么每一個子請求都要占用一條輸入模塊到中間模塊之間的鏈路，這樣就會出現(xiàn)外部阻塞。各種扇出機制各有優(yōu)缺點，可以結(jié)合使用。在在輸入級和輸出級同時扇出的機制中又可以根據(jù)不同的分配方式分為切分扇出算法及先中間級后輸入級算法兩種。

切割扇出算法(SFMA)[8]是把目的輸出模塊進行分組，分組數(shù)g為扇出值F 和切割值s 的比值向上取整，然后在進行路由時在第一級就進行扇出，即需要在第二級選擇g 個可用的中間交換單元，然后再在第二級和中間級扇出機制一樣進行同樣的處理。如圖1中輸入端口3的請求，如果按照切割算法理解的話其扇出值F 為3，切割值s為2，分為兩組，一組通過中間模塊CM1路由，另一組通過中間模塊CM2路由。

最后一種算法是中間級優(yōu)先扇出算法(CMFFMA)[9-10]，利用盡量少的中間模塊完成扇出，即首先選擇一個可以建立盡量多扇出的中間單元，建立其到輸出模塊的連接。如果到全部輸出模塊的連接均建立完成則路由成功，否則將余下的尚未完成的連接繼續(xù)按照上一步的方法處理，利用其他中間級單元的扇出能力完成扇出。例如在圖1中，由于沒有一個中間模塊能夠滿足輸入端口3的所有扇出請求，因此通過CM1 建立其中的兩條，然后再通過CM2建立剩余的連接。

通過以上對扇出的分析，我們可以得到采用先中間級后輸入級算法的扇出機制是最優(yōu)的。與切割扇出機制相比，它少了盲目性，多了預(yù)先檢測性，可以在第一級進行有目的扇出；與最遲扇出機制相比，它又有很強的靈活性。

1.3 Clos網(wǎng)絡(luò)組播算法仿真

(1) 仿真條件

采用OPNET軟件對不同的組播算法進行仿真，仿真中的請求是按照占用-空閑源模式產(chǎn)生，即每個輸入端口有占用和空閑兩種狀態(tài)，占用狀態(tài)表示該輸入端口當(dāng)前存在一個鏈接，每種狀態(tài)的持續(xù)時間均服從指數(shù)分布，如果1/μ表示占用的平均時間，1/λ表示空閑的持續(xù)時間，那么在以輸入端的狀態(tài)判斷，網(wǎng)絡(luò)中的負(fù)載p1=1/u/1/u+1/λ=λ/u+λ，如果用f表示組播的平均扇出，Pptp表示業(yè)務(wù)中單播的比率，那么網(wǎng)絡(luò)中的實際負(fù)載ρ=(Pptp+(1-Pptp)×f )×ρI。每個組播的扇出值按指數(shù)分布產(chǎn)生。

(2) 仿真結(jié)果

在具有組播業(yè)務(wù)的Clos網(wǎng)絡(luò)中網(wǎng)絡(luò)的阻塞率主要受組播業(yè)務(wù)的扇出值、組播比例和中間模塊數(shù)的影響，下面就分別進行仿真分析。

圖2是4種不同的算法在C(16， 16， 16)網(wǎng)絡(luò)規(guī)模、0.8負(fù)載以及單播比例為0.5時的阻塞率隨扇出值變化的曲線圖。

從圖2中可以看出隨著扇出值的增加阻塞率會有所增加，但是當(dāng)扇出值達到一定值時，阻塞率將趨于穩(wěn)定，這是因為在負(fù)載固定、輸出級有扇出的情況下，隨著扇出值的增加請求數(shù)量會減少。同時由于輸出級具有扇出功能，而輸出級的模塊數(shù)固定，所以當(dāng)扇出值超出一定值后扇出的目的模塊數(shù)不會有太多的變化，因此在扇出值大于一定范圍后，阻塞則趨于穩(wěn)定。在這幾種算法里CMFFMA的阻塞率最低，因為他的扇出順序是先輸出級、再中間級、最后輸入級，這樣可以最低限度地節(jié)約網(wǎng)絡(luò)中的鏈路資源，避免阻塞發(fā)生。

圖3為C(16，16，16)的Clos網(wǎng)絡(luò)在負(fù)載為0.8時的阻塞率隨單播比例變化的仿真結(jié)果。

從圖3中可以看出隨著單播比例的增加IFMA算法、SFMA和LFMA算法的阻塞率單調(diào)下降，而CMFFMA算法的阻塞率隨著單播比例的變化成拋物線狀，這是因為這兩種算法適宜于組播請求的建立，能夠最大程度的利用已有的空閑資源，因此在單播比例較低時網(wǎng)絡(luò)的阻塞率比較低，但是隨著單播比例的增加阻塞率會逐漸增加，當(dāng)?shù)竭_一定的比例時阻塞率又隨著單播比例的增加而下降，直到單播比例為1時，以上幾種算法的阻塞率均達到一個固定值。

圖4為C(16，16，16)規(guī)模的Clos網(wǎng)絡(luò)在0.8的負(fù)載，平均扇出值為8時及單播比例為0.5時各種算法的阻塞率隨中間模塊數(shù)的變化曲線。

從圖4中可以看出隨著中間模塊數(shù)的增加，不同算法的阻塞率下降的速度不同，其中LFMA算法和IFMA算法的下降最緩慢，其他兩種算法的下降速度很快；而且在中間模塊數(shù)遠小于嚴(yán)格無阻塞所需要的中間模塊數(shù)的情況下，Clos網(wǎng)絡(luò)的阻塞率可以下降到很低。

從以上分析可知IFMA算法的阻塞率在所有算法中是最高的，這是因為該算法采用輸入級扇出，組播業(yè)務(wù)的扇出均要在輸入級實現(xiàn)，這樣會造成很高的外部阻塞，而且占用的第一級鏈路數(shù)與第二級鏈路數(shù)相等。

圖5為IFMA算法的阻塞率隨中間模塊數(shù)的變化趨勢，網(wǎng)絡(luò)規(guī)模為C(16， m， 16)，平均扇出值為8，負(fù)載為0.8，全組播業(yè)務(wù)。

圖5中可以看出內(nèi)部阻塞率較小，故網(wǎng)絡(luò)的整體阻塞率主要由外部阻塞率決定。

上面分析了在單、組播業(yè)務(wù)混合的情況下網(wǎng)絡(luò)的整體阻塞率，但是由于單播和組播業(yè)務(wù)的不同，其阻塞率不盡相同，圖6為不同算法隨單播比例變化對組播業(yè)務(wù)阻塞率的影響。從圖6中可以看出隨著單播比例的增加，組播業(yè)務(wù)的阻塞率單調(diào)遞增。其中，CMFFMA算法的阻塞率最低，這是由于其更好的利用了網(wǎng)絡(luò)中的空閑鏈路資源；IFMA算法采用輸入級扇出，所以單播比例的增加并沒有影響其可用的鏈路資源的減少，因此阻塞率的增長最慢。

2 組播實現(xiàn)方案

在對組播業(yè)務(wù)及常見算法的比較分析的基礎(chǔ)上，本文設(shè)計出一種路由方案，針對不同的業(yè)務(wù)采用不同的處理方法。

由于三級均有扇出的CMFFMA算法的阻塞率最低，因此對于固定扇出業(yè)務(wù)可以采用該算法進行路由。

針對遞增業(yè)務(wù)的特點，同時為了降低對鏈路資源的占用，采用先輸出級、再中間級、最后輸入級扇出的策略。由于遞增業(yè)務(wù)是在固定扇出業(yè)務(wù)的基礎(chǔ)上增加的業(yè)務(wù)，因此首先判斷是否可以在固定業(yè)務(wù)已占用的輸出模塊內(nèi)完成扇出，如果路由成功則退出；否則再判斷是否可以通過固定業(yè)務(wù)已經(jīng)占有的中間級模塊完成路由，如果成功則退出；否則采用輸入模塊進行扇出，如果成功則退出；否則返回路由失敗。

圖7為采用本方案后的C(16， 16， 16)規(guī)模的Clos網(wǎng)絡(luò)，在單播比例為0.5、負(fù)載為0.8、平均扇出為8的時的阻塞率變化圖，其中遞增業(yè)務(wù)比例為遞增業(yè)務(wù)占組播業(yè)務(wù)的比例。由于遞增業(yè)務(wù)均是以單播的形式處理，而且對于遞增業(yè)務(wù)處理思想與固定組播業(yè)務(wù)類似，首先從輸出模塊進行扇出、再中間模塊、最后輸入級，因此遞增業(yè)務(wù)的阻塞率接近于單播業(yè)務(wù)的阻塞率，而且隨著遞增業(yè)務(wù)量的增加，網(wǎng)絡(luò)的阻塞率無太大變化。

3 結(jié)束語

隨著單播比例的增加，網(wǎng)絡(luò)中的組播業(yè)務(wù)的阻塞率會隨之增加。其中，中間級優(yōu)先扇出算法要求輸入級和輸出級都要有扇出功能，充分利用了交叉矩陣中的鏈路資源，因此阻塞率最低。雖然組播嚴(yán)格無阻塞所需要的中間模塊數(shù)很多，但是在實際的應(yīng)用中并不需要很多就可以達到很低的阻塞率。而且在相同的條件下，隨著中間級模塊數(shù)量的增加，輸入級和輸出級同時扇出的算法的阻塞率下降更快。對于遞增業(yè)務(wù)處理時可以按照組播扇出的思想進行處理，這樣對整體網(wǎng)絡(luò)中的阻塞率無明顯影響。

下一步的工作是將重排算法引入Clos網(wǎng)絡(luò)中的組播業(yè)務(wù)，通過對已建立的業(yè)務(wù)進行重排來降低阻塞率。

4 參考文獻

[1] SUN Shutao， HE Simin， ZHENG Yanfeng， et al. Multicast scheduling in buffered crossbar switches with multiple input queues[C]//Proceedings of 2005 Workshop on High Performance Switching and Routing(HPSR’05)， May 12-14， 2005， Hong Kong， China. Piscataway， NJ， USA: IEEE， 2005: 73-77.

[2] FU Hunglin， HWANG F K. On 3-stage Clos networks with different nonblocking requirements on two types of calls[J]. Journal of Combinatorial Optimization， 2005， 9(3):263-266.

[3] HWANG F K， SHENG-CHYANG L. On nonblocking multicast three-stage Clos networks[J].IEEE/ACM Transactions on Networking， 2000， 8(4): 535-539.

[4] CLOS C. A study of non-blocking switching network[J]. Bell System Technical Journal， 1953， 32(2): 406-424.

[5] HWANG F K. A survey of nooblocking multicast three-stage Clos networks[J]. IEEE Communications Magazine， 2003， 41(10): 34- 37.

[6] FRIEDMAN J. A lower bound on strictly non-blocking network[J]. Combinatorica， 1988， 8(2): 185-188.

[7] PARK Won-Bae， HENRY L. Owenand ellen wine zegura， SONET/SDH multicast routing algorithms in symmetrical three stage networks[C]//Proceedings of International Conference on Communications (ICC'95): Vol 3， Jun 18-22， 1995， Seattle， WA， USA. Piscataway， NJ， USA: IEEE， 1995: 1912-1917.

[8] Kim D S， DU Dingzhu. Performance of split routing algorithm for three-stage multicast networks[J]， IEEE/ ACM Transactions on Networking， 2000， 8(4): 526-534.

[9] YANG Yuanyuan， MASSOG G M. Fast path routing techniques for nonblocking broadcast networks[C]//Proceedings of IEEE 13th Annual International Phoenix Conference on Computers and Communications， Apr 12-15， 1994， Tempe， AZ， USA. Piscataway， NJ， USA: IEEE， 1994: 358-364.

[10] YANG Yuanyuan， WANG Jianchao. A more accurate analytical model on blocking probability of multicast networks[J]. IEEE Transactions on Communications， 2000， 48(11): 1930-1935.

收稿日期：2007-09-27

石增增，西安電子科技大學(xué)計算機學(xué)院在讀碩士研究生。主要研究方向為Clos交換網(wǎng)絡(luò)。

顧華璽，西安電子科技大學(xué)ISN國家重點實驗室副教授。博士畢業(yè)于西安電子科技大學(xué)。主要研究方向為互連網(wǎng)絡(luò)、片上網(wǎng)絡(luò)以及無線傳感器網(wǎng)絡(luò)中的關(guān)鍵技術(shù)等，已發(fā)表論文30余篇。

王長山，西安電子科技大學(xué)計算機學(xué)院副教授。畢業(yè)于吉林大學(xué)，主要研究方向為計算機軟件與網(wǎng)絡(luò)技術(shù)。已發(fā)表論文40余篇。