Optimization of p-Cycle Placement for Differentiated Levels of Protection

Abstract EN

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.