Fault-resilient broadcast, multicast, and unicast services

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.

What is claimed is: 
     
         1 . An apparatus, comprising:
 a processor and a memory communicatively connected to the processor, the processor configured to:
 receive a packet via a first redundant tree (RT) rooted at a source node and configured to serve a set of destination nodes, the first RT having a first tree identifier associated therewith, the packet including the first tree identifier of the first RT; 
 based on detection of a failure on the first RT, modify the packet by replacing the first tree identifier with a second tree identifier of a second RT rooted at the source node and configured to serve the set of destination nodes; and 
 propagate the modified packet via the second RT. 
   
     
     
         2 . The apparatus of  claim 1 , wherein the first RT and the second RT are configured to provide two node-disjoint paths from the source node to each destination node in the set of destination nodes. 
     
     
         3 . The apparatus of  claim 1 , wherein the packet comprises a unicast packet or a multicast packet. 
     
     
         4 . The apparatus of  claim 1 , wherein the packet is a unicast packet intended for the source node, wherein the failure on the first RT is in a direction toward the source node, wherein the modified unicast packet is propagated toward the source node. 
     
     
         5 . The apparatus of  claim 1 , wherein the packet is a multicast packet intended for the set of destination nodes, wherein the failure on the first RT is in a direction toward at least one destination node in the set of destination nodes, wherein the modified multicast packet is propagated toward at least one destination node in the set of destination nodes. 
     
     
         6 . The apparatus of  claim 1 , wherein the first tree identifier and the second tree identifier are identical except for one or more bit positions of the first tree identifier and the second tree identifier, wherein, to modify the packet, the processor is configured to:
 switch respective one or more values of the one or more bit positions of the first tree identifier to provide thereby the second tree identifier.   
     
     
         7 . The apparatus of  claim 1 , wherein the first RT is a first Point-To-Multipoint (P2MP) tree and the second RT is a second P2MP tree. 
     
     
         8 . The apparatus of  claim 1 , wherein the first RT is a first Virtual Local Area Network (VLAN) spanning tree (VST) and the second RT is a second VST. 
     
     
         9 . The apparatus of  claim 8 , wherein the first tree identifier is a first VLAN identifier and the second tree identifier is a second VLAN identifier. 
     
     
         10 . The apparatus of  claim 9 , wherein the first VLAN identifier and the second VLAN identifier are identical except for one or more corresponding bit positions of the first VLAN identifier and the second VLAN identifier, wherein, to modify the packet, the processor is configured to:
 switch respective one or more values of the one or more bit positions of the first VLAN identifier to provide thereby the second VLAN identifier.   
     
     
         11 . The apparatus of  claim 1 , wherein the failure on the first RT comprises a failure of a link or a node adjacent to the apparatus. 
     
     
         12 . The apparatus of  claim 1 , wherein the processor is configured to receive the packet from a switch fabric of the apparatus, wherein the processor is configured to propagate the modified packet via the second RT by providing the modified packet to the switch fabric of the apparatus for rerouting. 
     
     
         13 . The apparatus of  claim 1 , wherein the processor is configured to:
 receive a first keep-alive message from the source node on the first RT via a first port and receive a second keep-alive message from the source node on the second RT via a second port; and   send a first keep-alive message toward the source node on the first RT via the first port and second a second keep-alive message toward the source node on the second RT via the second port.   
     
     
         14 . The apparatus of  claim 1 , wherein the packet is a unicast packet generated by one of the destination nodes in the set of destination nodes or a multicast packet generated by the source node. 
     
     
         15 . The apparatus of  claim 1 , wherein the packet is a unicast packet, wherein the unicast packet further comprises an address of one of the destination nodes in the set of destination nodes. 
     
     
         16 . The apparatus of  claim 1 , wherein the packet is a multicast packet, wherein the multicast packet further comprises a multicast address. 
     
     
         17 . The apparatus of  claim 1 , wherein the packet is a unicast packet intended for the source node, wherein the failure on the first RT is in a direction toward the source node, wherein the processor is configured to:
 receive, via the second RT, a multicast packet intended for the set of destination nodes.   
     
     
         18 . The apparatus of  claim 1 , wherein the packet is a multicast packet intended for the set of destination nodes, wherein the failure on the first RT is in a direction toward at least one destination node in the set of destination nodes, wherein the processor is configured to:
 receive, via the second RT, a unicast packet intended for the source node.   
     
     
         19 . A computer-readable storage medium storing instructions which, when executed by a computer, cause the computer to perform a method, the method comprising:
 receiving a packet via a first redundant tree (RT) rooted at a source node and configured to serve a set of destination nodes, the first RT having a first tree identifier associated therewith, the packet including the first tree identifier of the first RT;   based on detection of a failure on the first RT, modifying the packet by replacing the first tree identifier with a second tree identifier of a second RT rooted at the source node and configured to serve the set of destination nodes; and   propagating the modified packet via the second RT.   
     
     
         20 . A method, comprising:
 using a processor and a memory for:
 receiving a packet via a first redundant tree (RT) rooted at a source node and configured to serve a set of destination nodes, the first RT having a first tree identifier associated therewith, the packet including the first tree identifier of the first RT; 
 based on detection of a failure on the first RT, modifying the packet by replacing the first tree identifier with a second tree identifier of a second RT rooted at the source node and configured to serve the set of destination nodes; and 
 propagating the modified packet via the second RT.