Nothing Special   »   [go: up one dir, main page]

WO2014008826A1 - 基于内部网关协议创建双向组播分发树的方法、装置及系统 - Google Patents

基于内部网关协议创建双向组播分发树的方法、装置及系统 Download PDF

Info

Publication number
WO2014008826A1
WO2014008826A1 PCT/CN2013/078659 CN2013078659W WO2014008826A1 WO 2014008826 A1 WO2014008826 A1 WO 2014008826A1 CN 2013078659 W CN2013078659 W CN 2013078659W WO 2014008826 A1 WO2014008826 A1 WO 2014008826A1
Authority
WO
WIPO (PCT)
Prior art keywords
node
multicast group
layer
nodes
multicast
Prior art date
Application number
PCT/CN2013/078659
Other languages
English (en)
French (fr)
Inventor
郝卫国
李振斌
刘毅松
Original Assignee
华为技术有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 华为技术有限公司 filed Critical 华为技术有限公司
Priority to EP13816047.8A priority Critical patent/EP2866377B1/en
Publication of WO2014008826A1 publication Critical patent/WO2014008826A1/zh
Priority to US14/594,864 priority patent/US9647959B2/en

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/20—Support for services
    • H04L49/201—Multicast operation; Broadcast operation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/02—Details
    • H04L12/16—Arrangements for providing special services to substations
    • H04L12/18—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast
    • H04L12/185—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast with management of multicast group membership
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/16—Multipoint routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L61/00—Network arrangements, protocols or services for addressing or naming
    • H04L61/50—Address allocation
    • H04L61/5069—Address allocation for group communication, multicast communication or broadcast communication

Definitions

  • the present invention relates to the field of communications technologies, and in particular, to a method, device, and system for creating a bidirectional multicast distribution tree based on an internal gateway protocol. Background technique
  • the multi-point to multi-point multicast application scenario is a Layer 2 virtual local area network (Virtual Local Area Network, referred to as VLAN) through overlay technology.
  • the broadcast packets are carried on the corresponding Layer 3 multicast group, and the Layer 3 multicast component is sent to simulate the multi-point to multi-point LAN application of the unknown unicast flooding and broadcasting in the Layer 2 VLAN.
  • each edge router is connected to both a multicast source and a receiver.
  • a two-way multicast distribution tree is suitable.
  • the multicast data can be from leaf to root. , you can also go from root to leaf.
  • a two-way multicast distribution tree in a network is generally constructed through Protocol Independent Multicast (hereinafter referred to as ⁇ ).
  • the inventor has found that the prior art has at least the following problems: In a multi-point to multi-point multicast scenario, a bidirectional protocol is required when multicast is required, and an internal operation is also required.
  • the Interior Gateway Protocol (hereinafter referred to as IGP) is used as a unicast routing protocol. Therefore, two sets of protocols need to be operated and operated at the same time, and the operation and maintenance is complicated.
  • Embodiments of the present invention provide a method for creating a bidirectional multicast distribution tree based on an internal gateway protocol.
  • the method, the device, and the system solve the problem of complicated operation and maintenance of the two sets of protocols of the IGP unicast routing protocol and the PIM multicast routing protocol in the multi-point to multi-point multicast scenario in the prior art.
  • the embodiment of the present invention adopts the following technical solutions:
  • a method for creating a bidirectional multicast distribution tree based on an IGP including: receiving a root address of the first node flooded by the at least one first node through the IGP, and a group supported by the first node
  • the first node is a node that is the root of the Flooding Tree; the first node is the source node according to the root address of the first node and the shortest path tree algorithm.
  • the first node is used as a source node to generate a shortest path to other nodes, and the shortest path is configured to flood
  • the method further includes: if the branch or leaf node of the flooding tree has multiple father nodes reaching the first node, selecting a unique node from the plurality of parent nodes according to attribute values of the plurality of parent nodes The branch or leaf node arrives at the parent node of the first node.
  • the attribute value of the father node includes a system ID.
  • the IGP is an Open Shortest Path First (hereinafter referred to as 0SPF) protocol
  • the attribute value of the father node includes a router ID.
  • the method further includes: if there are multiple parallel links between the two nodes in the flooding tree, selecting a unique one of the plurality of parallel links according to attribute values of the plurality of parallel links The link acts as a link between the two nodes.
  • the attribute value of the parallel link includes a line ID or a pseudo node ID.
  • the attribute value of the parallel link includes an interface IP address.
  • the multicast group range supported by the first node includes a multicast IP address supported by the first node and a mask corresponding to the multicast IP address, where the Layer 3 multicast group information is And determining the flooding tree corresponding to each layer of the multicast group by the range of the multicast group supported by the first node, including: according to the layer 3 multicast group information and the multicast IP address range carried by the first node And selecting a corresponding first node for the three-layer multicast group; if there are multiple first nodes covering the same multicast group, according to the mask carried by the multiple first nodes, from the plurality of first The first node with the longest mask is selected as the first node corresponding to the three-layer multicast group covered by the plurality of first nodes; if there are multiple first nodes with the longest mask, the HASH algorithm is adopted.
  • the first node that is the longest of the plurality of masks selects the unique node as the first node corresponding to the three-layer multicast group covered by the first node with
  • the prune of the flooding tree corresponding to each layer of the multicast group according to the layer 3 multicast group information includes: generating a corresponding outbound interface list of the local node according to the flooding tree; Each Layer 3 multicast group corresponding to the flooding tree traverses the node connected to each outbound interface in the outbound interface list; if the node connected to the outbound interface and all the nodes on the branch recursed to the leaf node by the node are not If the edge node of the multicast group information is advertised, the outbound interface information of the outbound interface in the outbound interface list is deleted; after the traversal of all the nodes connected to the outbound interface in the outbound interface list, if the outbound interface is Only the outbound interface connected to the upstream node is left in the list, and the local node is not the edge node that advertises the multicast group information.
  • an apparatus for creating a bidirectional multicast distribution tree based on an IGP including: a first receiving unit, configured to receive a root address of the first node that is flooded by at least one first node by using an IGP And the range of the multicast group supported by the first node, where the first node is a node that is the root of the flooding tree of the entire network;
  • a first creating unit configured to generate a shortest path to the other node by using the first node as a source node according to the root address of the first node and the shortest path tree algorithm received by the first receiving unit, according to the The shortest path constitutes a flooding tree;
  • a second receiving unit configured to receive Layer 3 multicast group information flooded by the edge node through the IGP;
  • a determining unit configured to: when the second receiving unit receives the layer 3 multicast group information flooded by the edge node by the IGP, according to the layer 3 multicast group information and the received by the first receiving unit The multicast group range supported by the first node determines a flooding tree corresponding to each layer 3 multicast group; the pruning unit is configured to determine, according to the layer 3 multicast group information, each layer 3 multicast group determined by the determining unit The corresponding flooding tree is pruned to generate a bidirectional multicast distribution tree.
  • the device for creating a bidirectional multicast distribution tree based on the IGP further includes: a first selecting unit, configured to: if the branching or leaf node of the flooding tree created by the first creating unit has multiple arrivals The father node of the first node selects a unique node from the plurality of parent nodes according to attribute values of the plurality of parent nodes as the branch node or the leaf node reaches the father node of the second node.
  • the attribute value of the father node includes a system ID.
  • the attribute value of the father node includes a router ID.
  • the device for creating a bidirectional multicast distribution tree based on the IGP further includes: a second selecting unit, configured to: if there are multiple nodes in the flooding tree created by the first creating unit A parallel link selects a unique link from the plurality of parallel links as a link between the two nodes according to attribute values of the plurality of parallel links.
  • the attribute value of the parallel link includes a line ID or a pseudo node ID.
  • the attribute value of the parallel link includes an interface IP address.
  • the determining unit includes:
  • a first selecting subunit configured to select a corresponding first node for the Layer 3 multicast group according to the Layer 3 multicast group information and the multicast IP address range carried by the first node;
  • a second selecting subunit configured to: if the first selected subunit is selected, the plurality of first nodes cover the same multicast group, according to the mask carried by the multiple first nodes, from the multiple The first node with the longest mask is selected as the first node corresponding to the three-layer multicast group covered by the plurality of first nodes;
  • a third selecting subunit configured to: if the second selected subunit is selected to obtain a first node having a plurality of masks, the HASH algorithm is used to select a unique one of the plurality of masked first nodes The node is the first node corresponding to the three-layer multicast group covered by the first node with the longest one of the plurality of masks.
  • the method includes:
  • a first generating subunit configured to generate a corresponding outbound interface list of the local node according to the flooding tree
  • a traversing subunit configured to traverse each of the outbound interface lists according to each of the three layer multicast groups corresponding to the flooding tree a node connected by an outgoing interface
  • the node for connecting the egress interface traversing the sub-unit traversal and all nodes on the branch recursed to the leaf node by the node are not edge nodes for publishing the multicast group information, and deleting the Outbound interface information of the outbound interface in the interface list;
  • a generating sub-unit configured to: after traversing all the nodes connected to the outbound interface in the outbound interface list, if only the outbound interface connected to the upstream node remains in the outbound interface list, and the local node does not publish the group
  • the edge node of the broadcast group information does not generate a multicast forwarding entry corresponding to the Layer 3 multicast group. Otherwise, the multicast forwarding entry corresponding to the Layer 3 multicast group is generated according to the outbound interface list after the traversal.
  • a system for creating a multicast distribution tree based on an IGP including: a first node, configured to flood a root address of the first node by using an IGP, and multicast supported by the first node a group range, where the first node is a node that is the root of the flooding tree root; the edge node is used to flood the Layer 3 multicast group information through the IGP;
  • a common node configured to receive a root address of the first node flooded by the at least one first node, and a range of multicast groups supported by the first node, according to a root address and a shortest path of the first node a tree algorithm, generating a shortest path to other nodes by using the first node as a source node, and forming a flooding tree according to the shortest path;
  • the common node is further configured to determine, according to the Layer 3 multicast group information and the range of multicast groups supported by the first node, when receiving the Layer 3 multicast group information that is flooded by the edge node.
  • a flooding tree corresponding to the Layer 3 multicast group and prune the flooding tree corresponding to each Layer 3 multicast group according to the Layer 3 multicast group information to generate a bidirectional multicast distribution tree.
  • a method, device, and system for creating a bidirectional multicast distribution tree based on an internal gateway protocol provided by an embodiment of the present invention according to a root address and a shortest path tree algorithm of a first node flooded by an IGP by a first node, to a first node Generating a shortest path to the other node for the source node, and constructing a flooding tree according to the shortest path, and receiving the Layer 3 multicast group information that the edge node floods through the IGP, according to the Layer 3 multicast group information and
  • the multicast group range supported by the first node determines the flooding tree corresponding to each Layer 3 multicast group, and prune the flooding tree corresponding to each Layer 3 multicast group according to the Layer 3 multicast group information to generate a bidirectional
  • the multicast distribution tree implements a two-way multicast distribution tree based on IGP, so that in a multi-point to multi-point multicast scenario, whether it is required to implement multicast or unicast, IGP is used. Operation and maintenance
  • 1 (a) is a flowchart 1 of a method for creating a bidirectional multicast distribution tree based on an IGP according to Embodiment 1 of the present invention
  • 1(b) is a second flowchart of a method for creating a bidirectional multicast distribution tree based on an IGP according to Embodiment 1 of the present invention
  • FIG. 2 (a) is a network architecture diagram of a multi-point to multi-point multicast scenario according to Embodiment 2 of the present invention
  • FIG. 2(b) is a flowchart of a method for creating a bidirectional multicast distribution tree based on an IGP according to Embodiment 2 of the present invention
  • FIG. 2(d) is a flooding tree with R2 as a root according to Embodiment 2 of the present invention.
  • FIG. 2(e) shows two two-node multicast distribution trees constructed by the two second nodes RP1 and RP2 according to the second embodiment of the present invention when constructing a two-way multicast distribution tree;
  • Figure 2 (f) is the first bidirectional multicast distribution tree in Figure 2 (e);
  • Figure 2 (g) is the second two-way multicast distribution tree in Figure 2 (e);
  • 2(h) is a flowchart 1 of the method in step 206 of the method for creating a bidirectional multicast distribution tree based on the IGP shown in FIG. 2(b);
  • FIG. 2(i) is a flowchart 2 of the method in step 206 of the method for creating a bidirectional multicast distribution tree based on the IGP shown in FIG. 2(b);
  • FIG. 3 is a schematic structural diagram 1 of a device for creating a bidirectional multicast distribution tree based on an IGP according to Embodiment 3 of the present invention
  • FIG. 3(b) is a schematic structural diagram of a determining unit in the apparatus for creating a bidirectional multicast distribution tree based on the IGP shown in FIG. 3(a);
  • FIG. 3(c) is a schematic structural diagram of a pruning unit in the apparatus for creating a bidirectional multicast distribution tree based on the IGP shown in FIG. 3(a);
  • FIG. 3(d) is a second schematic structural diagram of a device for creating a bidirectional multicast distribution tree based on an IGP according to Embodiment 3 of the present invention.
  • FIG. 3(e) is a schematic structural diagram 2 of a node device according to Embodiment 3 of the present invention. detailed description
  • Embodiment 1 A method, device and system for creating a bidirectional multicast distribution tree based on IGP. Embodiment 1:
  • a method for creating a bidirectional multicast distribution tree based on the IGP is provided in the embodiment of the present invention.
  • the method may be applied to all nodes of the entire network, and the method includes:
  • the first node is a node that is the root of the flooding tree of the entire network.
  • the root address of the first node and the range of the multicast group supported by the first node may be pre-configured.
  • at least one IP address is configured on each first node, and the IP address is configured. That is, the root address of the tree.
  • the range of the multicast group supported by the first node may be automatically configured by the first node according to its own attributes, which is not limited herein.
  • the root address of the first node and the range of the multicast group supported by the first node may be encapsulated in one configuration information at the same time, and may be separately encapsulated and then flooded separately. .
  • 102 Generate a shortest path to other nodes by using the first node as a source node according to a root address of the first node and a Shortest Path Tree (SPT) algorithm, according to the shortest path.
  • the path constitutes a flooding tree.
  • each Layer 3 multicast group corresponding to the Layer 3 multicast group information that is flooded by the edge node And flooding the tree, and prune the flooding tree corresponding to each layer of the multicast group according to the layer 3 multicast group information to generate a bidirectional multicast distribution tree.
  • each node since each node independently calculates the first node as the shortest path from the source node to other nodes based on the first node, each node has a unified network topology, and the phase is adopted. The same algorithm, so all nodes have the same understanding of the shape of the shortest path tree. Therefore, the nodes on the bidirectional multicast distribution tree need to periodically send Join and Prune messages to the upstream network.
  • the method provided in the embodiment of the present invention does not require the Join, Prune message in the PIM network, and can generate the shortest path tree information rooted at the first node to form a flooding tree, and further generate a corresponding bidirectional multicast distribution tree by pruning. , reducing the processing load of the CPU.
  • the method further includes:
  • ⁇ select a unique node from the plurality of parent nodes according to attribute values of the plurality of parent nodes as the The branch or leaf node arrives at the parent node of the first node.
  • the leaf node is the bottom node in the tree, and the leaf node has no child nodes.
  • the attribute values of the corresponding parent nodes are different.
  • the attribute value of the father node may include a system ID;
  • the attribute value of the parent node may include the router ID.
  • the method may be applied.
  • the tree root address and the shortest path tree algorithm according to the first node are used.
  • the first node generates a shortest path to the other node for the source node, and after the flooding tree is formed according to the shortest path, the method further includes:
  • the attribute values of the corresponding parallel links are different.
  • the attribute value of the parallel link may include a circuit ID (Principal ID) or a pseudo node ID (Pseudonode ID); when the IGP is an OSPF protocol, the The attribute value of the parallel link can include the interface IP address.
  • circuit ID Principal ID
  • Pseudonode ID pseudo node ID
  • the method for creating a bidirectional multicast distribution tree based on the internal gateway protocol provided by the embodiment of the present invention according to the root address and the shortest path tree algorithm of the first node flooded by the first node by the first node, using the first node as the source node
  • the shortest path to the other node is formed, and the flooding tree is formed according to the shortest path.
  • the multicast group scope determines a flooding tree corresponding to each layer of the multicast group, and prune the flooding tree corresponding to each layer of the multicast group according to the layer 3 multicast group information to generate a bidirectional multicast distribution tree.
  • the two-way multicast distribution tree is created based on the IGP, so that in the multi-point to multi-point multicast scenario, whether I need to implement multicast or unicast, the IGP is used to solve the operation and maintenance of the protocol.
  • the operation and maintenance of the two protocols of the IGP unicast routing protocol and the PIM multicast routing protocol need to be simultaneously operated and operated.
  • Embodiment 2 The method for creating a bidirectional multicast distribution tree based on the internal gateway protocol provided by the embodiment of the present invention is described in detail below by using a specific embodiment to enable a person skilled in the art to more clearly understand the technical solution provided by the embodiment of the present invention.
  • Embodiment 2
  • FIG. 2(a) is a multi-point to multi-point A network architecture diagram of a multicast scenario.
  • the entire network includes multiple nodes (R1 to R11).
  • the edge nodes R2 and R9 are connected to the terminals of the Layer 3 multicast group G1.
  • the edge nodes R4 and R10 are connected to the Layer 3 group.
  • the terminal of the group G2 is broadcasted; wherein, R1, R3, R7, and R8 are the first nodes.
  • the method for creating a bidirectional multicast distribution tree based on the IGP includes:
  • the first node in the entire network sends configuration information to the entire network node.
  • the first node is a node in the entire network that is the root of the flooding tree.
  • the configuration information includes a root address of the first node and a range of multicast groups supported by the first node.
  • R1 floods its configuration information to R2 ⁇ R11 in the whole network
  • R3 floods its configuration information to Rl, R2, and R4-R11 in the whole network
  • R7 floods its configuration information to R1 ⁇ R6 and R8-R11 in the whole network
  • R8 floods its configuration information to Rl ⁇ R7 and R9 ⁇ R11 in the whole network.
  • the entire network node receives the configuration information, and generates a shortest path to the other node by using the first node as the source node according to the root address and the shortest path tree algorithm in the configuration information sent by the first node, according to the The shortest path constitutes a flooding tree.
  • the trees are sorted according to the IP address of the flooding tree root. For example, if there are n trees, the tree number is from 1 to n.
  • Rl and R7 are taken as an example for detailed explanation:
  • the flooding tree with R1 as the root is the first tree, and the flooding tree with R7 as the root is the second tree.
  • R1 is the source node.
  • the shortest path from R1 to other nodes is generated to form the first bidirectional multicast distribution tree—the root of the tree is R1.
  • the first bidirectional multicast distribution tree is as follows: Path composition: R1- R4- R9- R11 ; Rl- R3- R6; Rl- R2- R7- RIO; Rl- R2- R5- R8» with R7 as the source node, as shown in Figure 2(d), generate R7
  • the shortest path to other nodes constitutes the second bidirectional multicast distribution tree—the root of the tree is R7.
  • the first bidirectional multicast distribution tree consists of the following paths: R7- R2- Rl- R4; R7- R5- R3- R6; R7- RIO- R8; R7-predative - Rll- R9.
  • ⁇ select a unique node from the plurality of parent nodes according to attribute values of the plurality of parent nodes. The branch or leaf node arrives at the parent node of the first node.
  • the attribute values of the corresponding parent nodes are different.
  • the attribute value of the father node may include a system ID;
  • the attribute value of the parent node may include a router ID, and of course, other IGPs may be applied, and are not described here.
  • the IGP is an IS-IS as an example.
  • the attribute value of the parent node may be a system ID, and the number of multiple parent nodes is K.
  • the attributes according to multiple father nodes are And selecting a unique node from the plurality of parent nodes as the parent node of the first node, the method may include: sorting the multiple father nodes according to the system ID of the multiple parent nodes, and sorting the : Parent 1, Parent2... ParentK , For the Jth tree, select the J mod K parent nodes.
  • the OSPF protocol is used as an example for the detailed description.
  • the attribute value of the father node may be a router ID, and the number of the plurality of parent nodes is K, and the attribute value according to the multiple father nodes is from the
  • the selecting a unique node among the plurality of parent nodes as the parent node of the first node or the leaf node may include: sorting the plurality of parent nodes according to the router ID of the multiple parent nodes, and sorting is: Parentl, Parent2 ... ParentK, For the Jth tree, select the J mod K father nodes.
  • the first bidirectional multicast distribution tree is RP1 as the root.
  • the first bidirectional multicast distribution tree consists of the following paths: RP1-R2-R1; RP1-R3-R1; RP1-R4.
  • the second bidirectional multicast distribution tree is RP2 as the root, and the second bidirectional multicast distribution tree is composed of the following paths: RP2-R2-R1; RP2-R3-R1; RP2-R4.
  • R1 and R4 are edge nodes connected to the multicast source and the receiver. The cost of the link between each node in the flooded tree is the same.
  • R1 can reach RP1 through two parent nodes R2 and R3.
  • the RP2 can be reached by the two parent nodes R2 and R3.
  • the unique node is selected as the parent node of R1 to reach RP1.
  • the first bidirectional multicast distribution tree takes RP1 as the root of the tree and consists of the following paths: RP1-R2-R1; RP1-R4.
  • the second bidirectional multicast distribution tree is rooted at RP2 and consists of the following paths: RP2-R3-R1; RP2-R4.
  • RP2-R3-R1 RP2-R4
  • the multicast data packet sent from R4 to RP1 passes through RP1 and reaches R2. Only R2 (through the R2-R1 interface) can send multicast data packets to the following flooding link, and will not pass the R3 to the flooding link below. Send multicast data packets to prevent R1 from receiving duplicate traffic.
  • the attribute values of the corresponding parallel links are different.
  • the attribute value of the parallel link may be a line identifier (circuit ID). It can also be a pseudo node ID (Pseudonode ID); when the IGP is OSPF, the attribute value of the parallel link can be the IP address of the interface.
  • circuit ID circuit ID
  • Pseudonode ID pseudo node ID
  • OSPF OSPF
  • the attribute value of the parallel link can be the IP address of the interface.
  • IGPs there are other IGPs, which can be applied. - Narrative.
  • the attribute value of the parallel link may be a line ID or a pseudo node identifier ID, and the number of multiple parallel links is K.
  • the attribute value of the multiple parallel links is selected from the plurality of parallel links as the link between the two nodes, and specifically includes: the attribute value according to the multiple parallel links may be the line ID or The pseudo node ID, sorting multiple parallel links, sorted into: Linel, Line 2... Line K, for the Jth tree, select J mod K parallel links.
  • the selected one of the multiple parallel links is selected according to the attribute values of the multiple parallel links.
  • the edge node associates the Layer 3 multicast group information connected thereto with the IGP to the entire network node.
  • the edge node is a node in the entire network that is connected to a multicast source and/or a receiver.
  • the multicast source connected to the edge node can also be the receiver.
  • the receiver will initiate the join of the Layer 3 multicast that needs to be added through the Internet Group Management Protocol (IGMP) packet.
  • IGMP Internet Group Management Protocol
  • edge nodes can be based on recipients
  • the sent IGMP message obtains Layer 3 multicast group information. If the edge node is connected to the multicast source and is not the receiver, the edge node can obtain the connected Layer 3 multicast group information by statically configuring or sensing the first packet of the multicast data stream sent by the multicast source.
  • the entire network node determines, according to the Layer 3 multicast group information and the range of the multicast group supported by the first node, the corresponding Layer 3 multicast group corresponding.
  • the flooding tree prune the flooding tree corresponding to each Layer 3 multicast group according to the Layer 3 multicast group information to generate a bidirectional multicast distribution tree.
  • the multicast group supported by the first node is a pre-configured corresponding Layer 3 multicast group, indicating that the Layer 3 multicast group can forward the multicast group data traffic by using the shortest path where the first node is located.
  • the multicast group range supported by the first node is in a group-range manner, and the group-range organization mode is a multicast IP address and a mask.
  • the flooding tree corresponding to each Layer 3 multicast group is determined according to the Layer 3 multicast group information and the multicast group range supported by each first node, as shown in FIG. 2( h ), Specifically, it may include:
  • the first node with the longest mask is selected from the plurality of first nodes according to the mask carried by the multiple first nodes.
  • first nodes with the longest mask use a HASH algorithm to select a unique node from the first node with the longest mask as the longest first node of the multiple masks.
  • the corresponding first node of the three-layer multicast group uses a HASH algorithm to select a unique node from the first node with the longest mask as the longest first node of the multiple masks.
  • the HASH algorithm has a large priority
  • the HASH algorithm can be:
  • G is the multicast group address
  • M is the calculation mask issued by the Bootstrap Router (hereinafter referred to as the BSR)
  • C(i) is the root address of the tree.
  • the above algorithm is to use the first node with a long mask length if multiple group-ranges cover the same multicast group. If the mask length is the same, select a unique first node according to the HASH algorithm. . Finally, all nodes of the entire network select the same first node as the root of the same Layer 3 multicast group.
  • the flooding tree corresponding to each Layer 3 multicast group is prune according to the Layer 3 multicast group information to generate a bidirectional multicast distribution tree, as shown in Figure 2 (i).
  • FIG. 2(a) a multipoint-to-multipoint multicast scenario shown in FIG. 2(a) and a flooding tree shown in FIG. 2(c) are taken as an example for detailed description.
  • each node in the flooding tree with R1 as a root generates a corresponding outbound interface list of the local node according to the flooding tree. For example, a list of outbound interfaces as shown in Table 1 is generated on the node R2, an outbound interface list as shown in Table 2 is generated on the node R4, and an outbound interface list as shown in Table 3 is generated on the node R7.
  • Table 1 List of outgoing interfaces generated on node R2 Outbound interface 21
  • Outbound interface 49 Table 3: List of outgoing interfaces generated on node R7 Outbound interface 72 outbound interface 710
  • FIG. 2(a) a multipoint-to-multipoint multicast scenario shown in FIG. 2(a) and a flooding tree shown in FIG. 2(c) are taken as an example for detailed description.
  • the flooding tree corresponding to each Layer 3 multicast group is determined according to the Layer 3 multicast group information and the range of multicast groups supported by the first node, and the flood corresponding to the Layer 3 multicast group G1 is determined.
  • the pan-tree is a flooding tree with R1 as the root of the tree.
  • Node R2 traverses the nodes connected to each outgoing interface in the interface list: Rl, R5, R7, and node R7 traverses the node connected to each outgoing interface in the outbound interface list: R2 , RlOo
  • the outbound interface of the outbound interface in the outbound interface list is deleted. information.
  • FIG. 2(a) a multipoint-to-multipoint multicast scenario shown in FIG. 2(a) and a flooding tree shown in FIG. 2(c) are taken as an example for detailed description.
  • R2 traverses the following branches:
  • Branch 1 R7-R10; branch 2: R5-R8; branch 3: R1-R3-R6; branch 4: R1-R4-R9-
  • All the nodes on the branch 1, the branch 2, and the branch 3 are not edge nodes that issue multicast group information, and R9 in the branch 4 is an edge node that sends multicast group information, so the node R2
  • the outbound interface information of the connection node R7 and the connection node R5 is deleted.
  • the outbound interface list corresponding to the deletion on the Layer 3 multicast group G1 node R2 is the outbound interface 21.
  • R7 traverses the following branches:
  • Branch 1 R10; Branch 2: R2-R5-R8; Branch 3: R2-R1-R3-R6; Branch 4: R2-R1-R4-R9- R11.
  • All the nodes on the branch 1 are not edge nodes that advertise multicast group information, and R2 in branch 2 and branch 3 are edge nodes that send multicast group information, and node R2 in branch 4 and The node R9 is the edge node that sends the multicast group information, so the outbound interface information of the connected node R10 in the node R7 is deleted.
  • the outgoing interface corresponding to the deleted layer G7 node R7 is corresponding.
  • the list is the outbound interface 72.
  • the edge node R4 and the edge node R9 are connected to the terminal of the three-layer multicast group G3, and the flooding corresponding to the three-layer multicast group G3 is determined according to the multicast group information and the range of the multicast group supported by the first node.
  • the tree is a flooding tree with R1 as the root of the tree.
  • Node R4 traverses the nodes connected to each outbound interface in the interface list: Rl, R9.
  • R4 traverses the following branches:
  • Branch 1 R9-R11 ; Branch 2: R1-R2- R5- R8; Branch 3: R1-R3-R6; Branch 4: Rl-R2-R7- R10.
  • All the nodes on the branch 2, the branch 3, and the branch 4 are not edge nodes that advertise multicast group information, and R9 in the branch 1 is an edge node that sends multicast group information, so the node R4 is The outgoing interface information of the connected node R1 is deleted. Finally, as shown in Table 3, corresponding to the Layer 3 multicast group G3, the deleted interface list on the node R4 is the outgoing interface 49.
  • the edge node After the traversal of all the nodes connected to the outbound interface in the outbound interface list, if only the outbound interface connected to the upstream node remains in the outbound interface list, and the local node does not publish the multicast group information.
  • the edge node does not generate a multicast forwarding entry corresponding to the Layer 3 multicast group. Otherwise, the multicast forwarding entry corresponding to the Layer 3 multicast group is generated according to the outbound interface list.
  • the multicast forwarding entry is a local outgoing interface and the remaining outgoing interface list, and the key is a multicast group IP.
  • the multicast forwarding entry corresponding to the Layer 3 multicast group is an outbound interface list with the multicast group information as the index value key.
  • the outbound interface list after the traversal of the node 7 has only the outbound interface connected to the upstream node: the outbound interface 72 and the local node R7 are not edge nodes that advertise the Layer 3 multicast group information. Therefore, the Layer 3 multicast group is not generated. Corresponding multicast forwarding entry.
  • the outbound interface list after the traversal of the node 2 there is only the outbound interface connected to the upstream node: the outbound interface 21, but because the local interface R2 is the edge node that advertises the Layer 3 multicast group information, it is generated according to the traversed outbound interface list.
  • Table 7 Layer 3 multicast group generated by node R2 Multicast forwarding entry corresponding to G1 Layer 3 multicast group G 1
  • the local outbound interface corresponds to the Layer 3 multicast group G3.
  • the outbound interface list after the traversal of the node 4 has only the outbound interface connected to the downstream node: the outbound interface 49, and thus the outgoing interface list according to the traversal
  • Table 8 Layer 3 multicast group generated by node R4 Multicast forwarding entry corresponding to G3 Layer 3 multicast group G 3 Outbound interface 49
  • the multicast forwarding entry of the corresponding Layer 3 multicast group can be generated on each node corresponding to the Layer 3 multicast group.
  • the foregoing step 2066 is a preferred step, and the receiver and the multicast group that are connected to the edge node are located on the same side of the first node (that is, the root of the flooding tree), and are sent by the multicast source to the receiver group.
  • the broadcast data will be directly forwarded to the receiver at the convergence point without further copying to the direction of the first node, thereby saving network bandwidth.
  • the multicast forwarding entry is based on the forwarding entry shown in Table 8.
  • the node R9 reports the multicast data to the node R4.
  • R4 does not need to continue reporting the multicast data to the first node R1, thereby saving network bandwidth.
  • the prune of the flooding tree corresponding to each Layer 3 multicast group according to the Layer 3 multicast group information to generate a bidirectional multicast distribution tree may also have other implementation manners, where an example is used for details. Description, but not limited to the following examples, not here - repeat.
  • a specific example is as follows: generating a corresponding outbound interface list of the local node according to the flooding tree; traversing each node connected to the outbound interface in the outbound interface list according to each Layer 3 multicast group corresponding to the flooding tree; If the node connected to the interface is a downstream node and the node and the downstream node are not the edge nodes that advertise the multicast group information, the outbound interface information of the outbound interface in the outbound interface list is deleted; After all the interfaces connected to the outbound interface are in the outbound interface list, if only the local outbound interface exists in the outbound interface list and the local node is not the edge node that advertises the multicast group information, the third node is not generated. Multicast forwarding entry corresponding to the layer multicast group, no The multicast forwarding entry corresponding to the Layer 3 multicast group is generated according to the outbound interface list after the traversal.
  • the edge node after receiving the multicast group data packet, the edge node searches the multicast forwarding entry based on the multicast group address G to obtain the corresponding outbound interface.
  • source port pruning is required for multicast data packets. Specifically, as shown in Table 9, the data packet of the multicast group G that is sent from the outbound interface 1 can only forward the packet to the outbound interface of the remaining port 2 until the outgoing interface N performs copying and forwarding, but cannot send packets to the packet. The incoming outgoing interface 1 is forwarded again.
  • the reverse path forwarding (reverse path forwarding) is performed.
  • the packets can only be sent from the outbound interface list.
  • the multicast data packet in the above figure can only be forwarded from the outbound interface 1, or the outbound interface 2... or the outbound interface, but cannot be accessed from other interfaces. If the RPF check fails from other interfaces, the packet is discarded.
  • the method for creating a bidirectional multicast distribution tree based on the internal gateway protocol provided by the embodiment of the present invention generates the first node as a source node according to the root address and the shortest path tree algorithm of the first node flooded by the first node through the IGP
  • the shortest path to the other node, according to the shortest path constitutes a flooding tree, and when receiving the layer 3 multicast group information flooded by the edge node through the IGP, according to the layer 3 multicast group information and the first node support
  • the multicast group scope determines the flooding tree corresponding to each Layer 3 multicast group, and prune the flooding tree corresponding to each Layer 3 multicast group according to the Layer 3 multicast group information to generate a bidirectional multicast distribution tree.
  • a two-way multicast distribution tree is created based on the IGP, so that in a multi-point to multi-point multicast scenario, whether it is required to implement multicast or unicast, the IGP is used to solve the operation and maintenance of the protocol.
  • Multipoint to multipoint multicast field in the prior art In the scenario, the operation and maintenance of the two sets of protocols, the IGP unicast routing protocol and the PIM multicast routing protocol, need to be operated at the same time.
  • the third embodiment of the present invention provides an apparatus for creating a bidirectional multicast distribution tree based on the IGP, as shown in FIG. 3(a), including:
  • a first receiving unit 31 configured to receive a root address of the first node that is flooded by the at least one first node by using the IGP, and a range of the multicast group supported by the first node, where the first node is The node of the network flooding tree root; the specific implementation method can be referred to as shown in step 101 in Figure 1 (a), and details are not described herein.
  • a first creating unit 32 configured to generate a shortest path to the other node by using the first node as a source node according to the root address of the first node and the shortest path tree algorithm received by the first receiving unit, according to
  • the shortest path constitutes a flooding tree; for the specific implementation method, refer to step 102 shown in FIG. 1(a), and details are not described herein again.
  • the second receiving unit 33 is configured to receive the Layer 3 multicast group information that the edge node floods through the IGP.
  • the Layer 3 multicast group information that the edge node floods through the IGP.
  • a determining unit 34 configured to: when the second receiving unit receives the layer 3 multicast group information flooded by the edge node by the IGP, according to the layer 3 multicast group information and the received by the first receiving unit
  • the multicast group range supported by the first node is used to determine the flooding tree corresponding to each layer of the multicast group.
  • the determining unit includes:
  • the first selecting sub-unit 341 is configured to select a corresponding first node for the Layer 3 multicast group according to the Layer 3 multicast group information and the multicast IP address range carried by the first node; For the implementation method, refer to step 2061 shown in Figure 2 (h), and details are not described herein.
  • a second selecting sub-unit 342 configured to: if the first selected sub-unit is selected to have multiple A node covers the same multicast group, and the first node with the longest mask is selected as the first node from the plurality of first nodes according to the mask carried by the plurality of first nodes.
  • the corresponding first node of the Layer 3 multicast group for the specific implementation method, refer to step 2062 shown in Figure 2 (h), and details are not described herein again.
  • a third selecting sub-unit 343, configured to: if the second selected sub-unit is selected to obtain a first node having a plurality of masks, the HASH algorithm is used to select a unique one of the plurality of masked first nodes.
  • the node is the first node corresponding to the three-layer multicast group covered by the first node with the longest plurality of masks.
  • the pruning unit 35 is configured to prune the flooding tree corresponding to each Layer 3 multicast group determined by the determining unit according to the Layer 3 multicast group information to generate a bidirectional multicast distribution tree.
  • the specific implementation method refer to step 103 shown in Figure 1 (a), and details are not described herein.
  • the pruning unit includes:
  • the first generating sub-unit 351 is configured to generate a corresponding outbound interface list of the local node according to the flooding tree. For the specific implementation method, refer to step 2064 shown in FIG. 2(i), and details are not described herein.
  • the traversing sub-unit 352 is configured to traverse the nodes connected to each outbound interface in the outbound interface list according to each Layer 3 multicast group corresponding to the flooding tree.
  • the description of step 2065 is not repeated here.
  • Step 2066 Deleting the sub-unit 353, if the node connected to the egress interface traversing the sub-unit traversal and all nodes on the branch recursed to the leaf node by the node are not edge nodes for publishing the multicast group information, deleting the For the detailed description of the outbound interface of the outbound interface, refer to step 2066 shown in Figure 2 (i), and details are not described here.
  • a generating sub-unit 354 configured to: after traversing all the nodes connected to the outbound interface in the outbound interface list, if only the outbound interface connected to the upstream node remains in the outbound interface list, and the local node is not released The edge node of the multicast group information does not generate the corresponding corresponding to the Layer 3 multicast group. The multicast forwarding entry is generated. Otherwise, the multicast forwarding entry corresponding to the Layer 3 multicast group is generated according to the outbound interface list after the traversal. For the specific implementation, refer to step 2067 shown in Figure 2 (i), and details are not described herein.
  • the device further includes:
  • a first selecting unit 36 configured to: if the branch or the leaf node of the flooding tree created by the first creating unit has multiple father nodes that reach the first node, according to the attribute values of the multiple father nodes Among the father nodes, a unique node is selected as the parent node of the second node as the branch or leaf node.
  • the IGP is an IS-IS, and the attribute value of the father node may include a system ID.
  • the IGP is an OSPF protocol, and the attribute value of the father node may include a router ID.
  • the device further includes:
  • a second selecting unit 37 configured to: if there are multiple parallel links between two nodes in the flooding tree created by the first creating unit, according to attribute values of the multiple parallel links from the multiple parallel chains The unique link is selected as the link between the two nodes.
  • the IGP is an IS-IS, and the attribute value of the parallel link may include a line ID or a pseudo node ID, or the IGP is an OSPF protocol, and the attribute value of the parallel link may include an interface IP address.
  • an embodiment of the present invention further provides a node device, including: a receiver, configured to receive a root address and a root address of the first node that is flooded by at least one first node by using an IGP
  • the range of the multicast group supported by the first node is the node that is the root of the flooding tree of the entire network; and is also used to receive the information of the Layer 3 multicast group flooded by the edge node through the IGP.
  • a processor configured to generate, according to the root address and the shortest path tree algorithm of the first node received by the receiver, a shortest path to another node by using the first node as a source node, and configuring according to the shortest path a flooding tree; further configured to: when the receiver receives the layer 3 multicast group information flooded by the edge node by the IGP, according to the layer 3 multicast group information and the received by the first receiving unit
  • the multicast group range supported by the first node determines a flooding tree corresponding to each Layer 3 multicast group; and is used for flooding corresponding to each Layer 3 multicast group determined by the determining unit according to the Layer 3 multicast group information.
  • the tree is pruned to generate a two-way multicast distribution tree.
  • the processor is further configured to: if the created branch or leaf node of the flooding tree has multiple fathers reaching the first node The node selects a unique node from the plurality of parent nodes according to attribute values of the plurality of parent nodes as the branch node or the leaf node reaches the father node of the second node.
  • the attribute value of the father node when the IGP is IS-IS, the attribute value of the father node includes a system ID.
  • the attribute value of the father node when the IGP is an OSPF protocol, the attribute value of the father node includes a router ID.
  • the processor is further configured to: if there are multiple parallel links between two nodes in the created flooding tree, according to multiple The attribute value of the strip parallel link selects a unique link from the plurality of parallel links as a link between the two nodes.
  • the attribute value of the parallel link when the IGP is IS-IS, the attribute value of the parallel link includes a line ID or a pseudo node ID.
  • the attribute value of the parallel link when the IGP is an OSPF protocol, the attribute value of the parallel link includes an interface IP address.
  • processor is specifically configured to:
  • the first node with the longest mask is selected from the plurality of first nodes according to the mask carried by the multiple first nodes. Determining a corresponding first node of the three-layer multicast group covered by the plurality of first nodes; If the first node having the longest plurality of masks is selected, the HASH algorithm is used to select a unique node from the first node with the longest mask as the longest first node of the plurality of masks. The corresponding first node of the three-layer multicast group.
  • processor is further specifically configured to:
  • the multicast forwarding entry corresponding to the Layer 3 multicast group is not generated, and the multicast forwarding entry corresponding to the Layer 3 multicast group is generated according to the outbound interface list after the traversal.
  • the embodiment of the present invention further provides a system for creating a bidirectional multicast distribution tree based on an internal gateway protocol, including: a first node, The root node address of the first node and the multicast group range supported by the first node are flooded by the IGP, and the first node is used as a node of the entire network flooding tree root; the edge node is used to pass the IGP Flooding Layer 3 multicast group information; a common node, configured to receive a root address of the first node flooded by the first node and a range of multicast groups supported by the first node, according to the first node The tree root address and the shortest path tree algorithm, the first node is used as the source node to generate the shortest path to other nodes, and constitutes a flooding tree; the common node is also used to receive the flooding of the edge node.
  • the flooding tree corresponding to each layer 3 multicast group is determined according to the layer 3 multicast group information and the range of multicast groups supported by the first node, and according to the layer 3 group
  • the broadcast group information prune the flooding tree corresponding to each Layer 3 multicast group to generate a bidirectional multicast distribution pair.
  • the node generates a shortest path to the other node for the source node, and forms a flooding tree according to the shortest path.
  • the node When receiving the Layer 3 multicast group information flooded by the edge node through the IGP, the node obtains the information according to the Layer 3 multicast group. And the multicast group range supported by the first node determines a flooding tree corresponding to each layer of the multicast group, and prune the flooding tree corresponding to each layer of the multicast group according to the layer 3 multicast group information to generate a flooding tree
  • the two-way multicast distribution tree implements a two-way multicast distribution tree based on IGP, so that in a multi-point to multi-point multicast scenario, whether it needs to implement multicast or unicast, IGP is used.
  • the operation and maintenance of the two technologies in the multi-point to multi-point multicast scenario in the prior art requires the simultaneous operation and maintenance of the IGP unicast routing protocol and the PIM multicast routing protocol. question.
  • the method, device and system for creating a bidirectional multicast distribution tree based on IGP provided by the embodiment of the present invention can be applied to a multi-point to multi-point multicast scenario.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明实施例公开一种基于内部网关协议创建双向组播分发树的方法、装置及系统，涉及通信技术领域，以解决在多点到多点的组播场景中，需要同时运维IGP单播路由协议和PIM组播路由协议两套协议出现的运维复杂的问题。本发明提供的技术方案包括：接收至少一个第一节点洪泛过来的第一节点的树根地址以及支持的组播组范围；根据所述树根地址以及最短路径树算法，以第一节点为源节点生成到其他节点的最短路径，根据最短路径构成洪泛树；在接收到边缘节点洪泛过来的三层组播组信息时，根据所述三层组播组信息以及所述第一节点支持的组播组范围确定各三层组播组对应的洪泛树，并根据所述三层组播组信息对各三层组播组对应的洪泛树进行剪枝以生成双向组播分发树。

Description

基于内部网关协议创建双向組播分发树的方法、 装置及系统 本申请要求于 2012 年 7 月 12 日提交中国专利局、 申请号为 201210241161.0、发明名称为 "基于内部网关协议创建双向组播分发树的方 法、 装置及系统" 的中国专利申请的优先权， 其全部内容通过引用结合在 本申请中。 技术领域
本发明涉及通信技术领域， 尤其涉及一种基于内部网关协议创建双向 组播分发树的方法、 装置及系统。 背景技术
当前网络中有很多多点到多点的组播应用场景， 多点到多点的组播应 用场景是通过覆盖 （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上遍历之后的出接口列表
Figure imgf000019_0001
对应于三层组播组 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上遍历之后的出接口列表
Figure imgf000020_0001
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、 磁碟或光盘等。
以上所述， 仅为本发明的具体实施方式， 但本发明的保护范围并不局 限于此， 任何熟悉本技术领域的技术人员在本发明揭露的技术范围内， 可 轻易想到变化或替换， 都应涵盖在本发明的保护范围之内。 因此， 本发明 的保护范围应以所述权利要求的保护范围为准。

Claims

权利要求
1、 一种基于内部网关协议 IGP创建双向组播分发树的方法， 其特征在 于， 包括：
接收至少一个第一节点通过 IGP洪泛过来的所述第一节点的树根地址 以及所述第一节点支持的组播组范围， 所述第一节点为作为整网洪泛树树 根的节点；
根据所述第一节点的树根地址以及最短路径树算法， 以所述第一节点 为源节点生成到其他节点的最短路径， 根据所述最短路径构成洪泛树； 在接收到边缘节点通过 IGP洪泛过来的三层组播组信息时， 根据所述 三层组播组信息以及所述第一节点支持的组播组范围确定各三层组播组对 应的洪泛树， 并根据所述三层组播组信息对各三层组播组对应的洪泛树进 行剪枝以生成双向组播分发树。
2、 根据权利要求 1所述的方法， 其特征在于， 在所述根据所述第一节 点的树根地址以及最短路径树算法， 以所述第一节点为源节点生成到其他 节点的最短路径， 根据所述最短路径构成洪泛树之后， 还包括：
若洪泛树的分支或叶子节点有多个到达所述第一节点的父亲节点， 根 据多个父亲节点的属性值从所述多个父亲节点中选取唯一的节点作为所述 分支或叶子节点到达所述第一节点的父亲节点。
3、 根据权利要求 2所述的方法， 其特征在于， 当所述 IGP为中间系统 的路由选择协议 IS-IS时， 所述父亲节点的属性值包括系统 ID。
4、 根据权利要求 2所述的方法， 其特征在于， 当所述 IGP为开放式最 短路径优先 OSPF协议时， 所述父亲节点的属性值包括路由器 ID。
5、 根据权利要求 1-4任一项所述的方法， 其特征在于， 在所述根据所 述第一节点的树根地址以及最短路径树算法， 以所述第一节点为源节点生 成到其他节点的最短路径， 根据所述最短路径构成洪泛树之后， 还包括： 若洪泛树中的两个节点之间存在多条平行链路， 根据多条平行链路的 属性值从所述多个平行链路中选取唯一的链路作为两个节点之间的链路。
6、 根据权利要求 5所述的方法， 其特征在于， 当所述 IGP为 IS-IS时， 所述平行链路的属性值包括线路 ID或者伪节点 ID。
7、 根据权利要求 5所述的方法， 其特征在于， 当所述 IGP为 OSPF协 议时， 所述平行链路的属性值包括接口 IP地址。
8、 根据权利要求 1-7任一项所述的方法， 其特征在于， 所述第一节点 支持的组播组范围包括该第一节点支持的组播 IP地址以及该组播 IP地址对 应的掩码， 所述根据所述三层组播组信息以及所述第一节点支持的组播组 范围确定各三层组播组对应的洪泛树， 包括：
根据所述的三层组播组信息以及所述第一节点携带的组播 IP 地址范 围， 为所述三层组播组选取相应的第一节点；
若存在多个第一节点覆盖同一个组播组， 根据所述多个第一节点携带 的掩码， 从所述多个第一节点中选取出掩码最长的第一节点作为所述多个 第一节点覆盖的三层组播组相应的第一节点；
若存在多个掩码最长的第一节点， 采用 HASH算法从所述多个掩码最 长的第一节点中选取唯一的节点作为所述多个掩码最长的第一节点覆盖的 三层组播组相应的第一节点。
9、 根据权利要求 1-8任一项所述的方法， 其特征在于， 所述根据所述 三层组播组信息对各三层组播组对应的洪泛树进行剪枝， 包括：
根据洪泛树生成本地节点的对应的出接口列表；
根据洪泛树对应的每个三层组播组， 遍历所述出接口列表中每个出接 口连接的节点；
若该出接口连接的节点以及由该节点递归到叶子节点的支路上所有节 点均不为发布所述组播组信息的边缘节点， 则删除所述出接口列表中该出 接口的出接口信息；
在遍历完成所述出接口列表中所有出接口连接的节点后， 若所述出接 口列表中仅剩有与上游节点连接的出接口且本地节点也不为发布所述组播 组信息的边缘节点， 不生成与所述三层组播组对应的组播转发表项， 否则 根据遍历之后的出接口列表生成与所述三层组播组对应的组播转发表项。
10、 一种基于内部网关协议 IGP创建双向组播分发树的装置， 其特征 在于， 包括：
第一接收单元， 用于接收至少一个第一节点通过 IGP洪泛过来的所述 第一节点的树根地址以及所述第一节点支持的组播组范围， 所述第一节点 为作为整网洪泛树树根的节点；
第一创建单元， 用于根据所述第一接收单元接收的所述第一节点的树 根地址以及最短路径树算法， 以所述第一节点为源节点生成到其他节点的 最短路径， 根据所述最短路径构成洪泛树；
第二接收单元， 用于接收边缘节点通过 IGP洪泛过来的三层组播组信 息；
确定单元， 用于在所述第二接收单元接收到边缘节点通过 IGP洪泛过 来的三层组播组信息时， 根据所述三层组播组信息以及所述第一接收单元 接收的所述第一节点支持的组播组范围确定各三层组播组对应的洪泛树； 剪枝单元， 用于根据所述三层组播组信息对所述确定单元确定的各三 层组播组对应的洪泛树进行剪枝以生成双向组播分发树。
11、 根据权利要求 10所述的装置， 其特征在于， 还包括：
第一选取单元， 用于若所述第一创建单元创建的洪泛树的分支或叶子 节点有多个到达所述第一节点的父亲节点， 根据多个父亲节点的属性值从 所述多个父亲节点中选取唯一的节点作为所述分支或叶子节点到达所述第 二节点的父亲节点。
12、 根据权利要求 11所述的装置， 其特征在于， 当所述 IGP为中间系 统到中间系统的路由选择协议 IS-IS 时， 所述父亲节点的属性值包括系统 ID。
13、 根据权利要求 11所述的装置， 其特征在于， 当所述 IGP为开放式 最短路径优先 OSPF协议时， 所述父亲节点的属性值包括路由器 ID。
14、 根据权利要求 10-13任一项所述的装置， 其特征在于， 还包括： 第二选取单元， 用于若所述第一创建单元创建的洪泛树中的两个节点 之间存在多条平行链路， 根据多条平行链路的属性值从所述多个平行链路 中选取唯一的链路作为两个节点之间的链路。
15、 根据权利要求 14所述的装置， 其特征在于， 当所述 IGP为 IS-IS 时， 所述平行链路的属性值包括线路 ID或者伪节点 ID。
16、 根据权利要求 14所述的装置， 其特征在于， 当所述 IGP为 OSPF 协议时， 所述平行链路的属性值包括接口 IP地址。
17、根据权利要求 10-16任一项所述的装置， 其特征在于， 所述确定单 元， 包括：
第一选取子单元， 用于根据所述的三层组播组信息以及所述第一节点 携带的组播 IP地址范围， 为所述三层组播组选取相应的第一节点；
第二选取子单元， 用于若所述第一选取子单元选取得到存在多个第一 节点覆盖同一个组播组， 根据所述多个第一节点携带的掩码， 从所述多个 第一节点中选取出掩码最长的第一节点作为所述多个第一节点覆盖的三层 组播组相应的第一节点；
第三选取子单元， 用于若所述第二选取子单元选取得到存在多个掩码 最长的第一节点， 采用 HASH算法从所述多个掩码最长的第一节点中选取 唯一的节点作为所述多个掩码最长的第一节点覆盖的三层组播组相应的第 一节点。
18、根据权利要求 10-17任一项所述的装置， 其特征在于， 所述根据所 述剪枝单元， 包括：
第一生成子单元， 用于根据洪泛树生成本地节点的对应的出接口列表； 遍历子单元， 用于根据洪泛树对应的每个三层组播组， 遍历所述出接 口列表中每个出接口连接的节点；
删除子单元， 用于若遍历子单元遍历的该出接口连接的节点以及由该 节点递归到叶子节点的支路上所有节点均不为发布所述组播组信息的边缘 节点， 则删除所述出接口列表中该出接口的出接口信息；
生成子单元， 用于在遍历完成所述出接口列表中所有出接口连接的节 点后， 若所述出接口列表中仅剩有与上游节点连接的出接口且本地节点也 不为发布所述组播组信息的边缘节点， 不生成与所述三层组播组对应的组 播转发表项， 否则根据遍历之后的出接口列表生成与所述三层组播组对应 的组播转发表项。
19、 一种基于内部网关协议 IGP创建组播分发树的系统， 其特征在于， 包括：
第一节点， 用于通过 IGP洪泛所述第一节点的树根地址以及所述第一 节点支持的组播组范围， 所述第一节点为作为整网洪泛树树根的节点； 边缘节点， 用于通过 IGP洪泛三层组播组信息；
普通节点， 用于接收至少一个第一节点洪泛过来的所述第一节点的树 根地址以及所述第一节点支持的组播组范围， 根据所述第一节点的树根地 址以及最短路径树算法， 以所述第一节点为源节点生成到其他节点的最短 路径， 根据所述最短路径构成洪泛树；
所述普通节点， 还用于在接收到所述边缘节点洪泛过来的三层组播组 信息时， 根据所述三层组播组信息以及所述第一节点支持的组播组范围确 定各三层组播组对应的洪泛树， 并根据所述三层组播组信息对各三层组播 组对应的洪泛树进行剪枝以生成双向组播分发树。
PCT/CN2013/078659 2012-07-12 2013-07-02 基于内部网关协议创建双向组播分发树的方法、装置及系统 WO2014008826A1 (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP13816047.8A EP2866377B1 (en) 2012-07-12 2013-07-02 Method, device, and system for establishing bi-directional multicast distribution tree based on interior gateway protocol
US14/594,864 US9647959B2 (en) 2012-07-12 2015-01-12 Method, device, and system for creating bidirectional multicast distribution tree based on interior gateway protocol

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201210241161.0 2012-07-12
CN201210241161.0A CN103546381B (zh) 2012-07-12 2012-07-12 基于内部网关协议创建双向组播分发树的方法、装置及系统

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US14/594,864 Continuation US9647959B2 (en) 2012-07-12 2015-01-12 Method, device, and system for creating bidirectional multicast distribution tree based on interior gateway protocol

Publications (1)

Publication Number Publication Date
WO2014008826A1 true WO2014008826A1 (zh) 2014-01-16

Family

ID=49915396

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2013/078659 WO2014008826A1 (zh) 2012-07-12 2013-07-02 基于内部网关协议创建双向组播分发树的方法、装置及系统

Country Status (4)

Country Link
US (1) US9647959B2 (zh)
EP (1) EP2866377B1 (zh)
CN (1) CN103546381B (zh)
WO (1) WO2014008826A1 (zh)

Families Citing this family (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103546381B (zh) * 2012-07-12 2017-06-09 华为技术有限公司 基于内部网关协议创建双向组播分发树的方法、装置及系统
US9647883B2 (en) 2014-03-21 2017-05-09 Nicria, Inc. Multiple levels of logical routers
CN105282041A (zh) * 2014-07-18 2016-01-27 中兴通讯股份有限公司 基于isis的洪泛方法及装置
JP6520362B2 (ja) * 2014-08-25 2019-05-29 富士通株式会社 生成方法、装置、及びプログラム
CN104283794B (zh) * 2014-10-11 2017-11-24 新华三技术有限公司 多链路透明互联trill网络中组播树选路方法和设备
US10129180B2 (en) 2015-01-30 2018-11-13 Nicira, Inc. Transit logical switch within logical router
US10686699B2 (en) * 2015-07-28 2020-06-16 Ciena Corporation Multicast systems and methods for segment routing
US10230629B2 (en) 2015-08-11 2019-03-12 Nicira, Inc. Static route configuration for logical router
US10075363B2 (en) 2015-08-31 2018-09-11 Nicira, Inc. Authorization for advertised routes among logical routers
CN106603407B (zh) * 2015-10-16 2020-10-27 中兴通讯股份有限公司 组播地址的传输方法和装置
US10095535B2 (en) 2015-10-31 2018-10-09 Nicira, Inc. Static route types for logical routers
WO2017168203A1 (en) * 2016-03-28 2017-10-05 Telefonaktiebolaget Lm Ericsson (Publ) Multipoint to multipoint trees for computed spring multicast
US10153973B2 (en) 2016-06-29 2018-12-11 Nicira, Inc. Installation of routing tables for logical router in route server mode
US10454758B2 (en) * 2016-08-31 2019-10-22 Nicira, Inc. Edge node cluster network redundancy and fast convergence using an underlay anycast VTEP IP
CN108075981B (zh) 2016-11-16 2021-04-09 华为技术有限公司 一种链路状态数据包的传输方法及路由节点
CN108536447B (zh) * 2018-04-11 2021-07-16 上海掌门科技有限公司 运维管理方法
US11050679B1 (en) * 2019-06-28 2021-06-29 Juniper Networks, Inc. Defining non-forwarding adjacencies in bipartite networks, such as Clos newtorks, having a level 2 backbone and level 1 nodes
CN111669537B (zh) * 2020-04-24 2023-12-29 视联动力信息技术股份有限公司 一种数据分发方法、装置、电子设备及存储介质
CN112787688A (zh) * 2020-12-31 2021-05-11 广东电网有限责任公司电力调度控制中心 一种组播树节点通信方法及装置

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101083664A (zh) * 2007-07-20 2007-12-05 中兴通讯股份有限公司 一种防止二层组播数据流洪泛的方法
US20080089335A1 (en) * 2006-10-13 2008-04-17 At&T Knowledge Ventures, L.P. System and method for routing packet traffic
CN102142970A (zh) * 2011-03-16 2011-08-03 华为技术有限公司 二层以太网络的组播树构建方法和网络节点设备
WO2012042440A2 (en) * 2010-09-29 2012-04-05 Telefonaktiebolaget L M Ericsson (Publ) Fast flooding based fast convergence to recover from network failures

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3842250B2 (ja) * 2003-07-08 2006-11-08 インターナショナル・ビジネス・マシーンズ・コーポレーション 経路制御装置、経路制御方法及びそのプログラム
US8675653B2 (en) * 2005-05-17 2014-03-18 Alcatel Lucent Co-existing static and dynamic IP multicast
US7835378B2 (en) * 2006-02-02 2010-11-16 Cisco Technology, Inc. Root node redundancy for multipoint-to-multipoint transport trees
CN101163103A (zh) * 2007-11-07 2008-04-16 孙先花 一种实现快速重路由的方法
US7911944B2 (en) * 2007-12-26 2011-03-22 Nortel Networks Limited Tie-breaking in shortest path determination
US8467389B2 (en) * 2011-02-16 2013-06-18 Solace Systems, Inc. Subscription Management and Routing Protocol (SMRP) and Method
CN103546381B (zh) * 2012-07-12 2017-06-09 华为技术有限公司 基于内部网关协议创建双向组播分发树的方法、装置及系统

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20080089335A1 (en) * 2006-10-13 2008-04-17 At&T Knowledge Ventures, L.P. System and method for routing packet traffic
CN101083664A (zh) * 2007-07-20 2007-12-05 中兴通讯股份有限公司 一种防止二层组播数据流洪泛的方法
WO2012042440A2 (en) * 2010-09-29 2012-04-05 Telefonaktiebolaget L M Ericsson (Publ) Fast flooding based fast convergence to recover from network failures
CN102142970A (zh) * 2011-03-16 2011-08-03 华为技术有限公司 二层以太网络的组播树构建方法和网络节点设备

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP2866377A4 *

Also Published As

Publication number Publication date
EP2866377B1 (en) 2017-04-05
CN103546381B (zh) 2017-06-09
EP2866377A1 (en) 2015-04-29
US9647959B2 (en) 2017-05-09
US20150124810A1 (en) 2015-05-07
EP2866377A4 (en) 2015-07-29
CN103546381A (zh) 2014-01-29

Similar Documents

Publication Publication Date Title
WO2014008826A1 (zh) 基于内部网关协议创建双向组播分发树的方法、装置及系统
Moy MOSPF: Analysis and experience
El-Sayed et al. A survey of proposals for an alternative group communication service
US7304955B2 (en) Scalable IP multicast with efficient forwarding cache
US9077551B2 (en) Selection of multicast router interfaces in an L2 switch connecting end hosts and routers, which is running IGMP and PIM snooping
CN103873373B (zh) 一种组播数据报文转发方法及设备
US8310957B1 (en) Minimum-cost spanning trees of unicast tunnels for multicast distribution
CN103346968B (zh) 用于路由组播数据的方法和装置
US20090080345A1 (en) Efficient multipoint distribution tree construction for shortest path bridging
CN102137000B (zh) 一种建立切换组播分发树的方法、装置及系统
EP2989755B1 (en) Efficient multicast delivery to dually connected (vpc) hosts in overlay networks
US11233741B1 (en) Replication mode selection for EVPN multicast
Rosenberg A primer of multicast routing
CN104579981B (zh) 一种组播数据报文转发方法及设备
Yang et al. A service-centric multicast architecture and routing protocol
Moy RFC1584: Multicast Extensions to OSPF
WO2012103748A1 (zh) 一种组播控制方法、路由设备及组播系统
AT&T survey.DVI
Zhang et al. Providing multicast through recursive unicast
CN113810285B (zh) 用于多播源发现协议msdp循环避免的方法和设备
Chakeres et al. Connecting MANET multicast
CN103595609B (zh) Trill网络互联方法、系统及设备
Veselý et al. IPv6 unicast and IPv4 multicast routing in OMNeT++.
Moy RFC1585: MOSPF: Analysis and Experience
Ferdaus et al. Routing: internet routing protocols and algorithms

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 13816047

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

REEP Request for entry into the european phase

Ref document number: 2013816047

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2013816047

Country of ref document: EP