The p-Cycle protection scheme is a technique to protect a mesh network from a failure of a link, with the benefits of ring like recovery speed and mesh-like capacity efficiency, similar to that of a shared backup path protection (SBPP). p-Cycle protection was invented in late 1990s, with research and development done mostly by Wayne D. Grover, and D. Stamatelakis.Asthana, R.; Singh, Y.N.; Grover, W.D.; "p-Cycles: An overview," IEEE Communications Surveys and Tutorials, vol.12, no.1, pp.97-111, First Quarter 2010
Overview of the p-Cycle
In Transport communication networks two methods were developed and introduced for restoration and recovery, one was a ring-based protection and the other was mesh restoration.Claus G. Gruber and Dominic A. Schupke.; "Capacity-efficient Planning of Resilient Networks with p-Cycles,". 2002. The ring based protection offered a quick recovery time at the expense of higher capacity redundancy, while the mesh restoration offered better capacity-efficiency at the expense of slower recovery times. In 1998 the p-Cycle became a promising technique for recovery in mesh networks because of the combined benefits of ring network recovery speed and mesh like capacity efficiency. In a mesh network, the spare capacity is used to create the ring like structures as shown in Figure 1. Due to the nature of the rings assuming bi-directional line switched ring (BLSR), only 2 end nodes are involved in a case of a link failure to switch traffic to a pre-planned cycle (path) and recover, as it is demonstrated in Figure 2.
One of the key differences between a ring-based scheme and the p-cycle scheme is the ability of the p-cycle to protect links that are not on the p-cycle ring as shown in Figure 3. The ability to protect two channel for every spare channel that is assigned to the p-cycle allows to achieve mesh-like capacity efficiency. This feature gives the p-cycle the additional efficiency over the ring-based schemes.Kodian, A.; Sack, A.; Grover, W.D.; "p-cycle network design with hop limits and circumference limits," Broadband Networks, 2004. BroadNets 2004. Proceedings. First International Conference on, vol., no., pp. 244- 253, 25-29 Oct. 2004 "Another over looked feature of the p-Cycle is that working paths may be freely routed over the network graph and are not limited to follow the ring-constrained routings".
P-Cycle Types
The p-cycles come in few variations depending on how they protect a given network and their underlying architecture. The types of p-cycles that are available are: Hamiltonian, Simple, Non-Simple, Span, Node encircling, Path, and Flow. The Hamiltonian, Simple, and Non-Simple are named after their underlying architecture (In relationship to the Network). The Span, Node, Path, and Flow p-cycles are named after the type of protection offered to the network.
Hamiltonian – a p-cycle in which the protection path passes through all nodes in a network only once. This p-cycle is illustrated in Figure 4.
Simple – a p-cycle in which the protection path is not required to pass through all the nodes in the network. The p-cycle is allowed to pass through any one node only once shown in Figure 1.
Non-simple – a p-cycle in which the protection path is allowed to pass through any given node more than once. This is shown in Figure 5.
Span p-cycle – a p-cycle whose primary job is to protect spans or links not on the p-cycle itself. This type of p-cycle is shown in Figure 3.
Node encircling – a p-cycle that protects in case of a node failure. In this type, the traffic that used to pass through that node before a failure is rerouted to an adjacent node(s) encircling the failed node, but not through the failed node.
Path protecting p-cycle – a p-cycle that protects a complete path, from source to destination as long as all the nodes are on the p-cycle.
Flow p-cycle – a p-cycle that offers protection for links that are on the p-cycle, the opposite of the Span p-cycle protection scheme.
Designs & Formation of p-cycles
To design p-cycle, a few methods may be used. The two main categories in which the p-cycles are formed are: Centralized or Distributed. Further categorization is based on a number of factors including order of the p-cycle and working demands based on routing. The p-cycles can be created after the working demands are routed in the network or at the same time depending on the needs and requirements. There are a number of papers dealing with the p-cycle design, and the idea that p-cycle networks are based many times on the single Hamiltonian cycle seems to float around. While the idea may be good from management simplicity, it does not mean it is the best possible solution.Onguetou, D.P.; Grover, W.D.; "p-cycle network design: From fewest in number to smallest in size," Design and Reliable Communication Networks, 2007. DRCN 2007. 6th International Workshop on, vol., no., pp.1-8, 7-10 Oct. 2007
Centralized
In the centralized method, the p-cycles can be determined and picked based on the possible candidate cycles from a large eligible set for the design in order to protect all the possible working channels and links. Another way in which the centralized method is used is based on network graphs. This way the p-cycles are chosen from a set of a network graph. For the centralized method, many techniques exist to accomplish the above computations. Some major ones are presented below:
Integer Linear Programming Models
In this model, there are a few techniques that are used for creating acceptable p-cycles in order to protect the network, some of those include:
Spare Capacity Optimization – The objective of this technique is to optimize the capacity used for the creation of the p-cycles (minimize) while insuring that all of the working channels are protected. This method creates p-cycles that protect off-cycle paths or spans. This model is able to provide an acceptable set of p-cycles that guarantees 100% protection in case of a single failure. It is possible to have more constrains to further specify and meet the required design specifications.
Joint Capacity Optimization – In this technique the optimization is extended not only to the spare capacity of the network but to the total capacity of the network. This includes the spare capacity and the working capacity of the network. Another difference is the routing on the working capacity is not done before the p-cycle formation. First a working route option is calculated for each source/destination pair, than from all the possible solutions found, a pair is selected along with the addition of spare capacity taken into consideration to optimize the total capacity of the network. The model for this technique can be found in . Protected Working Capacity Envelope Optimization – This model different from the other 2 models because in this model the p-cycles are found first. There are some considerations when creating the p-cycles based on the idea of optimizing the general volume of the working channels which must be protected. After the p-cycles are found, the working demand is routed on the network within the p-cycle protection domain. This concept is known as protected working capacity envelope (PWCE).
Heuristic Method
The first method of creating p-cycles is computationally intensive when the number of nodes is large.Zhenrong Zhang; Wen-De Zhong; Mukherjee, B.; "A heuristic method for design of survivable WDM networks with p-cycles," IEEE Communications Letters, vol.8, no.7, pp. 467- 469, July 2004 The Heuristic method presented called the ER-based unity-p-cycle, shows an attractive solution to solve the problem with creating p-cycles without the use of ILP. This method also has a solution that is close to that of an optimal solution, but without the extra computational time required. The general idea of the algorithm is to identify unity p-cycles that are able to protect as many working links as possible, this essentially reduces the number of spare units required for protection. A "unit p-cycle is able to protect one working link in opposite direction for every on cycle span and two working units for every straddling span. The number of spare units of a unity-p-cycle is equal to the number of the spans on the cycle." A ratio called ER is defined as the number of working links that are protected by the unity p-cycle to the number of spare units. The higher the ratio the better the efficiency of the protecting p-cycles and hence this is what the algorithm aims for.
The method can be explained as follows as given in is shown here: Based on algorithm in H. Hwang, S. Y. Ahn, Y. H. Yoo, and S. K. Chong, “Multiple shared backup cycles for survivable optical networks,” in Proc. ICCCN’01, Scottsdale, AZ, Oct. 2001, pp. 284–289. Find the possible cycles, and determine the working capacity for each based on one of the shortest path algorithms. Calculate the ratio ER of the unit-cycles for the cycles computed in step 1. Based on the ER calculation select the cycle with the highest ER. Remove the working links that can be protected by the selected cycle from above, and update the working capacity. Repeat the above steps until the working capacity on every span is 0.
Straddling Link Algorithm The Integer Linear Programming (ILP) method for creating p-cycles requires that all possible sets of cycles are found first up to a certain size or circumference of the network. As a result, this method is good for small or medium-sized networks.Doucette, J.; He, D.; Grover, W.D.; Yang, O.; "Algorithmic approaches for efficient enumeration of candidate p-cycles and capacitated p-cycle network design," Design of Reliable Communication Networks, 2003. (DRCN 2003). Proceedings. Fourth International Workshop on, vol., no., pp. 212- 220, 19-22 Oct. 2003 Because as the number of nodes increases, the network graph grows exponentially complicating the problem for ILP and substantially increasing the time required to compute the sets. Therefore, this method is not suitable for large networks and a different method must be used. One solution is a Straddling Link Algorithm (SLA) method. This method is fast and simple to create a set of cycles, but suffers from inefficiency for the overall network design. This is because the algorithm generates p-cycles that have only one straddling span.
The key feature of the SLA is the ability to find the p-cycles quickly. The Algorithm works by finding the shortest path between the nodes of a span, and then find another shortest path between the same set of the nodes that is disjoint from the first route. The p-cycle is than created by combining the previously found two routes into one. The span is able to use the other route as a backup in case of a failure. This formation of p-cycle is called a primary p-cycle. The problem with this method is that most primary p-cycles contain only one straddling span, and therefore are inefficient as compared to other types of constructed p-cycles.
Distributed