Clos網絡中的組播路由算法_第1頁
Clos網絡中的組播路由算法_第2頁
Clos網絡中的組播路由算法_第3頁
Clos網絡中的組播路由算法_第4頁
Clos網絡中的組播路由算法_第5頁
已閱讀5頁,還剩9頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

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

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

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

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

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

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

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

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

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

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

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

12、los網絡中網絡的阻塞率主要受組播業(yè)務的扇出值、組播比例和中間模塊數的影響,下面就分別進行仿真分析。圖2是4種不同的算法在C(16,16,16)網絡規(guī)模、0.8負載以及單播比例為0.5時的阻塞率隨扇出值變化的曲線圖。從圖2中可以看出隨著扇出值的增加阻塞率會有所增加,但是當扇出值達到一定值時,阻塞率將趨于穩(wěn)定,這是因為在負載固定、輸出級有扇出的情況下,隨著扇出值的增加請求數量會減少。同時由于輸出級具有扇出功能,而輸出級的模塊數固定,所以當扇出值超出一定值后扇出的目的模塊數不會有太多的變化,因此在扇出值大于一定范圍后,阻塞則趨于穩(wěn)定。在這幾種算法里CMFFMA的阻塞率最低,因為他的扇出順序是先輸出

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

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

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

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

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

18、增加,輸入級和輸出級同時扇出的算法的阻塞率下降更快。對于遞增業(yè)務處理時可以按照組播扇出的思想進行處理,這樣對整體網絡中的阻塞率無明顯影響。下一步的工作是將重排算法引入Clos網絡中的組播業(yè)務,通過對已建立的業(yè)務進行重排來降低阻塞率。4 參考文獻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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論