Ｃｌｏｓ網絡中的組播路由算法

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

關鍵詞：Clos網絡；組播；路由算法；扇出

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

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

根據組播請求的多個目的輸出端口的產生時間，可以把組播分為兩類[3]：第一類是固定扇出業務，所有的目的輸出端口是在請求一開始就確定；第二類是遞增業務，它的目的端口遞增，是不確定的。

1 Clos網絡的組播業務

為了支持網絡中的組播業務，網絡中的核心設備交換設備也應當具有組播功能。Clos網絡自提出以來[4]由于其低成本、易大規模實現，在交換設備中得到了廣泛的應用。

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

1.1 Clos網絡扇出機制

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

(1) 輸出級扇出

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

(2) 中間級扇出

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

(3) 輸入級扇出

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

1.2 Clos網絡組播算法介紹

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

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

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

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

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

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

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

1.3 Clos網絡組播算法仿真

(1) 仿真條件

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

(2) 仿真結果

在具有組播業務的Clos網絡中網絡的阻塞率主要受組播業務的扇出值、組播比例和中間模塊數的影響，下面就分別進行仿真分析。

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

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

圖3為C(16，16，16)的Clos網絡在負載為0.8時的阻塞率隨單播比例變化的仿真結果。

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

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

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

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

圖5為IFMA算法的阻塞率隨中間模塊數的變化趨勢，網絡規模為C(16， m， 16)，平均扇出值為8，負載為0.8，全組播業務。

圖5中可以看出內部阻塞率較小，故網絡的整體阻塞率主要由外部阻塞率決定。

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

2 組播實現方案

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

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

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

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

3 結束語

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

下一步的工作是將重排算法引入Clos網絡中的組播業務，通過對已建立的業務進行重排來降低阻塞率。

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

石增增，西安電子科技大學計算機學院在讀碩士研究生。主要研究方向為Clos交換網絡。

顧華璽，西安電子科技大學ISN國家重點實驗室副教授。博士畢業于西安電子科技大學。主要研究方向為互連網絡、片上網絡以及無線傳感器網絡中的關鍵技術等，已發表論文30余篇。

王長山，西安電子科技大學計算機學院副教授。畢業于吉林大學，主要研究方向為計算機軟件與網絡技術。已發表論文40余篇。