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.
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. 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. "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.
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 [1]. 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).
… excerpt ends here. Continue reading the full article.
