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两个节点的多播流量明显低于聚集树算法。因此，使用逆向建立多播树算法可以有效地节省带宽。