Joint Optimization of Working and p-cycle Protection Capacity

Recently, p-cycles were suggested as a way of protecting communication networks from link failures. p-cycle protection is considered a fast protection method similar to rings and 1+1 protection, but achieves capacity efficiency comparable to meshed protection methods. We consider the problem of jointly routing communication channels and protecting links using p-cycles. An integer linear programming model is presented and a column generation algorithm for solving the problem is implemented. This algorithm enables an experimental study of the efficiency of p-cycles. The results show, that p-cycles are significantly more efficient than rings and comparable to any meshed protection method. The results also show that substantial savings can be achieved when routing and protection is performed jointly as compared to when it is not. Based on the integer linear programming model, we discuss how protection costs can be taken into account in routing methods. We also we discuss an alternative efficiency measure of the p-cycles, which takes into account the interplay with existing p-cycles.