Granted Patent B2

US 9,722,861 · App. 14/143,120 · Granted Aug 1, 2017

Inventors: Yigal Bejerano (Springfield, NJ); Pramod V. Koppol (Manalapan, NJ)

Assignee: Alcatel Lucent

H04L41/0659H04L41/0663H04L41/0668H04L41/12

Abstract

Claims (82)

1. An apparatus, comprising:

a processor and a memory communicatively connected to the processor, the processor configured to:

receive a graph representing a topology of at least a portion of a network, the graph comprising a set of nodes and a set of links, the set of nodes comprising a multicast source node;

partition the graph into a pair of partitions including a first partition and a second partition, the first partition comprising each of the nodes of the set of nodes and a first subset of links of the set of links, the second partition comprising each of the nodes of the set of nodes and a second subset of links of the set of links; and

construct, based on the pair of partitions, a pair of point-to-multipoint (P2MP) trees including a first P2MP tree and a second P2MP tree, the first P2MP tree being constructed based on the first partition and the second P2MP tree being constructed based on the second partition.

2. The apparatus of claim 1 , wherein the first partition is a first redundant directed acyclic sub-graph (RDAG) and the second partition is a second RDAG.

3. The apparatus of claim 1 , wherein, to construct the pair of P2MP trees, the processor is configured to:

independently construct the first P2MP tree based on the first partition and construct the second P2MP tree based on the second partition.

4. The apparatus of claim 1 , wherein, to partition the graph into the pair of partitions, the processor is configured to:

construct a node arrangement for the set of nodes and the set of links; and

color the links, based on the node arrangement, to compute the first partition and the second partition.

5. The apparatus of claim 4 , wherein, to construct the node arrangement for the set of nodes and the set of links, the processor is configured to:

calculate a directed spanning tree rooted at the multicast source node; and

determine, based on the directed spanning tree, a skeleton list indicative of the node arrangement.

6. The apparatus of claim 4 , wherein, to construct the node arrangement for the set of nodes and the set of links, the processor is configured to:

calculate a directed spanning tree rooted at the multicast source node;

construct an initial skeleton list include a first node set including the multicast source node, one or more intermediate node sets including one or more outgoing neighbor nodes of the multicast source node in the directed spanning tree, and a last node set including the multicast source node; and

construct the node arrangement by performing an iterative skeleton list refinement using the initial skeleton list as an input.

7. The apparatus of claim 6 , wherein, to construct the initial skeleton list, the processor is configured to:

for each of the one or more outgoing neighbor nodes of the multicast source node, construct the associated intermediate node set to include each of the nodes in the subtree of the directed spanning tree rooted at the outgoing neighbor node.

8. The apparatus of claim 6 , wherein, to construct the node arrangement by performing the iterative skeleton list refinement using the initial skeleton list as an input, the processor is configured to:

at each of one or more iterations:

identify a node set having an associated anchor node and including a non-anchor node having an incoming neighbor node in a different node set;

create a new node set in which the non-anchor node is the anchor node of the new node set;

move, into the new node set, the non-anchor node and any descendents of the non-anchor node in the directed spanning tree; and

insert the new node set into the skeleton list between the identified node set and a node set including the non-anchor node.

9. The apparatus of claim 4 , wherein, to color the links, the processor is configured to:

for each link in the set of links that is not an outgoing neighbor of the multicast source node, color the link a first color associated with the first partition based on a determination that the link is a first link type or color the link a second color associated with the second partition based on a determination that the link is a second link type; and

for each link in the set of links that is an outgoing neighbor of the multicast source node, color the link in a manner tending to ensure that the first partition and the second partition induce two node-disjoint paths to each outgoing neighbor node of the multicast source node.

10. The apparatus of claim 4 , wherein, to color the links, the processor is configured to:

for each link in the set of links that is an outgoing neighbor node of the multicast source node:

based on a determination that all incoming non-source neighbor nodes of the outgoing neighbor node appear after the outgoing neighbor node in the node arrangement, color the link a first color associated with the first partition and add the link to the first partition, otherwise color the link a second color associated with the second partition and add the link to the second partition; or

based on a determination that the only incoming neighbor of the outgoing neighbor node is the multicast source node, color the link a first color and a second color and add the link to the first partition and the second partition; or

otherwise, based on one or more criteria, color the link a first color associated with the first partition and add the link to the first partition or color the link a second color associated with the second partition and add the link to the second partition.

11. The apparatus of claim 4 , wherein the processor is configured to:

based on a determination that at least one link in the set of links has not been colored:

color the at least one link in the set of links that has not been colored in a manner tending to ensure that:

for each 2-reachable node in the set of nodes of the first partition, any path from the multicast source node to the 2-reachable node in the first partition is node disjoint from any path from the multicast source node to the 2-reachable node in the second partition; and

for each 1-reachable node in the set of nodes of the first partition, any path from the multicast source node to the 1-reachable node in the first partition shares only cut nodes or cut links of the 1-reachable node with a path from the multicast source node to the 1-reachable node in the second partition.

12. The apparatus of claim 4 , wherein the node arrangement comprises a skeleton list including a node list having an anchor node that is a cut node for one or more other nodes of the node list, wherein the processor is configured to:

for one or more links from the anchor node to the one or more other nodes of the node list, color each of the one or more links a first color associated with the first partition and a second color associated with the second partition.

13. The apparatus of claim 4 , wherein the processor is configured to:

identify one of the links in the set of links as an internal link based on a determination that the one of the links is an incoming link of a node in a node set having an anchor node that is a cut node for the node set; and

color the internal link.

14. The apparatus of claim 1 , wherein the set of links comprises a cut link, wherein, to partition the graph into the first partition and the second partition, the processor is configured to:

include the cut link within both the first subset of links of the first partition and the second subset of links of the second partition.

15. The apparatus of claim 1 , wherein, to construct the pair of P2MP trees, the processor is configured to:

construct the first P2MP tree based on a first tree construction mechanism; and

construct the second P2MP tree based on a second tree construction mechanism.

16. The apparatus of claim 15 , wherein the first tree construction mechanism and the second tree construction mechanism are different.

17. The apparatus of claim 1 , wherein the processor is configured to partition the graph based on a node arrangement, wherein the processor is configured to:

based on addition, to the topology, of a new node having at least two incoming links from at least two neighbor nodes:

insert the new node into a location within the node arrangement; and

color the at least two incoming links based on the location of the new node within the node arrangement.

18. The apparatus of claim 1 , wherein the processor is configured to:

based on addition, to the topology, of a new node having a single incoming link from a neighbor node:

insert the new node into the first partition and color the incoming link a first color associated with the first partition; and

insert the new node into the second partition and color the incoming link a second color associated with the second partition.

19. The apparatus of claim 1 , wherein the processor is configured to partition the graph based on a node arrangement comprising a plurality of node sets, wherein the processor is configured to:

based on addition, to the topology, of a new node having a single incoming link from a neighbor node:

insert the new node into one of the node sets including the neighbor node.

20. The apparatus of claim 1 , wherein the topology includes a cut element, wherein the processor is configured to partition the graph based on a node arrangement comprising a skeleton list including a plurality of node sets, wherein the processor is configured to:

based on addition, to the topology, of a new node such that a particular node has a new incoming link:

modify the skeleton list by assign a sub-tree of a directed spanning tree rooted at the multicast source node to one of the node sets having an anchor node that is the closest cut node of particular node having the new incoming link; and

modify the node arrangement by performing an iterative skeleton list refinement using the modified skeleton list as an input.

21. The apparatus of claim 1 , wherein the processor is configured to:

based on removal of one or more elements from the topology:

identify one or more affected nodes affected by the removal of the one or more elements from the topology; and

modify at least one of the first partition and second partition based on the one or more affected nodes.

22. The apparatus of claim 1 , wherein the processor is configured to partition the graph based on a node arrangement comprising a skeleton list having a plurality of node sets, wherein the processor is configured to:

based on removal of one or more elements from the topology:

identify one or more affected nodes affected by the removal of the one or more elements from the topology; and

modify the node arrangement based on the one or more affected nodes.

23. A method, comprising:

using a processor and a memory for:

receiving a graph representing a topology of at least a portion of a network, the graph comprising a set of nodes and a set of links, the set of nodes comprising a multicast source node;

partitioning the graph into a pair of partitions including a first partition and a second partition, the first partition comprising each of the nodes of the set of nodes and a first subset of links of the set of links, the second partition comprising each of the nodes of the set of nodes and a second subset of links of the set of links; and

constructing, based on the pair of partitions, a pair of point-to-multipoint (P2MP) trees including a first P2MP tree and a second P2MP tree, the first P2MP tree being constructed based on the first partition and the second P2MP tree being constructed based on the second partition.

24. A non-transitory computer-readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method, the method comprising:

receiving a graph representing a topology of at least a portion of a network, the graph comprising a set of nodes and a set of links, the set of nodes comprising a multicast source node;

partitioning the graph into a pair of partitions including a first partition and a second partition, the first partition comprising each of the nodes of the set of nodes and a first subset of links of the set of links, the second partition comprising each of the nodes of the set of nodes and a second subset of links of the set of links; and

constructing, based on the pair of partitions, a pair of point-to-multipoint (P2MP) trees including a first P2MP tree and a second P2MP tree, the first P2MP tree being constructed based on the first partition and the second P2MP tree being constructed based on the second partition.

Assignments (14)

Continuity (2)