# A Generic Multi-layer Network Optimization Model with Demand Uncertainty

Uwe Steglich, Thomas Bauschert, Christina Büsing, Manuel Kutschka

► To cite this version:

Uwe Steglich, Thomas Bauschert, Christina Büsing, Manuel Kutschka. A Generic Multi-layer Network Optimization Model with Demand Uncertainty. 19th Open European Summer School (EUNICE), Aug 2013, Chemnitz, Germany. pp.13-24, 10.1007/978-3-642-40552-5_2. hal-01497029

HAL Id: hal-01497029

https://inria.hal.science/hal-01497029

Submitted on 28 Mar 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Generic Multi-layer Network Optimization Model with Demand Uncertainty

Uwe Steglich¹, Thomas Bauschert¹, Christina Büsing², and Manuel Kutschka³

¹ Chair for Communication Networks, Chemnitz University of Technology, D-09107 Chemnitz, Germany
{uwe.steglich,thomas.bauschert}@etit.tu-chemnitz.de

² Lehrstuhl für Operations Research, RWTH Aachen University, D-52062 Aachen, Germany
buesing@or.rwth-aachen.de

³ Lehrstuhl II für Mathematik, RWTH Aachen University, D-52062 Aachen, Germany
kutschka@math2.rwth-aachen.de

**Abstract.** In this work we introduce a mixed integer linear program (MILP) for multi-layer networks with demand uncertainty. The goal is to minimize the overall network equipment costs containing basic node costs and interface costs while guarding against variations of the traffic demand. Multi-layer network design requires technological feasible inter-layer connections. We present and evaluate two layering configurations, *top-bottom* and *variable*. The first layering configuration utilizes all layers allowing shortcuts and the second enables layer-skipping. Technical capabilities like *router-offloading* and layers able to *multiplex* traffic demand are also included in the model. Several case studies are carried out applying the *Γ*-robustness concept to take into account the demand uncertainties. We investigate the dependency of the robustness parameter *Γ* on the overall costs and possible cost savings by enabling *layer-skipping*.

**Keywords:** network, design, multi-layer, uncertainty, robustness

## 1 Introduction and Motivation

Today's telecommunication networks utilize different technologies for transporting multiple services like voice calls, web-content, television and business services. The traffic transported in networks is steadily increasing and operators have to extend their network capacities and migrate to new technologies. In the competitive market operators want to reduce overall network costs as much as possible. The nature of multi-layer networks allows a wide range of technological possibilities for transporting traffic through its layers. Evaluating all technological feasible interconnections provides a great potential in capital expenditures (CAPEX) savings. Also operational expenditures (OPEX) reductions are possible due to the different energy consumption of the network equipment of each layer.
The traffic demand influences network planning fundamentally. Conservative traffic assumptions lead to over provisioning and underestimated traffic values to a congested network. To strike a balance between these two extremes, concepts of uncertain demand modeling can be applied. The simplest way is to allocate a safety gap to the given traffic demand values. More sophisticated concepts are the Γ-robust approach by Bertsimas and Sim [1, 2] and the hose model approach by Duffield et al. [3]. Other formulations use stochastic programming, chance-constraints or a network design with several traffic matrices. Appropriate uncertainty models incorporate statistical insight of available historical data e.g. mean and peak demand values.

A further network planning challenge is the determination which technologies should be used in a multi-layered network. Multi-layer networks offer a high flexibility regarding the possibility of traffic offloading. Note that, it is not necessary that all nodes support all technologies.

Investigations about single-layer networks with uncertainty were performed for example by Koster et al. in [4] or by Orlowski in [5]. They focus on a logical (demand) layer and one physical layer. Multi-layer network models without demand uncertainty were proposed for example by Katib in [6] or Palkopoulou in [7]. The former deals with a strict layer structure of Internet Protocol/Multi-protocol Label Switching (IP MPLS) over Optical Transport Network (OTN) over Dense Wavelength-Division Multiplex (DWDM) and the latter evaluates the influence of multi-homing in a multi-layer networking scenario. A multi-layer network model with uncertainty was suggested in [8] by Belotti et al. The authors apply the Γ-robust optimization approach for a two-layer network scenario (MPLS, OTN) with demand uncertainty. In [9] Kubilinskas et al. propose three formulations for designing robust two-layer networks.

In this paper we deal with the following problem: Determine a cost optimal multi-layer network design allowing technology selection at each node and incorporating traffic demand uncertainty. Compared to other formulations, our proposed MILP formulation yields full flexibility regarding the number of layers and integrates layer-skipping and router offloading.

The paper is structured as follows: In Sect. 2 we shortly describe the relevant layers in today's communication networks. We present a generic multi-layer network optimization model and include traffic uncertainty constraints. Section 3 describes the input data used in the case studies: network topologies, traffic demand data, path sets and cost figures. The results of the multi-layer network optimization with demand uncertainty are presented in Sect. 4. Section 5 concludes the paper and gives an outlook on our future work.

## 2 Optimization Model

Generally, core networks may comprise the following technological layers: IP layer, MPLS layer, OTN layer and DWDM layer. With MPLS, network operators can establish explicit paths independently from the IP routing. OTN is specified in ITU-T G.709 [10] and defines optical network elements enabling transport,
switching and multiplexing of client signals. OTN introduces different Optical Transport Units (OTU) which serve as optical channel wrapper for Optical Data Units (ODU) in several granularities. Beyond OTN the optical multiplexing of different wavelengths onto one single fiber is realized by DWDM technology.

The traffic demand and its fluctuation can be treated as a further, logical layer. Thus, in our investigations we deal with five different layers.

A generic multi-layer network model was proposed in [7] to evaluate different homing architectures. We apply some modifications to this model and extend it to cope with traffic demand uncertainty.

Given is a set of layers $\mathcal{L}$ and for all $\ell \in \mathcal{L}$ an undirected graph with node set $\mathcal{N}_{\ell}$ and edges $\mathcal{E}_{\ell}$. A path set $\mathcal{P}_{\ell,j}$ with candidate paths is introduced for each layer $\ell \in \mathcal{L}$ and all commodities $j$. The interaction of two layers is also modeled by an edge. In the set $I_{\ell,n}$ different basic node types per layer $\ell \in \mathcal{L}$ and per node $n \in \mathcal{N}_{\ell}$ are specified. We define $\delta_{\ell}(n)$ to be the set of neighboring nodes of node $n$ in layer $\ell$.

We define the notation of layer sets as follows: $\mathcal{L}_{\ell}$ specifies the set containing all layers below the current layer $\ell$. With $\mathcal{L}^{\ell}$ the set of layers above the current layer $\ell$ is indicated. We denote the highest, logical layer (DEMAND) with $\ell_{max}$ and the lowest, physical layer (DWDM) with $\ell_0$. Layers with subinterfaces are contained in $\mathcal{L}_{sub}$.

The notation for the flow-variables $x_{i,ii,iii,iv}$ is as follows: $i$ is the source layer, $ii$ the destination layer, $iii$ the commodity or edge and $iv$ the candidate path. The demand parameter $\alpha_{\ell,e}$ specifies the nominal value and $\hat{\alpha}_{\ell,e}$ the deviation value (difference between peak and nominal) of all demands between a node pair $j/edge e$ in layer $\ell$.

## 2.1 Approach for Uncertainty

Traffic demand uncertainty is introduced in a general way. Fluctuations are described through the variables $\beta_{\ell,e}$ for all layers $\ell \in \mathcal{L}$ and edges $e \in \mathcal{E}_{\ell}$. As uncertainty can be handled in different ways this allows us a universal formulation for these uncertainty variables. The uncertain traffic demand is transported in fractions across different layers.

We apply edge-based flow conservation. The constraints (1) describe the flow conservation including the uncertainty. On the left hand side all demands from higher layers except the highest layer are summed up and have to be less or equal to the sum of all outgoing demands on the right hand side. The multiplexing factor $\mu_{s,\ell}$ converts capacity granularities between the source $s$ and current layer $\ell$. Variables $x_{s,\ell,j,p}$ contain the amount of traffic flowing in and $x_{\ell,s,e,p}$ out of the current layer. With $\beta_{\ell,e}$ we increase the amount of incoming demand by the uncertain demand. Via parameters $\alpha_{\ell,e}$ direct demand on a certain edge $e$ in a layer $\ell$ is allowed.
$$ \sum_{\substack{s \in \mathcal{L}^{\ell} \setminus \{\ell_{\max}\}, \\ j \in \mathcal{E}_s, p \in \mathcal{P}_{\ell,j}: e \in p}} \mu_{s,\ell} x_{s,\ell,j,p} + \alpha_{\ell,e} + \beta_{\ell,e} \le \sum_{\substack{s \in \mathcal{L}_{\ell}, \\ p \in \mathcal{P}_{s,e}}} x_{\ell,s,e,p} \quad \forall \ell \in \mathcal{L} \setminus \{\ell_0\}, \forall e \in \mathcal{E}_{\ell}. \qquad (1) $$

We decided to use the Γ-robust approach by Bertsimas and Sim [1, 2] where the fluctuation variables $\beta_{\ell,e}$ contain the worst case demand variation. New supplementary flow variables $\bar{x}$ are introduced. Uncertain flows start from layer $\ell_{\max}$ and terminate at a subset of lower layers. This holds true for all paths $p$ in layer $\ell$ and for all commodities $j$. The formulation (2) explains the concept of Γ-robustness. The binary variables $v_{j,p}$ are relaxed to $0 \le v_{j,p} \le 1$ and are used to select at most $\Gamma$ fractional demands to be on their peak value. The maximization ensures that these $\Gamma$ uncertain demand fractions are chosen which have the largest influence on the necessary edge capacity.

$$ \begin{array}{ll} \text{maximize} & \displaystyle \sum_{\substack{j \in \mathcal{E}_s, \\ p \in \mathcal{P}_{\ell,j}: e \in p}} \hat{a}_j \bar{x}_{s,\ell,j,p} v_{j,p} \\ \text{s.t.} & \displaystyle \sum_{j \in \mathcal{E}_s} v_{j,p} \le \Gamma \\ & 0 \le v_{j,p} \le 1 \\ & \forall s \in \mathcal{L}, \forall e \in \mathcal{E}_{\ell}, \forall \ell \in \mathcal{L}_{\ell_{\max}} \end{array} \qquad (2) $$

As proposed in [1, 8] this linear program can be dualized. The dual problem (DP) of the optimization problem in (2) is shown in (3). Compared to (2) the new dual variables $\vartheta_{\ell,e}$ and $\pi_{\ell,e,j,p}$ are introduced.

$$ \begin{array}{ll} \text{minimize} & \Gamma \vartheta_{\ell,e} + \sum_{\substack{j \in \mathcal{E}_s, \\ p \in \mathcal{P}_{\ell,j}: e \in p}} \pi_{\ell,e,j,p} \\ \text{s.t.} & \vartheta_{\ell,e} + \pi_{\ell,e,j,p} \ge \hat{a}_j \bar{x}_{s,\ell,j,p} \\ & \vartheta_{\ell,e}, \pi_{\ell,e,j,p} \ge 0 \\ & \forall s \in \mathcal{L}, \forall e \in \mathcal{E}_{\ell}, \forall \ell \in \mathcal{L}_{\ell_{\max}} \end{array} \qquad (3) $$

We use the DP to limit the lower bound of $\beta_{\ell,e}$ in our multi-layer network optimization model with uncertainty as shown in constraints (4) and (5).

$$ \Gamma \vartheta_{\ell,e} + \sum_{\substack{j \in \mathcal{E}_s, \\ p \in \mathcal{P}_{\ell,j}: e \in p}} \pi_{\ell,e,j,p} \le \beta_{\ell,e} \quad \forall \ell \in \mathcal{L} \setminus \mathcal{L}_0, \forall e \in \mathcal{E}_{\ell} \qquad (4) $$

$$ \vartheta_{\ell,e} + \pi_{\ell,e,j,p} \ge \mu_{\ell_{\max},\ell} \hat{\alpha}_j \bar{x}_{\ell_{\max},\ell,j,p} \quad \forall j \in \mathcal{E}_{\ell_{\max}}, \forall p \in \mathcal{P}_{\ell,j}: e \in p \qquad (5) $$

By constraints (6) the sum of all fractions of uncertain demand $\bar{x}$ are enforced to be one.
$$ \sum_{\substack{\ell \in \mathcal{L} \\ p \in \mathcal{P}_{\ell,j}}} \bar{x}_{\ell_{\max}, \ell, j, p} = 1 \quad \forall j \in \mathcal{E}_{\ell_{\max}} \qquad (6) $$

Uncertainty also has to be applied to the inter-layer node capacities. The number of access interfaces h between the layers is influenced by the additional demand entering this specific layer. We introduce new constraints for the lower bound of access interfaces originating in the highest layer into all other layers. The Γ-robustness is introduced by additional dual variables $\nu_{\ell,n}$ and $\lambda_{\ell,n,j,p}$ and reused fractional variables $\bar{x}$. These extensions are shown in constraints (7) and (8).

$$ \Gamma \nu_{\ell,n} + \sum_{\substack{j \in \delta_{\ell}(n), \\ p \in \mathcal{P}_{\ell,j}}} \lambda_{\ell,n,j,p} \le h_{\ell_{\max},\ell,n} \quad \forall \ell \in \mathcal{L} \setminus \{\ell_{\max}\}, \forall n \in \mathcal{N}_{\ell_{\max}} \qquad (7) $$

$$ \nu_{\ell,n} + \lambda_{\ell,n,j,p} \ge \eta_{\ell_{\max},\ell} \hat{\alpha}_j \bar{x}_{\ell_{\max},\ell,j,p} \quad \forall \ell \in \mathcal{L} \setminus \{\ell_{\max}\}, \forall n \in \mathcal{N}_{\ell_{\max}}, \forall j \in \delta_{\ell}(n), \forall p \in \mathcal{P}_{\ell,j} \qquad (8) $$

With (1) and (4) to (8) all requirements for handling traffic demand uncertainty in the generic multi-layer network optimization model are specified.

## 2.2 MILP with Uncertainty Extension

The objective (9) is to minimize the overall costs in all layers $\ell \in \mathcal{L}$. Costs are induced by all basic nodes $k_\ell$ and deployed interfaces $y_\ell$ (access and network interfaces) in each layer $\ell$.

$$ \text{minimize} \quad \sum_{\ell \in \mathcal{L}} (k_{\ell} + y_{\ell}) \qquad (9) $$

For the intra-layer demand the needed number of network interfaces $z_{\ell,e}$ are calculated by summing up all demands for all commodities in this layer — see constraints (10).

$$ \sum_{\substack{j \in \mathcal{E}_{\ell}, \\ p \in \mathcal{P}_{\ell,j}: e \in p}} x_{\ell, \ell, j, p} \le z_{\ell, e} \quad \forall \ell \in \mathcal{L}, \forall e \in \mathcal{E}_{\ell} \qquad (10) $$

The inter-layer node capacities for all demands not originating in the highest layer have to fulfill the constraints (11).

$$ \sum_{\substack{j \in \delta_{\ell}(n), \\ p \in \mathcal{P}_{\ell,j}}} \eta_{s, \ell} x_{s, \ell, j, p} \le h_{s, \ell, n} \quad \forall \ell \in \mathcal{L} \setminus \{\ell_{\max}\}, \forall s \in \mathcal{L}^{\ell} \setminus \{\ell_{\max}\}, \forall n \in \mathcal{N}_s \qquad (11) $$

Edges from and a specific node might be used and thereby require installation of network interfaces. For cost calculation the number of installed network
interfaces at a node is needed. This is formulated in constraints (12). $z_{\ell,e}$ contains the number of network interfaces on edge $e$ and $w_{\ell,n}$ the number of network interfaces at node $n$ of layer $\ell$.

$$ \sum_{e \in \delta_{\ell}(n)} z_{\ell,e} \le w_{\ell,n} \quad \forall \ell \in \mathcal{L}, \forall n \in \mathcal{N}_{\ell} \quad (12) $$

Some layers have a maximum demand limit per edge. This restriction is modeled in constraints (13) using parameter $\gamma_{\ell,e}$.

$$ z_{\ell,e} \le \gamma_{\ell,e} \quad \forall \ell \in \mathcal{L}, \forall e \in \mathcal{E}_{\ell} \quad (13) $$

For the node capacity constraints we have to distinguish between layers with and without subinterfaces. In both cases the node capacity is determined by the number of network interfaces $w_{\ell,n}$ and the access interfaces $h_{s,\ell,n}$ into this layer $\ell$. In case of subinterfaces a conversion factor $\eta_{s,\ell}$ is used. This is shown in constraints (14) and (15).

$$ w_{\ell,n} + \sum_{s \in \mathcal{L}^{\ell}} h_{s,\ell,n} \le q_{\ell,n} \quad \forall \ell \in \mathcal{L} \setminus \mathcal{L}_{\text{sub}}, \forall n \in \mathcal{N}_{\ell} \quad (14) $$

$$ w_{\ell,n} + \sum_{s \in \mathcal{L}^{\ell}} \eta_{s,\ell} h_{s,\ell,n} \le q_{\ell,n} \quad \forall \ell \in \mathcal{L}_{\text{sub}}, \forall n \in \mathcal{N}_{\ell} \quad (15) $$

Finally, in constraints (16), the costs are calculated based on the number of interfaces deployed in all nodes. The parameters $\varphi_{\ell}$ for basic nodes in layer $\ell$ and $\chi_{s,\ell}$ for access interfaces between layer $s$ and $\ell$ are input parameters from the applied cost model.

$$ \sum_{n \in \mathcal{N}_{\ell}} \varphi_{\ell} w_{\ell,n} + \sum_{\substack{s \in \mathcal{L}^{\ell} \\ n \in \mathcal{N}_{\ell}}} \chi_{s,\ell} h_{s,\ell,n} \le y_{\ell} \quad \forall \ell \in \mathcal{L} \quad (16) $$

The parameter $\psi_{\ell,d}$ represents the basic node costs depending on the basic node size $d$ and layer $\ell$. A binary decision variable $r_{\ell,d,n}$ is used to decide whether this node type is used. The overall costs of all basic nodes $k_{\ell}$ in a specific layer $\ell$ are derived by applying constraints (17).

$$ \sum_{\substack{n \in \mathcal{N}_{\ell} \\ d \in I_{\ell,n}}} \psi_{\ell,d} r_{\ell,d,n} \le k_{\ell} \quad \forall \ell \in \mathcal{L} \quad (17) $$

The maximum number of interfaces of a node is specified by the basic node type and its capacity. Constraints (18) give an upper bound for the total number of deployed interfaces $q_{\ell,n}$.

$$ q_{\ell,n} \le \sum_{d \in I_{\ell,n}} dr_{\ell,d,n} \quad \forall \ell \in \mathcal{L}, \forall n \in \mathcal{N}_{\ell} \quad (18) $$

We restrict the installation of basic nodes at a location to exactly one type. This is enforced by constraints (19).
$$ \sum_{d \in I_{\ell,n}} r_{\ell,d,n} \le 1 \quad \forall \ell \in \mathcal{L}, \forall n \in \mathcal{N}_{\ell} \qquad (19) $$

All bounds and limitations of the optimization variables are listed in (20).

$$ \begin{array}{ll} k_{\ell}, y_{\ell} \ge 0 & \forall \ell \in \mathcal{L} \\ x_{s,\ell,j,p} \ge 0 & \forall \ell \in \mathcal{L}, \forall s \in \mathcal{L}, \forall j \in \mathcal{E}_s, \forall p \in \mathcal{P}_{s,j} \\ \bar{x}_{\ell_{\max},\ell,j,p} \ge 0 & \forall \ell_{\max} \in \mathcal{L}_{\max}, \forall \ell \in \mathcal{L}, \forall j \in \mathcal{E}_{\ell}, \forall p \in \mathcal{P}_{\ell,j} \\ z_{\ell,e} \in \mathbb{Z}^{+} & \forall \ell \in \mathcal{L}, \forall e \in \mathcal{E}_{\ell} \\ h_{s,\ell,n} \in \mathbb{Z}^{+} & \forall \ell \in \mathcal{L}, \forall s \in \mathcal{L}^{\ell}, \forall n \in \mathcal{N}_{\ell} \\ w_{\ell,n} \ge 0 & \forall \ell \in \mathcal{L}, \forall n \in \mathcal{N}_{\ell} \\ q_{\ell,n} \in \mathbb{Z}^{+} & \forall \ell \in \mathcal{L}, \forall n \in \mathcal{N}_{\ell} \\ r_{\ell,d,n} \in \{0,1\} & \forall \ell \in \mathcal{L}, \forall n \in \mathcal{N}_{\ell}, \forall d \in I_{\ell,n} \\ \vartheta_{\ell,e}, \pi_{\ell,e,j,p} \ge 0 & \forall \ell \in \mathcal{L}, \forall j \in \mathcal{E}_{\ell_{\max}}, \forall p \in \mathcal{P}_{\ell,j} : e \in p \\ \nu_{\ell,n}, \lambda_{\ell,n,j,p} \ge 0 & \forall \ell \in \mathcal{L} \setminus \{\ell_{\max}\}, \forall n \in \mathcal{N}_{\ell_{\max}}, \forall j \in \delta_{\ell}(n), \forall p \in \mathcal{P}_{\ell,j} \end{array} \qquad (20) $$

## 2.3 MILP Size Estimation

In order to compare the complexity of the non-robust model with the model that includes Γ-robustness, we perform an estimation of the model sizes. In the following n is the number of nodes in all layers and p the overall number of paths in all layers.

The order of the number of variables increases from $n^2$ to $n^2p$ and the order of the created number of constraints increases from $n^2p$ to $n^4p$ for the model with uncertainty. This is caused by the dual variables and the required constraints for modeling the uncertainty in flow conservation and inter-layer node capacity.

The MILP size is a critical point in terms of computation time and optimality gap. A possible reduction of the model size can be achieved by merging layers, decreasing the set of candidate paths in selected layers and by omitting nodes in specific layers.

# 3 Input Data for the Case Studies

## 3.1 Example Network Topologies

It is assumed that all layers comprise the same node set. First of all, we define an artificial, small-scale 5-node network topology. It contains nodes A to E, bidirectional edges (A, B), (A, D), (A, E), (B, C), (C, D), (C, E) and has an average nodal degree of 2.40. Furthermore, we use the Abilene and Géant topologies from SNDlib [11]. Abilene is a reference for a mid-scale network containing 12 nodes (avg. nodal degree 2.50) and Géant is a large-scale network with 22 nodes (avg. nodal degree 3.27).
<table><caption>**Table 1.** Layer mapping configurations *top-bottom* and *variable*</caption><thead><tr><th>configuration</th><th>layer <i>l</i></th><th><i>L</i><sup><i>l</i></sup></th><th><i>L</i><sub><i>l</i></sub></th></tr></thead><tbody><tr><td rowspan="6">variable</td><td>DEMAND</td><td>Ø</td><td>IP</td></tr><tr><td>IP</td><td>DEMAND</td><td>MPLS, OTN, DWDM</td></tr><tr><td>MPLS</td><td>IP</td><td>OTN, DWDM</td></tr><tr><td>OTN</td><td>IP, MPLS</td><td>DWDM</td></tr><tr><td>DWDM</td><td>IP, MPLS, OTN</td><td>Ø</td></tr><tr><td>DEMAND</td><td>Ø</td><td>IP</td></tr><tr><td rowspan="4">top-bottom</td><td>IP</td><td>DEMAND</td><td>MPLS</td></tr><tr><td>MPLS</td><td>IP</td><td>OTN</td></tr><tr><td>OTN</td><td>MPLS</td><td>DWDM</td></tr><tr><td>DWDM</td><td>OTN</td><td>Ø</td></tr></tbody></table>

## 3.2 Traffic Demand

For the 5-node network we assume nominal demand values of $\alpha = 20$ GBit/s for all end-to-end node pairs. Overall 10 demand pairs exist in this network. The deviation of the demand values are assumed to be $\hat{\alpha} = 0.5 \cdot \alpha$ for node pairs $(A, B)$, $(A, D)$ and to be $\hat{\alpha} = 0.25 \cdot \alpha$ for the other node pairs.

For Abilene and Géant traffic measurement traces can be found in SNDlib [11]. We use the first week measurements and set $\alpha$ to the nominal value and $\hat{\alpha}$ to the maximum minus the nominal value. In total Abilene has 66 and Géant 462 demand pairs.

## 3.3 Network Layers

In our case studies we consider five network layers: One logical layer DEMAND and four technological layers IP, MPLS, OTN and DWDM. However, the MILP theoretically supports an unlimited number of layers.

In Table 1 technologically feasible mappings between the layers are shown. We distinguish between *variable* and *top-bottom* configuration. The top-bottom configuration is a worst case scenario in terms of overall costs as all layers have to be used by all demands. The variable configuration enables a technology selection by skipping some of the layers.

For our calculations it is assumed that all layers have a interface granularity of 40 GBit/s except the logical demand layer which has a granularity of 1 GBit/s.

## 3.4 Cost Model

We only consider CAPEX costs for our case studies. In [12] by Huelsermann et al. a CAPEX cost model for multi-layer networks is provided where the costs are separated into three main parts:
1. Basic node costs: chassis, power supplies, cooling, etc.

2. Interface costs: interfaces placed within one layer $ℓ$

3. Access interface costs: interfaces from a layer $s$ to a layer $ℓ$

All costs are normalized to the costs of a single 10G long-haul transponder and without any reference to a specific vendor. Basic node costs depend on the number of available slots. For IP and MPLS 16, 32, 48 and 64 slots with corresponding costs of 16.67, 111.67, 140.83 and 170.0 are distinguished. The costs for IP and MPLS equipment are assumed to be equal.

## 3.5 Path Sets

In the DWDM layer $k$-shortest paths are calculated choosing $k = 5$ for small-to mid-scale and $k = 2$ for large-scale networks. The DWDM-paths are modified and extended to provide path sets for the higher layers.

In [7] different bypassing options *Unrestricted*, *Restricted*, *Opaque* and *Transparent* were proposed. These options create different candidate paths for an end-to-end connection within a single layer. We apply the *Restricted*, *Opaque* and *Transparent* option for non-DWDM path sets. In addition to the $k$-shortest paths (*Opaque*) also the direct connection between source and destination exists (*Transparent*, bypassing at all intermediate nodes). Further paths are introduced by the *Restricted* option where specific nodes are skipped after a specific node hop count is exceeded. By use of these path sets we allow, that specific nodes might be skipped and traffic is offloaded. We assume a fully meshed graph in the logical DEMAND layer.

## 4 Results

In this section we present the results of our case studies. The main target is to evaluate whether our multi-layer network optimization model with uncertainty is solvable for realistic problem sizes applying off-the-shelf solvers.

For our calculations we use a conventional PC with multi-core CPU (Intel® Core™ i7-3930K CPU @ 3.20GHz) and 64 GBytes of memory. Operating system is Ubuntu in version 11.04. AMPL is used in version 20111121 and IBM® ILOG® CPLEX® in version 12.5. For the MIP gap tolerance the CPLEX default value of $1e-4$ is used and the time limit is set to 86400s (1 day).

In [13] was shown that choosing $\Gamma$ to about 6% of the number of demands is already sufficient to provide total robustness. Therefore, we perform a parameter study regarding $\Gamma$ and increase it from 0 (no uncertainty) up to 10 (at most ten demands on peak value). With the *top-bottom* configuration the overall real-time for the 5-node network is 124.2s (user runtime 1264.6s). As can be seen from Fig. 1 increasing $\Gamma$ rises the CAPEX costs up to 23% and influences mainly the DWDM layer. The reason is that the traffic demand is in the range of 50% of the interface capacities. Already two demands on nominal value utilize the interfaces completely. The course of the curve for the *variable* configuration
is similar, except that the MPLS and OTN layers are skipped. The cheapest
solution is to apply IP-over-DWDM in this case. The calculation time for *variable*
configuration is slightly smaller compared to *top-bottom* with a real-runtime of
73.6s (user-runtime 672.9s). CAPEX increases by 25.6% when Γ is varied from
0 to 10.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** CAPEX costs versus Γ uncertainty parameter for the 5-node network with *top-bottom* configuration</figcaption></figure>

In case of the *variable* configuration the optimization results for Abilene
and Géant are different compared to the 5-node network: the OTN layer is not
skipped. The computing times and memory requirements increase substantially.
For Abilene the computing time increases to a real-runtime of 218999.3s (user-
runtime 1835679.0s) and for Géant to a real-runtime of 39625.0s (user-runtime
401265.4). The reason why Géant has a lower runtime is that only a set of k = 2
shortest paths are used compared to k = 5 for Abilene. If we use k = 5 also for
Géant, CPLEX terminates with a out of memory exception.

In Fig. 2, for the Géant network a strong dependency on the parameter Γ can be observed. Already the step from no uncertainty to Γ = 1 raises CAPEX by 70.4%. For Γ = 10 a CAPEX increase of 117.2% is discovered.

The cost of the Abilene network does not change when introducing uncer-
tainty. Independently from Γ the CAPEX costs are 1537.04 for the IP layer,
117.05 for the OTN layer and 86.76 for the DWDM layer. The MPLS layer is
skipped. For none of the Abilene-runs the optimality gap was reached. Probably
the reason is that the traffic demands do not match well to the granularity of the
interface capacities yielding sufficient spare capacity to accommodate the traffic
fluctuations. It is planned to perform further investigations on this issue.

For both topologies (Abilene, Géant) the MPLS layer is skipped, but the
OTN layer is used for grooming IP demands. This behavior is correct as the cost
parameters of IP and MPLS are assumed to be equal.
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** CAPEX costs versus $\Gamma$ uncertainty parameter for the Géant network with *variable* configuration</figcaption></figure>

# 5 Conclusion and Outlook

We introduced a generic multi-layer network optimization model with traffic uncertainty applying the $\Gamma$-robust approach. The model has full flexibility regarding the number of layers. Path sets are calculated with the special bypassing options *Unrestricted*, *Restricted* and *Opaque* or *Transparent*. These options allow router offloading and shortcuts for selected layers. Two possible layer mapping configurations *top-bottom* and *variable* are considered. The former yields a worst-case solution for passing all layers with shortcuts and the latter a cost minimal solution with shortcuts and layer-skipping.

We evaluated the MILP for different network sizes. Compared to the non-robust model the computing time for the robust model increases significantly. When using off-the-shelf solvers especially in mid- and large-scale networks today computational power is still not sufficient to solve the problem to an optimality gap of $1e-4$. Hence, more advanced mathematical techniques for modeling and solving are needed.

By decreasing the size of the path sets for specific layers and the optimality gap for the multi-layer network model with uncertainty even large-scale networks remain solvable. Computing times are reasonable but the solver requires very large memory for improving the initial solution. Also modeling alternatives should be investigated for their potential to decrease the memory consumption for larger networks.

In our future work we will investigate several options to improve scalability and memory consumptions. We will analyze how different robustness metrics are influenced by the $\Gamma$ parameter setting. Furthermore, we will continue our studies with an improved cost model allowing more realistic comparisons of the MPLS and the OTN layer options.
**Acknowledgments.** This work was supported by the German Federal Ministry of Education and Research (BMBF) via the research project ROBUKOM [14].

**References**

1. Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Mathematical Programming **95**(1) (2003) 3–51

2. Bertsimas, D., Sim, M.: The price of robustness. Operations research **52**(1) (2004) 35–53

3. Duffield, N.G., Goyal, P., Greenberg, A., Mishra, P., Ramakrishnan, K.K., van der Merive, J.E.: A flexible model for resource management in virtual private networks. SIGCOMM Comput. Commun. Rev. **29**(4) (1999) 95–108

4. Koster, A.M.C.A., Kutschka, M., Raack, C.: Robust network design: Formulations, valid inequalities, and computations. Networks **61** (2013) 128–149

5. Orlowski, S.: Optimal design of survivable multi-layer telecommunication networks. PhD thesis, Technische Universität Berlin (2009)

6. Katib, I.A.: IP/MPLS over OTN over DWDM multilayer networks: Optimization models, algorithms, and analyses. PhD thesis, University of Missouri (2011)

7. Palkopoulou, E.: Homing Architectures in Multi-Layer Networks: Cost Optimization and Performance Analysis. PhD thesis, Chemnitz University of Technology (2012)

8. Belotti, P., Kompella, K., Noronha, L.: A comparison of OTN and MPLS networks under traffic uncertainty. IEEE/ACM Transactions on Networking (2011)

9. Kubilinskas, E., Nilsson, P., Pioro, M.: Design models for robust multi-layer next generation Internet core networks carrying elastic traffic. Journal of Network and Systems Management **13**(1) (2005) 57–76

10. Telecommunication Standardization Sector of ITU: ITU-T Recommendation G.709: Interfaces for the optical transport network. International Telecommunication Union (2009)

11. Orlowski, S., Wessäly, R., Pióro, M., Tomaszewski, A.: SNDlib 1.0—survivable network design library. Networks **55**(3) (May 2010) 276–286

12. Huelsermann, R., Gunkel, M., Meusburger, C., Schupke, D.A.: Cost modeling and evaluation of capital expenditures in optical multilayer networks. Journal of Optical Networking **7**(9) (2008) 814–833

13. Koster, A.M.C.A., Kutschka, M., Raack, C.: Towards robust network design using integer linear programming techniques. In: Next Generation Internet (NGI), 2010 6th EURO-NF Conference on, IEEE (2010) 1–8

14. Koster, A.M.C.A., Helmberg, C., Bley, A., Grötschel, M., Bauschert, T.: BMBF project ROBUKOM: Robust communication networks. In: Euro View 2012, Berlin · Offenbach, VDE-Verlag (2012)