Handbook of Optimization in Telecommunications M.G.C. Resende and P.M. Pardalos (Editors) Springer Science + Business Media, 2006.
Chapter 12
Ring network design
M. Henningsson, K. Holmberg, and D. Yuan
Abstract
Applying traditional methods of network design on modern telecommunication data often results in tree-like structures, due to the high capacities of the current optical fibers. However, the increasing importance of the traffic on telecommunication networks makes the issue of survivability more crucial. It is not acceptable that parts of the network are completely unable to communicate if a single link failure should occur. Therefore telecommunication networks must be designed so that certain survivability requirements are fulfilled. In this chapter we study the case where the survivability requirement is that the network should be composed of connected rings of links. In case of a failure in a ring, the traffic can simply be sent the other way around the ring. We describe a solution approach iteratively generating rings in a meaningful way, as the number of possible rings is very large. A model deciding the optimal usage of a given set of rings and a model generating valid rings are used together, to form a method of column generation-type. We also review work on other types of ring network design problems.
Keywords: Network design, rings, integer programming, column generation, heuristic.