Vol. 73, n° 1-2, January-February 2018
Content available on Springerlink
Guest editors
Eric Gourdin, Orange, France
Deep Medhi, University of Missouri Kansas-City, USA
Achille Pattavina, Politecnico di Milano, Italy
Editorial
Design of Reliable Communication Networks
Eric Gourdin, Deep Medhi, Achille Pattavina
k-node-disjoint hop-constrained survivable networks: polyhedral analysis and branch and cut
1, 2,3, 2, 4
(1) Normandie Univ, UNIHAVRE, LMAH, FR-CNRS-3335, Le Havre, France
(2) PSL, CNRS UMR 7243 LAMSADE, Université Paris-Dauphine, Paris, France
(3) Faculté des Sciences de Tunis, URAPOP, Université Tunis El Manar, Tunis, Tunisia
(4) Department of Industrial Engineering, Bilkent University, Ankara, Turkey
Abstract Given a graph with weights on the edges, a set of origin and destination pairs of nodes, and two integers L ≥ 2 and k ≥ 2, the k-node-disjoint hop-constrained network design problem is to find a minimum weight subgraph of G such that between every origin and destination there exist at least k node-disjoint paths of length at most L. In this paper, we consider this problem from a polyhedral point of view. We propose an integer linear programming formulation for the problem for L ∈{2,3} and arbitrary k, and investigate the associated polytope. We introduce new valid inequalities for the problem for L ∈{2,3,4}, and give necessary and sufficient conditions for these inequalities to be facet defining. We also devise separation algorithms for these inequalities. Using these results, we propose a branch-and-cut algorithm for solving the problem for both L = 3 and L = 4 along with some computational results.
Keywords k-node-disjoint hop-constrained paths, Survivable network, Polytope, Valid inequalities, Facets, Separation, Branch-and-cut
The 2 edge-disjoint 3-paths polyhedron
1, Bernard Fortz2,3, Luis Gouveia4
(1) Louvain School of Management, Université Catholique de Louvain, Louvain-la-Neuve, Belgium
(2) Computer Science Department, Université Libre de Bruxelles, Bruxelles, Belgium
(3) INOCS, INRIA Lille Nord-Europe, Lille, France
(4) Departamento de Estatística e Investigação Operacional, Faculdade de Ciências da Universidade de Lisboa, Lisboa, Portugal
Abstract Given an undirected graph, we study the problem of finding K edge-disjoint paths, each one containing at most L edges, between a given pair of nodes. We focus on the case of K = 2and L = 3. For this particular case, previous known compact formulations are valid only for the case with non-negative edge costs. We provide the first compact linear description that is also valid for general edge costs. We describe new valid inequalities that are added to a well known extended formulation in a layered graph, to get a full description of the polyhedron for K = 2and L = 3. We use a reduction of the problem to a size-2 stable set problem to prove this second property.
Keywords Network design, Survivability, Hop constraints, Combinatorial optimization
Mixed integer optimization for the combined capacitated facility location-routing problem
Dimitri Papadimitriou1, Didier Colle2, Piet Demeester2
(1) Nokia Bell Labs, Antwerp, Belgium
(2) Ghent University, Gent, Belgium
Abstract This paper combines the multi-product variant of the capacitated facility location problem with multicommodity flow routing. This problem shares many similarities with the digital content placement and retrieval problem when minimizing the cost of installing a set of servers for storing multiple sets of data objects (files) and connecting clients to them in order to satisfy their demands while accounting for the induced arc load. However, the regular formulation of the facility location problem models the cost of allocating the demand originated by individual clients independently of the others. The combination of this problem with flow routing removes the demand allocation independence property, leading to strongly interrelated facility location and routing decisions. Moreover, involving multiple types of data objects yields facility capacity constraints with a more complex structure than the simple superposition of per-product constraints. This paper proposes a mixed integer programming formulation for this combined problem and evaluate the computational performance for solving it. Experimental results obtained with this combined formulation are provided and compared with those obtained when solving these two problems sequentially. With the latter, the routing cost increases (up to doubling) or the facility installation cost increases (up to requiring more than twice the number of facilities) compared to the cost values obtained by solving the combined problem. This paper also extends the combined model with demand rerouting to evaluate its cost gain compared to demand protection as provided by the reliable facility location model. The results obtained with the combined formulation indicate that when subject to representative failure probabilities, demand rerouting can significantly outperform demand protection up to a factor four.
Keywords Mixed integer programming, Capacitated facility location, Flow routing
Exploring the logical layer to support differentiated resilience classes in multilayer networks
1, 1, Teresa Gomes2
(1) Graduate Telecommunications and Networking Program, School of Computing and Information, University of Pittsburgh, Pittsburgh, USA
(2) Department of Electrical and Computer Engineering, University of Coimbra / INESC Coimbra, Coimbra, Portugal
Abstract The concept of providing differentiated classes of resilient services over communications networks has received attention in the literature. A number of proposals tried to address the problem by provisioning different resilience classes of service with various protection schemes. However, most of these works are applied to a single layer and lack cross-layer coordination in multilayer scenarios. In addition, there is an increasing need for supporting services with very high resilience requirements over future communications networks. In this paper, we utilize the spine concept idea of embedding a subnetwork at the physical layer with comparatively high availability link and node values (Gomes et al. 2014; Alashaikh et al. Comput Netw 82:4–19 2015), to provide a foundation for resilience differentiation between multiple classes of flows. Cross-layer mapping and spine-aware routing are performed in a way that transfers the spine differentiation capability to the upper layer network and flows. We provide joint routing-mapping optimization formulations with different protection configurations and evaluate their performance in a multilayer scenario. Furthermore, we compare providing protection at the lower layer versus protection at the upper layer in terms of QoR class availability differentiation and resource requirements.
Keywords Cross-layer mapping, Differentiated services, Flow availability
Power reduction strategies with differentiated quality of protection in IP-over-WDM networks
Ali Hmaiti1, Francesco Musumeci1, Massimo Tornatore1
(1) Department of Electronics, Information and Bioengineering, Politecnico di Milano, Milan, Italy
Abstract This work considers two important aspects of modern communication networks, network survivability, and energy efficiency. Survivability is a design requirement to provide failure recovery against network outages such as fiber cuts. To ensure survivability, traditionally, spare network (i.e., backup) resources are reserved in case of failures of primary (i.e., working) network resources. On the other hand, energy efficiency is required to cope with the continuous growth of the Internet traffic. Backup resources increase the energy consumption, especially if constantly powered-on. Hence, a trade-off between energy efficiency and network resiliency arises. To increase transport capacity and reduce energy consumption, wavelength division multiplexed (WDM) networks are adopted as the most practical solution for data transport in core networks, which are the focus of our work. In WDM networks, different levels of protection (i.e., dedicated, shared) can be implemented for different traffic demands, and different protection levels are characterized by different power consumptions. We consider a differentiated quality of protection (Diff-QoP) scheme where different levels of protection are provided. In this context, we investigate on two different power-reduction strategies to be used in protected WDM networks: (i) setting backup devices into low-power modes (sleep mode) and (ii) adapting the devices (i.e., transmitting/receiving equipment) usage to hourly traffic variations. We present exact modeling through Integer Linear Program (ILP) of the three scenarios and a provisioning algorithm to solve the problem of power minimized design of resilient optical core networks, under static and dynamic traffic conditions. We evaluate the performance of the proposed algorithm under static traffic conditions by comparing the obtained results with the optimal solution, in absence of traffic grooming. We show that the proposed heuristic reduces the computational time by three orders of magnitude with an optimality gap ranging from 8.88 up to 23.88%. Furthermore, we include traffic grooming and solve the problem under dynamic traffic conditions. Our findings show that enabling sleep mode (SM) for backup devices can help reduce total power consumption up to 20 and up to 38% when considering with Diff-QoP. Finally, adapting the number of transmitting/receiving devices to actual traffic needs guarantees power savings up to 80%, especially during off-peak hours.
Keywords Differentiated quality-of-protection, Reliable optical core networks, Dynamic provisioning, Resiliency
Assessing the risk of complex ICT systems
1, 2, 3,4, Nancy Perrot4, Jean-Philippe Wary4
(1) Thales Group, Paris, France
(2) PSL Research University, CNRS, LAMSADE, université Paris-Dauphine, Paris, France
(3) Université Paris-Dauphine, Paris, France
(4) Orange Labs, Paris, France
Abstract ICT systems are becoming increasingly complex and dynamic. They mostly include a large number of heterogeneous and interconnected assets (both physically and logically), which may be in turn exposed to multiple security flaws and vulnerabilities. Moreover, dynamicity is becoming paramount in modern ICT systems, since new assets and device configurations may be constantly added, updated, and removed from the system, leading to new security flaws that were not even existing at design time. From a risk assessment perspective, this adds new challenges to the defenders, as they are required to maintain risks within an acceptable range, while the system itself may be constantly evolving, sometimes in an unpredictable way. This paper introduces a new risk assessment framework that is aimed to address these specific challenges and that advances the state of the art along two distinct directions. First, we introduce the risk assessment graphs (RAGs), which provide a model and formalism that enable to characterize the system and its encountered risks. Nodes in the RAG represent each asset and its associated vulnerability, while edges represent the risk propagation between two adjacent nodes. Risk propagations in the graph are determined through two different metrics, namely the accessibility and potentiality, both formulated as a function of time and respectively capture the topology of the system and its risk exposure, as well as the way they evolve over time. Second, we introduce a quantitative risk assessment approach that leverages the RAGs in order to compute all possible attack paths in the system and to further infer their induced risks. Our approach achieves both flexibility and generality requirements and applies to a wide set of applications. In this paper, we demonstrate its usage in the context of a software-defined networking (SDN) testbed, and we conduct multiple experiments to evaluate the efficiency and scalability of our solution.
Keywords Risk assessment, Graph theory, Complex ICT systems
Provisioning dynamic and critical demand structures for geographically correlated failures
1, Yufei Cheng2, Cory Beard1, James P. G. Sterbenz3,4, Deep Medhi1
(1) Department of Computer Science and Electrical Engineering, University of Missouri, Kansas City, USA
(2) Amazon Technologies, Seattle, USA
(3) Department of Electrical Engineering & Computer Science and Information & Telecommunication Technology Center, The University of Kansas, Lawrence, USA
(4) School of Computing and Communications, Lancaster University, Lancaster, UK
Abstract During disasters and other geographically correlated failures, the local telecommunications infrastructure undergoes a unique set of challenges. First, the telecommunications infrastructure is typically damaged reducing the capability to sustain the normal level of demands on the networks. Second, the demands on the telecommunications infrastructure increase typically by an order of magnitude. This is both for critical demands and non-critical demands. Third, critical demands, which may now be used to support disaster first responder and recovery efforts take on a crucial role. In this work, we propose multi-situational linear programming techniques to create disaster modes that take advantage of the non-coincidence of disasters in different geographic areas simultaneously reducing cost and improving restoration of demands during disasters. We also propose efficient heuristics to provision for disasters at a lower cost than standard provisioning with 1 + 1 redundancy. Additionally, we use diverse routing techniques to reduce the likelihood of damage to critical services. The restoration of demands during disasters also presents challenges for network provisioners. We present both heuristic and linear programming methods to assist with restoration of services in stressed network environments giving critical demands priority. Finally, service level agreements (SLAs) are used to provide a framework for these concepts.
Keywords Traffic engineering, Disaster planning, Mission critical networks
Emergency optical network planning with multi-vendor interconnection and portable EDFAs
1, 2, Masaki Shiraiwa1, Takehiro Tsuritani2, Hiroaki Harai1, Yoshinari Awaji1, Naoya Wada1
(1) NICT, 4-2-1, Nukui-Kitamachi Koganei, Tokyo, Japan
(2) KDDI Reasearch Inc., 2-1-15 Ohara Fujimino-shi, Saitama, Japan
Abstract In this paper, we introduce an emergency optical network design problem for the low-cost post-disaster recovery of core optical transport networks. We take into account both the interconnection of the surviving multi-vendor resources and the utilization of portable emergency erbium-doped fiber amplifiers (EDFAs). The surviving multi-vendor optical nodes (e.g., reconfigurable optical add/drop multiplexer (ROADM) or wavelength cross-connect (WXC) nodes) and fiber links are the available resources during a disaster recovery and should be efficiently utilized first. The portable EDFAs are emergency resources added to replace the optical nodes that have either been destroyed or are down because of power outages. To solve this design problem, we propose an emergency network planning method using an integer linear programming (ILP) formulation such that the locations for the emergency interconnection of the multi-vendor networks and placement of the portable EDFAs are optimally selected. Evaluations show the benefits of the multi-vendor interconnection approach and utilization of emergency portable EDFAs.
Keywords Multi-vendor, Interconnection, Emergency optical networks, Planning, Emergency portable EDFA, Disaster recovery
Geo-aware erasure coding for high-performance erasure-coded storage clusters
1, 1, Udaya Parampalli1, Aaron Harwood1
(1) Department of Computing and Information Systems, University of Melbourne, Parkville, Australia
Abstract Erasure code-based distributed storage systems are increasingly being used by storage providers for big data storage since they offer the same reliability as replication with a significant decrease in the amount of storage required. But, when it comes to a storage system with data nodes spread across a very large geographical area, the node’s recovery performance is affected by various factors that are both network and computation related. In this paper, we present a XOR-based code supplemented with the ideas of parity duplication and rack awareness that could be adopted in such storage clusters to improve the recovery performance during node failures and compare it with popular implementations of erasure codes, namely Facebook’s Reed-Solomon codes and XORBAS local recovery codes. The code performance along with the proposed ideas are evaluated on a geo-diverse cluster deployed on the NeCTAR research cloud. We also present a scheme for intelligently placing blocks of coded storage depending on the design of the code, inspired by local reconstruction codes. The sum of all these propositions could offer a better solution for applications that are deployed on coded storage systems that are geographically distributed, in which storage constraints make triple replication not affordable, at the same time ensuring minimal recovery time is a strict requirement.
Keywords Distributed storage, Erasure codes, Geographical diversity, XOR based codes, Code aware placement, Hadoop distributed file system, HDFS-RAID
RAPTOR: a network tool for mitigating the impact of spatially correlated failures in infrastructure networks
1, Arunabha Sen1, Chunming Qiao2, Nasir Ghani3, Nathalie Mitton4
(1) School of Computing, Informatics and Decision System Engineering, Arizona State University, Tempe, USA
(2) Department of Computer Science and Engineering, SUNY at Buffalo, Buffalo, USA
(3) Department of Electrical Engineering, University of South Florida, Tampa, USA
(4) Inria, Villeneuve D’ASCQ, France
Abstract Current practices of fault-tolerant network design ignore the fact that most network infrastructure faults are localized or spatially correlated (i.e., confined to geographic regions). Network operators require new tools to mitigate the impact of such region-based faults on their infrastructures. Utilizing the support from the U.S. Department of Defense, and by consolidating a wide range of theories and solutions developed in the last few years, the authors of this paper have developed Raptor, an advanced Network Planning and Management Tool that facilitates the design and provisioning of robust and resilient networks. The tool provides multi-faceted network design, evaluation, and simulation capabilities for network planners. Future extensions of the tool currently being worked upon not only expand the tool’s capabilities, but also extend these capabilities to heterogeneous interdependent networks such as communication, power, water, and satellite networks.
Keywords Spatially correlated faults, Region-based faults, Geographically correlated faults, Fault-tolerant network design, Network robustness and resilience, Network tool