1多播發(fā)展簡(jiǎn)介
　　隨著Internet的發(fā)展，視頻廣播、視頻會(huì)議等應(yīng)用迅速增加。其中大部分應(yīng)用需要通過(guò)一對(duì)多或多對(duì)多的通信方式來(lái)完成，并且在傳輸數(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)用。
　　本文提出了使用逆向多播樹(shù)算法在MPLS上構(gòu)建多播應(yīng)用的方法，使用定源多播SSM(Source Specific Multicast)協(xié)議構(gòu)建多播樹(shù)，即從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)逆向構(gòu)建多播樹(shù)。
2 MPLS與多播相結(jié)合的問(wèn)題與解決
　　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多播樹(shù)。將邊界路由器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ì)隨著多播組的增加不斷增大。隨之而來(lái)的是路由器內(nèi)存消耗的迅速上升、查表時(shí)間的延長(zhǎng)和轉(zhuǎn)發(fā)速度的下降。
　　為減少路由器內(nèi)保存的多" title="的多">的多播組狀態(tài)數(shù)和MFT的體積，提出了聚集多播樹(shù)(Aggregated Multicast)算法。該算法并不需要為每個(gè)多播組建立相應(yīng)的多播樹(shù)，而是用一棵聚集樹(shù)支持多個(gè)多播組。文獻(xiàn)^[4]以此方法為基礎(chǔ)構(gòu)建MPLS上可靠多播應(yīng)用，即當(dāng)有鏈路" title="鏈路">鏈路斷開(kāi)時(shí)，該聚集樹(shù)失效，由后備鏈路重新組合生成新的聚集樹(shù)，以提高多播傳遞的可靠性。但是某個(gè)多播組很可能與聚集樹(shù)并不完全匹配，可能發(fā)生多播信息被傳送到一些節(jié)點(diǎn)，而這些節(jié)點(diǎn)并非該多播組的成員，從而造成帶寬的浪費(fèi)。
　　文獻(xiàn)^[5]中通過(guò)第2層的支持實(shí)現(xiàn)了MPLS廣播機(jī)制，并對(duì)其進(jìn)行了擴(kuò)展，使其在MPLS域內(nèi)支持稠密模式(Dense Mode)的多播通信。但稠密模式本身就會(huì)造成帶寬的浪費(fèi)。
3 逆向多播樹(shù)構(gòu)建算法
　　聚集樹(shù)算法會(huì)在部分枝節(jié)點(diǎn)處產(chǎn)生帶寬的浪費(fèi)，PIM-SM的實(shí)施會(huì)消耗過(guò)多的資源。于是本文采用了仿SSM多播路由協(xié)議的方法，通過(guò)逆向構(gòu)建多播樹(shù)在MPLS域內(nèi)實(shí)施多播。
3.1 通過(guò)質(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)以及通過(guò)該接口轉(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來(lái)判斷是否需要向接口發(fā)送來(lái)自于多播組GID的多播信息。以樹(shù)形結(jié)構(gòu)表示某MPLS域內(nèi)的多播拓?fù)浣Y(jié)構(gòu)，如圖1所示。多播組G1、G2、G3的多播源主機(jī)通過(guò)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)建多播樹(shù)
　　多播源發(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后，即通過(guò)相連的LER廣播該GID，防止相同的GID被分配給不同的多播組。
　　多播組成員發(fā)送加入請(qǐng)求、申請(qǐng)加入多播組時(shí)，請(qǐng)求經(jīng)過(guò)的從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑就成為多播樹(shù)的一部分。多播源將按照該路徑自上而下發(fā)送多播信息。因此，新成員加入多播組的過(guò)程即為樹(shù)枝節(jié)點(diǎn)內(nèi)MFT建立的過(guò)程，亦為多播樹(shù)建立的過(guò)程。
　　(1)加入多插組。逆向構(gòu)建多播樹(shù)算法，類似于SSM協(xié)議。組成員發(fā)送的加入請(qǐng)求到達(dá)LER后，LER分析該數(shù)據(jù)內(nèi)的多播組地址，然后查找LER內(nèi)部的GLT表，找到該多播組的源地址S，按照指向該地址的LSP把數(shù)據(jù)包發(fā)往該多播樹(shù)的根節(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]，則說(shuō)明該接口會(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)過(guò)的接口。
　　如圖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ù)耗盡問(wèn)題
　　由于MPLS域內(nèi)采取20bit作為傳輸標(biāo)記。所以，質(zhì)數(shù)的數(shù)量是否會(huì)由于多播組的增加被用盡是個(gè)需要考慮的問(wèn)題。為此，計(jì)算100～1 000內(nèi)質(zhì)數(shù)分布，得到的質(zhì)數(shù)分布圖如圖2所示。可以看出質(zhì)數(shù)隨著自然數(shù)增大逐漸增多。

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

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