ABSTRACT In real‐life applications, most optimization problems are variants of well‐known combinatorial optimization problems, including additional constraints to fit with a particular use case. Usually, efficient algorithms to handle a restricted subset of these additional constraints already exist or can be easily derived, but combining them together is difficult. The goal of our paper is to provide a framework that allows merging several so‐called atomic algorithms to solve an optimization problem, including all associated additional constraints together. The core proposal, referred to as Atomic Column Generation (ACG) and derived from Dantzig–Wolfe decomposition, allows converging to an optimal global solution with any kind of atomic algorithms. We show that this decomposition improves the continuous relaxation and describe the associated Branch‐and‐Price algorithm. We consider a specific use case in telecommunication networks where several Path Computation Elements (PCE) are combined as atomic algorithms to route traffic. We demonstrate the efficiency of ACG on the resource‐constrained shortest path problem associated with each PCE and show that it remains competitive with benchmark algorithms.

In backbone networks, it is fundamental to quickly protect traffic against any unexpected event, such as failures or congestions, which may impact Quality of Service (QoS). Standard solutions based on Segment Routing (SR), such as Topology-Independent Loop-Free Alternate (TI-LFA), are used in practice to handle failures, but no distributed solutions exist for distributed and tactical congestion mitigation. A promising approach leveraging SR has been recently proposed to quickly steer traffic away from congested links over alternative paths. As the pre-computation of alternative paths plays a paramount role to efficiently mitigating congestions, we investigate the associated path computation problem aiming at maximizing the amount of traffic that can be rerouted as well as the resilience against any 1-link failure. In particular, we focus on two variants of this problem. First, we maximize the residual flow after all possible failures. We show that the problem is NP-Hard, and we solve it via a Benders decomposition algorithm. Then, to provide a practical and scalable solution, we solve a relaxed variant problem, that maximizes, instead of flow, the number of surviving alternative paths after all possible failures. We provide a polynomial algorithm. Through numerical experiments, we compare the two variants and show that they allow to increase the amount of rerouted traffic and the resiliency of the network after any 1-link failure.

Various routing protocols are deployed to operate networks, and border routers manage the exchange of routing information. Network engineers carefully configure routing policies to ensure reliable, efficient, and secure connectivity. However, the complexity of these configurations can lead to errors and issues like routing loops. Existing control plane verification solutions offer comprehensive analysis but struggle with scalability. This demonstration presents a scalable verification tool capable of locating routing loops in large multi-protocol and multi-instance networks, demonstrating its efficiency and performance with numerical results and live verification.

Deep Reinforcement Learning (DRL) algorithms have recently made significant strides in improving network performance. Nonetheless, their practical use is still limited in the absence of safe exploration and safe decision-making. In the context of commercial solutions, reliable and safe-to-operate systems are of paramount importance. Taking this problem into account, we propose a safe learning-based load balancing algorithm for Software Defined-Wide Area Network (SD-WAN), which is empowered by Deep Reinforcement Learning (DRL) combined with a Control Barrier Function (CBF). It safely projects unsafe actions into feasible ones during both training and testing, and it guides learning towards safe policies. We successfully implemented the solution on GPU to accelerate training by approximately 110x times and achieve model updates for on-policy methods within a few seconds, making the solution practical. We show that our approach delivers near-optimal Quality-of-Service (QoS) performance in terms of end-to-end delay while respecting safety requirements related to link capacity constraints. We also demonstrated that on-policy learning based on Proximal Policy Optimization (PPO) performs better than off-policy learning with Deep Deterministic Policy Gradient (DDPG) when both are combined with a CBF for safe load balancing.

Multi-topology routing (MTR) provides an attractive alternative to segment routing for traffic engineering when network devices cannot be upgraded. However, due to a high overhead in terms of link state messages exchanged by topologies and the need to frequently update link weights to follow evolving network conditions, MTR is often limited to a small number of topologies and the satisfaction of loose QoS constraints. To overcome these limitations we propose vMTR, an MTR extension where demands are routed over virtual topologies that are silent, i.e., they do not exchange LSA messages, and that are continuously derived from a very limited set of real topologies, optimizing each a QoS parameter. In this context, we present a polynomial and exact algorithm for vMTR and, as a benchmark, a local search algorithm for MTR. We show that vMTR helps reducing drastically the number of real topologies and that it is more robust to QoS changes.

In SD-WAN networks, the traffic issued from multiple high capacity hubs towards low capacity spokes can create congestions in the underlay and degrade unnecessarily the Quality of Service (QoS). To mitigate this issue, shaping policies can be dynamically controlled to adapt to WAN performance and traffic. While existing solutions work for a single hub, at tunnel level, and in a reactive manner, we propose a more advanced solution for multiple hubs at application level. Our Dynamic QoS solution also takes proactive actions to prevent congestions and protect high priority traffic. It ensures a fast convergence towards an optimal rate allocation. This demonstration presents the design and implementation of this feature in AR8140 devices. It presents a performance evaluation in a testbed and simulation.

With the advent of big data applications, coflow scheduling has become a cornerstone for the engineering of traffic in datacenters. Minimizing the average weighted Coflow Completion Times (CCT) is a crucial step to minimize the execution time of jobs running in distributed computing frameworks. In this paper, we present a new$\sigma $-order coflow scheduling solution, ONE-PARIS, an online semi-clairvoyant and semi-distributed implementation suitable to minimize the weighted CCT in production environments. We achieves this through ONE-PARIS scheduler for ordering coflows and a decentralized resource allocation mechanism, called Sync-Rate, enabling to respect the order of priority of coflows provided by ONE-PARIS and ensuring efficient synchronization between flows of the same coflow in order to free up bandwidth for low-priority flows. Extensive simulations on both synthetic and real traffics show that our proposed coflow scheduler outperforms other state-of-art schemes.

Tactical Traffic Engineering (TE) solutions are a must to adapt traffic steering when unexpected congestions occur. While already available, centralized solutions to locally optimizes congested tunnels and links suffer from a slow reaction time of several minutes. To address this issue, we propose a distributed Congestion Mitigation (CM) mechanism that leverages Segment Routing (SR) to offload traffic away from congested links using Unequal Cost Multi Paths (UCMP) over alternative paths. In this paper, we introduce an efficient algorithm for alternative paths’ computation, and two methods to compute UCMP weights, depending on whether remote link loads are available or not. We show that the proposed path computation method is faster than a modified K-shortest path algorithm. For traffic splitting, we show that the knowledge of remote link loads and per-destination traffic is a key to mitigate congestions in loaded scenarios, approaching the results obtained with an optimal solution. However, when not available, a local solution can already mitigate congestions in lightly loaded scenarios.

The average coflow completion time (CCT) is the standard performance metric in coflow scheduling. However, standard CCT minimization may introduce unfairness between the data transfer phase of different computing jobs. Thus, while progress guarantees have been introduced in the literature to mitigate this fairness issue, the trade-off between fairness and efficiency of data transfer is hard to control. This paper introduces a fairness framework for coflow scheduling based on the concept of slowdown, i.e., the performance loss of a coflow compared to isolation. By controlling the slowdown it is possible to enforce a target coflow progress while minimizing the average CCT. In the proposed framework, the minimum slowdown for a batch of coflows can be determined in polynomial time. By showing the equivalence with Gaussian elimination, slowdown constraints are introduced into primal-dual iterations of the CoFair algorithm. The algorithm extends the class of the$\sigma$-order schedulers to solve the fair coflow scheduling problem in polynomial time. It provides a 4-approximation of the average CCT w.r.t. an optimal scheduler. Extensive numerical results demonstrate that this approach can trade off average CCT for slowdown more efficiently than existing state of the art schedulers.

This paper presents a study of the optimal Admission Control in Damper-based Networks (ACDN) problem. The use of dampers in large-scale networks is becoming increasingly beneficial for a wide range of applications as it provides a reliable means of achieving deterministic delay guarantees without the need for synchronization between routers. In this context, optimal admission control solutions are required to fully utilize capacity. The problem being studied is a variant of the Unsplittable Multi-Commodity Flow (UMCF) problem, with additional constraints related to forwarding and shaping. This paper proposes two Integer Linear Programming (ILP) formulations to address the ACDN problem. The former is a compact formulation, which is solved using the CPLEX solver. The latter is an extended path formulation, for which a Branch-and-Price algorithm is developed, including a column generation procedure, an efficient branching scheme, and reinforced by a primal heuristic. Tests on realistic instances show that solving the path formulation using the Branch-and-Price algorithm is better than solving the compact formulation using CPLEX. Our algorithm divides by 14 the average running time given by CPLEX, and the path formulation gives a stronger linear relaxation with an average optimally gap of 0.3%. This work builds upon previous research [1] that developed a heuristic for finding near-optimal solutions, and instead aims to find exact optimal solutions for ACDN.

In modern SD-WAN networks, a global controller is able to steer traffic on different paths based on application requirements and global intents. However, existing solutions cannot dynamically tune the way bandwidth is shared between flows inside each network, in particular when the available capacity is uncertain due to cross traffic. In this context, we propose a global QoS (Quality of Service) policy optimization model that dynamically adjusts rate limits of applications based on their requirements to follow the evolution of network conditions. It relies on a novel cross-traffic estimator for the available bandwidth of overlay links that only exploits already available measurements. We propose a centralized local search algorithm with cross-traffic estimation and show in packet-level simulations a significant performance improvement in terms of SLA (Service Level Agreement) satisfaction. The adaptive tuning of load balancing and QoS policies based on cross-traffic estimation can improve SLA satisfaction by 40% compared to static policies.

This paper proposes an Attention-based Multi-Agent Cooperation (AMAC) approach to reduce message exchange overhead in Multi-Agent Reinforcement Learning-based smart load balancing. AMAC shares only most relevant messages across agents to coordinate decision-making without degrading original performance. Experiments show that AMAC significantly lowers inter-agent communications overhead and learning complexity and outperforms multiple MARL benchmarks in Key Performance Indicators (KPIs) and Key Quality Indicators (KQIs).

Nowadays, centralized Path Computation Elements (PCE) integrate control plane algorithms to optimize routing and load-balancing continuously. When a link fails, the traffic load is automatically transferred to the remaining paths according to the configuration of load-balancers. In this context, we propose a load-balancing method that anticipates load transfers to ensure the protection of traffic against any Shared-Risk-Link-Group (SRLG) failure. The main objective of this approach is to make better use of bandwidth compared to existing methods. It consists in reserving a minimum amount of extra bandwidth on links so that the rerouting of traffic is guaranteed. We propose a non-linear non-convex model for the problem of minimizing the bandwidth reservation cost. We introduce a new approximation approach based on a neural network to convexify the problem and apply Kelley’s cutting plane method to solve the problem. Finally, we show that our algorithm significantly improves the CPU time against a compact model solved using the SCIP solver.

This paper explores the use of multi-agent deep learning as well as learning to cooperate principles to meet strict service level agreements, in terms of throughput and end-to-end delay, for a set of classified network flows. We consider agents built on top of a weighted fair queuing algorithm that continuously set weights for three flow groups: gold, silver, and bronze. We rely on a novel graph-convolution based, multi-agent reinforcement learning approach known as DGN. As benchmarks, we propose centralized and distributed deep Q-network algorithms and evaluate their performances in different network, traffic, and routing scenarios, highlighting both the effectiveness of our proposals and the importance of agent cooperation. We show that our DGN-based approach meets stringent throughput and delay requirements across different scenarios, decreasing silver and bronze flow median waiting delays by more than 50 % and reducing the SLA violations of the latter by nearly 60 %, with respect to a classic priority queuing approach.

Reducing Coflow Completion Time (CCT) has a significant impact on data-intensive application performance in datacenter networks. An efficient allocation of network resources allows for accelerating the computations to be performed. In this paper, we propose a new scheduler, named ELITE, to minimize the Weighted Coflow Completion Time (WCCT). Our scheduling algorithm is a 2-approximation of the optimal and the rate allocation can achieve a 4-approximation as long as the scheduling priority is respected. We also present a new rate allocation procedure, named RACO, that shows near-optimal performance when combined with our scheduling algorithms. We also propose a low complexity online scheduler, named LSPRT to attain near-optimal performance in online setting. With extensive simulations, we demonstrate the effectiveness of our algorithms by measuring the performance gain of ELITE and LSPRT over previous solutions in the literature. In particular, ELITE and LSPRT perform about 44 % better than Varys, while Sincronia achieves only 32 % against Varys.

In this paper, we explore the use of an actor-critic architecture for Deep Reinforcement Learning (DRL) to improve load balancing beyond traditional algorithms. Some centralized Reinforcement Learning (RL) algorithms have targeted in the reward function expression the Quality of Experience (QoE) for video flows, but this requires access to clients, or the Maximum Link Utilization (MLU) for other types of flows. In our approach, we tune the actor-critic algorithm to only leverage on QoS parameters in order to load balance traffic in the network and maximize the QoE experienced by the users. This avoids having to collect observations and performance measurements from client applications, as it only focuses on network metrics that can be easily measured. We explore both centralized and distributed solutions to assess the feasibility of the proposed smart load balancing solutions. We compare them to ECMP, QoE-based reward methods, and RILNET that uses an underlying DDPG optimization approach. The proposed algorithms are shown to outperform previous approaches.

With 5G networking, deterministic guarantees are emerging as a key enabler. In this context, we present a scalable Damper-based architecture for Large-scale Deterministic IP Networks (D-LDN) that meets required bounds on end-to-end delay and jitter. This work extends the original LDN [1] architecture, where flows are shaped at ingress gateways and scheduled for transmission at each link using an asynchronous and cyclic opening of gate-controlled queues. To further relax the need for clock synchronization between devices, we use dampers, that consist in jitter regulators, to control the burstiness flows to provide a constant target delay at each hop. We introduce in details how data plane functionalities are implemented at all nodes (gateways and core) and we derive how the end-to-end delay and jitter are calculated. For the control plane, we propose a column generation algorithm to quickly take admission control decisions and maximize the accepted throughput. For a set of flows, it determines acceptance and selects the best shaping and routing policy. Through a proof-of-concept implementation in simulation, we verify that the architecture meets promised guarantees and that the control plane can operate efficiently at large-scale.

To optimize bandwidth utilization in wide area networks, a centralized controller typically maintains routing policies at edge routers. In this context, we propose a versatile intent-based policy optimization model that carefully selects the set of overlay links which are allowed for applications based on their requirements and the overall intents of the operator. The optimization model embeds QoS and traffic predictions to anticipate the impact of routing decisions. To address large scale scenarios where the behavior of the network and devices is not known exactly, we integrate data-driven predictions into a local search algorithm to optimize routing policies. The algorithm supports several intents such as the minimization of the congestion or the maximization of the network quality. Thanks to packet-level simulations on an SD-WAN scenario, we show that our intent-based policy optimization system improves significantly performances. For instance, the latency is improved by 40% when the high-quality intent is selected. In addition, the percentage of time SLAs are met is improved by 10% compared to legacy load balancing mechanisms.

We consider robust network design problems where an uncertain traffic vector belonging to a polytope has to be dynamically routed to minimize either the network congestion or some linear reservation cost. We focus on the variant in which the underlying graph is directed. We prove that an O(√k) = O(n)-approximation can be obtained by solving the problem under static routing, where k is the number of commodities and n is the number of nodes. This improves previous results of Hajiaghayi et al. [SODA'2005] and matches the Ω(n) lower bound of Ene et al. [STOC'2016] and the Ω(√k) lower bound of Azar et al. [STOC'2003]. Finally, we introduce a slightly more general problem version where some flow restrictions can be added. We show that it cannot be approximated within a ratio of k^{c/(log log k)} (resp. n^{c/(log log n)}) for some constant c. Making use of a weaker complexity assumption, we prove that there is no approximation within a factor of 2^{log^{1- ε} k} (resp. 2^{log^{1- ε} n}) for any ε > 0.

Abstract Taking into account the dynamic nature of traffic in telecommunication networks, the robust network design problem is to fix the edge capacities so that all demand vectors belonging to a polytope can be routed. While a common heuristic for this co‐NP‐hard problem is to compute, in polynomial time, an optimal static routing, affine routing can be used to obtain better solutions. It consists in restricting the routing to affinely depend on the demands. We show that a node‐arc formulation is less conservative than an arc‐path formulation. We also provide a cycle‐based formulation that is equivalent to the node‐arc formulation. To further reduce the solution's cost, several new formulations are obtained by relaxing flow conservation constraints and aggregating demands. As might be expected, aggregation allows us to reduce the size of formulations. A more striking result is that aggregation reduces the solution's cost.

Deterministic performance is a key enabler for 5G applications. While specific data-plane solutions have been proposed to reach a low deterministic end-to-end latency and jitter, legacy round-robin schedulers can already be used to guarantee bounds on the end-to-end latency, when associated with per-flow shapers. In this context, we propose a latency-guaranteed network slicing solution that trades-off between complexity and performance. We propose control plane algorithms to configure sub-channelized interfaces with an independent QoS scheduler at each physical port used by a slice. The algorithms allocate service rates and decide about queue assignments and routing inside each slice. Through numerical results on large network topologies, we demonstrate that our column-generation and two-steps algorithms can improve traffic acceptance while reducing the amount of reserved capacity.

To improve bandwidth utilization in IP networks, flow aggregates are typically split over multiple paths. In this context, we propose a fully distributed load balancing mechanism that operates only from the edge. Each source is able to determine the split ratios based on already available link state information so as to minimize the maximum link utilization in the network. Without extra signaling, our solution provides a feasible load balancing at each iteration and diminishing returns until convergence to a stable state. Through numerical results on a wide variety of instances, we show that it converges to a near-optimal solution in a few iterations. Thanks to packet-level simulations on an SD-WAN scenario, we also compare its performance in a dynamic environment over centralized and legacy load balancing solutions.

The deployment of 5G networks is paving the road to custom network services. It is now possible to envision the automatic decomposition of a physical network into several virtual networks to serve a wide range of user needs. This technology is also referred to as network slicing. To guarantee the strict isolation of virtual networks, it is possible to rely on underlay technologies such as Flex Ethernet (FlexE). In this demo, we present a slicing solution based on Multi-Topology-Routing (MTR). We will demonstrate how IGP weights can be designed for the embedding of a slice, described by a traffic matrix and end-to-end latency requirements, to minimize the cost of underlay bandwidth reservations.

Deterministic performance is a key enabler for 5G networking. In this context, we present a highly scalable Large-scale Deterministic Network (LDN) architecture providing end-to-end latency and bounded jitter guarantees in IP networks. At the data plane, flows are first shaped at ingress gateways using gate-control queues, achieving a very fine granularity compared to existing state of the art solutions. Inside the network, traffic is scheduled using an asynchronous cyclic queuing mechanism that can be implemented in real devices as it requires only 3 FIFO queues. The data plane relies on standard IP routing and a quasi-static mapping table to deterministically aggregate and forward packets over cycles with a low complexity in O(1). For the control plane, we present an advanced column generation algorithm to quickly take admission control decisions in large-scale networks. For a set of flows, it determines acceptance and selects the best shaping and routing policy. Through a proof-of-concept implementation and simulations, we show that our LDN architecture can guarantee end-to-end latency and bounded jitter. We also demonstrate that our advanced control plane algorithm brings an improvement up to 40% in terms of accepted traffic over classical routing.

Whether it is for network engineering or business intelligence insight purposes, it is crucial for an Internet Service Provider (ISP) to infer the Quality of Experience (QoE) perceived by the end user during a video streaming session. Specifically, it is important to detect video stalls as soon as they occur, to rapidly take counter-measures such as re-allocating resources more fairly among users. Video stalls fall into two different classes: (i) those caused by poor network conditions and (ii) those caused directly by the user when scrubbing or dragging the video playback forwards or backwards. However, only the former type of stalls degrade the QoE perceived by the end user. Therefore, in this paper we propose a technique to detect and classify stall events by observing the packets associated to a streaming session. We solve a least squares problem to minimize the distance between the estimated chunk's bitrate and the potential bitrate sequence that a plausible playback buffer dynamics would produce. This amounts to finding the maximally likely state sequence for a properly defined Hidden Markov Model. We propose two polynomial dynamic programming algorithms, one of which running in online fashion, computing the exact solution in the ideal case of complete and exact measurement set. We claim that our method is also applicable in an encrypted scenario, since it is robust with respect to the estimation error of a number of parameters, as we show via simulations.

Classic network control techniques have as sole objective the fulfillment of Quality-of-Service (QoS) metrics, being quantitative and network- centric. Nowadays, the research community envisions a paradigm shift that will put the emphasis on Quality of Experience (QoE) metrics, which relate directly to the user satisfaction. Yet, assessing QoE from QoS measurements is a challenging task that powerful Software Defined Network controllers are now able to tackle via machine learning techniques. In this paper we focus on a few crucial QoE factors and we first propose a Bayesian Network model to predict re- buffering ratio. Then, we derive our own novel Neural Network search method to prove that the BN correctly captures the discovered stalling data patterns. Finally, we show that hidden variable models based and context information boost performance for all QoE related measures.

The surge of video traffic is a challenge for service providers that need to maximize Quality of Experience (QoE) while optimizing the cost of their infrastructure. In this paper, we address the problem of routing multiple HTTP-based Adaptive Streaming (HAS) sessions to maximize QoE. We first design a QoS-QoE model incorporating different QoE metrics which is able to learn online network variations and predict their impact on representative classes of adaptation logic, video motion and client resolution. Different QoE metrics are then combined into a QoE score based on ITU-T Rec. P.1202.2. This rich score is used to formulate the routing problem. We show that, even with a piece-wise linear QoE function in the objective, the routing problem without controlled rate allocation is non-linear. We therefore express a routing-plus-rate allocation problem and make it scalable with a dual subgradient approach based on Lagrangian relaxation where subproblems select a single path for each request with a trivial search, thereby connecting explicitly QoE, QoE and HAS bitrate. We show with ns-3 simulations that our algorithm provides values for HAS QoE metrics (quality, rebufferings, variation) equivalent to MILP and better than QoS-based approaches.

To optimize routing of flows in datacenters, SDN controllers receive a packet-in message whenever a new flow appears in the network. Unfortunately, flow arrival rates can peak to millions per second, impairing the ability of controllers to treat them on time. Flow scheduling copes with such sheer numbers by segmenting the traffic between elephant and mice flows and by treating elephant flows in priority, as they disrupt short lived TCP flows and create bottlenecks. We propose a learning algorithm called SOFIA and able to perform optimal online flow segmentation. Our solution, based on stochastic approximation techniques, is implemented at the switch level and updated by the controller, with minimal signaling over the control channel. SOFIA is blind, i.e., it is oblivious to the flow size distribution. It is also adaptive, since it can track traffic variations over time. We prove its convergence properties and its message complexity. Moreover, we specialize our solution to be robust to traffic classification errors. Extensive numerical experiments characterize the performance of our approach in vitro. Finally, results of the implementation in a real OpenFlow controller demonstrate the viability of SOFIA as a solution in production environments.

The performance of computer networks relies on how bandwidth is shared among different flows. Fair resource allocation is a challenging problem particularly when the flows evolve over time. To address this issue, bandwidth sharing techniques that quickly react to the traffic fluctuations are of interest, especially in large-scale settings with hundreds of nodes and thousands of flows. In this context, we propose a distributed algorithm based on the alternating direction method of multipliers (ADMM) that tackles the multi-path fair resource allocation problem in a distributed SDN control architecture. Our ADMM-based algorithm continuously generates a sequence of resource allocation solutions converging to the fair allocation while always remaining feasible, a property that standard primal-dual decomposition methods often lack. Thanks to the distribution of all computer intensive operations, we demonstrate that we can handle large instances at scale.

Software‐Defined Networking and Network Function Virtualization are two paradigms that offer flexible software‐based network management. Service providers are instantiating Virtualized Network Functions, for example, firewalls, DPIs, gateways—to highly facilitate the deployment and reconfiguration of network services with reduced time‐to‐value. They use Service Function Chaining technologies to dynamically reconfigure network paths traversing physical and virtual network functions. Providing a cost‐efficient virtual function deployment over the network for a set of service chains is a key technical challenge for service providers, and this problem has recently caught much attention from both Industry and Academia. In this article, we propose a formulation of this problem as an Integer Linear Program that allows one to find the best feasible paths and virtual function placement for a set of services with respect to a total financial cost, while taking into account the (total or partial) order constraints for Service Function Chains of each service and other constraints such as end‐to‐end latency, anti‐affinity rules between network functions on the same physical node and resource limitations in terms of network and processing capacities. Furthermore, we propose a heuristic algorithm based on a linear relaxation of the problem that performs close to optimum for large scale instances. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(2), 97–106 2018

We consider a multi‐domain network scenario and we study the Inter‐Domain Path Computation problem under the Domain Uniqueness constraint ( ‐ ), that is, a path cannot visit a domain twice. It is known that hierarchical Path Computation Element (h‐PCE) architecture, that is commonly used to solve ‐ , shows poor scalability with respect to the number of domains. For this reason, we devise a new domain clustering concept allowing one to artificially reduce the number of domains in an offline phase, in order to solve ‐ with lower complexity at run‐time. More specifically, we first prove the ‐completeness of the feasibility problem associated with ‐ and the inapproximability of ‐ itself. Yet, we show that the number of domains is the real computational bottleneck for the solution of ‐ . Then we provide a necessary and sufficient condition for a domain clustering to be proper, that is, without loss of optimality. Such a condition can be verified offline on the inter‐domain graph. We finally show via numerical experiments the impact of the inter‐domain treewidth on the computational speed‐up brought by proper clustering.

The centralized control in Software Defined Networks paves the way for new services like Bandwidth Calendaring (BWC), where the possibility to shift temporally future bandwidth requests allows to efficiently use network resources. Assuming perfect knowledge of the calendar for all future bandwidth reservations is unrealistic. In this paper, we study the online version of the BWC problem presented in [1], where for unpredictable incoming demands an admission decision, scheduling and path allocation must be taken instantaneously. We design an algorithm for solving the online version of the BWC problem and proposes two heuristic approaches to exploit the scheduling flexibility of demands. Our numerical results reveal that the proposed solution approach outperforms state-of-the art methods by up to 70% in terms of accepted traffic.

End-to-end encryption seemingly signifies the death of caching, because current methods ensure that no two sessions are alike. In this paper, we show that servers can reuse encrypted content between sessions, thereby rejuvenating caching. The main idea of our technique is to allow interim nodes to cache content based on pseudo-identifiers instead of real file identities. This enables caching of reusable pseudo-identifiers, whilst maintaining content confidentiality, i.e., ensuring that only the client and the server know the actual identity of the requested file. Furthermore, we provide an extension that prevents client linkability, i.e., ensuring it is impossible to tell if two clients are viewing the same content. Finally, we formally analyse the balance between security and the hit probability performance of the cache.

Content Delivery Networks (CDN) are witnessing the outburst of video streaming (e.g., personal live streaming or Video-on-Demand) where the video content, produced or accessed by mobile phones, must be quickly transferred from a point to another of the network. Whenever a user requests a video not directly available at the edge server, the CDN network must (1) identify the best location in the network where the content is stored, (2) set up a connection and (3) deliver the video as quickly as possible. For this reason, existing CDNs are adopting an overlay structure to reduce latency, leveraging the flexibility introduced by the Software Defined Networking (SDN) paradigm. In order to guarantee a satisfactory Quality of Experience (QoE) to users, the connection must respect several Quality of Service (QoS) constraints. In this paper, we focus on the sub-problem (2), by presenting an approach to efficiently compute and maintain paths in the overlay network. Our approach allows to speed up the transfer of video segments by finding minimum delay overlay paths under constraints on hop count, jitter, packet loss and relay node capacity. The proposed algorithm provides a near-optimal solution, while drastically reducing the execution time. We show on traces collected in a real CDN that our solution allows to maximize the number of fast video transfers.

Load-balancing and network optimization in SDN networks require efficient flow splitting during the path computation phase. The way flow splitting is typically implemented in switches is to map the output of an hash function computed on the headers of incoming flows to the content stored in a Ternary Content Addressable Memory (TCAM), a very efficient but scarce resource. Although a large TCAM budget means that the flow distribution can more accurately model a fractional ideal, the distribution of flow volume amongst the paths is constrained in reality to use only a limited number of TCAM rows. In this paper, we present a flow splitting algorithm that maximizes the total number of demands allocated in the network according to the TCAM size constraints and, at the same time, minimize the total routing cost. Although the problem is NP-hard, we show through simulations that we can achieve good approximations of the optimal solution in a reasonable amount of time.

Software-Defined Network (SDN) controllers include mechanisms to globally reconfigure the network in order to respond to a changing environment. While iterative methods are employed to solve flow optimization problems, demands arrive or leave the system changing the optimization instance and requiring further iterations. In this paper, we focus on the general class of iterative solvers considering an exponential decrease over time in the optimality gap. Assuming dynamic arrivals and departures of demands, the computed optimality gap at each iteration Q(t) is described by an auto-regressive stochastic process. At each time slot the controller may choose to apply the current iteration to the network or not. Applying the current iteration improves the optimality gap but requires flow reconfiguration which hurts QoS and system stability. To limit the reconfigurations, we propose two control policies that minimize the flow allocation cost while respecting a network reconfiguration budget. We validate our model by experimenting with a realistic network setting and using standard Linear Programming tools used in the SDN industry. We show that our policies provide a practical means of keeping the optimally gap small within a given reconfiguration constraint.

By offloading the control plane to powerful computing platforms running on commodity hardware, Software Defined Networking (SDN) unleashes the potential to operate computation intensive machine learning tools and solve complex optimization problems in a centralized fashion. This paper studies such an opportunity under the framework of the centralized SDN Admission Control (AC) problem. We first review and adapt some of the key AC algorithms from the literature, and evaluate their performance under realistic settings. We then propose to take a step further and build an AC meta-algorithm that is able to track the best AC algorithm under unknown traffic conditions. To this aim, we exploit a machine learning technique called Strategic Expert meta-Algorithm (SEA).

SDN unleashes the potential to perform computational intensive machine learning algorithms to solve complex routing problems. This demo presents an architecture for the SDN controller that integrates several online routing algorithms for the real-time admission control of new connection requests. The demonstrator permits to compare the evolution of the network according to the admission decisions taken by different online algorithms and to simulate future scenarios to support strategic decisions aimed at improving the infrastructure.

Energy is classically considered as a critical resource in Wireless Sensor Networks (WSNs). These networks are composed of tiny devices that auto-organize around one or few gateways, which may have various roles from simple reference or traffic sinks to full network orchestrator. Such a gateway could influence the network behavior, for instance by decreasing activity when energy becomes scarce. It however needs to be able to estimate the nodes remaining energy. Indeed, this gateway is on the path of all traffic going in or out the WSN. This traffic sample could be used to acquire a coarse estimate of individual nodes energy consumption. The accuracy of this estimation can then be improved by explicit signaling if needed. This paper presents Tee, a set of such Traffic-based energy estimators that operates at the WSN gateway. We evaluate, by simulation, the accuracy of two such estimators in IEEE 802.15.4 networks running RPL and ContikiMAC, a duty cycled MAC layer. Results show that such silent estimators benefit from information already available at the gateway, such as the routing topology. However, they still underestimate the consumption due to the routing control messages, to the packets strobing, or to contention and collisions and can easily be complemented by lightweight explicit calibrations.

This paper introduces Rest, a reliable streaming protocol for lossy networks. Rest ensures full reliability while recovering losses as soon as possible thanks to the proactive injection of redundancy packets encoded following an on-the-fly scheme. It dynamically adapts the sending of codes depending on the estimation of the packet error rate with periodic acknowledgments to limit feedback dependency and protocol overhead. Results show that data are smoothly delivered to the receiving application with minimum overhead when errors are uniform. For systems with limited processing capacity, we propose to use a bounded encoding window to deliver data more uniformly while limiting decoding matrices size. We study the performance of Rest under different network conditions and highlight the underlying trade-offs behind each system parameter. We show that an optimal acknowledgement frequency can be estimated to minimize overhead while meeting system requirements in terms of delivery delay and computational power.

Network Functions Virtualization (NFV) is transforming how networks are architected and network services delivered. The network is more flexible and adaptable, it can scale with traffic demands. To manage video traffic in the network, or get protection from cyber-attacks, Deep Packet Inspection is increasingly deployed at specific locations in the network. The virtual Deep Packet Inspection (vDPI) engines can be dynamically deployed as software on commodity servers within emerging NFV infrastructures. For a network operator, deploying a set of vDPIs over the network is a matter of finding the appropriate placement that meets the traffic management or cyber-security targets (such as the number of inspected flows) and operational cost constraints (license fees, network efficiency or power consumption). In this work, we formulate the vDPI placement problem as a cost minimization problem. The cost captures the different objectives the operator is pursuing. A placement of vDPIs on the network nodes realizes a trade-off between these possibly conflicting goals. We cast the problem as a multi-commodity flow problem and solve it as an Integer Linear Program (ILP). We then devise a centrality-based greedy algorithm and assess its validity by comparing it with the ILP optimal solution on a real data set (GEANT network with 22 nodes and real traffic matrix). We further analyze the scalability of the heuristic by applying it to larger random networks of up to 100 nodes. The results show the network structure and the costs strongly influence time performance. They also show that after a size limit (between 40 to 80 nodes in our case), the execution time increases exponentially due to combinatorial issues. Finally, they demonstrate that the heuristic well approximate the optimal on smaller problem instances.

Software-Defined Networking (SDN) is now envisioned for Wide Area Networks (WAN) and deployed constrained networks. Such networks require a resilient, scalable and easily extensible SDN control plane. In this paper, we propose DISCO, a DIstributed SDN COntrol plane able to cope with the distributed and heterogeneous nature of modern overlay networks and deployed networks. A DISCO controller manages its own network domain, communicates with other DISCO controllers to provide end-to-end network services and share aggregated network-wide information. This east-west communication is based on a lightweight and highly manageable control channel which can self-adapt to network conditions.

Software-Defined Networking (SDN) is now envisioned for Wide Area Networks (WAN) and constrained overlay networks. Such networks require a resilient, scalable and easily extensible SDN control plane. In this paper, we propose DISCO, an extensible DIstributed SDN COntrol plane able to cope with the distributed and heterogeneous nature of modern overlay networks. A DISCO controller manages its own network domain and communicates with other controllers to provide end-to-end network services. This east-west communication is based on a lightweight and highly manageable control channel. We implemented DISCO on top of the Floodlight OpenFlow controller and the AMQP protocol and we evaluated it through an inter-domain topology disruption use case.

In Wireless Sensor Networks (WSNs) for monitoring applications, energy saving and fast data collection are two challenging tasks. Asynchronous radio duty cycling protocols can achieve very low energy consumption in low traffic conditions and they are fault-tolerant to clock drifts. However, they may exhibit a delay degradation due to the decoupled wake-up periods of the nodes. In this paper, we present RAWMAC, a cross-layer approach where RPL, a tree-based routing protocol, orchestrates the asynchronous duty-cycled ContikiMAC MAC layer. The wake-up instants of the nodes are dynamically aligned, with respect to the RPL topology, to minimize the delay for data collection. We implement RAWMAC for the Contiki operating system and we analyze the impact of several key system parameters. Results show that RAWMAC outperforms ContikiMAC in terms of delay for data collection, while keeping the same performance in terms of throughput and energy consumption.

Routing in overlay networks typically involves engineering an overlay topology on top of the Internet to balance traffic along overlay paths so that quality and/or resilience of delivered services are improved. It can be used to reduce latency for delay-sensitive applications. It then consists in selecting, for any pair of nodes, an intermediate overlay node which reduces the latency on this one-hop overlay path against the latency on the direct overlay path between them. In this paper, we propose to optimize the overhead generated by the overlay route computation mechanism by introducing a differentiation between the nodes that are highly used as relay and those that are not. Our approach relies on disseminating at a high frequency the link states with the identified sub-set of nodes and at a lower frequency all the link states. We conduct large experimentations on PlanetLab to evaluate the trade-off between the performances in terms of RTT gain and the reduction of the control overhead compared to the state of the art.

In scenarios like the surveillance of isolated areas, when the border node of a network does not have a permanent connection with the Internet, Wireless Sensor Networks (WSNs) are calling for resilient in-network data storage techniques which minimize the risk of data loss. The efficiency of these techniques can be largely improved exploiting information on the status of the network, such as that used by routing protocols. In particular, one of the most used protocol in Internet of Things (IoT) scenarios is the IPv6 Routing Protocol for Low power and lossy networks (RPL). In this paper, we propose a redundant distributed data storage and retrieval mechanism to increase the resilience and storage capacity of a RPL-based WSN against local memory shortage. We evaluate our approach in the Contiki operating system through extensive analysis with the Cooja simulator.

We propose a transport protocol capable of dynamically adapting to network and receiver properties in multi-destination, multi-channel wireless networks. The key feature of our solution resides in its ability to convey common traffic to a group of users, while at the same time distributing information to each user as quickly as possible. This is achieved by clustering receivers in groups, each group being served at a suitable throughput. We emphasize in this study on the two groups of receivers case. We show analytically and through OMNet++ simulations that groups formation is decided by the wireless link performance and the proportion of receivers constituting each group. Our solution captures dynamically these effects. Indeed, our transport is capable to cope transparently with wireless links changes (i.e specturm handoff) by adapting dynamically its transmission rate and groups composition. It is therefore adapted for point-to-multipoint cognitive radio networks.

Cooperative ITS systems are expected to highly improve the efficiency of road mobility. Wireless communications are used by these systems to disseminate centralized real-time traffic information to radio-equipped vehicles. Current proposals for traffic information dissemination either exploit dedicated cellular transmissions to interested vehicles, or cooperatively relay the information through vehicular ad-hoc networks. However, dedicated cellular transmissions may pose energy cost and traffic scalability issues to network operators. On the contrary, purely ad-hoc solutions may suffer from network disconnections and not always ensure adequate service reliability. To overcome these limitations, this paper introduces RoAHD, a hybrid approach in which a few messages injected through the cellular system are followed by a cooperative multi-hop dissemination in the vehicular network. RoAHD exploits multi-hop road connectivity information obtained at a low channel cost. Thanks to this knowledge, it is capable to operate smart injection decisions to ensure good levels of message delivery.

In this paper, we investigate the ability of using Delay Tolerant Networking (DTN) in Public Safety networks, where bandwidth and storage are constrained. We formalize the problem as a Wardrop equilibrium over a time-discretized graph. Driven by our findings, we propose RECOR, a centralized REsource-Constrained ORacle-based DTN routing mechanism, which spreads the demand across multiple store-carry forward paths to satisfy the node storage and link transport constraints observed in intervention situations. By applying the proposed mechanism to real Bluetooth-based DTN traces, we show that the transmission bottleneck can be compensated, but only up to a certain extent, by increasing storage capacity and delay. We also analyze the benefit of strategies that provide more resources to highly connected nodes (e.g. ambulances and firetrucks) which can then feed incentives and policies for DTN network engineering. Finally, the idea presented here is general and suggests the necessity of trace-driven simulation and specific modeling tools for appropriate design of future DTN resource management policies.

Major wireless operators are nowadays facing network capacity issues in striving to meet the growing demands of mobile users. At the same time, 3G-enabled devices increasingly benefit from ad hoc radio connectivity (e.g., Wi-Fi). In this context of hybrid connectivity, we propose Push-and-track, a content dissemination framework that harnesses ad hoc communication opportunities to minimize the load on the wireless infrastructure while guaranteeing tight delivery delays. It achieves this through a control loop that collects user-sent acknowledgements to determine if new copies need to be reinjected into the network through the 3G interface. Push-and-Track includes multiple strategies to determine how many copies of the content should be injected, when, and to whom. The short delay-tolerance of common content, such as news or road traffic updates, make them suitable for such a system. Based on a realistic large-scale vehicular dataset from the city of Bologna composed of more than 10,000 vehicles, we demonstrate that Push-and-Track consistently meets its delivery objectives while reducing the use of the 3G network by over 90%.

We analyze the dynamics of a mobility data set collected in a pipelined disruption-tolerant network (DTN), a particular class of intermittently-connected wireless networks characterized by a 1-D topology. First, we collected and investigated traces of contact times among thousands of participants of a rollerblading tour in Paris. The data set shows extreme dynamics in the mobility pattern of a large number of nodes. Most strikingly, fluctuations in the motion of the rollerbladers cause a typical accordion phenomenon—the topology expands and shrinks with time, thus influencing connection times and opportunities between participants. Second, we show through an analytical model that the accordion phenomenon, through the variation of the average node degree, has a major impact on the performance of epidemic dissemination. Finally, we test epidemic dissemination and other existing forwarding schemes on our traces, and conclude that routing should adapt to the varying, though predictable, nature of the network. To this end, we propose DA-SW (Density-Aware Spray-and-Wait), a measurement-oriented variant of the spray-and-wait algorithm that tunes, in a dynamic fashion, the number of a message copies to be disseminated in the network. The particularity of DA-SW is that it relies on a set of abaci that represents the three phases of the accordion phenomenon: aggregation, expansion, and stabilization. We show that DA-SW leads to performance results that are close to the best case (obtained with an oracle).

Delay Tolerant Networks (DTN) do not provide any end to end connectivity guarantee. Thus, transporting data over such networks is a tough challenge as most of Internet applications assume a form of persistent end to end connection. While research in DTN has mainly addressed the problem of routing in various mobility contexts with the aim to improve bundle delay delivery and data delivery ratio, little attention has been paid to applications. This paper investigates the support of streaming-like applications over DTN. We identify how DTN characteristics impact on the overall performances of these applications and present Tetrys, a transport layer mechanism, which enables robust streaming over DTN. Tetrys is based on an on the fly coding mechanism able to ensure full reliability without retransmission and fast in-order bundle delivery in comparison to classical erasure coding schemes. We evaluate our Tetrys prototype on real DTN connectivity traces captured from the Rollerblading tour in Paris. Simulations show that on average, Tetrys clearly outperforms all other reliability schemes in terms of bundles delivery service.

This paper addresses the problem of engineering energy-efficient target detection applications using unattended Wireless Sensor Networks (WSNs) for long-lasting surveillance of areas of interest. As battery energy depletion is an issue in this context, an approach consists of switching on and off sensing and communication modules of wireless sensors according to duty cycles. Making these modules work in an intermittent fashion impacts (i) the latency of notification transmission (depending on the communication duty cycle) and (ii) the probability of missed target detection (depending on the number of deployed nodes and the sensing duty cycle). In order to optimize the system parameters according to performance objectives, we first derive an analytical engineering toolkit which evaluates the probability of missed detection (Pmd), the notification transmission latency (D), and the network lifetime (¿) under the assumption of random node deployment. Then, we show how this toolbox can be used to optimally configure system parameters under realistic performance constraints.

Is the temporal dimension alone sufficient to characterize contacts in opportunistic networks? Several studies analyze the temporal aspect of contacts with significant results concerning contact and inter-contact distributions. Nevertheless, only the temporal dimension does not give a complete overview of contact characterization. In this paper, we propose the surround indicator as a metric to exhibit the contact's surrounding environment in opportunistic networks. We evaluate the surround indicator on two existing datasets and show that contacts have too heterogeneous and too unstable surrounds to be considered only in terms of duration. Besides a large variability of the surrounding environment within the duration of a single contact, it is frequent to observe contacts of identical duration that exhibit differences in their surrounds of more than a hundred times.

Mobile wireless ad hoc networks (MANETs) naturally support a traffic mix of elastic and real-time flows but the shared nature and lossy properties of the radio medium make their coexistence challenging. We argue in this paper for a new kind of elastic data transport service which would preserve the quality of real-time priority flows while guaranteeing an acceptable (tunable) end-to-end delivery time of elastic data. We propose to use mechanisms from Delay Tolerant Networking (DTN) to support hop-by-hop data transfer from source to destination and an adaptation of TCP which monitors its aggressiveness towards local VoIP traffic on each hop. The scheme is evaluated in simulation on a simple 4-node scenario and in a more realistic case where doubling data transfer time allows for the support of seven VoIP flows of medium quality against none for standard TCP.

We analyze the dynamics of a mobility dataset collected in a pipelined disruption-tolerant network (DTN), a particular class of intermittently-connected wireless networks characterized by a one-dimensional topology. First, we collected and investigated traces of contact times among a thousand participants of a rollerblading tour in Paris. The dataset shows extreme dynamics in the mobility pattern of a large number of nodes. Most strikingly, fluctuations in the motion of the rollerbladers cause a typical accordion phenomenon - the topology expands and shrinks with time, thus influencing connection times and opportunities between participants. Second, we show through an analytical model that the accordion phenomenon, through the variation of the average node degree, has a major impact on the performance of epidemic dissemination. Finally, we test epidemic dissemination and other existing forwarding schemes on our traces, and argue that routing should adapt to the varying, though predictable, nature of the network. To this end, we propose DA-SW (density-aware spray-and-wait), a measurement-oriented variant of the spray-and-wait algorithm that tunes, in a dynamic fashion, the number of a message copies disseminated in the network. We show that DA-SW leads to performance results that are close to the best case (obtained with an oracle).

The purpose of this work is to bridge the gap between high-end networked devices and wireless networks of ubiquituous and resource-constrained sensors and actuators by extensively applying Service-Oriented Architecture (SOA) patterns. We present a multi-level approach that implements existing SOA standards on higher tiers, and propose a novel protocol stack, WSN-SOA, which brings the benefits of SOA to low capacity nodes without the overhead of XML-based technologies. This solution fully supports network dynamicity, auto-configuration, service discovery, device heterogeneity and interoperability with legacy architectures. As a proof-of-concept, we have studied a surveillance scenario in which the detection of an intruder, conducted within the range of a network of wireless sensors (e.g., MICAz from Crossbow), leads to the automatic triggering of tracking activities by a Linux-powered network camera and of alerts and video streams toward a control room.

We propose in this work a single copy and multi-hop opportunistic routing scheme for sparse delay tolerant networks (DTNs). The scheme uses as only input the estimates of the average inter-contact times between the nodes in the network. Defined as the fixed point of a recursive process, it aims at minimizing delivery time in case of independent exponential pairwise inter-contacts. The two properties of loop-free forwarding and polynomial convergence make the scheme workable for routing in DTNs. The routing performances of the scheme are evaluated on three publicly available reference data sets. Comparisons with well known single-copy schemes, including MED and thetwohoprelay strategy, consistently demonstrate improvements for both delivery ratio and delay.

We consider the challenge of enhancing sensor networks for surveillance and global security with increased distributed data processing capabilities, including multi-sensor fusion, data aggregation or mining, and rule-based alert generation. We advocate a novel architecture that will enable the creation of more resilient and complex monitoring applications. We exemplify its benefits in a chemical accident scenario. The architecture introduces new processing nodes in the field and derives the requirements for the software they will run. We propose to consider the use of a service oriented architecture (SOA) to program and deploy the data processing applications. We analyze existing and on-going work within the Web Services community and conclude that it is possible to implement the architecture with an appropriate combination of COTS (commercial off-the-shelf software components). We conclude with our plans to move forward in this direction and validate the approach on a hardware and software testbed.

Abstract Because a delay‐tolerant network (DTN) can often be partitioned, routing is a challenge. However, routing benefits considerably if one can take advantage of knowledge concerning node mobility. This paper addresses this problem with a generic algorithm based on the use of a high‐dimensional Euclidean space, that we call MobySpace, constructed upon nodes' mobility patterns. We provide here an analysis and a large‐scale evaluation of routing schemes using MobySpace by replaying real mobility traces. The specific MobySpace evaluated is based on the frequency of visits of nodes to each possible location. We present simulation results for single‐copy and multi‐copy routing strategies that use MobySpace as a means to route bundles or to control flooding. We show that routing based on MobySpace can achieve good performance compared to a number of common algorithms. Copyright © 2007 John Wiley & Sons, Ltd.

Because a delay tolerant network (DTN) can often be partitioned, routing is a challenge. However, routing benefits considerably if one can take advantage of knowledge concerning node mobility. This paper addresses this problem with a generic algorithm based on the use of a high-dimensional Euclidean space, that we call MobySpace, constructed upon nodes' mobility patterns. We provide here an analysis and a large scale evaluation of this routing scheme in the context of ambient networking by replaying real mobility traces. The specific MobySpace evaluated is based on the frequency of visits of nodes to each possible location. We show that routing based on MobySpace can achieve good performance compared to that of a number of standard algorithms, especially for nodes that are present in the network a large portion of the time. We determine that the degree of homogeneity of node mobility patterns has a high impact on routing. And finally, we study the ability of nodes to learn their own mobility patterns.