The ability of the Software-Defined Network (SDN) to transport traffic flows depends, in particular, on the SDN switches being able to communicate with SDN controllers, which are responsible for the setup of network connections and the configuration of switches. Since in principle the number of SDN controllers is limited they must be installed in a set of carefully selected node locations. Whereas the problem of controller placement is well defined and has been thoroughly studied and effectively solved for the nominal network state, it becomes difficult when the network is subject to attacks, especially as they can occur anywhere and anytime. In this paper we tackle the problem of controller placement resilient to network attacks considering probabilistic characterisation of attacks and equitable access of switches to controllers. We treat the problem as a specific facility location problem with the objective of providing resilience to network attacks, and analyze a couple of major solution fairness criteria. We derive a number of Mixed-Integer Linear Programming (MILP) problem models that exploit robust optimization and fair optimization concepts and techniques, and examine their effectiveness by means of a numerical study that uses five transport networks.

Abstract One of the major challenges in managing 5G networks is the reconfiguration of network slices. The task covers in particular reconfiguration and relocation of virtual network functions (VNFs) so as to match the service requirements of the slices and the availability of resources of the data centers. In this article, we study in deep the problem of optimal VNFs reconfiguration analyzing a number of its variants. We define two exact, compact integer linear programming formulations of the VNFs reconfiguration problem, and derive two approximate solution algorithms, one of them based on the column generation method. Numerical tests and comparisons illustrate the performance of the algorithms and the quality of the provided solutions.

International audience

Abstract Flow thinning (FT) is a traffic protection mechanism for communication networks with variable link capacities, for example wireless networks. With FT, end‐to‐end traffic demands use dedicated logical tunnels, for example MPLS tunnels, whose nominal capacity is subject to thinning in order to follow fluctuations in link capacities availability. Moreover, instantaneous traffic of each demand is throttled at its originating node accordingly to the current total capacity available on the demand's dedicated tunnels so that the network is always capable of carrying the admitted traffic. In this paper, we deal with efficient, implementable versions of FT, referred to as affine FT (AFT) and quadratic FT (QFT). By deriving appropriate link availability state and path generation algorithms, we show how real‐life network dimensioning problems for AFT/QFT can be efficiently treated using a proper characterization of the network link availability states. Results of a numerical study illustrate tractability of the cost minimization problems, and assess efficiency of AFT/QFT as compared with other protection mechanisms.

The presented paper deals with wireless networks composed of FSO (free space optics) links supported by terrestrial optical fiber connections in order to increase resilience to adverse weather conditions. An FSO link realizes, at low cost, a broadband optical transmission system established by means of two parallel light beams connecting a pair of (remote) transceivers placed in the line of sight. However, a major disadvantage of FSO links (with respect to fiber links) is their sensitivity to weather conditions: bad weather affects optical channel, resulting in substantial degradation of the transmission power at the receivers, which in general leads to capacity degradation on multiple FSO links. When the transmission power received at the end node of an FSO link is decreased, the signal modulation and coding scheme (MCS) at the transmitter should be adjusted accordingly; in effect, an FSO link can be kept operational, but with decreased capacity, even if the channel is affected. Yet, since in severe weather conditions some FSO links may not be able to realize any reliable transmission at all (whichever MSC is used), the network may become disconnected and a portion of traffic lost. Therefore, it is reasonable to consider using fibers instead of free space light beams since weather insensitive (and high capacity) fibers installed on the key links will ensure network connectivity in all weather states. Certainly, the so obtained connectivity does not come for free because of the high cost of the optical fiber connections as compared to the FSO systems and hence the number of fibers should be kept at minimum. Thus, for designing hybrid FSO/fiber networks we need an optimization model for finding cheapest configurations of links (and their capacities) that will be able to carry the demanded traffic on acceptable level in all weather states foreseen in network operation. This is not a simple task as it requires not only robust network optimization methods but also a tractable way of characterizing possible weather states (which are not known in advance) and their influence on FSO link capacity. In the paper we present an approach to the so described task and illustrate its effectiveness by means of a numerical study.

The present study deals with Elastic Flow Rerouting (EFR)—an original traffic restoration strategy for protecting traffic flows in communication networks (including wireless networks) against multiple link failures. EFR aims at alleviating the trade‐off between practicability of traffic restoration and the cost of network resources observed in existing networking solutions. We present an extension of EFR capable of managing multiple partial link failures. We describe EFR and its extension, formulate the EFR related optimization problems, and discuss approaches for their resolution. We also discuss numerical results illustrating effectiveness of EFR in terms of the link capacity cost. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 267–281 2015

In this work we address the problem of joint link scheduling and power assignment in WSNs. It focuses on finding a feasible schedule and a power assignment scheme such that the schedule length is minimized and the concurrent transmissions have a fair quality in terms of SINR (Signal-to-Interference-and-Noise Ratio). As the problem is shown to be NP-hard we propose a greedy heuristic for the scheduling problem which seeks to minimize the number of time slots for link scheduling. Our goal is to design an algorithm that performs transmission power control in order to guarantee fair SINR link transmissions. This insures that every node that is actively transmitting in the network chooses a transmission power which will minimally affect the other concurrent transmissions. Hence, we opt for a cooperative strategy which intends to maximize the minimum value of SINR. This problem is modeled and solved using an iterative algorithm based on linear programming which provides an optimal solution. The solution of this problem may be crucial for the performance of WSNs as it impacts different network requirements such as lifetime (energy savings), delay (schedule length) and throughput (number of concurrent links in a time slot).

Abstract In this article, we revisit a classical optimization problem occurring in designing survivable multicommodity flow networks. The problem, referred to as FR, assumes flow restoration that takes advantage of the so‐called stub release. As no compact linear programming (LP) formulation of FR is known and at the same time all known noncompact LP formulations of FR exhibit \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard dual separation, the problem itself is believed to be \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard, although without a proof. In this article, we study a restriction of FR (RFR) that assumes only elementary (cycle‐free) admissible paths—an important case virtually not considered in the literature. The two problems have the same noncompact LP formulations as they differ only in the definition of admissible paths: all paths (also those including cycles) are allowed in FR, while only elementary paths are allowed in RFR. Because of that, RFR is in general computationally more complex than FR. The purpose of this article, is three‐fold. First, the article reveals an interesting special case of RFR—the case with only one failing link—for which a natural noncompact LP formulation obtained by reducing the general RFR formulation still exhibits \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard dual separation, but nevertheless this special case of RFR is polynomial. The constructed example of a polynomial multicommodity flow problem with difficult dual separation is of interest since, to our knowledge, no example of this kind has been known. In this article, we also examine a second special case of RFR, this time assuming two failing links instead of one, which turns out to be \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard. This implies that problem RFR is \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*} \end{document} ‐hard in general (more precisely, for two or more failure states). This new result is the second contribution of the article. Finally, we discuss the complexity of FR in the light of our new findings, emphasizing the differences between RFR and FR. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract The robust optimization framework proposed by Bertsimas and Sim accounts for data uncertainty in integer linear programs. This article investigates the polyhedral impacts of this robust model for the 0‐1 knapsack problem. In particular, classical cover cuts are adapted to provide valid inequalities for the robust knapsack problem. The strength of the proposed inequalities is studied theoretically. Then, experiments on the robust bandwidth packing problem illustrate the practical interest of these inequalities for solving hard robust combinatorial problems. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

The Wireless Sensor Networks (WSNs) design related questions give rise to new complex and difficult theoretical problems and challenges in operations research and optimization areas. As WSNs become increasingly pervasive, a good understanding of these problems in terms of theoretical complexity is of great help in designing appropriate algorithms. In this paper, we examine some of the most fundamental optimization problems related to coverage, topology control, scheduling, routing and mobility in WSNs. Then we focus on their complexity and analyze the differences that exist with the counter part conventional theoretical problems or those already studied in traditional networks. We present as well some of the main methods proposed in the literature and report some open issues regarding these problems.

In this paper we study the multi-period network design problem (MPND), and focus on a special case, called multi-period network design with incremental routing (MPNDI). We optimize simultaneously the network architecture and the link dimensioning under discrete cost functions in order to route all traffic demands in line with traffic growth over a discrete time horizon. We are interested here in incremental routing, that is, routing paths used at a given period to route some traffic demands have to be preserved over subsequent periods. We present here some new valid inequalities related to multi-period incremental routing, in addition to some previous results already presented in [13]. Finally, some computational results for a range of instances with eight and ten nodes for two and three periods are given. They provide a comparison of the classical MPND problem and the MPNDI problem in terms of overall costs and CPU time.

Abstract In this paper, we study a special case of multiperiod network design (MPND) problems, multiperiod network design with incremental routing (MPNDI), as applied to the transmission layer of an optical network. We optimize simultaneously the network architecture and the link dimensioning under discrete cost functions in order to route all traffic demands in line with traffic growth over a discrete time horizon. Because of operational requirements, routing paths used at a given period to route some traffic demands have to be preserved over subsequent periods; this is called incremental routing with respect to incremental flow. To handle the high dimensionality, a compact formulation omitting explicitly written flow variables is given. We examine the dominant polyhedron of the incremental multicommodity flow and provide a polyhedral study of it. Finally, a solution approach taking advantage of the polyhedral structure of MPNDI is proposed, and computational results for a range of instances with 8 and 10 nodes are provided. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 109–117 2007

In this paper we focus on the single-facility capacitated survivable network design problem. We optimize simultaneously the network topology and the link dimensioning in order to route all traffic commodities according to survivability requirements. The latter are actually expressed in terms of the spare capacity required to address link failures in the context of different rerouting strategies. We present a mixed-integer linear programming model solved by combining several approaches. To tackle the high dimensionality and to separate the continuous and integer variables, we use Benders' decomposition and a cutting-plane approach. Going beyond the proposed method itself, we examine and compare two well-known restoration techniques: local and end-to-end reroutings. Numerous computational results for realistic network instances provide a comparison of these rerouting mechanisms in terms of installed capacities, network density as well as overall costs and CPU time.

We consider the fair flow problem in a multiple source multiple sink network, as applied to telecommunication networks. We present an iterative algorithm for computing fair routing in networks where the available resources are shared among competing flows according to a max-min fair sharing criterion. Our main objective is computing optimal routing paths, with regard to max-min fairness, in stable and known traffic conditions. It is a linear programming based approach which permits a lexicographical maximization of the vector of fair-share attributed to the connections competing for network resources. An optimality proof and some computational results are also presented.