The structure of fixed telecommunication networks currently undergoes significant changes. More and more applications/services (e-mail, video, fixed and mobile phone telephony,...) are realised using a logical IP/MPLS routing layer on top of a physical optical transport layer. Network operators have to design their networks in an efficient way such as to satisfy customers' demands with high quality at reasonable cost.
The design of a two-layer network consists of planning a topology for both layers, dimensioning hardware (e.g., routers and cross-connects) and link capacities, and routing communication demands. Also survivability constraints have to be respected in the planning process in order to account for cable cuts or equipment failures. Due to the lack of better planning methods, the two layers have usually been planned one after the other in the past, although there are strong interdepencies between them. The existing mathematical models for an integrated planning of both layers are very hard to solve to optimality using conventional solution approaches. In a first phase (at the time with Siemens), this project aimed at enhancing existing models and algorithms by multi-layer aspects in order to reduce computation times. This goal was achieved by using advanced model reduction techniques and by adapting established cutting planes known from single-layer network planning to the multi-layer context. In a second phase (now with Nokia Siemens Networks), the goal was to extend the solution methods to large-scale two-layer networks with 50-70 nodes and survivability constraints. For such large planning instances, it is out of question to just apply a black-box mixed-integer programming solver because of the huge linear programs and the enormous computation times. We have developed problem-specific enhancements to a branch-and-cut-and-price approach to compute feasible network configurations with a quality guarantee.
Algorithms for two-layer network design
A well-established approach to solve network design problems is the use of a branch-and-cut algorithm. This generic approach for solving mixed-integer programs can be enhanced by problem-specific plugins, like cutting planes making use of the network structure, or primal heuristics which compute feasible solutions based on information known from the specific planning problem. During the last 15 years, several cutting planes have been developed for single-layer network design. Within this project, various types of cutting planes have been adapted to the multi-layer context. Using these extensions and advanced model reduction techniques, we could reduce computation times on practical network planning instances with 15-20 nodes from one day to a few hours (see Koster et al, 2008). The developed algorithms are now in use at Nokia Siemens Networks.
Large networks with a survivable routing, however, are still extremely hard to solve. Single node or link failures at the physical layer lead to multiple failures at the logical layer, and the size of the resulting mixed-integer programming formulations make it impossible to use a black-box MIP solver. In a second phase, we have thus developed a variety of problem-specific enhancements to a branch-and-cut algorithm that exploit the underlying network structure. These enhancements combine known results from linear and integer programming and from single-layer network design which have been adapted to multi-layer networks in this project. For example, we have extended the cutting planes mentioned above in a way such that they take the inter-layer survivability constraints into account. Column generation allows us to apply linear and integer programming techniques even to large networks with 50 or more nodes. Primal solutions are computed by heuristics which solve a restriction of the original problem as a sub-MIP within the branch-and-cut tree.
As a result, we can compute feasible network configurations even for large two-layer networks with 50-70 nodes and survivability constraints, and we can compute useful lower bounds on the optimal network cost to assess the quality of these solutions. This was not possible at the beginning of this project. Nevertheless, solving such huge problems is still hard. To reduce the computation times, more knowledge of the underlying polyhedral structure is required, and special combinatorial multi-layer algorithms for important subproblems are needed. These issues are further investigated in the project B3: Integrated Planning of Multi-layer Networks.
Publications
- A.M.C.A. Koster, S. Orlowski, C. Raack, G. Baier, T. Engel. Single-layer Cuts for Multi-layer Network Design Problems. In: Telecommunications Modeling, Policy and Technology, B. Golden and S. Raghavan and E. Wasil (Eds.), pp. 1–24, Springer, College Park, MD, U.S.A., 2008. Selected proceedings 9th INFORMS Telecommunications Conference.
