Joint Routing and Protection Using p-cycles

Thomas Stidsen, Tommy Thomadsen

AbstractToday people rely heavily on electronic communication systems like the Internet, telephone systems, etc. Hence, it is important to ensure reliable electronic communication. The bulk of the electronic communication today is carried by circuit switched networks, thus protection against failures in these networks is paramount. Protection is possible by rerouting the electronic communication, bypassing the failed network component. In order to be able to reroute, extra capacity is, nevertheless, needed.

This article considers the recently suggested fast protection method, p- cycles. We develop a method for minimizing the capacity needed for protection using p-cycles. The routing of tra c in uence the amount of extra capacity needed, thus we consider joint optimization of routing and protection.

An integer linear programming model is presented and a column generation algorithm is developed. The algorithm is faster and obtains better bounds and solutions than existing methods. The algorithm enables an experimental study of the capacity e ciency of p-cycles. The results show that p-cycles are comparable to any other protection method, with respect to the capacity usage. The results also show that substantial capacity savings can be achieved when routing and protection is performed jointly.

Based on the integer linear programming model, we discuss how protection costs can be taken into account in routing methods. We also discuss an alternative e ciency measure of the p-cycles, which takes into account the interaction with existing p-cycles.
Keywordsnetworks, p-cycles, routing, protection, column-generation
TypeTechnical report
Year2005
PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
AddressRichard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby
SeriesIMM-Technical Report-2005-10
Electronic version(s)[pdf]
BibTeX data [bibtex]
IMM Group(s)Operations Research