CN100433731C - 一种实现vpn组播的方法 - Google Patents

Abstract

本发明涉及一种公网组播分发树的匹配方法，包括：组管理路由器计算当前私网组播组在各现有的公网组播分发树中的各覆盖度数值；判断公网组播分发树中是否存在覆盖度数值大于覆盖度阈值的公网组播分发树，如果是，再判断是否存在唯一覆盖度最大的分发树，如果是，则选择该覆盖度最大的公网组播分发树；如果否，则再判断是否存在唯一静态的分发树，如果是，则选择该静态的公网组播分发树；如果否，则又判断是否存在唯一引用的数量最多的分发树，如果是，则选择该公网组播分发树；如果否，则选择创建时间最早的公网组播分发树。本发明还涉及一种实现VPN组播的方法，选择匹配的树或新建一个树。本发明减少了带宽的浪费。

Description

一种实现VPN组播的方法

技术领域

本发明涉及一种公网组播分发树的匹配方法，本发明还涉及一种实现VPN组播的方法。属通信领域。

背景技术

网络中，每个用户接入点称作一个站点(Site)。VPN(虚拟专用网)网络中包括如下实体：运营商边界路由器(Provider Edge Router，简称PE)用于在运营商骨干网中为用户提供网络接口、存储虚拟路由(VirtualRouting Forwarding Instance，简称VRF)转发、处理VPN-IPv4路由、接入位于各个站点的VPN子网，是VPN的主要实现部分；用户边界路由器(Customer Edge Router，简称CE)，用户VPN站点中接入运营商骨干网的网络接口，汇聚本站点的私网路由，发布和接收用户网络路由；运营商网络核心路由器(简称P路由器)，承担着所有数据包在骨干网中转发的任务；每个站点的VPN用户经用户边界路由器CE连接本地运营商边界路由器PE，并在PE上对应特定的存储虚拟路由VRF。VRF上配置一些策略，规定该站点的路由器可以接收哪些站点的路由信息，可以向外发布那些路由信息。每个PE根据BGP(边界网关协议)的扩展信息进行路由计算，生成每个相关VPN的路由表。运营商边界路由器PE设备维护多个路由表，支持动态路由协议的多实例。

运营商网络是用于传递不同站点的组播数据包的公网网络。其中，包括公网组播组(简称P-Group)，公网组播分发树(简称P-Tree)。

用户的私网是一个独立的、自治的IPv4网络系统。其中，包括私网组播组(简称C-Group)，私网组播分发树(简称C-Tree)。

组播VPN可以以多种形式方案实现，如单播方案，这种方案存在着严重的效率问题，每改变其中的一个CE，其它所有的都需要重新配置，因此系统的扩展性能很差。组播域方案(Multicast-Domain，简称MD)，组播数据在骨干网组播域路由器中采用洪泛的方式传送，数据转发不是最优转发，会到达没有私网接收者的路由器，然后被丢弃掉，这在一定程度上浪费了骨干网中的网络带宽，也增加了路由器的处理负荷。

目前较优的方案是组播域(MD)改进方案，当组播域中某个VPN的某个组播组数据传输量超过一定的阈值时，采用VPN-IP PIM方案会为该组播组建立一个动态的MDT(Multicast Distribution Tree，组播分发树)，组播流量可以沿着这条动态MDT优化路径流动。这样既能减小运营商管理公网中组播路由的负担，同时也为高速的组播数据传输提供了保障。事实上，这种为VPN建立动态MDT的方案仍然存在着一定的局限性，因为在运营上网络中需要支持的VPN数目很多，而且每个VPN中又有很多动态MDT，所以采用改进的组播域方法时公网中组播路由表项依然很多；同时，在这种方案当中只能检测公网组播组中流量大的情况，而对站点分布稀疏所造成的缺憾却不能很好的处理。

改进的组播域方案以其路由表项完全可控，同时又能针对特定的数据源进行优化传输的优势获得了大多数研究者的认可。但是，改进的组播域方案只考虑了某个源发送速率高的问题，而没有考虑站点分布稀疏的问题，而这时的带宽浪费依然是非常大的。

发明内容

本发明所要解决的技术问题在于针对现有技术中的不足，通过覆盖度计算，利用现有公网组播分发树进行匹配的方法，减少了公网中网络带宽的浪费，同时减少了公网中路由器维护的组播树信息量，在减小服务器负担的同时使得网络能够支持更多的虚拟专用网组播业务。

为此，本发明提供了一种公网组播分发树的匹配方法，包括如下步骤：

步骤1、组管理路由器按照如下覆盖度公式计算当前私网组播组在各现有的公网组播分发树中的各覆盖度数值，

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{Tree})$

其中，PEs为运营商边界路由器，C-Group为私网组播组，P-Tree为公网组播分发树，覆盖度是指当私网组播组的接收者运营商边界路由器成员都是公网组播分发树的运营商边界路由器成员时，私网组播组对公网组播分发树的覆盖程度；

步骤2、组管理路由器判断所述公网组播分发树中是否存在覆盖度数值大于预先设定的覆盖度阈值的公网组播分发树，如果是，则执行步骤3；如果否，则匹配失败，然后结束；

步骤3、组管理路由器在大于所述覆盖度阈值的公网组播分发树中判断是否存在唯一一个覆盖度最大的公网组播分发树，如果是，则将该覆盖度最大的公网组播分发树匹配为该私网组播组的分发树；如果否，则执行步骤4；

步骤4、组管理路由器在大于所述覆盖度阈值的公网组播分发树中判断是否存在唯一一个静态的公网组播分发树，如果是，则将该静态的公网组播分发树匹配为该私网组播组的分发树；如果否，则执行步骤5；

步骤5、组管理路由器判断是否存在唯一一个被各私网组播组引用的数量最多的公网组播分发树，如果是，则将该公网组播分发树匹配为该私网组播组的分发树；如果否，则执行步骤6；

步骤6、将创建时间最早的公网组播分发树匹配为该私网组播组的分发树。

本发明还提供了一种实现VPN组播的方法，包括如下步骤：

步骤1、组管理路由器依据改变承载树状态的私网组播组信号，在现有的公网组播分发树中，判断是否存在一个能够覆盖当前私网组播组的，并且按照所述公网组播分发树的匹配方法选择出的与该私网组播组相匹配的公网组播分发树；如果是，则执行步骤3；如果否，则执行步骤2；

步骤2、为该私网组播组建立一个新的公网组播分发树，然后结束；

步骤3、选择该公网组播分发树为该私网组播组的分发树。

本发明通过覆盖度计算，利用现有公网组播分发树进行匹配的方法，减少了公网中维护的组播路由表信息量；本发明又应用公网组播分发树的匹配方法，建立一个符合覆盖度要求的分发树，减少了现有技术中对接收成员站点分布稀疏所造成的带宽浪费，在覆盖度不满足条件的情况下，通过选择或新建一个P-Tree的方法，使得满足覆盖度的要求，就避免了接收成员站点分布稀疏的情况，减少了带宽的浪费，同时减少了公网中组播路由表维护的信息量。

下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。

附图说明

图1为本发明第一实施例的流程图；

图2为本发明第二实施例的流程图。

具体实施方式

下面首先介绍一下本发明所涉及的相关术语。

组管理路由器：为进行管理和维护工作并用于完成映射功能的路由器。组管理路由器是相对于每个C-Group来说的。如，切换到公网中的私网组播组(C-Group)，需要为其选择一个公网组播分发树(P-Tree)作为它的分发树。组管理路由器就是监督和管理C-Group，为其建立分发树P-Tree，并通知C-Group的其它接收者运营商边界路由器PE切换到该P-Tree上。一个路由器实体可能包含了很多的组管理路由器，这些组管理路由器可以共享该路由器的分发树，或者向该路由器申请新建一棵分发树。我们也用组管理路由器来表示一个包含组管理路由器的路由器实体。

覆盖度：是指当私网组播组(C-Group)的接收者PE成员都是P-Tree的PE成员时(也就是说两者是子集与原集的关系)，C-Group对P-Tree的覆盖程度。其值为[0，1]之间的一个实数值。如果采用某个P-Tree来分发该C-Group的数据包，覆盖度越小，则表示带宽浪费程度越大。其公式如下：

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{Tree})$

其中，PEs为运营商边界路由器，C-Group为私网组播组，P-Tree为公网组播分发树。

组播域：为每个VPN所配置的一棵的分发树，它是一棵静态共享树，包括了VPN的所有PE成员，所有的C-Group默认使用这棵树分发数据，一些VPN的控制消息也在这棵树中进行分发。

切换：私网中的数据包在公网中传输时，我们需要给它选择一个P-Tree作为分发树，而且为了优化传输，所采用的公网分发树也是动态变化的，我们把这个选择分发树的过程叫做“切换”过程。根据分发树类型的不同和切换的前提条件不同，切换也分为多种类型。

本发明所涉及的树型如下：

公网组播分发树(P-Tree)采用源树类型。当私网组播组(C-Group)是源树时，应当采用源树类型的P-Tree分发数据；当C-Group是共享树，但是站点内包括一个RP(Rendezvous Point，汇聚点)点，且数据源是单播数据包到RP点的，该组的数据包在穿越公网时，也可以采用源树类型的P-Tree，以实现最优转发。

公网组播分发树(P-Tree)采用共享树类型。私网组播组(C-Group)是共享树时，应当采用共享树类型的P-Tree。

公网组播分发树(P-Tree)还可以分为静态树和动态树两种。

静态树P-Tree是由手工配置建立的。凡是在公网中拓扑稳定的分发树都可以采用静态配置的方式，并且任何静态树是不能被路由器自动删除的。例如，所有的组播域必须采用静态树来实现，而且对于公网中长期出现的P-Tree也应当配置成静态组播树，以便于稳定公网中P-Tree路由项，减少维护开销，加快转发过程。

为了减少公网中的路由表的信息量，就必须支持动态树P-Tree。这些P-Tree只有在需要时才会被建立，并且在有C-Group引用时会一直存在，直到其引用计数为零时，组管理路由器才会主动释放该动态树，以减少公网中维护的组播路由项。可以建立的动态树的数量应当通过某种方式由运营商来控制，以保证运营商网络拥有良好的可扩展性。

PE路由器为了维护其所建立P-Tree以及C-Group与P-Tree的映射关系，需要维护树表和组表以管理这些基本信息。本发明所涉及的树表与组表如下：

树表保存了组管理路由器建立的P-Tree信息，是为C-Group选择公网转发树的主要依据。表1为树表所包含的数据项，如表1所示：

表1

IP Address

Tree Label

Tree-Type

Ref-Count

Dynamic

PEs-List

表1中，

IP Address：P-Tree的IPv4组播地址，即P-Group；

Tree Label：P-Tree的标记；

Tree-Type：P-Tree的类型，源树或是共享树；

Ref-Count：引用该树的C-Group个数；

Dynamic：动态建立的标记，标识该P-Tree是否是动态建立的；

PEs-List：PE成员列表，标识P-Tree所覆盖的PE成员。

表2为组表保存的切换到P-Tree上的C-Group的成员信息，如表2所示：

表2

VPN-RD

G

PEs-List

表2中，

VPN-RD：标识该组所属的VPN；

G：私网组播地址；

PEs-List：PE成员列表，标识该组覆盖的PE成员。

在组表中的C-Group是那些符合切换条件，离开默认的组播域分发树，在公网中进行优化传输的C-Group。为了表示该组发生了切换，并且维护该组在公网中的信息，需要组管理路由器周期性的向组播域发送相应的MDTJoin TLV(切换消息)消息，来通知其它接收者PE将该C-Group在组播域外的相应P-Tree上传输。

另一个可供选择的方案是：如果能够容忍Join(加入组播组)过程的延迟，就可以不用维护组表。当需要获取C-Group的成员列表时，通过临时发送成员PE查询消息来获知该组所有的成员PEs。

本发明所涉及的定义常量如下：

流量阈值：为了防止在边界上发生的频繁切换现象，需要定义流量阈值的上下两个边界。在流量检测过程中，当某个C-Group的流量高出流量上界时，它将被切换到公网当中，而当其流量低于流量下界时，它又会被切换回组播域当中。而在流量下界与上界之间存在一段死区，当流量值位于该区域时，C-Group保持原有状态不变。控制该死区的长度能够控制公网组播组的稳定程度。

实施例1

图1为本发明的第一实施例的流程图。如图1所示，包括如下步骤：

步骤1、组管理路由器按照如下覆盖度公式计算当前私网组播组在各现有的公网组播分发树中的各覆盖度数值，

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{Tree})$

其中，PEs为运营商边界路由器，C-Group为私网组播组，P-Tree为公网组播分发树；

步骤2、组管理路由器判断所述公网组播分发树中是否存在覆盖度数值大于预先设定的覆盖度阈值的公网组播分发树，如果是，则执行步骤3；如果否，则匹配失败，然后结束；

步骤3、组管理路由器在大于所述覆盖度阈值的公网组播分发树中判断是否存在唯一一个覆盖度最大的公网组播分发树，如果是，则执行步骤7；如果否，则执行步骤4；

步骤4、组管理路由器在大于所述覆盖度阈值的公网组播分发树中判断是否存在唯一一个静态的公网组播分发树，如果是，则执行步骤8；如果否，则执行步骤5；

步骤5、组管理路由器判断是否存在唯一一个被各私网组播组引用的数量最多的公网组播分发树，如果是，则执行步骤9；如果否，则执行步骤6；

步骤6、将选择创建时间最早的公网组播分发树匹配为该私网组播组的分发树；

步骤7、将该覆盖度最大的公网组播分发树匹配为该私网组播组的分发树，然后结束；

步骤8、将该静态的公网组播分发树匹配为该私网组播组的分发树，然后结束；

步骤9、将该公网组播分发树匹配为该私网组播组的分发树，然后结束。

以上步骤具体操作如下：

假设需要为一个包含成员{PE1，PE4，PE8}的组R分配一棵树，以下表11列表为树表。

其中覆盖度是计算得出的。

表11

序号	PE1	PE2	PE3	PE4	PE5	PE6	PE7	PE8	树型	引用数	覆盖度
												1	√	√	√	×	√	×	×	√	静态	13	-

2	√	√	×	√	×	×	√	√	静态	12	0.6
												3	×	√	√	√	×	×	√	√	静态	9	-
4	√	×	×	√	√	×	×	√	静态	16	0.75
												5	√	√	×	√	×	×	×	√	静态	16	0.75
6	×	√	√	√	√	√	√	×	静态	12	-
												7	√	×	√	√	×	√	×	√	静态	8	0.6
8	√	√	√	×	×	√	×	√	静态	11	-
												9	√	×	√	√	√	×	√	√	动态	3	0.5
10	√	√	×	√	×	√	√	×	动态	6	-
												11	×	√	√	×	×	×	×	×	动态	2	-
12	√	×	√	√	×	×	×	√	动态	1	0.75
												13	×	√	×	√	×	×	√	√	动态	1	-
14	×	×	×	×	×	×	√	×	动态	3	-
												15	√	√	×	√	√	×	×	√	动态	1	0.6
16	√	√	×	√	√	×	√	√	动态	2	0.5
												17	×	√	×	√	√	×	×	√	动态	1	-
18	√	×	×	√	×	√	×	×	动态	1	-
												19	×	×	√	×	×	×	×	×	动态	1	-

步骤101、假设我们将覆盖度阈值定为0.6，则我们可以看到满足覆盖度要求的树如表12所示，为：

表12

序号	PE1	PE2	PE3	PE4	PE5	PE6	PE7	PE8	树型	引用数	覆盖度
												2	√	√	×	√	×	×	√	√	静态	12	0.6
4	√	×	×	√	√	×	×	√	静态	16	0.75
												5	√	√	×	√	×	×	×	√	静态	16	0.75
7	√	×	√	√	×	√	×	√	静态	8	0.6
												12	√	×	√	√	×	×	×	√	动态	1	0.75
15	√	√	×	√	√	×	×	√	动态	1	0.6

步骤102、再选取唯一一个覆盖度最大的树，结果如表13中所示：

表13

序号	PE1	PE2	PE3	PE4	PE5	PE6	PE7	PE8	树型	引用数	覆盖度
												4	√	×	×	√	√	×	×	√	静态	16	0.75
5	√	√	×	√	×	×	×	√	静态	16	0.75
												12	√	×	√	√	×	×	×	√	动态	1	0.75

步骤103、步骤102中没有得到唯一的树，则选取静态树，结果如表14中所示：

表14

序号	PE1	PE2	PE3	PE4	PE5	PE6	PE7	PE8	树型	引用数	覆盖度
												4	√	×	×	√	√	×	×	√	静态	16	0.75
5	√	√	×	√	×	×	×	√	静态	16	0.75

步骤104、步骤103也没有得到唯一的树，则选取引用数最多的树。如表15中所示，而由于现在选出的两棵树引用数相同，故结果没有变化：

表15

序号	PE1	PE2	PE3	PE4	PE5	PE6	PE7	PE8	树型	引用数	覆盖度
												4	√	×	×	√	√	×	×	√	静态	16	0.75
5	√	√	×	√	×	×	×	√	静态	16	0.75

步骤105、步骤104中也没有得到唯一的树，则选取创建时间最早的树，如表16中所示，时间最早的在第一个，结果如下：

表16

序号	PE1	PE2	PE3	PE4	PE5	PE6	PE7	PE8	树型	引用数	覆盖度
												4	√	×	×	√	√	×	×	√	静态	16	0.75

经过以上步骤，即可选取出序号为4的结果唯一的树，将该树匹配给组R，引用数加一，并修改树表和组表中维护的其它信息，一次选树和分配过程即可完成。

实施例2

图2为本发明第二实施例的流程图。实施例2为一种实现VPN组播的方

法，包括如下步骤：

步骤11、组管理路由器依据改变承载树状态的私网组播组信号，在现有的公网组播分发树中，判断是否存在一个能够覆盖当前私网组播组的，并且按照所述公网组播分发树的匹配方法选择出的与该私网组播组相匹配的公网组播分发树；如果是，则执行步骤13；如果否，则执行步骤12；

步骤12、为该私网组播组建立一个新的公网组播分发树，然后结束；

步骤13、选择该公网组播分发树为该私网组播组的分发树。

本实施例中步骤12中所说的建立一个新的树，是针对当前的私网组播组内的成员单独建立一个新的公网组播分发树。

实施例3

本实施例与实施例2的区别仅在于步骤11中的组管理路由器接收到改变承载树状态的私网组播组信号来自于网络侧发来的新增用户组播组或现有组播组的新用户加入消息。

实施例4

本实施例与实施例2的区别仅在于步骤11中的改变承载树状态的私网组播组信号来自于组管理路由器判断覆盖度的数值是否小于预先设定的第一覆盖度阈值，并且流量数值是否小于预先设定的流量阈值的信号。

实施例5

本实施例与实施例2的区别仅在于步骤11中的改变承载树状态的私网组播组信号来自于组管理路由器判断覆盖度数值是否小于等于预先设定的第二覆盖度阈值，并且流量数值是否大于等于预先设定的流量阈值的信号。

最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。

Claims (5)

1.一种公网组播分发树的匹配方法，其特征在于，包括如下步骤：

步骤1、组管理路由器按照如下覆盖度公式计算当前私网组播组在各现有的公网组播分发树中的各覆盖度数值，

$\mathrm{PEs}(C-\mathrm{Group})\⊆(P-\mathrm{Tree})$

其中，PEs为运营商边界路由器，C-Group为私网组播组，P-Tree为公网组播分发树，覆盖度是指当私网组播组的接收者运营商边界路由器成员都是公网组播分发树的运营商边界路由器成员时，私网组播组对公网组播分发树的覆盖程度；

步骤2、组管理路由器判断所述公网组播分发树中是否存在覆盖度数值大于预先设定的覆盖度阈值的公网组播分发树，如果是，则执行步骤3；如果否，则匹配失败，然后结束；

步骤3、组管理路由器在大于所述覆盖度阈值的公网组播分发树中判断是否存在唯一一个覆盖度最大的公网组播分发树，如果是，则将该覆盖度最大的公网组播分发树匹配为该私网组播组的分发树；如果否，则执行步骤4；

步骤4、组管理路由器在大于所述覆盖度阈值的公网组播分发树中判断是否存在唯一一个静态的公网组播分发树，如果是，则将该静态的公网组播分发树匹配为该私网组播组的分发树；如果否，则执行步骤5；

步骤5、组管理路由器判断是否存在唯一一个被各私网组播组引用的数量最多的公网组播分发树，如果是，则将该公网组播分发树匹配为该私网组播组的分发树；如果否，则执行步骤6；

步骤6、将创建时间最早的公网组播分发树匹配为该私网组播组的分发树。

2.一种应用权利要求1所述的公网组播分发树的匹配方法实现VPN组播的方法，其特征在于，包括如下步骤：

步骤1、组管理路由器依据改变承载树状态的私网组播组信号，在现有的公网组播分发树中，判断是否存在一个能够覆盖当前私网组播组的，并且按照所述公网组播分发树的匹配方法选择出的与该私网组播组相匹配的公网组播分发树；如果是，则执行步骤3；如果否，则执行步骤2；

步骤2、为该私网组播组建立一个新的公网组播分发树，然后结束；

步骤3、选择该公网组播分发树为该私网组播组的分发树。

3.根据权利要求2所述的实现VPN组播的方法，其特征在于，所述改变承载树状态的私网组播组信号来自于网络侧发来的新增用户组播组或现有组播组的新用户加入消息。

4.根据权利要求2所述的实现VPN组播的方法，其特征在于，所述步骤1中的改变承载树状态的私网组播组信号来自于组管理路由器判断覆盖度的数值是否小于预先设定的第一覆盖度阈值，并且流量数值是否小于预先设定的流量阈值的信号。

5.根据权利要求2所述的实现VPN组播的方法，其特征在于，所述步骤1中的改变承载树状态的私网组播组信号来自于组管理路由器判断覆盖度数值是否小于等于预先设定的第二覆盖度阈值，并且流量数值是否大于等于预先设定的流量阈值的信号。

Images