A Novel Efficient Design of Node-Protecting p-Cycles in WDM Mesh Networks

The design of p-cycles in WDM mesh networks has been extensively studied. However, most of studies only deal with a single link failure rather than node failure. In this paper, we develop a new scalable and efficient design method for computing node-protecting p-cycles. The performance of our new proposed design method makes an obvious improvement ~20% in capacity redundancy over that of the previous design method. The conventional design methods formulate the problem of p-cycle design as an Integer Linear Program (ILP). To solve the ILP, the prerequisite is to a priori enumerated all possible p-cycle candidates. For a large network, the resulting ILP maybe intractable as the huge number of cycles may exist. We propose a new design and solution method based on large scale optimization tools, namely Column Generation (CG), where p-cycles are generated on-line when needed. The main advantage of our CG-based method is that no p-cycles are a-priori off-line enumerated, the generation of the promising set of p-cycles is embedded in the optimization process. Extensive experiments on several network instances have been conducted for comparison. Experimental results show that our new proposed methods outperforms the previous method in terms of capacity efficiency.