The densification of Wi-Fi deployments means that fully distributed random channel access is no longer sufficient for high and predictable performance. Therefore, the upcoming IEEE 802.11bn amendment introduces multi-access point coordination (MAPC) methods. This paper addresses a variant of MAPC called coordinated spatial reuse (C-SR), where devices transmit simultaneously on the same channel, with the power adjusted to minimize interference. The C-SR scheduling problem is selecting which devices transmit concurrently and with what settings. We provide a theoretical upper bound model, optimized for either throughput or fairness, which finds the best possible transmission schedule using mixed-integer linear programming. Then, a practical, probing-based approach is proposed which uses multi-armed bandits (MABs), a type of reinforcement learning, to solve the C-SR scheduling problem. We validate both classical (flat) MAB and hierarchical MAB (H-MAB) schemes with simulations and in a testbed. Using H-MABs for C-SR improves aggregate throughput over legacy IEEE 802.11 (on average by 80% in random scenarios), without reducing the number of transmission opportunities per station. Finally, our framework is lightweight and ready for implementation in Wi-Fi devices.

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.

Abstract This article considers resilience of service networks that are composed of service and control nodes to node‐targeted attacks. Two complementary problems of selecting attacked nodes and placing control nodes reflect the interaction between the network operator and the network attacker. This interaction can be analyzed within the framework of game theory. Considering the limited performance of the previously introduced iterative solution algorithms based on non‐compact problem models, new compact integer programming formulations of the node attack optimization problem are proposed, which are based on the notion of pseudo‐components and on a bilevel model. The efficiency of the new formulations is illustrated by the numerical study that uses two reference networks (medium‐size and large‐size), and a wide range of the sizes of attacks and controllers placements.

Abstract In software defined networks (SDN) packet data switches are configured by a limited number of SDN controllers, which respond to queries for packet forwarding decisions from the switches. To enable optimal control of switches in real time the placement of controllers at network nodes must guarantee that the controller‐to‐controller and switch‐to‐controller communications delays are bounded. Apart from the primary controllers that control the switches in the nominal state, separate backup controllers can be introduced that take over when the primary controllers are unavailable, and whose delay bounds are relaxed. In this paper, we present optimization models to jointly optimize the placement of primary and backup controllers in long‐distance SDN networks, aimed at maximizing the network's resilience to node‐targeted attacks. Applying the models to two well‐known network topologies and running a broad numerical study we show that, when compared with the standard approach of using only primary controllers, the use of backup controllers provides significant resilience gains, in particular in case of tight delay bounds.

In Software Defined Networks (SDNs), a number of controllers are placed in a given data plane network. In a standard logically centralized control plane, each controller acts simultaneously as a primary controller for some switches and as a backup controller for other switches, and the controller placements must meet given switch-controller (SC) and controller-controller (CC) delay bounds. Then, the SDN should be resilient to network disruptions such as node-targeted attacks. To improve the SDN resilience to this kind of disruptions, we assume that some controllers are deployed only as backup controllers so that they take over the functions of primary controllers only in case of disruption. We propose an optimization model that solves a relevant primary and backup controller placement problem, where a minimum number of primary controllers minimizing the maximum SC delay is first established, and then a joint primary and backup controller placement maximizing the resilience of the SDN against a list of the most dangerous node-targeted attacks is determined. A numerical study illustrating the merits of the proposed optimization methodology is presented.

Abstract Ideally, the network should be dynamically reconfigured as traffic evolves. Yet, even within the software defined network paradigm, network reconfigurations cannot be too frequent due to a number of reasons related to route consistency, forwarding rules instantiation, individual flows dynamics, traffic monitoring overhead, and so on. In this paper, we focus on the fundamental issue of deciding whether, when, and how to reconfigure the network while traffic evolves. We consider a problem of optimizing semi‐stable routing in the capacitated multicommodity flow network when one may use at most a given maximum number of routing configurations (called routing clusters) and when each routing configuration must be used for at least a given minimum amount of time. We propose an efficient solution approach based on routing cluster generation that provides a tight lower bound on the minimum of a selected objective function (like maximum link delay or a sum of link delays) and suboptimal solutions very close to the calculated bound. The approach scales well with the size of the network.

We consider a network security and configuration management problem of locating service controllers so as to maximize availability of services in case of targeted attacks on the network infrastructure. Assuming that the attacker has full knowledge of the network topology but can only try to predict controller locations, we model the attacker's behavior introducing a set of probabilistic network availability measures and formulating an optimization problem model that determines the potentially most dangerous attacks the attacker might launch. We also formulate a counter-part optimization model that allows the network operator to derive the optimal placement of controllers, which maximizes availability of services with respect to a given set of network attacks. We explain the models and illustrate our considerations using a running small, intuitive network example. And we also perform extensive numerical experiments with a realistic network data to evaluate and compare the potential effectiveness of different attack strategies, and the effectiveness of the counter-measures that the network operator can adopt.

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.

Ideally, the network should be dynamically reconfigured as traffic evolves. Unfortunately, even in SDN paradigm, network reconfigurations cannot be too frequent due to a number of reasons related to route stability, forwarding rules instantiation, individual flows dynamics, traffic monitoring overhead, etc. In this paper, we focus on the fundamental problem of deciding whether, when, and how to reconfigure the network during traffic evolution. We consider a problem of optimizing semi-stable routing in the capacitated multicommodity flow network when one may use at most a given maximum number of routing configurations (called clusters) and when each routing configuration must be used for at least a given minimum amount of time. We propose a solution method based on cluster generation that provides a good lower bound on the minimum network delay (i.e., the total of link delays) and scales well with the size of the network.

Established approaches to data aggregation in wireless sensor networks (WSNs) do not cover the variety of new use cases developing with the advent of the Internet of Things (IoT). In particular, the current push toward fog computing, in which control, computation, and storage are moved to nodes close to the network edge, induces a need to collect data at multiple sinks, rather than the single sink typically considered in WSN aggregation algorithms. Moreover, for machine-to-machine communication scenarios, actuators subscribing to sensor measurements may also be present, in which case data should be not only aggregated and processed in-network but also disseminated to actuator nodes. In this paper, we present mixed-integer programming formulations and algorithms for the problem of energy-optimal routing and multiple-sink aggregation, as well as joint aggregation and dissemination, of sensor measurement data in IoT edge networks. We consider optimization of the network for both minimal total energy usage, and min-max per-node energy usage. We also provide a formulation and algorithm for throughput-optimal scheduling of transmissions under the physical interference model in the pure aggregation case. We have conducted a numerical study to compare the energy required for the two use cases, as well as the time to solve them, in generated network scenarios with varying topologies and between 10 and 40 nodes. Although aggregation only accounts for less than 15% of total energy usage in all cases tested, it provides substantial energy savings. Our results show more than 13 times greater energy usage for 40-node networks using direct, shortest-path flows from sensors to actuators, compared with our aggregation and dissemination solutions.

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 This article describes the Survivable Network Design Library (SNDlib), a data library for fixed telecommunication network design available at http://sndlib.zib.de . In the current version 1.0, the library contains data related to 22 networks which, combined with a set of selected planning parameters, leads to 830 network design problem instances. In this article, we discuss the data concepts of SNDlib and describe a mathematical model for each design problem considered in the library. We also provide information on characteristic features and the origin of the SNDlib problem instances. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract In this article we prove 𝒩𝒫‐hardness of two well‐known optimization problems related to the design of multicommodity flow networks with two different methods for providing network resiliency against failures: path diversity and flow restoration. Path diversity is a static mechanism that consists of using, for each demand, a number of paths and oversizing the flows assigned to these paths so that for any failure the total surviving flow is not less than the volume of the demand. By contrast, flow restoration is a dynamic mechanism that consists of reassigning the failed flows to backup paths when a failure occurs. Both mechanisms are of practical interest because although flow restoration is in general superior to path diversity in terms of the required amount of resource capacity, it might be too complicated to implement. By providing an appropriate reduction from the fractional graph coloring problem, we show that both problems are 𝒩𝒫‐hard in the general case of failure scenarios that admit simultaneous failures of multiple links. Finally, we discuss how to efficiently solve the two problems using path generation techniques. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Our goal is to present a mathematical model useful for distributed optimization of traffic routing in multi-domain Internet networks. In such environments each domain is operated autonomously and has access to limited information about the rest of the network. Our model reflects this through an appropriate problem decomposition with respect to individual domains. The decomposition aims at supporting a distributed process of routing optimization that could be run in the control plane of the network using existing EGP routing protocols. The usefulness of the decomposition is investigated and illustrated with numerical examples.

The Warsaw metropolitan network is undergoing a radical architectural and technological transformation. The transformation, forced by the large unrealized demand for telephone stations, and structural traffic bottlenecks, is based on the installation of eight digital transit switches of high capacity. The so-formed upper transit layer gives an opportunity for the deployment of an efficient traffic routing system, for carrying the growing traffic well beyond the year 2000 without additional investments. A step-wise strategy is presented far the deployment of a modern traffic routing system in the Warsaw network, adapted to, and taking advantage of the fast transformation of the network. The choice of the strategy is based on a case study of the traffic handling efficiency of various routing systems in a model of the Warsaw metropolitan network.>