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

?

3.2 逆向構建多播樹
　　多播源發送建立信息至相連的LER，該LER為其分配一個組標簽GID，LER內部保存GLT(Group Label Table)表。表內包括：多播源S、多播組G、多播組在該MPLS域內的組標志號GID，并保證S、G、GID在該MPLS域內一一對應。當LER為某多播組分配好GID后，即通過相連的LER廣播該GID，防止相同的GID被分配給不同的多播組。
　　多播組成員發送加入請求、申請加入多播組時，請求經過的從葉子節點到根節點的路徑就成為多播樹的一部分。多播源將按照該路徑自上而下發送多播信息。因此，新成員加入多播組的過程即為樹枝節點內MFT建立的過程，亦為多播樹建立的過程。
　　(1)加入多插組。逆向構建多播樹算法，類似于SSM協議。組成員發送的加入請求到達LER后，LER分析該數據內的多播組地址，然后查找LER內部的GLT表，找到該多播組的源地址S，按照指向該地址的LSP把數據包發往該多播樹的根節點——多播源。LSR從接口i接收到加入請求后，從數據包中提取組信息GID，然后在MFT中對該接口i對應的AMID進行檢查和更新：
　　If(mod(AMID[i]，GID)!=0))
　　AMID[i]=AMID[i]*GID；
　　如果GID可以整除AMID[i]，則說明該接口會將GID代表的多播組信息從該接口轉發出去；否則，更新該AMID[i]，與新GID作乘法運算。
　　(2)多播數據包轉發。MPLS網絡中，單播包和多播包被賦予不同的標簽號。當LER收到多播源發送的數據包后，即查找GLT表，將對應的GID壓入數據包。然后，采取與LSR相同的操作——查找MFT，判斷該從哪些接口向外發送該包。方法如下：
　　/*n為路由器接口數，從0到n-2為n-1個接口(除去接收多播包的接口)*/
　　for(int i=0；i＜n-1；i++)　　/*當該接口的AMID非默認值時，AMID默認值為1*/
　　if(AMID[i]!=1)
　　if(mod(AMID[i]，GID)==0)
　　Send(Packet，IFID[i])；
　　參照公式1，由于所有GID為質數，AMID為若干質數的乘積，所以AMID一定不會被其他質數整除。當AMID可以被GID整除時，該AMID對應的接口一定為該GID所屬多播組的多播數據經過的接口。
　　如圖1所示，當LSR2從接口1接收到GID為5的多播包后，即計算mod(10，5)=0；mod(6，5)=1。因此，判斷該包應該從接口2傳至LSR3。
　　(3)退出多播組。當葉子節點想要退出多播組時，發送退出信息至與它連接的LER。LER查找GLT，將該多播組對應的標簽號GID壓入退出數據包，并沿LSP傳至該多播源。當LSR接收到退出信息時，會更新它的MFT。方法如下：
　　If(mod(AMID[i]，GID)==0)
　　AMID[i]=AMID[i]/GID；
　　即使該接口對應的AMID[i]不再可以被GID整除。當一個LSR所有下游接口都返回退出信息時，該節點向上游節點發送退出信息。
4 數值分析與仿真
4.1 質數耗盡問題
　　由于MPLS域內采取20bit作為傳輸標記。所以，質數的數量是否會由于多播組的增加被用盡是個需要考慮的問題。為此，計算100～1 000內質數分布，得到的質數分布圖如圖2所示?？梢钥闯鲑|數隨著自然數增大逐漸增多。

4.2 逆向法與稀疏模式法比較
　　與MPLS上建立PIM-SM多播樹方法相比，逆向構建多播樹算法可以節省轉發表體積，減少查詢時間。假設一個LSR節點有n個接口，該域內有m個多播組。則最壞的情況下，轉發表體積為TableSize=n*m，而逆向構建算法的MFT始終保持MFTableSize=n。逆向構建多播樹不需要RP節點的支持。在MPLS域間，多播組標簽號、多播組和多播源分別一一對應。

4.3 逆向法與傳統聚集法比較
　　與聚集多播樹相比，逆向構建多播樹不需要核心控制節點生成聚集樹，并且可以節省大量帶寬。為更好地說明問題，擴展網絡仿真工具jns^[6]對聚集樹算法和逆向構建多播樹算法進行仿真。仿真拓撲結構如圖1所示，通過收集LSR3和LSR4在兩種不同多播算法下的流量來比較帶寬使用情況。
　　在聚集多播樹算法下，LSR2節點把G1、G2、G3多播組的信息分別傳遞給LSR3和LSR4。因此，對于聚集樹算法，通過節點LSR3與LSR4的流量是相同的。在逆向構建多播樹算法下，LSR2只把G1和G2多播組的信息傳給LSR3，把G1、G3多播組的信息傳給LSR4。
　　兩種算法下LSR3與LSR4多播流量對比分別如圖3和圖4所示。從圖3、圖4中可以看出，在完成同樣的多播信息的傳遞與接收時，使用逆向構建多播樹算法，經過LSR3、LSR4兩個節點的多播流量明顯低于聚集樹算法。因此，使用逆向建立多播樹算法可以有效地節省帶寬。