《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 業(yè)界動(dòng)態(tài) > 逆向多播樹構(gòu)建算法在MPLS上的應(yīng)用

逆向多播樹構(gòu)建算法在MPLS上的應(yīng)用

2008-06-10
作者:熊齊邦,,蔣 琰

  摘 要: 提出了一種在MPLS網(wǎng)絡(luò)中構(gòu)建多播樹的新方法——逆向構(gòu)建算法,。用數(shù)值分析和仿真方法證明了逆向構(gòu)建多播樹不僅可以解決MPLS多播標(biāo)簽數(shù)不足的問題,,還可以有效地減小多播轉(zhuǎn)發(fā)表的體積,,提高帶寬利用率,。
  關(guān)鍵詞: MPLS 聚集 多播 服務(wù)質(zhì)量


1多播發(fā)展簡介
  隨著Internet的發(fā)展,,視頻廣播,、視頻會(huì)議等應(yīng)用迅速增加,。其中大部分應(yīng)用需要通過一對(duì)多或多對(duì)多的通信方式來完成,,并且在傳輸數(shù)據(jù)的同時(shí),,需要服務(wù)質(zhì)量" title="服務(wù)質(zhì)量">服務(wù)質(zhì)量QoS(Quality of Service)保障,。因此,多播技術(shù)的應(yīng)用和QoS的支持成為網(wǎng)絡(luò)應(yīng)用拓展的重要因素,。
  多協(xié)議標(biāo)簽交換MPLS(Multi Protocol Label Swit-ching)[1]作為IETF的一個(gè)標(biāo)準(zhǔn),,很有可能成為下一代主干網(wǎng)絡(luò)的主要傳輸方式。它對(duì)帶寬控制和QoS保障提供了很好的支持,。整合多播與MPLS不僅可以加強(qiáng)網(wǎng)絡(luò)性能的發(fā)揮,,而且有利于多播的拓展和應(yīng)用。
  本文提出了使用逆向多播樹算法在MPLS上構(gòu)建多播應(yīng)用的方法,,使用定源多播SSM(Source Specific Multicast)協(xié)議構(gòu)建多播樹,,即從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)逆向構(gòu)建多播樹。
2 MPLS與多播相結(jié)合的問題與解決
  IETF提出了關(guān)于如何在MPLS域內(nèi)構(gòu)建多播的整體框架[2],。將所有標(biāo)準(zhǔn)多播協(xié)議以MPLS的方式進(jìn)行了分析,,并且考慮了MPLS下多播的特性,如聚集,、洪泛和剪枝等,。指出要在MPLS下實(shí)現(xiàn)多播就意味著實(shí)現(xiàn)一對(duì)多的標(biāo)簽交換路徑LSP(Label Switched Path)或者多對(duì)多的LSP,而目前的MPLS只提供了一對(duì)一的LSP,。
  解決方法之一是使用映射方法,,將一對(duì)多的LSP映射為多組一對(duì)一的LSP。使用該方法在MPLS域內(nèi)構(gòu)建稀疏模式多播協(xié)議PIM-SM" title="PIM-SM">PIM-SM(Protocol Independent Multicast-Sparse Mode)[3],,需要使用加入/剪枝信息構(gòu)建LSP多播樹,。將邊界路由器LER(Label Edged Router)作為多播組的集合點(diǎn)RP(Rendezvous Point),當(dāng)入口LER接收到加入請(qǐng)求后,,將請(qǐng)求轉(zhuǎn)發(fā)至RP,。RP在多播轉(zhuǎn)發(fā)表MFT(Multicast Forwarding Table)內(nèi)加入記錄,新記錄為指向新加入LER的LSP,。標(biāo)簽交換路由LSR器(Label Switched Router)只需要按照標(biāo)簽進(jìn)行轉(zhuǎn)發(fā),,不需要保存多播組狀態(tài)。但是,,該方法存在嚴(yán)重的隱患:當(dāng)有大量的活動(dòng)組存在于域內(nèi)時(shí),,很有可能導(dǎo)致標(biāo)簽不足;而且,,MFT的體積會(huì)隨著多播組的增加不斷增大,。隨之而來的是路由器內(nèi)存消耗的迅速上升、查表時(shí)間的延長和轉(zhuǎn)發(fā)速度的下降,。
  為減少路由器內(nèi)保存的多" title="的多">的多播組狀態(tài)數(shù)和MFT的體積,,提出了聚集多播樹(Aggregated Multicast)算法。該算法并不需要為每個(gè)多播組建立相應(yīng)的多播樹,而是用一棵聚集樹支持多個(gè)多播組,。文獻(xiàn)[4]以此方法為基礎(chǔ)構(gòu)建MPLS上可靠多播應(yīng)用,,即當(dāng)有鏈路" title="鏈路">鏈路斷開時(shí),該聚集樹失效,,由后備鏈路重新組合生成新的聚集樹,,以提高多播傳遞的可靠性。但是某個(gè)多播組很可能與聚集樹并不完全匹配,,可能發(fā)生多播信息被傳送到一些節(jié)點(diǎn),,而這些節(jié)點(diǎn)并非該多播組的成員,從而造成帶寬的浪費(fèi),。
  文獻(xiàn)[5]中通過第2層的支持實(shí)現(xiàn)了MPLS廣播機(jī)制,,并對(duì)其進(jìn)行了擴(kuò)展,使其在MPLS域內(nèi)支持稠密模式(Dense Mode)的多播通信,。但稠密模式本身就會(huì)造成帶寬的浪費(fèi),。
3 逆向多播樹構(gòu)建算法
  聚集樹算法會(huì)在部分枝節(jié)點(diǎn)處產(chǎn)生帶寬的浪費(fèi),PIM-SM的實(shí)施會(huì)消耗過多的資源,。于是本文采用了仿SSM多播路由協(xié)議的方法,,通過逆向構(gòu)建多播樹在MPLS域內(nèi)實(shí)施多播。
3.1 通過質(zhì)數(shù)法則聚集標(biāo)簽
  為實(shí)現(xiàn)多播信息在路由器內(nèi)的復(fù)制轉(zhuǎn)發(fā),,對(duì)每個(gè)路由器添加多播轉(zhuǎn)發(fā)表MFT。每個(gè)表中包含該路由器的接口號(hào)IFID(Interface ID)以及通過該接口轉(zhuǎn)發(fā)的多播組的聚集標(biāo)簽號(hào)AMID(Aggregated Multicast Group ID),。這里使用了標(biāo)簽聚集算法,,使MFT的體積不會(huì)隨著多播組的增加而變大,一直保持常量,,其數(shù)目為該路由器的接口數(shù),。為了使一個(gè)聚集標(biāo)簽號(hào)代表多個(gè)多播組,為每個(gè)多播組分配一個(gè)組標(biāo)簽號(hào)GID(Group ID),,并且要求該標(biāo)簽號(hào)必須為質(zhì)數(shù),。把從同一個(gè)接口轉(zhuǎn)發(fā)的多播組標(biāo)簽號(hào)的乘積作為該接口的AMID。
  公式1:
  設(shè)有質(zhì)數(shù)GID1,,GID2,,GID3,GID4,。
  乘積AMID1= GID1*GID2*GID4,,必不可被GID3整除,必可被GID1,、GID2,、GID4中任意一個(gè)數(shù)整除,這是由質(zhì)數(shù)本身的特點(diǎn)決定的。
  因此,,以組GID能否整除聚集標(biāo)簽號(hào)AMID來判斷是否需要向接口發(fā)送來自于多播組GID的多播信息,。以樹形結(jié)構(gòu)表示某MPLS域內(nèi)的多播拓?fù)浣Y(jié)構(gòu),如圖1所示,。多播組G1,、G2、G3的多播源主機(jī)通過LSR1連接到MPLS域,,LSR3連接著多播組G1和G3的組成員,,LSR4連接著多播組G1和G2的組成員。
  假定多播組G1,、G2,、G3都已經(jīng)分配了多播組標(biāo)簽號(hào)GID,分別為質(zhì)數(shù)2,、3,、5,則如圖1中所示,,可得到LSR2內(nèi)MFT表,,如表1所示。

?


3.2 逆向構(gòu)建多播樹
  多播源發(fā)送建立信息至相連的LER,,該LER為其分配一個(gè)組標(biāo)簽GID,,LER內(nèi)部保存GLT(Group Label Table)表。表內(nèi)包括:多播源S,、多播組G,、多播組在該MPLS域內(nèi)的組標(biāo)志號(hào)GID,并保證S,、G,、GID在該MPLS域內(nèi)一一對(duì)應(yīng)。當(dāng)LER為某多播組分配好GID后,,即通過相連的LER廣播該GID,,防止相同的GID被分配給不同的多播組。
  多播組成員發(fā)送加入請(qǐng)求,、申請(qǐng)加入多播組時(shí),,請(qǐng)求經(jīng)過的從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑就成為多播樹的一部分。多播源將按照該路徑自上而下發(fā)送多播信息,。因此,,新成員加入多播組的過程即為樹枝節(jié)點(diǎn)內(nèi)MFT建立的過程,亦為多播樹建立的過程,。
  (1)加入多插組,。逆向構(gòu)建多播樹算法,,類似于SSM協(xié)議。組成員發(fā)送的加入請(qǐng)求到達(dá)LER后,,LER分析該數(shù)據(jù)內(nèi)的多播組地址,,然后查找LER內(nèi)部的GLT表,找到該多播組的源地址S,,按照指向該地址的LSP把數(shù)據(jù)包發(fā)往該多播樹的根節(jié)點(diǎn)——多播源,。LSR從接口i接收到加入請(qǐng)求后,從數(shù)據(jù)包中提取組信息GID,,然后在MFT中對(duì)該接口i對(duì)應(yīng)的AMID進(jìn)行檢查和更新:
  If(mod(AMID[i],,GID)!=0))
  AMID[i]=AMID[i]*GID;
  如果GID可以整除AMID[i],,則說明該接口會(huì)將GID代表的多播組信息從該接口轉(zhuǎn)發(fā)出去,;否則,更新該AMID[i],,與新GID作乘法運(yùn)算,。
  (2)多播數(shù)據(jù)包轉(zhuǎn)發(fā)。MPLS網(wǎng)絡(luò)中,,單播包和多播包被賦予不同的標(biāo)簽號(hào),。當(dāng)LER收到多播源發(fā)送的數(shù)據(jù)包后,即查找GLT表,,將對(duì)應(yīng)的GID壓入數(shù)據(jù)包,。然后,采取與LSR相同的操作——查找MFT,,判斷該從哪些接口向外發(fā)送該包,。方法如下:
  /*n為路由器接口數(shù),從0到n-2為n-1個(gè)接口(除去接收多播包的接口)*/
  for(int i=0,;i<n-1,;i++)  /*當(dāng)該接口的AMID非默認(rèn)值時(shí),,AMID默認(rèn)值為1*/
  if(AMID[i]!=1)
  if(mod(AMID[i],,GID)==0)
  Send(Packet,IFID[i]),;
  參照公式1,,由于所有GID為質(zhì)數(shù),AMID為若干質(zhì)數(shù)的乘積,,所以AMID一定不會(huì)被其他質(zhì)數(shù)整除,。當(dāng)AMID可以被GID整除時(shí),該AMID對(duì)應(yīng)的接口一定為該GID所屬多播組的多播數(shù)據(jù)經(jīng)過的接口,。
  如圖1所示,,當(dāng)LSR2從接口1接收到GID為5的多播包后,,即計(jì)算mod(10,5)=0,;mod(6,,5)=1。因此,,判斷該包應(yīng)該從接口2傳至LSR3,。
  (3)退出多播組。當(dāng)葉子節(jié)點(diǎn)想要退出多播組時(shí),,發(fā)送退出信息至與它連接的LER,。LER查找GLT,將該多播組對(duì)應(yīng)的標(biāo)簽號(hào)GID壓入退出數(shù)據(jù)包,,并沿LSP傳至該多播源,。當(dāng)LSR接收到退出信息時(shí),會(huì)更新它的MFT,。方法如下:
  If(mod(AMID[i],,GID)==0)
  AMID[i]=AMID[i]/GID;
  即使該接口對(duì)應(yīng)的AMID[i]不再可以被GID整除,。當(dāng)一個(gè)LSR所有下游接口都返回退出信息時(shí),,該節(jié)點(diǎn)向上游節(jié)點(diǎn)發(fā)送退出信息。
4 數(shù)值分析與仿真
4.1 質(zhì)數(shù)耗盡問題

  由于MPLS域內(nèi)采取20bit作為傳輸標(biāo)記,。所以,,質(zhì)數(shù)的數(shù)量是否會(huì)由于多播組的增加被用盡是個(gè)需要考慮的問題。為此,,計(jì)算100~1 000內(nèi)質(zhì)數(shù)分布,,得到的質(zhì)數(shù)分布圖如圖2所示??梢钥闯鲑|(zhì)數(shù)隨著自然數(shù)增大逐漸增多,。


4.2 逆向法與稀疏模式法比較
  與MPLS上建立PIM-SM多播樹方法相比,逆向構(gòu)建多播樹算法可以節(jié)省轉(zhuǎn)發(fā)表體積,,減少查詢時(shí)間,。假設(shè)一個(gè)LSR節(jié)點(diǎn)有n個(gè)接口,該域內(nèi)有m個(gè)多播組,。則最壞的情況下,,轉(zhuǎn)發(fā)表體積為TableSize=n*m,而逆向構(gòu)建算法的MFT始終保持MFTableSize=n,。逆向構(gòu)建多播樹不需要RP節(jié)點(diǎn)的支持,。在MPLS域間,多播組標(biāo)簽號(hào),、多播組和多播源分別一一對(duì)應(yīng),。

4.3 逆向法與傳統(tǒng)聚集法比較
  與聚集多播樹相比,,逆向構(gòu)建多播樹不需要核心控制節(jié)點(diǎn)生成聚集樹,并且可以節(jié)省大量帶寬,。為更好地說明問題,,擴(kuò)展網(wǎng)絡(luò)仿真工具jns[6]對(duì)聚集樹算法和逆向構(gòu)建多播樹算法進(jìn)行仿真。仿真拓?fù)浣Y(jié)構(gòu)如圖1所示,,通過收集LSR3和LSR4在兩種不同多播算法下的流量來比較帶寬使用情況,。
  在聚集多播樹算法下,LSR2節(jié)點(diǎn)把G1,、G2,、G3多播組的信息分別傳遞給LSR3和LSR4。因此,,對(duì)于聚集樹算法,,通過節(jié)點(diǎn)LSR3與LSR4的流量是相同的。在逆向構(gòu)建多播樹算法下,,LSR2只把G1和G2多播組的信息傳給LSR3,,把G1、G3多播組的信息傳給LSR4,。
  兩種算法下LSR3與LSR4多播流量對(duì)比分別如圖3和圖4所示,。從圖3、圖4中可以看出,,在完成同樣的多播信息的傳遞與接收時(shí),,使用逆向構(gòu)建多播樹算法,經(jīng)過LSR3,、LSR4兩個(gè)節(jié)點(diǎn)的多播流量明顯低于聚集樹算法,。因此,使用逆向建立多播樹算法可以有效地節(jié)省帶寬,。


  MPLS技術(shù)解決了傳統(tǒng)網(wǎng)絡(luò)中IP分組交換的問題,,能提供靈活的流量工程與虛擬專用網(wǎng)絡(luò)的業(yè)務(wù)。MPLS與多播的結(jié)合可以有效解決多播的擴(kuò)展問題,。本文提出了逆向構(gòu)建多播樹算法,,并且將其與傳統(tǒng)的MPLS上構(gòu)建多播樹的方法進(jìn)行比較,證明了其實(shí)施的可行性和優(yōu)越性,。
  逆向構(gòu)建多播樹在縮減轉(zhuǎn)發(fā)表的同時(shí),,降低了潛在的帶寬浪費(fèi),,為MPLS域內(nèi)實(shí)現(xiàn)多播提供了一種新方法,。但是,其具體實(shí)現(xiàn)細(xì)節(jié),,如健壯性,、安全性及利用MPLS的特性對(duì)多播應(yīng)用提供QoS保障等問題還需要進(jìn)一步研究,。
參考文獻(xiàn)
1 Rosen E,Viswanathan A,,Callon R.Multi-protocol label switching architecture[S].IETF RFC3031,,2001
2 Ooms D,Sales B,,Livens W et al.Overview of IP multicast in a multi-protocol label switching MPLS environment[S].IETF RFC 3353,,2002
3 Cho J Y,Chung M Y.A simple method for implementing PIM to ATM based MPLS networks[C].In:Proceedings ninth IEEE international conference networks,,2001
4 Cui J H,,F(xiàn)aloutsos M,Gerla M.An architecture for scalable,,efficient,,and fast fault-tolerant multicast provisioning[J].IEEE Network,2004,;18(2):26~34
5 Bag M M,,Samadian B S,Nikoopour M et al.A case for dense-mode multicast support in MPLS[C].In:Computers and communications proceedings,,ISCC 2004:1063~1070
6 Java Network Simulator.Open source project from sourceforge.http://jns.sourceforge.net/,,2002-07-16

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,,并不代表本網(wǎng)站贊同其觀點(diǎn),。轉(zhuǎn)載的所有的文章、圖片,、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有,。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容,、版權(quán)和其它問題,,請(qǐng)及時(shí)通過電子郵件或電話通知我們,以便迅速采取適當(dāng)措施,,避免給雙方造成不必要的經(jīng)濟(jì)損失,。聯(lián)系電話:010-82306118;郵箱:[email protected],。