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.

• Nokia Siemens Networks GmbH & Co. KG
• Arie Koster, University of Warwick, UK