p-Cycles have been extensively studied under a single link failure scenario. Even though not as common, single node failures may occur as well, and the resulting consequences can be devastating. Failure-Independent Path-Protecting (FIPP) p-cycles provide end-to-end path protection, and thereby protection against node failures, assuming that precautions are taken.
In this paper, we propose enhanced p-cycles, called node p-cycles, different from the FIPP p-cycle scheme, which can guarantee 100% protection against a single node failure. We design a scalable optimization model in order to design node p-cycles, which relies on a column generation formulation.
Extensive comparative experiments have been conducted after designing a column generation framework for all compared protection schemes, in order to guarantee scalable models for each of them. Experiments include (link) p-cycles, node p-cycles, FIPP p-cycles and a node p-cycle model previously proposed by Onguetou and Grover (2009). We show that node p-cycles offering node and link protection only require slightly more spare capacity than link p-cycles, while requiring sometimes less, sometimes more spare capacity than FIPP p-cycles. For the comparison with the work of Grover and Onguetou (2009), results show that our new node p-cycle scheme clearly outperforms their design in terms of capacity efficiency.
Paru en juin 2012 , 30 pages