Optimization of -Cycle Placement for Differentiated Levels of Protection

This paper develops a new scalable and efficient model for the design of p -cycles with the differentiated levels of node protection. The proposed model allows the indicated level of node survivability ranging from 0% to 100%, which could facilitate a carrier offer node-failure survivability (and hence availability) on a differentiated service basis. To design p -cycles, an integer linear program (ILP) is usually formulated with the prerequisite of a prior enumeration of all possible p -cycle candidates. A huge number of candidates may exist in a large-scale network. Thus, the resulting ILP becomes intractable. We propose a new design and solution method based on large-scale optimization techniques, known as column generation (CG). With CG, our design method generates p -cycle candidates dynamically when needed. Extensive experiments have been conducted for evaluation. The numerical results show that, with the spare capacity used only for link protection, up to 50% node-failure survivability can be achieved for free. Full node protection can be achieved at a marginal cost in comparison with those for link protection only.