Stochastic Eulerian Lagrangian method

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 discovered 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.

Fig 1. p-Cycle in a mesh network creating ring like structure.

Fig 2. Failure on a p-cycle showing the 2 nodes involved in recovery.

Fig 3. Failure of straddling span and recovery of that link by the p-cycle.

Fig 4. A Hamiltonian p-cycle, the protection path passes through all the nodes in the network only once

Fig 5. A Non-Simple p-cycle, the protection path passes through the blue node more than once.

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 its 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).

Heuristic Method

The first method of creating p-cycles is computationally intensive when the number of nodes is large. 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-cyle 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 [6] is shown here:

1. Based on algorithm in [7] Find the possible cycles, and determine the working capacity for each based on one of the shortest path algorithms.
2. Calculate the ratio ER of the unit-cycles for the cycles computed in step 1.
3. Based on the ER calculation select the cycle with the highest ER.
4. Remove the working links that can be protected by the selected cycle from above, and update the working capacity.
5. 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. 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-cyles quickly. The Algorithm works by finding the shortest path between the nodes of a span, and than 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

The distributed method for creating p-cycles differs from the centralized approach in a number of ways. The major difference being in assumptions made in centralized methods. This assumption is based on the fact that p-cycles are always guaranteed to protect 100% of the working capacity. In other words it is assumed that its always possible to create the p-cycles that are able to protect the working capacity in full. The distributed method deals with logical configuration and assignment of already in-place physical capacities. this means that the distributed method is aimed towards real life operations where the physical links are fixed but logical distinction can be made of how the spare and working capacity can be used and or decided. This method does not always make it possible to be able to protect 100% of the working capacities as there may not be enough of the spare capacity to create the required p-cycles in order protect all of the working links on the network. The distributed method can be done in one of the two ways:

Distributed cycle pre-configuration

This method is a based on rules and concepts adopted from the Selfhealing Network protocol. The idea behind the (DCPC) is as follows: each spare link has a state associated with it called a statelet with a number of states. The node sees each logical link with an incoming state and an outgoing state. The incoming state from the link to the node originates from an adjacent node that is connected by that link. Also each outbound state from a link has an incoming state which forms its precursor. Based on this idea, a number of statelets is sent throughout the network (broadcast) and forms a tree of states. "Each node in the tree, is rooted at the precursor port from which the outgoing statelets are propagated." This is called a state route. There are two node options in the algorithm namely Cycler and the Tandem, each having it specific role. The Cycler is a sender/chooser role, in this mode the Cycler sends and receives parts of a state it initiated. All of the nodes adopt this behavior and this is accomplished in a round-robin scheme. The other role is the Tandem, which works by mediating the state broadcasts competition with new rules and criteria not found in Selfhealing networks. Simply put, each node is allowed to explore the network and discover possible p-cycles. The Tandem role also dictates allowed discovery of p-cycles by the Cycler node type. Based on the DCPC, the p-cycles are self-organized in the spare capacity of the network and are found in a distributed way. The algorithm can be re-run each time a network change occurs to create an optimum use of spare capacity. For more information the reader is encouraged to read [9].

Swarm Intelligence System

This method is based on an intelligent system that is found in nature. Its a distributed method that relies on agents working independently, yet communicating with each other by a means of massages that are left or collected at each node which was visited by that agent. This behavior is similar to that of ants, and so called a p-cycle ant system. The aggregation of the messages left or generated by those ants is the basis of forming p-cycles in the system. This technique has high adaptability and redundancy in the network and as a result optimal solutions are possible.

Efficiency of p-cycles

The efficiency of a p-cycle is based on type of p-cycle in use. The Hamiltonian p-cycle, where the p-cycle passes through all the nodes only once, can be very efficient when the working capacity that is unprotected is able to have all the relationships required by a full Hamiltonian implementation. While the Hamiltonian seems to float around as the choice of p-cycle formation, it is not the only type allowed. In some network configurations a mix of the Hamiltonian p-cycle with other types is required to achieve optimal efficiency in the network design. A study preformed last years showed that an efficient way to create p-cycles can be achieved in mesh networks that are flat. This means that the number of links not on the p-cycle or spans is identical.

A type of network called a homogeneous network, where all of the spans have equal working capacity, showed an efficiency that was not quite optimal in terms of spare to working capacity ratio. This is due to the loss of an ability for a p-cycle to protect more than one straddling span. As an alternative a concept of semi-homogeneous mesh networks was developed. In this type of network the ability of the p-cycle to protect more than one straddling span allowed it to reach an efficiency of

$1/(\overline{d}-1)$

which is a lower limit. Thus it was proven that with the use of Hamiltonian p-cycles in the semi-homogeneous networks, the theoretical efficiency could be reached, but with some exceptions as real network are different and a mix of different p-cycle is required to achieve optimal solutions for a given network topology and design.

Applications

The idea behind p-cycles protection was an ability to offer protection in mesh optical networks by combining the benefits of ring like recovery speed and the efficiency of a mesh network, however the concept is not only limited to transport optical networks and can be extended to higher levels and other network types:

• IP
• WDM
• ASTN
• ASON
• SDH
• MPLS
• SONET
• Segment protection
• Optical Mesh Networks
• Optical Multicast Media Traffic