Matheon-B3: Integrierte Planung von Multi-layer Telekommunikationsnetzen
Moderne Telekommunikationsnetze bestehen aus technologisch unterschiedlichen Teilnetzen, sogenannten Schichten (layer), zwischen denen eine Client-Server Beziehung besteht: Jede Schicht ist in eine andere Schicht eingebettet, wobei Verbindungen der Client-Schicht durch Pfade in der Server-Schich realisiert werden. So können beispielsweise Verbindungen in Internet (IP) Kernnetzen durch Lichtwege in darunter liegenden optischen Fasernetzen, sogenannten DWDM-Netzen, realisiert werden. In diesem Projekt entwickeln wir mathematische Modelle und Algorithmen, welche die gleichzeitige Planung mehrere Netzschichten erlauben. Aufgrund des außerordentlichen Potentials zur Kosten- und Energieersparnis sind solche integrierten Planungsansätze von steigender Bedeutung für Netzbetreiber.
Wir verfolgen in diesem Projekt zwei Ziele: Auf der einen Seite wollen wir realistische Modelle und geeignete Algorithmen entwickeln, die in der Praxis zur Netzplanung eingesetzt werden können. Hier arbeiten wir eng mit verschiedenen Netzbetreibern und Telekommunikationsunternehmen zusammen. Auf der anderen Seite wollen wir die mathematische Struktur der Planungsprobleme untersuchen und verstehen, um bessere Aussagen über die Qualität von Lösungen machen zu können sowie existierende Lösungsmethoden zu verbessern.
Our network planning problems can be roughly described as follows:
Given are a planning topology consisting of potential nodes and links, a set of installable link capacities on all layers, installable hardware at the nodes, and communication demands with routing and survivability constraints. A network is feasible if all installed hardware components and link capacities fit together, and if all communication demands can be routed without exceeding the installed capacities even in all considered failure scenarios. The objective is to find a feasible network with minimal total installation cost.
In multi-layer planning problems, the routing is nested: upper layer (logical) links are implemented by paths in a lower (physical) layer whose links may again be realized in another layer. This makes multi-layer planning problems extremely hard to solve. First, it leads to a possibly exponential number of logical links on which integer capacities have to be installed, and second, physical node or link failures may induce multiple link failures at the logical layer.
Achievements (since 2006)
We have developed integrated mixed-integer programming (MIP) models for designing two-layer transport networks subject to many practically relevant side constraints. Examples of such constraints are:
- several available bit-rates,
- different types of node equipment,
- network survivability (multiple virtual failures), and
- a realistic hardware cost-model.
Due to the high individual complexity, a combination of all these constraints has not been considered before. In all previous models from the literature, either important side constraints have been left out, or the set of feasible solutions was heavily restricted in order to solve realistic instances.
Based on our models, we have developed an optimization software which implements a branch-and-cut-and-price algorithm enhanced by a variety of problem-specific methods. These methods allow to compute solutions with a quality guarantee for realistic networks and planning scenarios. Among others, we developed the following plug-ins, most of them based on new theoretical insights on the mathematical structure of multi-layer planning problems:
- preprocessing and model reductions which preserve optimality,
- primal (MIP-based) heuristics,
- problem specific (multi-layer) cutting planes, and
- column generation to create routing variables dynamically.
We have applied these methods in a funded cooperation with Nokia Siemens Networks (NSN). Compared to the state-of-the-art MIP solvers SCIP and CPLEX, we could significantly reduce optimality gaps and computation times on realistic planning scenarios provided by NSN. On a German 17-node Internet backbone instance we reduced the computation time by a factor of 20, from more than half a day to 45 minutes. Our methods allow us to compute feasible network configurations and to assess their quality using non-trivial lower bounds on the optimal network cost even for large, dense two-layer networks with 50-70 nodes and survivability requirements, which has not been possible before and which is unique at the international level. With a state-of-the-art MIP solver, even solving the LP relaxation is out of question for such large instances.
Our results have been published for instance in Orlowski et al. , Koster et al. [2008, 2009], Orlowski , Raack and Koster , Raack et al. ,. The model mentioned above has also been successfully used within the project Eibone (see Bley et al. ).
With various partners, we were also working on several activities which are related to this project and have partly emerged from it:
- In multi-layer networks, the failure of a single node or physical link causes all traversing logical links to fail at the same time. Such multiple link failures are difficult to handle both from a practical and an algorithmic point of view. Together with Michal Pióro from Warsaw University of Technology, we have investigated the complexity of column generation in the presence of multiple link failures. We could show that with any realistic rerouting mechanism proposed in the network design literature, the problem of finding improving path-flow variables with multiple failures is NP-hard (see Orlowski and Pióro ).
- In cooperation with Michal Pióro and with the help of many other contributors from universities and network operators, we have set up the Survivable Network Design Library (SNDlib), a library of benchmarking problems for survivable telecommunication network planning (see Orlowski, Pióro, Tomaszewski, and Wessäly ).
Current and Future Activities
Our current research focuses on the following three crucial aspects of multi-layer network design:
- Energy efficiency
Survivability: Solving large multi-layer networks with survivability requirements is still extremely hard and requires instance-specific techniques. Further theoretical and algorithmic research is necessary in order to better understand the structural difficulties and to design more stable algorithms. To improve dual bounds and methods, we have already started to develop multi-layer cutting planes (see Raack and Koster , and Müller ), and to prove their computational benefit. We also aim to investigate suitable relaxations and models of the planning problems that better scale with the network size.
Robustness: Together with Arie Koster from University of Aachen (RWTH) we work on the design of networks that are robust with respect to changing network traffic. End-user demands behave strongly dynamic in practice, especially in the IP domain. We try to extend our models and approaches to incorporate uncertainty of demand matrices.
Energy efficiency: In recent years energy efficiency has become a key factor for network operators when deciding about network architectures and topologies. In a cooperation with the TU Berlin we are estimating the potential of saving energy in IP-over-DWDM networks when allowing node equipment to switch to a standby mode depending on the traffic state.
Multi-layer core and metro networks: In the third funding period we aim to work on the integrated design of multi-layer core and metro networks. The latter bridge the area between the core backbone network and user access by concentrating and aggregating traffic. Such an integrated design includes multi-layer capacity and routing planning with different technologies (e.g., Ethernet/IP/DWDM) and survivability requirements as well as hierarchy planning, that is, deciding which nodes become backbone or metro nodes, where to aggregate traffic, and how to connect metro to backbone networks. The integrated planning of backbone and metro networks in a single-layer context has been considered in this project during the first funding period, whereas the multi-layer aspects are being studied now. Consequently, the integration of both topics is not only of major practical importance but also a natural extension of our previous work.
- F. Idzikowski, S. Orlowski, C. Raack, H. Woesner, A. Wolisz. Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios . Technical Report ZR-10-07, ZIB, May 2010, submitted to IEEE Communications Magazine.
- Tobias Achterberg, Christian Raack. The MCF-Separator – Detecting and Exploiting Multi-Commodity Flows in MIPs . Submitted to Mathematical Programming C, , 2010.
- Christian Raack, Arie M. C. A. Koster, Roland Wessaely. On cut-based inequalities for capacitated network design polyhedra . Networks, (to appear), 2010.
- S. Orlowski. Optimal Design of Survivable Multi-layer Telecommunication Networks . PhD Thesis, TU Berlin, May 2009.
- S. Orlowski, M. Pióro. On the complexity of column generation in survivable network design with path-based survivability concepts . Technical Report ZR-08-51, ZIB, December 2008. Short version published at the 4th International Network Optimization Conference (INOC 2009), Pisa, Italy, April 2009.
- A.M.C.A. Koster, C. Raack. A packing integer program arising in two-layer network design . In: Proceedings of the 4th International Network Optimization Conference (INOC 2009), Pisa, Italy, April 2009. Matheon preprint 646.
- A. Bley, U. Menne, R. Klaehne, C. Raack, R. Wessäly. Multi-layer network design – A model-based optimization approach . In: Proceedings of the 5th Polish-German Teletraffic Symposium 2008, pp. 107–116, Berlin, Germany, 2008. Matheon preprint 645.
- A. Bley, B. Fortz, E. Gourdin, K. Holmberg, O. Klopfenstein, M. Pióro, A. Tomaszewski, H. Ümit. Optimization of OSPF Routing in IP Networks . In: Graphs and Algorithms in Communication Networks, A.M.C.A. Koster and X. Munoz (Eds.), Springer-Verlag, chapter 8, 2009. To appear.
- J. Müller. Facets of the cutset polyhedron of 2-layer survivable network design problems . Master's Thesis, TU Berlin, December 2008.
- A.M.C.A. Koster, S. Orlowski, C. Raack, G. Baier, T. Engel, P. Belotti. Branch-and-cut techniques for solving realistic two-layer network design problems . In: Graphs and Algorithms in Communication Networks, A.M.C.A. Koster and X. Munoz (Eds.), Springer-Verlag, chapter 4, 2009. To appear.
- 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., chapter 1, 2008.
- A. Bley. Routing and Capacity Optimization for IP Networks . In: Proceedings of Operations Research 2007, Saarbrücken, Germany, pp. 9–16, 2007.
- A. Bley. Routing and Capacity Optimization for IP Networks . PhD Thesis, TU Berlin, 2007.
- S. Orlowski, A.M.C.A. Koster, C. Raack, R. Wessäly. Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics . In: Proceedings of the Third International Network Optimization Conference (INOC 2007), Spa, Belgium, April 2007.
- C. Raack, A.M.C.A. Koster, S. Orlowski, R. Wessäly. Capacitated network design using general flow-cutset inequalities . In: Proceedings of the Third International Network Optimization Conference (INOC 2007), Spa, Belgium, April 2007.
- S. Orlowski, M. Pióro, A. Tomaszewski, R. Wessäly. SNDlib 1.0–Survivable Network Design Library . Technical Report ZR-07-15, ZIB, 2007. Accepted for Networks. A short version appeared in the INOC 2007 proceedings.
- A. Bley, T. Koch. Integer Programming Approaches to Access and Backbone IP-Network Planning . In: Proceedings of 3rd International Conference on High Performance Scientific Computing, Hanoi, Vietnam, 2006.
- S. Orlowski, R. Wessäly. The Effect of Hop Limits on Optimal Cost in Survivable Network Design . In: Telecommunications Planning: Innovations in Pricing, Network Design and Management, S. Raghavan and G. Anandalingam (Eds.), volume 33 of Operations Research/Computer Science Interfaces, pp. 151–166, Springer-Verlag, chapter 8, January 2006.
- S. Orlowski, R. Wessäly. Survivable Logical Network Design with an Underlying Physical Layer . Technical Report 300, DFG Research Center Matheon, December 2005.
- S. Orlowski, R. Wessäly. An Integer Programming Model for Multi-Layer Network Design . Technical Report ZR-04-49, Konrad-Zuse-Zentrum für Informationstechnik Berlin, December 2004.
- A. Bley. A Lagrangian Approach for Integrated Network Design and Routing in IP Networks . In: Proceedings of International Network Optimization Conference (INOC 2003), pp. 107–113, Evry/Paris, October 2003.
- A. Bley, M. Pattloch. Modellierung und Optimierung der X-WiN Plattform . DFN-Mitteilungen, (67):4–7, 2005.
- T. Koch, R. Wessäly. Hierarchical Infrastructure Planning in Telecommunication Networks . In: Proceedings of INFRATRAIN Autumn School "Network Economics – Modeling and Regulating Transport and Energy Sectors in Europe", 2004.
- A. Bley, A. Zymolka. Planung kostenoptimaler Informations- und Kommunikations-Infrastrukturen . In: Proceedings of 8th Kasseler Symposium Energie-Systemtechnik: Energie und Kommunikation, Kassel, November 2003.
07/2002 - 05/2014