p2-Cycles: p-Cycles with parasitic protection links

The p-cycle and its Failure Independent Path Protection (FIPP) extension are known to be efficient and agile protection strategies. The p-cycle is pre-configured such that if there is a failure, only the switches at two end nodes need to be reconfigured. In this paper, we extend the p-cycle by allowing cycles to have attached links, called Parasitic Protection Links (PPL), in order to protect paths whose source and destination nodes are not only located on the cycle but also connected by a PPL to the cycle. A p-cycle with PPL is named p2-cycle.We address the unicast service protection problem against single-link failures by using p2-cycle in mesh networks for both static and dynamic traffic scenarios. In the static case, the problem is formulated as an Integer Linear Program (ILP). We further propose two p2-cycle based heuristic algorithms, Strict Routing Protection (SRP) and Flexible Routing Protection (FRP), to address the dynamic traffic case. The numerical results show that the p2-cycle scheme provides better capacity efficiency than the FIPP p-cycle scheme in all the traffic scenarios considered and achieves only less than 1% extra total cost over the optimum in COST239, provided by Shared Backup Path Protection (SBPP) approach when the traffic load is high. We also study the failure recovery performance in terms of average number of switch reconfigurations (NOR), and show that the performance of the p2-cycle becomes much better than that of SBPP and gets close to FIPP as the traffic demand increases. In the dynamic case, both SRP and FRP outperform FIPP p-cycle schemes in terms of blocking probability in most scenarios considered. In general, the p2-cycle protection scheme outperforms the p-cycle based in terms of capacity efficiencies which being slightly slower in terms of traffic recovery speed.