Design of survivable WDM networks using pre-configured protection structures with unrestricted shapes

We propose a novel protection approach for the design of link-protection schemes in survivable Wavelength Division Multiplexing mesh networks by merging the well-known p-cycle- and p-tree-protection structures. So doing, we aim at gathering the advantages of p-cycles in terms of protection capabilities, and of p-trees in terms of protection flexibilities (local re-routing, scalability) in a single protection scheme. As opposed to existing protection schemes based on protection structures with a pre-defined shape, the building blocks of the new scheme are protection structures with unrestricted shapes. Thus, they allow more flexibility in provisioning spare capacity, and provide higher capacity efficiency when compared to the shaped-protection schemes that have been proposed so far. In order to cope with the size of the solution space which includes all the possible protection structures, we propose an efficient and scalable optimization technique in large-scale systems named column generation (CG). In our CG-based optimization approach, the shape of a candidate protection structure is dynamically decided during the optimization process according to a link spare capacity budget. Experimental results on different network instances show that the protection plan resulting from the merging of p-cycle and p-tree structures is, on average, ~15% less capacity redundant and ~15% more reliable than the pure p-cycle one. It also requires, on average, ~30% less protection structures. In addition, those structures provide backup paths ~30% smaller than those of the p-cycle-based scheme.