本发明涉及通信技术领域， 尤其涉及一种基于内部网关协议创建双向 组播分发树的方法、 装置及系统。 背景技术

当前网络中有很多多点到多点的组播应用场景 ， 多点到多点的组播应 用场景是通过覆盖 （Overlay )技术将二层虚拟局域网 （Virtual Local Area Network, 以下筒称为 VLAN ) 中的广播报文承载在对应的三层组播组上， 通过三层组播组分发树来模拟二层 VLAN中未知单播洪泛、 广播等多点到 多点的局域网应用。 在多点到多点的组播场景中， 每个边缘路由器既连接 组播源又连接接收者， 这种场景下比较适合采用双向组播分发树， 组播数 据 4艮文可以从叶子到根， 也可以从根到叶子。 目前， 一般通过双向协议无 关组播（ Protocol Independent Multicast , 以下筒称为 ΡΙΜ )来构建网络中双 向组播分发树。

在实现本发明实施例的过程中， 发明人发现， 现有技术至少存在以下 问题： 在多点到多点的组播场景中，在需要实现组播 时采用双向 ΡΙΜ协议， 同时也需要运行内部网关协议（ Interior Gateway Protocol, 以下筒称为 IGP ) 作为单播路由协议， 所以需要同时运维两套协议， 运维复杂。

发明内容

本发明实施例提供一种基于内部网关协议创建 双向组播分发树的方 法、 装置及系统， 以解决现有技术中在多点到多点的组播场景中 ， 需要同 时运维 IGP单播路由协议和 PIM组播路由协议两套协议出现的运维复杂的 问题。

为达到上述目的， 本发明实施例采用如下技术方案：

一方面， 提供了一种基于 IGP创建双向组播分发树的方法， 包括： 接收至少一个第一节点通过 IGP洪泛过来的所述第一节点的树根地址 以及所述第一节点支持的组播组范围， 所述第一节点为作为整网洪泛树 ( Flooding Tree )树根的节点； 根据所述第一节点的树根地址以及最短路径 树算法， 以所述第一节点为源节点生成到其他节点的最 短路径， 根据所述 最短路径构成洪泛树； 在接收到边缘节点通过 IGP洪泛过来的三层组播组 信息时， 根据所述三层组播组信息以及所述第一节点支 持的组播组范围确 定各三层组播组对应的洪泛树， 并根据所述三层组播组信息对各三层组播 组对应的洪泛树进行剪枝以生成双向组播分发 树。

进一步， 可选的， 在所述根据所述第一节点的树根地址以及最短 路径 树算法， 以所述第一节点为源节点生成到其他节点的最 短路径， 根据所述 最短路径构成洪泛树之后， 还包括： 若洪泛树的分支或叶子节点有多个到 达所述第一节点的父亲节点， 根据多个父亲节点的属性值从所述多个父亲 节点中选取唯一的节点作为所述分支或叶子节 点到达所述第一节点的父亲 节点。

进一步， 可选的， 当所述 IGP为中间系统到中间系统的路由选择协议 ( Intermediate System to Intermediate System Routing Protocol, 以下筒称为 IS-IS )时， 所述父亲节点的属性值包括系统 ID。 当所述 IGP为开放式最短 路径优先（ Open Shortest Path First, 以下筒称为 0SPF )协议时， 所述父亲 节点的属性值包括路由器 ID。

进一步， 可选的， 在所述根据所述第一节点的树根地址以及最短 路径 树算法， 以所述第一节点为源节点生成到其他节点的最 短路径， 根据所述 最短路径构成洪泛树之后， 还包括： 若洪泛树中的两个节点之间存在多条 平行链路， 根据多条平行链路的属性值从所述多个平行链 路中选取唯一的 链路作为两个节点之间的链路。

进一步， 可选的， 当所述 IGP为 IS-IS时， 所述平行链路的属性值包括 线路 ID或者伪节点 ID。 当所述 IGP为 OSPF协议时，所述平行链路的属性 值包括接口 IP地址。

进一步， 可选的， 所述第一节点支持的组播组范围包括该第一节 点支 持的组播 IP地址以及该组播 IP地址对应的掩码，所述根据所述三层组播组 信息以及所述第一节点支持的组播组范围确定 各三层组播组对应的洪泛 树， 包括： 根据所述的三层组播组信息以及所述第一节点 携带的组播 IP地 址范围， 为所述三层组播组选取相应的第一节点； 若存在多个第一节点覆 盖同一个组播组， 根据所述多个第一节点携带的掩码， 从所述多个第一节 点中选取出掩码最长的第一节点作为所述多个 第一节点覆盖的三层组播组 相应的第一节点； 若存在多个掩码最长的第一节点， 采用 HASH算法从所 述多个掩码最长的第一节点中选取唯一的节点 作为所述多个掩码最长的第 一节点覆盖的三层组播组相应的第一节点。

进一步， 可选的， 所述根据所述三层组播组信息对各三层组播组 对应 的洪泛树进行剪枝， 包括： 根据洪泛树生成本地节点的对应的出接口列表 ； 根据洪泛树对应的每个三层组播组， 遍历所述出接口列表中每个出接口连 接的节点； 若该出接口连接的节点以及由该节点递归到叶 子节点的支路上 所有节点均不为发布所述组播组信息的边缘节 点， 则删除所述出接口列表 中该出接口的出接口信息； 在遍历完成所述出接口列表中所有出接口连接 的节点后， 若所述出接口列表中仅剩有与上游节点连接的 出接口且本地节 点也不为发布所述组播组信息的边缘节点， 不生成与所述三层组播组对应 的组播转发表项， 否则根据遍历之后的出接口列表生成与所述三 层组播组 对应的组播转发表项。 另一方面， 还提供了一种基于 IGP创建双向组播分发树的装置， 包括： 第一接收单元， 用于接收至少一个第一节点通过 IGP洪泛过来的所述 第一节点的树根地址以及所述第一节点支持的 组播组范围， 所述第一节点 为作为整网洪泛树树根的节点；

第一创建单元， 用于根据所述第一接收单元接收的所述第一节 点的树 根地址以及最短路径树算法， 以所述第一节点为源节点生成到其他节点的 最短路径， 根据所述最短路径构成洪泛树；

第二接收单元， 用于接收边缘节点通过 IGP洪泛过来的三层组播组信 息；

确定单元， 用于在所述第二接收单元接收到边缘节点通过 IGP洪泛过 来的三层组播组信息时， 根据所述三层组播组信息以及所述第一接收单 元 接收的所述第一节点支持的组播组范围确定各 三层组播组对应的洪泛树； 剪枝单元， 用于根据所述三层组播组信息对所述确定单元 确定的各三 层组播组对应的洪泛树进行剪枝以生成双向组 播分发树。

进一步， 可选的， 所述基于 IGP创建双向组播分发树的装置， 还包括： 第一选取单元， 用于若所述第一创建单元创建的洪泛树的分支 或叶子 节点有多个到达所述第一节点的父亲节点， 根据多个父亲节点的属性值从 所述多个父亲节点中选取唯一的节点作为所述 分支或叶子节点到达所述第 二节点的父亲节点。

进一步， 可选的， 当所述 IGP为 IS-IS时， 所述父亲节点的属性值包括 系统 ID。 当所述 IGP为 OSPF协议时， 所述父亲节点的属性值包括路由器 ID。

进一步， 可选的， 所述基于 IGP创建双向组播分发树的装置， 还包括： 第二选取单元， 用于若所述第一创建单元创建的洪泛树中的两 个节点 之间存在多条平行链路， 根据多条平行链路的属性值从所述多个平行链 路 中选取唯一的链路作为两个节点之间的链路。 进一步， 可选的， 当所述 IGP为 IS-IS时， 所述平行链路的属性值包括 线路 ID或者伪节点 ID。 当所述 IGP为 OSPF协议时，所述平行链路的属性 值包括接口 IP地址。

进一步， 可选的， 所述确定单元， 包括：

第一选取子单元， 用于根据所述的三层组播组信息以及所述第一 节点 携带的组播 IP地址范围， 为所述三层组播组选取相应的第一节点；

第二选取子单元， 用于若所述第一选取子单元选取得到存在多个 第一 节点覆盖同一个组播组， 根据所述多个第一节点携带的掩码， 从所述多个 第一节点中选取出掩码最长的第一节点作为所 述多个第一节点覆盖的三层 组播组相应的第一节点；

第三选取子单元， 用于若所述第二选取子单元选取得到存在多个 掩码 最长的第一节点， 采用 HASH算法从所述多个掩码最长的第一节点中选� � 唯一的节点作为所述多个掩码最长的第一节点 覆盖的三层组播组相应的第 一节点。

进一步， 可选的， 所述根据所述剪枝单元， 包括：

第一生成子单元， 用于根据洪泛树生成本地节点的对应的出接口 列表； 遍历子单元， 用于根据洪泛树对应的每个三层组播组， 遍历所述出接 口列表中每个出接口连接的节点；

删除子单元， 用于若遍历子单元遍历的该出接口连接的节点 以及由该 节点递归到叶子节点的支路上所有节点均不为 发布所述组播组信息的边缘 节点， 则删除所述出接口列表中该出接口的出接口信 息；

生成子单元， 用于在遍历完成所述出接口列表中所有出接口 连接的节 点后， 若所述出接口列表中仅剩有与上游节点连接的 出接口且本地节点也 不为发布所述组播组信息的边缘节点， 不生成与所述三层组播组对应的组 播转发表项， 否则根据遍历之后的出接口列表生成与所述三 层组播组对应 的组播转发表项。 再一方面， 还提供了一种基于 IGP创建组播分发树的系统， 包括： 第一节点， 用于通过 IGP洪泛所述第一节点的树根地址以及所述第一 节点支持的组播组范围， 所述第一节点为作为整网洪泛树树根的节点； 边缘节点， 用于通过 IGP洪泛三层组播组信息；

普通节点， 用于接收至少一个第一节点洪泛过来的所述第 一节点的树 根地址以及所述第一节点支持的组播组范围， 根据所述第一节点的树根地 址以及最短路径树算法， 以所述第一节点为源节点生成到其他节点的最 短 路径， 根据所述最短路径构成洪泛树；

所述普通节点， 还用于在接收到所述边缘节点洪泛过来的三层 组播组 信息时， 根据所述三层组播组信息以及所述第一节点支 持的组播组范围确 定各三层组播组对应的洪泛树， 并根据所述三层组播组信息对各三层组播 组对应的洪泛树进行剪枝以生成双向组播分发 树。

本发明实施例提供的基于内部网关协议创建双 向组播分发树的方法、 装置及系统， 根据第一节点通过 IGP洪泛过来的第一节点的树根地址以及 最短路径树算法， 以第一节点为源节点生成到其他节点的最短路 径， 根据 所述最短路径构成洪泛树， 在接收到边缘节点通过 IGP洪泛过来的三层组 播组信息时， 根据所述三层组播组信息以及第一节点支持的 组播组范围确 定各三层组播组对应的洪泛树， 并根据所述三层组播组信息对各三层组播 组对应的洪泛树进行剪枝以生成双向组播分发 树， 实现了基于 IGP创建双 向组播分发树， 使得在多点到多点的组播场景中， 不管是需要实现组播还 是需要实现单播， 均采用 IGP, 筒化了协议的运维， 解决了现有技术中在多 点到多点的组播场景中， 需要同时运维 IGP单播路由协议和 PIM组播路由 协议两套协议出现的运维复杂的问题。 附图说明

图 1 ( a ) 为本发明实施例一提供的基于 IGP创建双向组播分发树的方 法的流程图一; 图 1 (b)为本发明实施例一提供的基于 IGP创建双向组播分发树的方 法的流程图二；

图 2 (a) 为本发明实施例二提供的多点到多点的组播场 景的网络架构 图；

图 2 ( b )为本发明实施例二提供的基于 IGP创建双向组播分发树的方 法的流程图；

图 2 (c)为本发明实施例二提供的以 R1为树根的洪泛树；

图 2 (d)为本发明实施例二提供的以 R2为树根的洪泛树；

图 2 (e)为本发明实施例二提供的两个第二节点 RP1、 RP2在构建双 向组播分发树时， 构建得到两颗双向组播分发树；

图 2 (f)为图 2 (e) 中的第一颗双向组播分发树；

图 2 (g)为图 2 (e) 中的第二颗双向组播分发树；

图 2 (h)为图 2 (b)所示的基于 IGP创建双向组播分发树的方法中步 骤 206的方法流程图一；

图 2 (i)为图 2 (b)所示的基于 IGP创建双向组播分发树的方法中步 骤 206的方法流程图二；

图 3 (a) 为本发明实施例三提供的基于 IGP创建双向组播分发树的装 置的结构示意图一；

图 3 (b)为图 3 (a)所示的基于 IGP创建双向组播分发树的装置中确 定单元的结构示意图；

图 3 (c)为图 3 (a)所示的基于 IGP创建双向组播分发树的装置中剪 枝单元的结构示意图；

图 3 (d)为本发明实施例三提供的基于 IGP创建双向组播分发树的装 置的结构示意图二；

图 3 (e)为本发明实施例三提供的节点设备的结构示 意图二。 具体实施方式

为了解决现有技术中在多点到多点的组播场景 中， 需要同时运维 IGP 单播路由协议和 PIM组播路由协议两套协议出现的运维复杂的问 题， 本发 明实施例提供一种基于 IGP创建双向组播分发树的方法、 装置及系统。 实施例一：

如图 1(a)所示， 本发明实施例提供的一种基于 IGP创建双向组播分发 树的方法， 在本实施例中， 可以应用于整网的所有节点， 该方法包括：

101、接收至少一个第一节点通过 IGP洪泛过来的所述第一节点的树根 地址以及所述第一节点支持的组播组范围。

其中， 所述第一节点为作为整网洪泛树树根的节点。 所述第一节点的 树根地址以及所述第一节点支持的组播组范围 可以是预先配置的， 在本实 施例中，每个第一节点上至少配置有一个 IP地址， 所述 IP地址即为所述树 根地址。 当然， 其中第一节点支持的组播组范围也可以是所述 第一节点根 据自身的属性自动配置的， 此处不作限定。

值得说明的是所述第一节点的树根地址以及所 述第一节点支持的组播 组范围可以同时封装在一个配置信息中， 也可以进行分别封装， 再进行分 别洪泛， 此处不作限定。

102、根据所述第一节点的树根地址以及最短路 径树（ Shortest Path Tree, 以下筒称为 SPT ) 算法， 以所述第一节点为源节点生成到其他节点的最 短 路径， 根据所述最短路径构成洪泛树。

103、 在接收到边缘节点通过 IGP洪泛过来的三层组播组信息时， 根据 所述三层组播组信息以及所述第一节点支持的 组播组范围确定各三层组播 组对应的洪泛树， 并根据所述三层组播组信息对各三层组播组对 应的洪泛 树进行剪枝以生成双向组播分发树。

值得说明的是， 由于每个节点都基于第一节点独立计算第一节 点作为 源节点到其他节点的最短路径， 每个节点都拥有统一的全网拓朴， 采用相 同的算法 ， 因此所有节点对于最短路径树的形态理解都是 一致的， 这样相 对于现有技术中的 ΡΙΜ网络， 双向组播分发树上的节点需要周期性往上游 发送 Join、 Prune消息， 本发明实施例中提供的方法不需要 PIM 网络中的 Join, Prune消息 ， 也能够生成以第一节点为根的最短路径树信息 以构成洪 泛树， 进一步通过剪枝生成相应的双向组播分发树， 减轻了 CPU的处理负 担。

如图 1(b)所示， 进一步的， 为了避免相同的组播组报文被重复发往第 一节点， 在所述根据所述第一节点的树根地址以及最短 路径树算法， 以所 述第一节点为源节点生成到其他节点的最短路 径， 根据所述最短路径构成 洪泛树之后， 还包括：

104、 若洪泛树的分支或叶子节点有多个到达所述第 一节点的父亲节 点， ^ ^: 艮据多个父亲节点的属性值从所述多个父 亲节点中选取唯一的节点作 为所述分支或叶子节点到达所述第一节点的父 亲节点。

其中， 所述叶子节点就是树中最底端的节点， 叶子节点没有子节点。 值得说明的是,对于不同的 IGP,其对应的父亲节点的属性值是不同的， 举例说明，在所述 IGP为 IS-IS时，所述父亲节点的属性值可以包括系统 ID; 在所述 IGP为 OSPF协议时， 所述父亲节点的属性值可以包括路由器 ID, 当然还有其他的 IGP, 可以应用该方法， 此处不——赘述。

如图 1(b)所示， 进一步的， 为了避免相同的组播组报文被重复的发往 一个节点， 在所述根据所述第一节点的树根地址以及最短 路径树算法， 以 所述第一节点为源节点生成到其他节点的最短 路径， 根据所述最短路径构 成洪泛树之后， 还包括：

105、 若洪泛树中的两个节点之间存在多条平行链路 ， 根据多条平行链 路的属性值从所述多个平行链路中选取唯一的 链路作为两个节点之间的链 路。

值得说明的是，对于不同的 IGP,其对应的平行链路的属性值是不同的， 举例说明，在所述 IGP为 IS-IS时，所述平行链路的属性值可以包括线路 ID ( Circuit ID ), 或者伪节点 ID ( Pseudonode ID ); 在所述 IGP为 OSPF协议 时， 所述平行链路的属性值可以包括接口 IP地址， 当然还有其他的 IGP, 可以应用该方法， 此处不——赘述。

本发明实施例提供的基于内部网关协议创建双 向组播分发树的方法， 根据各第一节点通过 IGP洪泛过来的第一节点的树根地址以及最短路 径树 算法， 以第一节点为源节点生成到其他节点的最短路 径， 根据最短路径构 成洪泛树， 在接收到边缘节点通过 IGP洪泛过来的三层组播组信息时， 根 据所述三层组播组信息以及第一节点支持的组 播组范围确定各三层组播组 对应的洪泛树， 并根据所述三层组播组信息对各三层组播组对 应的洪泛树 进行剪枝以生成双向组播分发树， 实现了基于 IGP创建双向组播分发树， 使得在多点到多点的组播场景中， 不管是需要实现组播还是需要实现单播， 均采用 IGP, 筒化了协议的运维，解决了现有技术中在多点 到多点的组播场 景中， 需要同时运维 IGP单播路由协议和 PIM组播路由协议两套协议出现 的运维复杂的问题。

为了使本领域技术人员能够更清楚地理解本发 明实施例提供的技术方 案， 下面通过具体的实施例， 对本发明实施例提供的基于内部网关协议创 建双向组播分发树的方法进行详细说明。 实施例二：

本发明又一实施例提供的一种基于 IGP创建双向组播分发树的方法， 应用于多点到多点的组播场景中，如图 2(a)所示，为多点到多点的组播场景 的网络架构图， 整网中包括多个节点 （R1~R11 ), 其中边缘节点 R2和 R9 下面挂接三层组播组 G1的终端， 边缘节点 R4和 R10下面挂接三层组播组 G2的终端； 其中， Rl、 R3、 R7、 R8为第一节点。 如图 2(b)所示， 所述基 于 IGP创建双向组播分发树的方法， 包括：

201、 整网中的第一节点将配置信息发送给整网节点 。 其中， 所述第一节点为整网中作为洪泛树树根的节点 。

在本实施例， 所述配置信息包括该第一节点的树根地址以及 该第一节 点支持的组播组范围。

具体的， R1将自身的配置信息洪泛给整网中的 R2~R11 ; R3将自身的 配置信息洪泛给整网中的 Rl、 R2、 R4-R11 ; R7将自身的配置信息洪泛给 整网中的 R1~R6、 R8-R11 ; R8将自身的配置信息洪泛给整网中的 Rl~ R7、 R9~ R11。

202、 整网节点接收所述配置信息， 根据各第一节点发送的配置信息中 的树根地址以及最短路径树算法， 以各第一节点为源节点生成到其他节点 的最短路径， 根据所述最短路径构成洪泛树。

如果存在多颗泛洪树， 则根据泛洪树树根 IP地址大小对树进行排序， 比如有 n颗树， 则树的编号从 1一直到 n。

此处以 Rl、 R7为例进行详细的说明：

若 R1树根 IP比 R7的树根 IP地址小，则以 R1为树根的泛洪树为第一 颗树， 以 R7为树根的泛洪树为第二颗树。

以 R1为源节点， 如图 2(c)所示， 生成 R1到其他节点的最短路径， 构 成第一颗双向组播分发树——树根为 R1 , 第一颗双向组播分发树由以下路 径组成： R1- R4- R9- R11 ; Rl- R3- R6; Rl- R2- R7- RIO; Rl- R2- R5- R8» 以 R7为源节点， 如图 2(d)所示， 生成 R7到其他节点的最短路径， 构 成第二颗双向组播分发树——树根为 R7 , 第一颗双向组播分发树由以下路 径组成： R7- R2- Rl- R4; R7- R5- R3- R6; R7- RIO- R8; R7-謂- Rll- R9。

203、 若洪泛树的分支或叶子节点有多个到达所述第 一节点的父亲节 点， ^ ^: 艮据多个父亲节点的属性值从所述多个父 亲节点中选取唯一的节点作 为所述分支或叶子节点到达所述第一节点的父 亲节点。

值得说明的是，对于不同的 IGP,其对应的父亲节点的属性值是不同的， 例如， 在所述 IGP为 IS-IS时， 所述父亲节点的属性值可以包括系统 ID; 在所述 IGP为 OSPF协议时， 所述父亲节点的属性值可以包括路由器 ID, 当然还有其他的 IGP, 可以应用该方法， 此处不——赘述。

在本实施例中， 以在 IGP为 IS-IS为例进行详细的说明， 所述父亲节点 的属性值可以是系统 ID, 多个父节点的数目为 K, 所述根据多个父亲节点 的属性值从所述多个父亲节点中选取唯一的节 点作为所述分支或叶子节点 到达第一节点的父亲节点， 具体可以包括： 按照多个父亲节点的系统 ID将 多个父亲节点进行排序， 排序为： Parent 1、 Parent2... ParentK , 对于第 J颗 树， 选取第 J mod K个父亲节点。

在本实施例中， 以 IGP为 OSPF协议为例进行详细的说明， 父亲节点 的属性值可以是路由器 ID, 多个父亲节点的数目为 K, 所述根据多个父亲 节点的属性值从所述多个父亲节点中选取唯一 的节点作为所述分支或叶子 节点到达第一节点的父亲节点， 具体可以包括： 按照多个父亲节点的路由 器 ID将多个父亲节点进行排序， 排序为： Parentl , Parent2... ParentK, 对 于第 J颗树， 选取第 J mod K个父亲节点。

举例说明，对如图 2(e)所示，两个第一节点 RP1、 RP2在构建洪泛树时， 构建得到两颗洪泛树。 第一颗双向组播分发树为——以 RP1为树根， 第一 颗双向组播分发树由以下路径组成： RP1-R2-R1 ; RP1-R3-R1 ; RP1-R4。 第 二颗双向组播分发树为——以 RP2为树根， 第二颗双向组播分发树由以下 路径组成： RP2-R2-R1 ; RP2-R3-R1 ; RP2-R4。 其中 Rl、 R4为边缘节点， 连接有组播源和接收者， 构建的洪泛树中的每个节点之间的链路 cost值相 同， R1可以通过两个父亲节点 R2、 R3到达 RP1 , 也可以通过两个父亲节 点 R2、 R3到达 RP2, 为了避免相同的组播报文的被重复的发往第一 节点 RP1、 RP2通过步骤 203的计算， 选取唯一的节点作为 R1到达 RP1的父亲 节点， 选取唯一的节点作为 R1到达 RP2的父亲节点， 形成如图 2(f)所示的 第一颗双向组播分发树以及如图 2(g)所示的第二颗双向组播分发树， 其中 第一颗双向组播分发树以 RP1 为树根， 由以下路径组成： RP1-R2-R1 ; RP1-R4。 第二颗双向组播分发树以 RP2 为树根， 由以下路径组成： RP2-R3-R1 ; RP2-R4。 这样， 从 R1发往 RP1 的组播数据报文， 只能经过 R2进行转发。 从 R4发往 RP1的组播数据报文， 经过 RP1到达 R2, 只有 R2 (通过 R2-R1接口 ) 才能往下面洪泛链路发送组播数据报文， 不会通过 R3往下面洪泛链路发送组播数据报文， 避免 R1收到双份重复流量。

204、 若在洪泛树中的两个节点之间存在多条平行链 路， 根据多条平行 链路的属性值从所述多个平行链路中选取唯一 的链路作为两个节点之间的 链路。

值得说明的是，对于不同的 IGP,其对应的平行链路的属性值是不同的， 例如， 在所述 IGP 为 IS-IS 时， 所述平行链路的属性值可以是线路标识 ( Circuit ID ),也可以是伪节点标识（ Pseudonode ID ); 在所述 IGP为 OSPF 协议时， 平行链路的属性值可以是接口 IP地址， 当然还有其他的 IGP, 可 以应用该方法， 此处不——赘述。

在本实施例中， 以 IGP为 IS-IS为例进行详细的说明， 所述平行链路的 属性值可以是线路 ID或者伪节点标识 ID, 多个平行链路的数目为 K,所述 根据多条平行链路的属性值从所述多个平行链 路中选取唯一的链路作为两 个节点之间的链路， 具体可以包括： 按照多个平行链路的属性值可以是线 路 ID或者伪节点标识 ID, 将多个平行链路进行排序， 排序为： Linel、 Line 2... Line K, 对于第 J颗树， 选取第 J mod K个平行链路。 当然， 对于 OSPF 协议， 所述根据多条平行链路的属性值从所述多个平 行链路中选取唯一的

205、边缘节点将与其连接的三层组播组信息 通过 IGP洪泛给整网节点。 其中， 所述边缘节点为整网中与组播源和 /或接收者连接的节点。

一般来说， 边缘节点连接的组播源同时也可以是接收者， 接收者都会 通过 Internet组管理协议 ( Internet Group Management Protocol , 以下筒称为 IGMP )报文发起加入其需要加入的三层组播组， 边缘节点可以根据接收者 发送的 IGMP报文获得三层组播组信息。 如果， 边缘节点连接到组播源不 是接收者， 边缘节点可以通过静态配置或者感知组播源发 送过来的组播数 据流首包报文获取连接的三层组播组信息。

206、 整网节点在接收到边缘节点洪泛过来的三层组 播组信息时， 根据 所述三层组播组信息以及各第一节点支持的组 播组范围确定各三层组播组 对应的洪泛树， 根据所述三层组播组信息对各三层组播组对应 的洪泛树进 行剪枝以生成双向组播分发树。

其中所述第一节点支持的组播组范围为预先配 置的对应的三层组播 组， 表明该三层组播组可以使用该第一节点所在的 最短路径转发组播组数 据流量。在本实施例中，所述第一节点支持的 组播组范围，采用 group-range 方式， group-range组织方式为〈组播 IP地址、 掩码 >。

在本实施例中， 所述根据所述三层组播组信息以及各第一节点 支持的 组播组范围确定各三层组播组对应的洪泛树， 如图 2 ( h )所示， 具体可以 包括：

2061、 根据所述的三层组播组信息以及各第一节点携 带的组播 IP地址 范围， 为所述三层组播组选取相应的第一节点。

2062、 若存在多个第一节点覆盖同一个组播组， 根据所述多个第一节 点携带的掩码， 从所述多个第一节点中选取出掩码最长的第一 节点作为所 述多个第一节点覆盖的三层组播组相应的第一 节点。

2063、 若存在多个掩码最长的第一节点， 采用 HASH算法从所述多个 掩码最长的第一节点中选取唯一的节点作为所 述多个掩码最长的第一节点 覆盖的三层组播组相应的第一节点。

具体的， 在本实施例中， 采用 HASH值大的优先选择， HASH算法可 以是：

Value(G,M,C(i))=(l 103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2 ^Λ 31 其中， G为组播组地址， M为自举路由器 （Bootstrap Router , 以下 筒称为 BSR )发布的计算掩码， C(i)为树根地址。

筒要说明：上述算法就是如果有多个 group-range覆盖了同一个组播组， 则使用掩码长度长的第一节点， 如果掩码长度相同， 则根据 HASH算法选 择一个唯一的第一节点。 最终， 整网所有节点对于同一个三层组播组， 会 选择同一个第一节点作为树根。

在本实施例中， 所述根据所述三层组播组信息对各三层组播组 对应的 洪泛树进行剪枝以生成双向组播分发树， 如图 2 ( i )所示， 具体可以包括：

2064、 根据洪泛树生成本地节点的对应的出接口列表 。

在本实施例中， 以图 2 ( a )所示的多点到多点组播场景以及图 2 ( c ) 所示的洪泛树为例进行详细的说明。

具体的，以 R1为树根的洪泛树中每个节点上均根据洪泛树� ��成本地节 点的对应的出接口列表。例如，在节点 R2上生成如表 1所示的出接口列表， 在节点 R4上生成如表 2所示的出接口列表， 在节点 R7上生成如表 3所示 的出接口列表。

表 1 : 节点 R2上生成的出接口列表 出接口 21

出接口 25

出接口 27 表 2: 节点 R4上生成的出接口列表 出接口 41

出接口 49 表 3: 节点 R7上生成的出接口列表 出接口 72 出接口 710

2065、 根据洪泛树对应的每个三层组播组， 遍历所述出接口列表中每 个出接口连接的节点。

在本实施例中， 以图 2 ( a )所示的多点到多点组播场景以及图 2 ( c ) 所示的洪泛树为例进行详细的说明。

假设， 根据上述步骤： 根据所述三层组播组信息以及各第一节点支持 的组播组范围确定各三层组播组对应的洪泛树 ，确定出三层组播组 G1对应 的洪泛树是以 R1为树根的洪泛树， 节点 R2遍历出接口列表中每个出接口 连接的节点： Rl、 R5、 R7, 节点 R7遍历出接口列表中每个出接口连接的 节点： R2、 RlOo

2066、 若该出接口连接的节点以及由该节点递归到叶 子节点的支路上 所有节点均不为发布所述组播组信息的边缘节 点， 则删除所述出接口列表 中该出接口的出接口信息。

在本实施例中， 以图 2 ( a )所示的多点到多点组播场景以及图 2 ( c ) 所示的洪泛树为例进行详细的说明。

对应于三层组播组 G1 , 具体的， R2遍历出以下支路：

支路 1 : R7-R10;支路 2: R5-R8;支路 3: R1-R3-R6;支路 4: R1-R4-R9-

Rll。

其中， 上述支路 1、 支路 2以及支路 3上的所有节点均不为发布组播组 信息的边缘节点， 而支路 4中 R9为发送组播组信息的边缘节点， 故将节点 R2中连接节点 R7以及连接节点 R5的出接口信息删除；最终，如表 4所示， 对应于三层组播组 G1节点 R2上删除后的出接口列表为出接口 21。

表 4: 对应于三层组播组 G1节点 R2上遍历之后的出接口列表

对应于三层组播组 Gl , 具体的， R7遍历出以下支路：

支路 1 : R10; 支路 2: R2-R5-R8; 支路 3: R2-R1-R3-R6; 支路 4: R2-R1-R4-R9- R11。

其中， 上述支路 1 上的所有节点均不为发布组播组信息的边缘节 点， 而支路 2和支路 3中的 R2为发送组播组信息的边缘节点， 支路 4中节点 R2 以及节点 R9为发送组播组信息的边缘节点， 故将节点 R7中连接节点 R10的出接口信息删除； 最终， 如表 5所示， 对应于三层组播组 G1节点 R7上删除后的出接口列表为出接口 72。

表 5： 对应于三层组播组 G1节点 R7上遍历之后的出接口列表

I 出接口 72 I

假设， 边缘节点 R4以及边缘节点 R9下面还挂接有三层组播组 G3的 终端， 且根据组播组信息以及第一节点支持的组播组 范围确定出三层组播 组 G3对应的洪泛树是以 R1为树根的洪泛树， 节点 R4上遍历出接口列表 中每个出接口连接的节点： Rl、 R9。

具体的， R4遍历出以下支路：

支路 1 : R9-R11 ; 支路 2: R1-R2- R5- R8; 支路 3: R1-R3-R6; 支路 4: Rl-R2-R7- R10。

其中， 上述支路 2、 支路 3 以及支路 4上的所有节点均不为发布组播组 信息的边缘节点， 而支路 1中 R9为发送组播组信息的边缘节点， 故将节点 R4中连接节点 R1的出接口信息删除； 最终， 如表 3所示， 对应于三层组 播组 G3 , 节点 R4上删除后的出接口列表为出接口 49。

表 6： 对应于三层组播组 G3节点 R4上遍历之后的出接口列表

2067、 在遍历完成所述出接口列表中所有出接口连接 的节点后， 若所 述出接口列表中仅剩有与上游节点连接的出接 口且本地节点也不为发布所 述组播组信息的边缘节点， 不生成与所述三层组播组对应的组播转发表项 ， 否则根据遍历之后的出接口列表生成与所述三 层组播组对应的组播转发表 项。

所述组播转发表项为本地出接口和上述剩余的 出接口列表并集， key为 组播组 IP。

在本实施例中， 所述三层组播组对应的组播转发表项为以组播 组信息 为索引值 key的出接口列表。

具体的， 对应于三层组播组 G1 :

节点 7遍历之后的出接口列表仅剩有与上游节点连� �的出接口： 出接 口 72且本地节点 R7也不是发布三层组播组信息的边缘节点， 故而， 不生 成所述三层组播组对应的组播转发表项。

节点 2遍历之后的出接口列表中虽然仅剩有与上游� �点连接的出接口： 出接口 21 , 但是由于本地接口 R2为发布三层组播组信息的边缘节点， 根 据遍历后的出接口列表生成如表 7所示的三层组播组 G1对应的组播转发表 项。

表 7： 节点 R2上生成的三层组播组 G1对应的组播转发表项 三层组播组 G 1

出接口 21

本地出接口 具体的， 对应于三层组播组 G3 , 节点 4遍历之后的出接口列表中仅剩 有与下游节点连接的出接口： 出接口 49 , 故而根据遍历后的出接口列表生 成如表 8所示的三层组播组 G3对应的组播转发表项。

表 8： 节点 R4上生成的三层组播组 G3对应的组播转发表项 三层组播组 G 3 出接口 49

本地出接口 值得说明的是， 根据上述步骤 2066删除后得到的出接口信息， 在每个 节点上可以对应于三层组播组生成对应的三层 组播组的组播转发表项。 上 述步骤 2066为优选步骤， 可以使得边缘节点上挂接的接收者和组播组均 位 于第一节点 （即洪泛树的树根） 的同一侧时， 由组播源发往接收者的组播 数据将在汇合点直接转发给接收者， 而不需要继续向第一节点的方向复制， 从而节省了网络带宽， 具体参见表 8所示的节点 R4上生成的三层组播组 G3对应的组播转发表项， 根据表 8所示的转发表项， 在节点 R9上挂接的 三层组播组 G3的终端为组播源时， 节点 R9将组播数据上报给节点 R4之 后， 节点 R4不需要将该组播数据继续向第一节点 R1上报， 从而节省了网 络带宽。

当然， 所述根据所述三层组播组信息对各三层组播组 对应的洪泛树进 行剪枝以生成双向组播分发树， 还可以有其他的实现方式， 此处以一实例 进行详细说明， 但并不限于下述实例， 此处不——赘述。

具体举例如下： 根据洪泛树生成本地节点的对应的出接口列表 ； 根据 洪泛树对应的每个三层组播组， 遍历所述出接口列表中每个出接口连接的 节点； 若该出接口连接的节点为下游节点且该节点以 及该节点的而下游节 点均不为发布所述组播组信息的边缘节点， 则删除所述出接口列表中该出 接口的出接口信息； 在遍历完成所述出接口列表中所有出接口连接 的节点 后， 若所述出接口列表中仅剩有本地出接口且本地 节点也不为发布所述组 播组信息的边缘节点， 不生成与所述三层组播组对应的组播转发表项 ， 否 则根据遍历之后的出接口列表生成与所述三层 组播组对应的组播转发表 项。

值得说明的是， 在边缘节点接收到组播组数据报文后， 基于组播组地 址 G在组播转发表项中进行查找， 获取相应的出接口。 转发过程中， 对于 组播数据报文， 需要执行源端口剪枝功能。 具体的， 如表 9所示， 从出接 口 1进来的组播组 G的数据报文， 只能将报文向剩余端口出接口 2—直到 出接口 N进行复制转发， 而不能向报文的进来的出接口 1再进行转发。

表 9: 组播组地址 G

出接口 1

出接口 2 出接口 N ― 此外， 组播组数据报文转发过程中， 还需要做反向路径转发 （reverse path forwarding , 以下筒称为 RPF )检查， 报文只能从出接口列表中进来， 比如上图中组播数据报文只能从出接口 1、 或出接口 2...或出接口 Ν进来， 而不能从其他接口进来， 如果从其他接口进来 RPF检查失败， 报文丟弃。

本发明实施例提供的基于内部网关协议创建双 向组播分发树的方法， 根据第一节点通过 IGP洪泛过来的第一节点的树根地址以及最短路 径树算 法， 以第一节点为源节点生成到其他节点的最短路 径， 根据所述最短路径 构成洪泛树， 在接收到边缘节点通过 IGP洪泛过来的三层组播组信息时， 根据所述三层组播组信息以及第一节点支持的 组播组范围确定各三层组播 组对应的洪泛树， 并根据所述三层组播组信息对各三层组播组对 应的洪泛 树进行剪枝以生成双向组播分发树， 实现了基于 IGP创建双向组播分发树， 使得在多点到多点的组播场景中， 不管是需要实现组播还是需要实现单播， 均采用 IGP, 筒化了协议的运维，解决了现有技术中在多点 到多点的组播场 景中， 需要同时运维 IGP单播路由协议和 PIM组播路由协议两套协议出现 的运维复杂的问题。 实施例三：

本发明实施例三提供了一种基于 IGP创建双向组播分发树的装置， 如 图 3 (a)所示， 包括：

第一接收单元 31, 用于接收至少一个第一节点通过 IGP洪泛过来的所 述第一节点的树根地址以及所述第一节点支持 的组播组范围， 所述第一节 点为作为整网洪泛树树根的节点； 其具体的实现方法可以参见如图 1 (a) 所示的步骤 101所述， 此处不再赘述。

第一创建单元 32, 用于根据所述第一接收单元接收的所述第一节 点的 树根地址以及最短路径树算法， 以所述第一节点为源节点生成到其他节点 的最短路径， 根据所述最短路径构成洪泛树； 其具体的实现方法可以参见 如图 1 (a)所示的步骤 102所述， 此处不再赘述。

第二接收单元 33, 用于接收边缘节点通过 IGP洪泛过来的三层组播组 信息； 其具体的实现方法可以参见如图 1 (a)所示的步骤 103所述， 此处 不再赘述。

确定单元 34, 用于在所述第二接收单元接收到边缘节点通过 IGP洪泛 过来的三层组播组信息时， 根据所述三层组播组信息以及所述第一接收单 元接收的所述第一节点支持的组播组范围确定 各三层组播组对应的洪泛 树； 其具体的实现方法可以参见如图 1 (a)所示的步骤 103所述， 此处不 再赘述。

在本实施例中， 如图 3 (b)所述确定单元， 包括：

第一选取子单元 341,用于根据所述的三层组播组信息以及所述� �一节 点携带的组播 IP地址范围， 为所述三层组播组选取相应的第一节点； 其具 体的实现方法可以参见如图 2 (h)所示的步骤 2061所述， 此处不再赘述。

第二选取子单元 342,用于若所述第一选取子单元选取得到存在� �个第 一节点覆盖同一个组播组， 根据所述多个第一节点携带的掩码， 从所述多 个第一节点中选取出掩码最长的第一节点作为 所述多个第一节点覆盖的三 层组播组相应的第一节点； 其具体的实现方法可以参见如图 2 (h)所示的 步骤 2062所述， 此处不再赘述。

第三选取子单元 343,用于若所述第二选取子单元选取得到存在� �个掩 码最长的第一节点， 采用 HASH算法从所述多个掩码最长的第一节点中选 取唯一的节点作为所述多个掩码最长的第一节 点覆盖的三层组播组相应的 第一节点。 其具体的实现方法可以参见如图 2 (h)所示的步骤 2063所述， 此处不再赘述。

剪枝单元 35, 用于根据所述三层组播组信息对所述确定单元 确定的各 三层组播组对应的洪泛树进行剪枝以生成双向 组播分发树。 其具体的实现 方法可以参见如图 1 (a)所示的步骤 103所述， 此处不再赘述。

在本实施例中， 如图 3 (c)所示， 所述剪枝单元， 包括：

第一生成子单元 351,用于根据洪泛树生成本地节点的对应的出� �口列 表； 其具体的实现方法可以参见如图 2 (i)所示的步骤 2064所述， 此处不 再赘述。

遍历子单元 352, 用于根据洪泛树对应的每个三层组播组，遍历 所述出 接口列表中每个出接口连接的节点； 其具体的实现方法可以参见如图 2 (i) 所示的步骤 2065所述， 此处不再赘述。

删除子单元 353,用于若遍历子单元遍历的该出接口连接的� �点以及由 该节点递归到叶子节点的支路上所有节点均不 为发布所述组播组信息的边 缘节点， 则删除所述出接口列表中该出接口的出接口信 息； 其具体的实现 方法可以参见如图 2 (i)所示的步骤 2066所述， 此处不再赘述。

生成子单元 354 ,用于在遍历完成所述出接口列表中所有出接� �连接的 节点后， 若所述出接口列表中仅剩有与上游节点连接的 出接口且本地节点 也不为发布所述组播组信息的边缘节点， 不生成与所述三层组播组对应的 组播转发表项， 否则根据遍历之后的出接口列表生成与所述三 层组播组对 应的组播转发表项。其具体的实现方法可以参 见如图 2 ( i )所示的步骤 2067 所述， 此处不再赘述。

进一步的， 为了避免相同的组播组报文被重复发往第一节 点， 如图 3 ( d )所示， 该装置， 还包括：

第一选取单元 36, 用于若所述第一创建单元创建的洪泛树的分支 或叶 子节点有多个到达所述第一节点的父亲节点， 根据多个父亲节点的属性值 从所述多个父亲节点中选取唯一的节点作为所 述分支或叶子节点到达所述 第二节点的父亲节点。 其具体的实现方法可以参见如图 1 ( b )所示的步骤 104所述， 此处不再赘述。

其中， 所述 IGP为 IS-IS, 所述父亲节点的属性值可以包括系统 ID。 或 者所述 IGP为 OSPF协议， 所述父亲节点的属性值可以包括路由器 ID。

进一步的， 为了避免相同的组播组报文被重复的发往一个 节点， 如图 3 ( d )所示， 该装置， 还包括：

第二选取单元 37 , 用于若所述第一创建单元创建的洪泛树中的两 个节 点之间存在多条平行链路， 根据多条平行链路的属性值从所述多个平行链 路中选取唯一的链路作为两个节点之间的链路 。 其具体的实现方法可以参 见如图 1 ( b )所示的步骤 105所述， 此处不再赘述

其中， 所述 IGP为 IS-IS, 所述平行链路的属性值可以包括线路 ID或 者伪节点 ID, 或者所述 IGP为 OSPF协议， 所述平行链路的属性值可以包 括接口 IP地址。

如图 3 ( e )所示， 本发明实施例还提供一种节点设备， 包括： 接收器， 用于接收至少一个第一节点通过 IGP洪泛过来的所述第一节 点的树根地址以及所述第一节点支持的组播组 范围， 所述第一节点为作为 整网洪泛树树根的节点； 还用于接收边缘节点通过 IGP洪泛过来的三层组 播组信息。 处理器， 用于根据所述接收器接收的所述第一节点的树 根地址以及最 短路径树算法， 以所述第一节点为源节点生成到其他节点的最 短路径， 根 据所述最短路径构成洪泛树；还用于在所述接 收器接收到边缘节点通过 IGP 洪泛过来的三层组播组信息时， 根据所述三层组播组信息以及所述第一接 收单元接收的所述第一节点支持的组播组范围 确定各三层组播组对应的洪 泛树； 用于根据所述三层组播组信息对所述确定单元 确定的各三层组播组 对应的洪泛树进行剪枝以生成双向组播分发树 。

进一步的， 为了避免相同的组播组报文被重复发往第一节 点， 所述处 理器， 还用于若创建的洪泛树的分支或叶子节点有多 个到达所述第一节点 的父亲节点， 根据多个父亲节点的属性值从所述多个父亲节 点中选取唯一 的节点作为所述分支或叶子节点到达所述第二 节点的父亲节点。

其中， 当所述 IGP为 IS-IS时， 所述父亲节点的属性值包括系统 ID。 当所述 IGP为 OSPF协议时， 所述父亲节点的属性值包括路由器 ID。

进一步的， 为了避免相同的组播组报文被重复的发往一个 节点， 所述 处理器， 还用于若创建的洪泛树中的两个节点之间存在 多条平行链路， 根 据多条平行链路的属性值从所述多个平行链路 中选取唯一的链路作为两个 节点之间的链路。

其中， 当所述 IGP为 IS-IS时， 所述平行链路的属性值包括线路 ID或 者伪节点 ID。 当所述 IGP为 OSPF协议时， 所述平行链路的属性值包括接 口 IP地址。

进一步的， 所述处理器， 具体用于：

根据所述的三层组播组信息以及所述第一节点 携带的组播 IP 地址范 围， 为所述三层组播组选取相应的第一节点；

若选取得到存在多个第一节点覆盖同一个组播 组， 根据所述多个第一 节点携带的掩码， 从所述多个第一节点中选取出掩码最长的第一 节点作为 所述多个第一节点覆盖的三层组播组相应的第 一节点； 若选取得到存在多个掩码最长的第一节点， 采用 HASH算法从所述多 个掩码最长的第一节点中选取唯一的节点作为 所述多个掩码最长的第一节 点覆盖的三层组播组相应的第一节点。

进一步的， 所述处理器， 还具体用于：

根据洪泛树生成本地节点的对应的出接口列表 ；

根据洪泛树对应的每个三层组播组， 遍历所述出接口列表中每个出接 口连接的节点；

若遍历子单元遍历的该出接口连接的节点以及 由该节点递归到叶子节 点的支路上所有节点均不为发布所述组播组信 息的边缘节点， 则删除所述 出接口列表中该出接口的出接口信息；

在遍历完成所述出接口列表中所有出接口连接 的节点后， 若所述出接 口列表中仅剩有与上游节点连接的出接口且本 地节点也不为发布所述组播 组信息的边缘节点， 不生成与所述三层组播组对应的组播转发表项 ， 否则 根据遍历之后的出接口列表生成与所述三层组 播组对应的组播转发表项。

对应于本发明实施例提供的基于内部网关协议 创建双向组播分发树的 装置， 本发明实施例还提供了一种基于内部网关协议 创建双向组播分发树 的系统， 包括： 第一节点， 用于通过 IGP洪泛所述第一节点的树根地址以 及所述第一节点支持的组播组范围， 所述第一节点作为整网洪泛树树根的 节点； 边缘节点， 用于通过 IGP洪泛三层组播组信息； 普通节点， 用于接 收第一节点洪泛过来的所述第一节点的树根地 址以及所述第一节点支持的 组播组范围， 根据各第一节点的树根地址以及最短路径树算 法， 以各第一 节点为源节点生成到其他节点的最短路径， 构成洪泛树； 所述普通节点， 还用于在接收到所述边缘节点洪泛过来的三层 组播组信息时， 根据所述三 层组播组信息以及各第一节点支持的组播组范 围确定各三层组播组对应的 洪泛树， 并根据所述三层组播组信息对各三层组播组对 应的洪泛树进行剪 枝以生成双向组播分发才对。 本发明实施例提供的基于内部网关协议创建双 向组播分发树的装置、 节点设备及系统， 根据第一节点通过 IGP洪泛过来的第一节点的树根地址 以及最短路径树算法， 以第一节点为源节点生成到其他节点的最短路 径， 根据所述最短路径构成洪泛树， 在接收到边缘节点通过 IGP洪泛过来的三 层组播组信息时， 根据所述三层组播组信息以及第一节点支持的 组播组范 围确定各三层组播组对应的洪泛树， 并根据所述三层组播组信息对各三层 组播组对应的洪泛树进行剪枝以生成双向组播 分发树， 实现了基于 IGP创 建双向组播分发树， 使得在多点到多点的组播场景中， 不管是需要实现组 播还是需要实现单播， 均采用 IGP, 筒化了协议的运维， 解决了现有技术中 在多点到多点的组播场景中， 需要同时运维 IGP单播路由协议和 PIM组播 路由协议两套协议出现的运维复杂的问题。

本发明实施例提供的基于 IGP创建双向组播分发树的方法、 装置及系 统， 能够应用于多点到多点的组播场景中。

本领域普通技术人员可以理解实现上述实施例 方法中的全部或部分步 骤是可以通过程序来指令相关的硬件完成， 所述的程序可以存储于一计算 机可读存储介质中， 如 ROM/RAM、 磁碟或光盘等。

以上所述， 仅为本发明的具体实施方式， 但本发明的保护范围并不局 限于此， 任何熟悉本技术领域的技术人员在本发明揭露 的技术范围内， 可 轻易想到变化或替换， 都应涵盖在本发明的保护范围之内。 因此， 本发明 的保护范围应以所述权利要求的保护范围为准 。