Path segment protecting p-cycles

Abstract

This disclosure introduces a significant extension to the method of p-cycles for network protection. The main advance is the generalization of the p-cycle concept to protect multi-span segments of contiguous working flow, not only spans that lie on the cycle or directly straddle the p-cycle. This effectively extends the p-cycle technique to include path protection, or protection of any flow segment along a path, as well as the original span protecting use of p-cycles. It also gives an inherent means of transit flow protection against node loss. We present a capacity optimization model for the new scheme and compare it to prior p-cycle designs and other types of efficient mesh-survivable networks. Results show that path-segment-protecting p-cycles (“flow p-cycles” for short) have capacity efficiency near that of a path-restorable network without stub release. An immediate practical impact of the work is to suggest the of use flow p-cycles to protect transparent optical express flows through a regional network.

What is claimed is:  
     
         1 . A telecommunications network, comprising: 
 plural nodes connected by plural spans and arranged to form a mesh network;    at least one pre-configured cycle of spare capacity being established in the mesh network, the pre-configured cycle including plural nodes of the mesh network; and    the plural nodes of the pre-configured cycle being configured to protect at least one path segment, where the path segment includes at least two intersecting nodes within the pre-configured cycle and at least one intermediate node in a path that includes the two intersecting nodes and straddles the pre-configured cycle.    
     
     
         2 . The telecommunications network of  claim 1  in which the path segments are segments of a working path with a start node not connected to the pre-configured cycle.  
     
     
         3 . The telecommunications network of  claim 1  in which the path segments are segments of a working path with an end node not connected to the pre-configured cycle.  
     
     
         4 . The telecommunications network of  claim 1  in which the pre-configured cycle of spare capacity is provided by: 
 a) identifying all working flows in the mesh network to be restored;  
 b) identifying the spare capacity of the pre-configured cycle to restore all working flows for all spans subject to failure in all path segments;  
 c) providing spare capacity along the pre-configured cycle sufficient to restore all working flows.  
 
     
     
         5 . The telecommunications network of  claim 1  in which establishing a pre-configured cycle comprises the steps of: 
 pre-selecting a set of candidate cycles for forming into pre-configured cycles;  
 allocating working paths and spare capacity in the mesh network based on the set of candidate cycles; and  
 providing the mesh network with spare capacity arranged in pre-configured cycles according to the allocation determined in the preceding step.  
 
     
     
         6 . The telecommunications network of  claim 5  in which the allocation of working paths and spare capacity is jointly optimized.  
     
     
         7 . The telecommunications network of  claim 5  in which pre-selecting candidate cycles includes ranking a set of closed paths in the mesh network according to the degree to which each closed path protects spans on and off the closed path, and selecting candidate cycles from the set of closed paths.  
     
     
         8 . The telecommunications network of  claim 7  in which pre-selecting candidate cycles comprises: 
 a) determining a scoring credit for each closed path in the set of closed paths, where the scoring credit of said closed path is calculated to predict the success of the closed path as a pre-configured cycle; and  
 b) choosing a select number of closed paths based on the scoring credit to be the pre-selected candidate cycles.  
 
     
     
         9 . The telecommunications network of  claim 8  in which the scoring credit is calculated by increasing said scoring credit by a value for each flow within said closed path that is protected by said closed path, increasing said scoring credit by a larger value for each flow not on said closed path that is protected by said closed path, weighting the value provided by each flow according to the traffic along said each flow and the length of each flow, and taking the ratio of said scoring credit with the cost of said closed path.  
     
     
         10 . The telecommunications network of  claim 5  in which a mixed selection strategy is used for pre-selecting candidate cycles.  
     
     
         11 . The telecommunications network of  claim 1  in which establishing the pre-configured cycle comprises recording at a node on a pre-configured cycle an identification of protected flow paths that pass through the node and are protected by the pre-configured cycle.  
     
     
         12 . The telecommunications network of  claim 11  in which protecting a path segment comprises, upon failure of a span in a protected flow path, the node, at which the identification of the protected flow paths is recorded, routing the telecommunications traffic along the pre-configured cycle.  
     
     
         13 . The telecommunications network of  claim 4  where the path segment is part of a path of an express flow through a network region.  
     
     
         14 . The telecommunications network of  claim 4  where the pre-configured cycle is an area boundary flow protecting p-cycle.  
     
     
         15 . A method of operating a telecommunications network, the telecommunications network comprising plural nodes connected by plural spans and arranged to form a mesh network, the method comprising the steps of: 
 establishing at least one pre-configured cycle of spare capacity in the mesh network, the pre-configured cycle including plural nodes of the mesh network; and    configuring the plural nodes of the pre-configured cycle to protect at least one path segment, where the path segment includes at least two intersecting nodes within the pre-configured cycle and at least one intermediate node in a path that includes the two intersecting nodes and straddles the pre-configured cycle.    
     
     
         16 . The method of  claim 15  in which the path segments are segments of a working path with a start node not connected to the pre-configured cycle.  
     
     
         17 . The method of  claim 15  in which the path segments are segments of a working path with an end node not connected to the pre-configured cycle.  
     
     
         18 . The method of  claim 15  in which the pre-configured cycle of spare capacity is provided by: 
 a) identifying all working flows in the mesh network to be restored;  
 b) identifying the spare capacity of the pre-configured cycle to restore all working flows for all spans subject to failure in all path segments;  
 c) providing spare capacity along the pre-configured cycle sufficient to restore all working flows.  
 
     
     
         19 . The method of  claim 15  in which establishing a pre-configured cycle comprises the steps of: 
 pre-selecting a set of candidate cycles for forming into pre-configured cycles;  
 allocating working paths and spare capacity in the mesh network based on the set of candidate cycles; and  
 providing the mesh network with spare capacity arranged in pre-configured cycles according to the allocation determined in the preceding step.  
 
     
     
         20 . The method of  claim 19  in which the allocation of working paths and spare capacity is jointly optimized.  
     
     
         21 . The method of  claim 19  in which pre-selecting candidate cycles includes ranking a set of closed paths in the mesh telecommunications network according to the degree to which each closed path protects spans on and off the closed path, and selecting candidate cycles from the set of closed paths.  
     
     
         22 . The method of  claim 21  in which pre-selecting candidate cycles comprises: 
 a) determining a scoring credit for each closed path in the set of closed paths, where the scoring credit of said closed path is calculated to predict the success of the closed path as a pre-configured cycle; and  
 b) choosing a select number of closed paths based on the scoring credit to be the pre-selected candidate cycles.  
 
     
     
         23 . The method of  claim 22  in which the scoring credit is calculated by increasing said scoring credit by a value for each flow within said closed path that is protected by said closed path, increasing said scoring credit by a larger value for each flow not on said closed path that is protected by said closed path, weighting the value provided by each flow according to the traffic along said each flow and the length of each flow, and taking the ratio of said scoring credit with the cost of said closed path.  
     
     
         24 . The method of  claim 19  in which a mixed selection strategy is used for pre-selecting candidate cycles.  
     
     
         25 . The method of  claim 15  in which establishing the pre-configured cycle comprises recording at a node on a pre-configured cycle an identification of protected flow paths that pass through the node and are protected by the pre-configured cycle.  
     
     
         26 . The method of  claim 25  in which protecting a path segment comprises, upon failure of a span in a protected flow path, the node, at which the identification of the protected flow paths is recorded, routing the telecommunications traffic along the pre-configured cycle.  
     
     
         27 . The method of  claim 18  where the path segment is part of a path of an express flow through a network region.  
     
     
         28 . The method of  claim 18  where the pre-configured cycle is an area boundary flow protecting p-cycle.