ZIB-Logo
KONRAD-ZUSE-ZENTRUM
FÜR INFORMATIONSTECHNIK
BERLIN
Home » Forschung » Diskrete Mathematik » Optimierung » Telekommunikation

Matheon-B3: Integrierte Planung von Multi-layer Telekommunikationsnetzen

Projektbeschreibung

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.


Network Design

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. [2007], Koster et al. [2008, 2009], Orlowski [2009], Raack and Koster [2009], Raack et al. [2010],. The model mentioned above has also been successfully used within the project Eibone (see Bley et al. [2008]).


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 [2008]).
  • 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 [2007]).


Current and Future Activities

Our current research focuses on the following three crucial aspects of multi-layer network design:


  • Survivability
  • Robustness
  • 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 [2009], and Müller [2008]), 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.


Publications


Duration

07/2002 - 05/2014