摘要：提出了一种在MPLS网络中构建多播树的新方法——逆向构建算法。用数值分析和仿真方法证明了逆向构建多播树不仅可以解决MPLS多播标签数不足的问题，还可以有效地减小多播转发表的体积，提高带宽利用率。
关键词：MPIS聚集多播服务质量
1 多捶发展简介
随着Internet的发展，视频广播、视频会议等应用迅速增加。其中大部分应用需要通过一对多或多对多的通信方式来完成，并且在传输数据的同时，需要服务质量Qos(Quality of Service)保障。因此，多播技术的应用和QoS的支持成为网络应用拓展的重要因素。
多协议标签交换MPLS(Multi Protocol Label Switehing)作为IETF的一个标准，很有可能成为下一代主干网络的主要传输方式。它对带宽控制和QoS保障提供了很好的支持。整合多播与MPLS不仅可以加强网络性能的发挥，而且有利于多播的拓展和应用。
本文提出了使用逆向多播树算法在MPLS上构建多播应用的方法，使用定源多播SSM(Source Speeific Multicast)协议构建多播树，即从叶子节点
2 MPLS与多播相结合的问题与解决
IETF提出了关于如何在MPLS域内构建多播的整体框架。将所有标准多播协议以MPLS的方式进行了分析，并且考虑了MPIS下多播的特性，如聚集、洪泛和剪枝等。指出要在MPKS下实现多播就意味着实现一对多的标签交换路径LSP(Label Switched Path)或者多对多的ISP，而目前的MPLS只提供了一对一的LSP。
解决方法之一使用映射方法，将一对多的LSP映射为多组一对一的LSP。使用该方法在MPLS域内构建稀疏模式多播协议P1M-SM（Protoeol Independent Mulficast-Sparse Mode)，需要使用加入，剪枝信息构建LSP多播树。将边界路由器LER(Label Edged Router)作为多播组的集合点RP(Rendezvous Point)，当口LER接收到加入请求后，将请求转发至RP。RP在多播转发表MFT(Multicast Forwarding Table)内加入记录，新记录为指向新加入LER的LSP。标签交换路由LSR器(LabelSwitched Router)只需要按照标签进行转发，不需要保存多播组状态。但是，该方法存在严重的隐患：当有大量的活动组存在于域内时，很有可能导致标签不足；而且，MFT的体积会随着多播组的增加不断增大。随之而来的是路由器内存消耗的迅速上升、查表时间的延和转发速度的下降。
为减少路由器内保存的多播组状态数和MFT的体积，提出了聚集多播树(Aggregated Mulficast)算法。该算法并不需要为每个多播组建立相应的多播树，而是用一棵聚集树支持多个多播组。文献以此方法为基础构建MPIS上可靠多插应用，即当有链路断开时，该聚集树失效，由后备链路重新组合生成新的聚集树，以提高多播传递的可靠性。但是某个多播组很可能与聚集树并不完全匹配，可能发生多播信息被传送到一些节点，而些节点并非该多播组的成员，从而造成带宽的浪费。
文献中通过第2层的支持实现了MPLS广播机制，并对其进行了扩展，使其在MPLS域内支持稠密模式(Dense Mode)的多播通信。但稠密模式本身就会造成带宽的浪费。
3 逆向多播树构建算法
聚集树算法会在部分枝节点处产生带宽的浪费，PIM—SM的实施会消耗过多的资源。于是本文采用了仿SSM多播路由协议的方法，通过逆向构建多播树在MPLS域内实多播。
3．1 通过质数法则聚集标签
为实现多播信息在路由器内的复制转发，对每个路由器添加多播转发表MFT。每个表中包含该路由器的接口号。IFID(Intefface ID)以及通过该接口转发的多播组的聚集标签号AMID(Aggregated Muhieast Group ID)。这里使用了标签聚集算法，使MFT的体积不会随着多播组的增加而变大，一直保持常量，其数目为该路由器的接口数。为了使一个聚集标签号代表多个多播组，为每个多播组分配一个组标签号GID(Group ID)，并且要求该标签号必须为质数。把从同一个接口转发的多播组标签号的乘积作为该接口的AMID。
公式1：
设有质数G1D1，GID2．GID3，GID4。
乘积AMIDl=GIDl}GID2*GID4，必不可被GID3整除，必可被GIDl、GID2、GID4中任意一个数整除，这是由质数本身的特点决定的。
因此，以组GID能否整除聚集标签号AMID来判断是否需要向接口发送来自于多播组GID的多播信息。以树形结构表示某MPLS域内
的多播拓扑结构，如图1所示。多播组G1、G2、G3的多播源主机通过LSR1连接到MPLS域，LSR3连接着多播组GI和G3的组成员，LSR4连接着多播组GI和G2的组成员。
假定多播组Gl、G2、G3都已经分配了多播组标签号GID，分别为质数2、3、5，则如图1中所示，可得到KSR2内MFT表，如表l所示。
点击看原图 多播组成员发送加入请求、申请加入多播组时，请求经过的从叶子节点到根节点的路径就成为多播树的一部分。多播源将按照该路径自上而下发送多播信息。因此，新成员加入多播组的过程即为树枝节点内MFT建立的过程，亦为多播树建立的过程。 (1)加入多插组。逆向构建多播树算法，类似于SS (2)多播数据包转发。MPLS网络中，单播包和多播包被赋予不同的标签号。当LER收到多播源发送的数据包后，即查找GLT表，将对应的GID压入数据包。然后，采取与LSR相同的操作——查找MFT，判断该从哪些接口向外发送该包。方法如下： 点击看原图 如图l所示，当LSR2从接口1接收到GID为5的多播包后，即计算mod(10，5)=O；mod(6，5)=1。因此，判断该包应该从接口2传至LSR3。 (3)退出多播组。当叶子节点想要退出多播组时，发送退出信息至与它连接的LER。LER查找GLT，将该多播组对应的标签号GID压入退出数据包，并沿LSP传至该多播源。当LSR接收到退出信息时，会更新它的MFT。方法如下： 即使该接口对应的AMID[i]不再可以被GID整除。当一个LSR所有下游接口都返回退出信息时，该节点向上游节点发送退出信息。 4 数值分析与仿真 4．2 逆向法与稀疏模式法比较 4．3 逆向法与传统聚集法比较 点击看原图 在聚集多播树算法下，LSR2节点把G1、G2、G3多播组的信息分别传递给LSR3和LSR4。因此，对于聚集树算法，通过节点LSR3与LSR4的流量是相同的。在逆向构建多播树算法下，LSR2只把G1和G2多播组的信息传给LSR3，把Gl、G3多播组的信息传给LSR4。 两种算法下LSR3与LSR4多播流量对比分别如图3和图4所示。从图3、图4中可以看出，在完成同样的多播信息的传递与接收时，使用逆向构建多播树算法，经过LSR3、LSR4两个节点的
多播源发送建立信息至相连的LER，该LER为其分配一个组标签GID，LER内部保存GLT（Group Label Table）表。表内包括：多播源S、多播组G、多播组在该MPLS域内的组标志号GID，并保证S、G、GID在该MPLS域内一一对应。当LER为某多播组分配好GID后，即通过相连的LER广播该GID，防止相同的GID被分配给不同的多播组。
M协议。组成员发送的加入请求到达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作乘法运算。
照公式1，由于所有GID为质数，AMID为若干质数的乘积，所以AMID一定不会被其他质数整除。当AMID可以被GID整除时，该AMID对应的接口一定为该GID所属多播组的多播数据经过的接口。
4．1 质数耗尽问题
由于MPLS域内采取20bit作为传输标记。所以，质数的数量是否会由于多播组的增加被用尽是个需要考虑的问题。为此，计算100~1000内质数分布，得到的质数分布图如图2所示。可以看出质数随着自然数增大逐渐增多。
与MPLS上建立PIM-SM多播树方法相比，逆向构建多播树算法可以节省转发表体积，减少查询时间。假设一个LSR节点有n个接口，该域内有m个多播组。则最坏的情况下，转发表体积为TableSize=n*m，而逆向构建算法的MFT始终保持MFTableSize=n。逆向构建多播树不需要RP节点的支持。在MPLS域间，多播组标签号、多播组和多播源分别一一对应。
与聚集多播树相比，逆向构建多播树不需要核心控制节点生成聚集树，并且可以节省大量带宽。为更好地说明问题，扩展网络仿真工具jns对聚集树算法和逆向构建多播树算法进行仿真。仿真拓扑结构如图1所示，通过收集LSR3和LSR4在两种不同多播算法下的流量来比较带宽使用情况。
点击看原图 MPLS技术解决了传统网络中IP分组交换的问题，能提供灵活的流量工程与虚拟专用网络的业务。MPLS与多播的结合可以有效解决多播的扩展问题。本文提出了逆向构建多播树算法，并且将其与传统的MPLS上构建多播树的方法进行比较，证明了其实施的可行性和优越性。 逆向构建多播树在缩减转发表的同时．降低了潜在的带宽浪费，为MPLS域内实现多播提供了一种新方法。但是，其具体实现细节，如健壮性、安全性及利用MPLS的特性对多播应用提供QoS保障等问题还需要进一步研究。 
