Granted Patent B2

US 8,243,585 · App. 12/546,762 · Granted Aug 14, 2012

Abstract

Claims (59)

1. A method for providing fault-resilient propagation of multicast using Redundant Multicast Trees (RMTs), the method comprising:

identifying each potential Shared Risk Link Group (SRLG) conflict associated with a pair of RMTs providing node-disjoint paths to a plurality of destination nodes, wherein the pair of RMTs comprises a first RMT from a first multicast source node to each of the destination nodes and a second RMT from a second multicast source node to each of the destination nodes, wherein each potential SRLG conflict comprises a plurality of links;

identifying each potential SRLG conflict that is an actual SRLG conflict, wherein a potential SRLG conflict is determined to be an actual SRLG conflict if first and second paths for one of the destination nodes over the respective first and second RMTs each traverse at least one link of the potential SRLG conflict; and

for each actual SRLG conflict, determining a detour path for protecting the links of the actual SRLG conflict.

2. The method of claim 1 , further comprising:

determining the first RMT and the second RMT.

3. The method of claim 2 , wherein the first and second RMTs are determined in a manner for minimizing the number of SRLGs on the first and second RMTs.

4. The method of claim 3 , wherein identifying each potential SRLG conflict that is an actual SRLG conflict comprises:

for each of the destination nodes:

traversing a first traversal path, on the first RMT, between the destination node toward the first multicast source node;

traversing a second traversal path, on the second RMT, between the destination node and the second multicast source node; and

if the first and second traversal paths each traverse at least one link associated with the same potential SRLG conflict, identifying the potential SRLG conflict as being an actual SRLG conflict.

5. The method of claim 3 , wherein identifying each potential SRLG conflict that is an actual SRLG conflict is performed using an array comprising an entry for each respective potential SRLG conflict, wherein identifying each potential SRLG conflict that is an actual SRLG conflict comprises:

traversing a first traversal path, on the first RMT, between the destination node and the first multicast source node, and for each link of the first traversal path that is associated with a potential SRLG conflict:

identifying the potential SRLG conflict; and

marking the entry in the array that is associated with the identified potential SRLG conflict; and

traversing a second traversal path, on the second RMT, between the destination node and the second source node, and for each link of the second traversal path that is associated with a potential SRLG conflict:

identifying the potential SRLG conflict;

checking the entry in the array that is associated with the identified potential SRLG conflict; and

if the entry in the array is marked, identifying the potential SRLG conflict as being an actual SRLG conflict.

6. The method of claim 1 , wherein each detour path is a label switched path (LSP).

7. The method of claim 1 , wherein the first and second multicast source nodes each are configured to receive a content stream from a content source node, wherein the first and second multicast source nodes each are configured to multicast the content stream over the first and second RMTs respectively.

8. The method of claim 1 , wherein the first RMT includes the second multicast source node and the second RMT includes the first multicast source node.

9. The method of claim 1 , further comprising:

generating configuration information for use in establishing the first and second RMTs and the detour path within a network.

10. The method of claim 9 , further comprising:

propagating the configuration information toward the network.

11. An apparatus for providing fault-resilient propagation of multicast traffic using Redundant Multicast Trees (RMTs), the apparatus comprising:

a processor and a memory, the processor configured to:

identify each potential Shared Risk Link Group (SRLG) conflict associated with a pair of RMTs providing node-disjoint paths to a plurality of destination nodes, wherein the pair of RMTs comprises a first RMT from a first multicast source node to each of the destination nodes and a second RMT from a second multicast source node to each of the destination nodes, wherein each potential SRLG conflict comprises a plurality of links;

identify each potential SRLG conflict that is an actual SRLG conflict, wherein a potential SRLG conflict is determined to be an actual SRLG conflict if first and second paths for one of the destination nodes over the respective first and second RMTs each traverse at least one link of the potential SRLG conflict; and

determine, for each actual SRLG conflict, a detour path for protecting the links of the actual SRLG conflict.

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

determine the first RMT and the second RMT.

13. The apparatus of claim 12 , wherein the first and second RMTs are determined in a manner for minimizing the number of SRLGs on the first and second RMTs.

14. The apparatus of claim 13 , wherein, for identifying each potential SRLG conflict that is an actual SRLG conflict, the processor is configured to:

perform the following for each of the destination nodes:

traverse a first traversal path, on the first RMT, between the destination node toward the first multicast source node;

traverse a second traversal path, on the second RMT, between the destination node and the second multicast source node; and

if the first and second traversal paths each traverse at least one link associated with the same potential SRLG conflict, identify the potential SRLG conflict as being an actual SRLG conflict.

15. The apparatus of claim 13 , wherein the processor is configured to identify each potential SRLG conflict that is an actual SRLG conflict using an array comprising an entry for each respective potential SRLG conflict, wherein, for identifying each potential SRLG conflict that is an actual SRLG conflict, the processor is configured to:

traverse a first traversal path, on the first RMT, between the destination node and the first multicast source node, and for each link of the first traversal path that is associated with a potential SRLG conflict:

identify the potential SRLG conflict; and

mark the entry in the array that is associated with the identified potential SRLG conflict; and

traverse a second traversal path, on the second RMT, between the destination node and the second source node, and for each link of the second traversal path that is associated with a potential SRLG conflict:

identify the potential SRLG conflict;

checking check the entry in the array that is associated with the identified potential SRLG conflict; and

if the entry in the array is marked, identify the potential SRLG conflict as being an actual SRLG conflict.

16. The apparatus of claim 11 , wherein each detour path is a label switched path (LSP).

17. The apparatus of claim 11 , wherein the first and second multicast source nodes each are configured to receive a content stream from a content source node, wherein the first and second multicast source nodes each are configured to multicast the content stream over the first and second RMTs respectively.

18. The apparatus of claim 11 , wherein the first RMT includes the second multicast source node and the second RMT includes the first multicast source node.

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

generate configuration information for use in establishing the first and second RMTs and the detour path within a network.

20. The apparatus of claim 19 , wherein the processor is configured to:

propagate the configuration information toward the network.

21. A non-transitory computer readable medium storing instructions which, when executed by a computer, cause the computer to perform a method for providing fault-resilient propagation of multicast traffic using Redundant Multicast Trees (RMTs), the method comprising:

identifying each potential Shared Risk Link Group (SRLG) conflict associated with a pair of RMTs providing node-disjoint paths to a plurality of destination nodes, wherein the pair of RMTs comprises a first RMT from a first multicast source node to each of the destination nodes and a second RMT from a second multicast source node to each of the destination nodes, wherein each potential SRLG conflict comprises a plurality of links;

identifying each potential SRLG conflict that is an actual SRLG conflict, wherein a potential SRLG conflict is determined to be an actual SRLG conflict if first and second paths for one of the destination nodes over the respective first and second RMTs each traverse at least one link of the potential SRLG conflict; and

for each actual SRLG conflict, determining a detour path for protecting the links of the actual SRLG conflict.

Assignments (8)