Fault-resilient broadcast, multicast, and unicast services

Patent metadata

Field	Value
Publication number	US-9722861-B2
Application number	US-201314143120-A
Country	US
Kind code	B2
Filing date	Dec 30, 2013
Priority date	Jul 7, 2013
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

In general, various capabilities related to fault-resilient services within communication networks are presented. The services may include broadcast services, multicast services, unicast services, or the like, as well as various combinations thereof. A capability for providing local protection to unicast traffic at a node associated with a pair of redundant trees is presented herein. A capability for providing local protection to multicast traffic at a node associated with a pair of redundant trees is presented herein. A capability for constructing a pair of redundant trees is presented herein. A capability for constructing a pair of redundant trees includes partitioning a graph into a pair of partitions based on a link coloring mechanism and constructing the pair of redundant trees based on the pair of partitions.

First claim

What is claimed is:

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 th

Assignees

• Bejerano Yigal
• Koppol Pramod V
• Alcatel Lucent

Inventors

• Bejerano Yigal
• Koppol Pramod V

Classifications

• H04L41/12 Primary

  Discovery or management of network topologies · CPC title

• H04L41/0659 Primary

  by isolating or reconfiguring faulty entities · CPC title

• H04L41/0663

  Performing the actions predefined by failover planning, e.g. switching to standby network elements · CPC title

• H04L41/0668

  by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure · CPC title