Metaheuristic approaches for IP/MPLS network design

• Author: Claudio Risso,Sergio Nesmachnow,Franco Robledo
• Published date: 01 March 2018
• DOI: http://doi.org/10.1111/itor.12418
• Date: 01 March 2018

Intl. Trans. in Op. Res. 25 (2018) 599–625

DOI: 10.1111/itor.12418

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Metaheuristic approaches for IP/MPLS network design

Claudio Risso, Sergio Nesmachnow and Franco Robledo

Facultad de Ingenier´

ıa, Universidad de la Rep´

ublica, J.H. y Reissig 565, Montevideo, 11300, Uruguay

E-mail: crisso@fing.edu.uy [Risso]; sergion@fing.edu.uy [Nesmachnow]; frobledo@fing.edu.uy [Robledo]

Received 14 July2016; received in revised form 13 January 2017; accepted 24 March 2017

Abstract

This work introduces metaheuristic approaches for designing resilient and cost-effective multiprotocol label

switching (MPLS) networks, a technology that is gaining prominent importance since most of the global

data traffic is Internet traffic, and most internet protocol (IP) traffic within service provider backbones is

being supported upon the IP/MPLS technology. Our approach is innovative because it integrates an overlay

network design problem with the effective usage of traffic-engineering featuresof this technology. Due to the

resulting complexity and a high level of technologicaldetail, we decided to use metaheuristics to find solutions

to prospective scenarios for two real-world applications. The best results were achieved using evolutionary

algorithms and GRASP (Greedy Randomized Adaptive Search Procedure). The relative improvements for

some of these scenarios are outstanding and reveal how using the protection mechanisms provided by newer

technologies may advance efficiency standards more than legacy protection schemas.

Keywords:optimization; network design; metaheuristics; resiliency; traffic engineering

1. Introduction

The optimal design of networks is a classical family within combinatorial optimization prob-

lems (Kerivin and Mahjoub, 2005). Single-layer network design problems, where control variables

are solely associated with the presence of edges between nodes or their correspondingcapacities, are

usual for early stages of infrastructure development. However, a new generation of services aims at

minimizing capital expenditures and getting the highest revenues from existing assets,so engineering

focuses on reusing the most of the legacy infrastructure. Such is the case of the telecommunications

industry, where optical fiber, formerly used to interconnect the multiplexers of digital voice circuits,

are evolving to support connections between nodes that move large Internet traffic.

Real-world telecommunications networks are structured into layers: subterranean/submarine

conduits are used to channelize optical fibers, over which optical transport networks are de-

ployed (Koster and Orlowski, 2008; Oellrich, 2008). Internet traffic flows over Internet proto-

col/multiprotocol label switching (IP/MPLS) networks whose nodes are linked by high-speed

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

600 C. Risso et al. / Intl. Trans. in Op. Res. 25 (2018) 599–625

optical connections (Kan and Narula, 2009; Ruiz and Pedrola, 2011). An overlay network is a logi-

cal network where the connections between nodes are actually implemented as services of another

network, referred to as physical. A network design problem that integrates at least one overlay is

multilayered. Therefore, telecommunication networks are intrinsically multilayered.

This work addresses the problem of designing a resilient and cost-effective multilayer network:

an IP/MPLS overlay to be deployed over an existing optical network. There are many alternatives

to implement protection upon IP/MPLS networks. Protection schemes and models are intrinsically

related. A classic optical network supports cuts in optical fibers based on the idea of reserving

physically independent spare connections. This scheme protects the logical links themselves and

dramatically reduces the design complexity of the logical layer. Such simplicity comes at the price

of inefficiency. This work explores native IP/MPLS protection over real-world scenarios in order

to get conclusions about how to use the IP/MPLS technology efficiently.

The main contributions the research reported in this work are (a) a unified model to cover

two extreme alternatives to implement protection based on standard features of the IP/MPLS

technology,(b) a complementary real-world application case—the network of Uruguayan academic

institutions—from which we explore further instances and design constraints, and (c) practical

examples where the spread of cost between manual constructions and those coming from the

optimization process are about 40%, a figure that could not have been achieved applying the

premises used in other approaches.

The document is organized as follows. Section 2 introduces the problem formulation. The tech-

niques applied to solve the problem are presented in Section 3, just before describing the proposed

algorithms in Section 4. The experimental evaluation is reported in Section 5. Finally, Section 6

presents the conclusions and the main lines for future work.

2. Problem formulation

2.1. Definition

An overlay network is a logical network where the connections between nodes are deployed as

services of another network (the physical network). By GP=(VP,P)and GL=(VL,L), we denote

the physical and logical levels, respectively. Figure 1 illustrates a potential solution to the problem

over a simple instance.In this solution, the logical link between V1 and V3 is deployed over physical

links (V1,V4) and (V4,V3). This path is called the lightpath of the logical link. The design of an

overlay network requires defining these lightpaths, that is, requires an application ρ:L→G+

Pto

map each logical link to a path over the physical graph. For simplicity, we assume V=VP=VL.

Our problem also considers the capacity to assign to each logical link, defined by ¯

b:L→{0}∪ ˆ

B,

where ˆ

Bis the set of capacities to assign to each logical link (0 represents that the logical link is not

used). Hence, the physicalimplementation of GLis given by (¯

b,ρ),whereρis defined for every in L

such that ¯

b() > 0. Conversely, we denote by ρ−1:P→P(L)to the function that given a physical

link, preturns the set of logical links that use pin its lightpath, that is, ∈ρ−1(p)iff p∈ρ().

Data networks arebuilt to offer connectivity, so we assume a knownset of traffic demands among

nodes. Let D=((dpq)) be the matrix of positive demands between each pair of nodes. We assume

that the traffic volume is symmetric (dpq =dqp), in line with real-world applications, since optical

backbone networks only provide symmetrical connections.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies