We consider the coflow scheduling problem in the non-clairvoyant setting assuming flow sizes are random variables that follow some probability distribution. The goal is to minimize the weighted average completion time of coflows in expectation. We first obtain inequalities for this problem that are valid for all non-anticipative order-based rate-allocation policies and define a polyhedral relaxation of the performance space of such scheduling policies. This relaxation is used to analyze the performance of a simple priority policy in which the priority order is computed by Sincronia from expected flow sizes instead of their unknown actual values. We establish an upper bound on the approximation ratio of this priority policy with respect to the optimal priority policy for arbitrary probability distributions of flow sizes (with finite first and second moments). Tighter upper bounds are obtained for some specific distributions. Extensive numerical results suggest that performance of the proposed policy is much better than the upper bound.

Datacenter networks commonly facilitate the transmission of data in distributed computing frameworks through coflows, which are collections of parallel flows associated with a common task. Most of the existing research has concentrated on scheduling coflows to minimize the time required for their completion, i.e., to optimize the average dispatch rate of coflows in the network fabric. Nevertheless, modern applications often produce coflows that are specifically intended for online services and mission-crucial computational tasks, necessitating adherence to specific deadlines for their completion. In this paper, we introduce$\mathtt {WDCoflow}$, a new algorithm to maximize the weighted number of coflows that complete before their deadline. By combining a dynamic programming algorithm along with parallel inequalities, our heuristic solution performs at once coflow admission control and coflow prioritization, imposing a$\sigma$-order on the set of coflows. With extensive simulation, we demonstrate the effectiveness of our algorithm in improving up to$3\times$more coflows that meet their deadline in comparison the best SoA solution, namely$\mathtt {CS\rm{-}MHA}$. Furthermore, when weights are used to differentiate coflow classes,$\mathtt {WDCoflow}$is able to improve the admission per class up to$4\times$, while increasing the average weighted coflow admission rate.

Resource allocation algorithms in wireless networks can require solving complex optimization problems at every decision epoch. For large scale networks, when decisions need to be taken on time scales of milliseconds, using standard convex optimization solvers for computing the optimum can be a time-consuming affair that may impair real-time decision making . In this paper, we propose to use Data-driven and Deep Feedforward Neural Networks (DFNN) for learning the relation between the inputs and the outputs of two such resource allocation algorithms that were proposed in Nguyen et al. (2019, 2020). On numerical examples with realistic mobility patterns, we show that the learning algorithm yields an approximate yet satisfactory solution with much less computation time.

Network Function Virtualization (NFV) simplifies the deployment of network services by leveraging virtualization technologies to make the management of network functions more flexible and cost efficient. The deployment of these services requires the allocation of Virtual Network Function - Forwarding Graphs (VNF-FGs), which implies placing and chaining VNFs according to the requests of VNF-FGs. In this paper, we consider the offline allocation of VNF-FGs problem to improve resource utilization and reduce total costs. We focus on how VNF-FG demands are routed so as to optimize resource utilization without adding capacity to the infrastructure. Given a non-linear cost function associated to each network resource, we formulate the problem as a non-linear single-path routing problem in an extended graph. Then, we propose to adapt a single-path routing heuristic algorithm inspired from game theory to solve it. We show that this algorithm converges and establishes its approximation ratio in a number of cases. Experimental results obtained for different network topologies and different cost functions show that this algorithm provides very good quality solutions with substantially lower computing times compared to the optimal solution.

We consider the SFC embedding (SFCE) problem in the Slice as a Service (SlaaS) model. In this model, a slice provider leases resources from multiple cloud and network providers in order to instantiate the Service Function Chain (SFC) requested by a slice tenant. As the slice provider has no visibility on the infrastructures of the resource providers, in which resources may be purchased and released quite rapidly, it has to query them to determine what are the possible allocations and their costs. We show that when there are many resource providers and many VNFs composing the SFC, the number of queries to be made for discovering a minimum cost SFC embedding grows quickly, leading to excessively long deployment times. In order to reduce the latter quantity, we propose to query resource providers strategically, rather than collecting the information on all possible allocations at once. We provide bounds on the number of queries to be made in this approach, and propose to exploit a Shortest Path Discovery algorithm in order to reduce this number of queries and thus the SFC deployment time. Our numerical results suggest that this algorithm is fairly efficient, and that the deployment times can be significantly shortened, in particular when initial estimates of allocation costs can be provided by the slice provider.

Fog Computing brings resources closer to the end-user and improves user experience. Tasks with stringent QoS requirements can be processed locally in the Edge while the more elastic ones can be sent to the Cloud. For the benefits of this flexible architecture to be seen, task allocation algorithms should be dynamic and adapt to the load in the Fog and in the Cloud. Using a discrete-event simulation approach, we evaluate the performance of four simple adaptive algorithms based on congestion estimation and compare them with the standard nearest node algorithm that uses non adaptive routing. We consider a setting in which base stations (access nodes) forward traffic to computing nodes (Fog and Cloud nodes) in a distributed way without coordination and sharing of state-information between the access and computing nodes. The algorithms are tested for their adaptability to sudden changes in the arrival rate of requests (to model peak hours) as well as robustness to the variance of the request-size distributions to understand the advantages and drawbacks of each of them. They are shown to perform well in scenarios with and without offloading.

We consider a routing overlay in which the delay of a path can be obtained at some fixed cost by sending probe packets, and investigate the joint minimization of the probing cost and the routing delay. Assuming that link delays are modelled by Markov chains, this problem can be cast as a Markov Decision Process (MDP). Unfortunately, computing the exact solution of this MDP is prohibitively expensive due to the well-known "curse of dimensionality". In this work we propose two scalable approaches that are fast enough to provide efficient solutions on practical time scales. We analyze the complexity of both approaches, and evaluate their accuracy in small synthetic scenarios for which the optimal monitoring policy can be computed. Finally, the robustness and the scalability of the proposed solutions are analyzed using real delay data collected over the Internet.

We investigate the asymptotic performance of a reward incentive Delay Tolerant Network based on mean field limit. We consider a two-hop network with one source and one destination and N relays. The source is backlogged and sends messages to the destination by forwarding to the relays it meets. For each message, there is a promised reward for the first one who successfully transmits it to the destination. It was shown in a previous work, the optimal policy for the relays is of thresholds type (a relay will accept a message until certain time and drop it after a second threshold). When the second threshold in infinite, we give the mean-field ODE and show that all the messages have the same probability of success. When the second threshold is finite we only give an ODE approximation since the dynamics are not Markovian.

This article is devoted to nonlinear single‐path routing problems, which are known to be NP‐hard even in the simplest cases. For solving these problems, we propose an algorithm inspired from Game Theory in which individual flows are allowed to independently select their path to minimize their own cost function. We design the cost function of the flows so that the resulting Nash equilibrium of the game provides an efficient approximation of the optimal solution. We establish the convergence of the algorithm and show that every optimal solution is a Nash equilibrium of the game. We also prove that if the objective function is a polynomial of degree , then the approximation ratio of the algorithm is . Experimental results show that the algorithm provides single‐path routings with modest relative errors with respect to optimal solutions, while being several orders of magnitude faster than existing techniques. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 52–66 2017

A central problem in Delay Tolerant Networks (DTNs) is to persuade mobile nodes to participate in relaying messages. Indeed, the delivery of a message incurs a certain number of costs for a relay. We consider a two-hop DTN in which a source node, wanting to get its message across to the destination as fast as possible, promises each relay it meets a reward. This reward is the minimum amount that offsets the expected delivery cost, as estimated by the relay from the information given by the source (number of existing copies of the message, age of these copies). A reward is given only to the relay that is the first one to deliver the message to the destination. We show that under fairly weak assumptions, the expected reward the source pays remains the same irrespective of the information it conveys, provided that the type of information does not vary dynamically over time. On the other hand, the source can gain by adapting the information it conveys to a meeting relay. For the particular cases of two relays or exponentially distributed intercontact times, we give some structural results on the optimal adaptive policy.

Cloud systems include both locally based servers at user premises and remote servers and multiple Clouds that can be reached over the Internet. This paper describes a smart distributed system that combines local and remote Cloud facilities. It operates with a task allocation system that takes decisions to allocate tasks dynamically to the service that offers the best overall Quality of Service and a routing overlay which optimizes network delay for data transfer between clouds. Internet-scale experiments exhibit the effectiveness of our approach in adaptively distributing workload across multiple clouds.

This paper uses big data and machine learning for the real-time management of Internet scale quality-of-service (QoS) route optimisation with an overlay network. Based on the collection of data sampled every 2 min over a large number of source-destinations pairs, we show that intercontinental Internet protocol (IP) paths are far from optimal with respect to QoS metrics such as end-to-end round-trip delay. We, therefore, develop a machine learning-based scheme that exploits large scale data collected from communicating node pairs in a multihop overlay network that uses IP between the overlay nodes, and selects paths that provide substantially better QoS than IP. Inspired from cognitive packet network protocol, it uses random neural networks with reinforcement learning based on the massive data that is collected, to select intermediate overlay hops. The routing scheme is illustrated on a 20-node intercontinental overlay network that collects some 2 × 106measurements per week, and makes scalable distributed routing decisions. Experimental results show that this approach improves QoS significantly and efficiently.

A central problem in Delay Tolerant Networks (DTNs) is to persuade mobile nodes to participate in relaying messages. Indeed, the delivery of a message incurs a certain number of costs for a relay. We consider a two-hop DTN in which a source node, wanting to get its message across to the destination as fast as possible, promises each relay it meets a reward. This reward is the minimum amount that offsets the expected delivery cost, as estimated by the relay from the information given by the source (number of existing copies of the message, age of these copies). A reward is given only to the relay that is the first one to deliver the message to the destination. For two relays and exponentially distributed inter-contact times, we show that the expected reward the source pays remains the same irrespective of the information it conveys, provided that the type of information does not vary dynamically over time. On the other hand, the source can gain by adapting the information that it conveys to a meeting relay.

Price of anarchy is an oft-used worst-case measure of the inefficiency of noncooperative decentralized architectures. For a noncooperative load-balancing game with two classes of servers and for a finite or infinite number of dispatchers, we show that the price of anarchy is an overly pessimistic measure that does not reflect the performance obtained in most instances of the problem. We explicitly characterize the worst-case traffic conditions for the efficiency of noncooperative load-balancing schemes and show that, contrary to a common belief, the worst inefficiency is in general not achieved in heavy traffic.

The problem of scheduling strictly periodic tasks, that is tasks that have to be executed at constant time intervals over an infinite time horizon, naturally arises in real-time video signal processing and in the design of critical embedded systems. We address this problem assuming that the objective is to find a schedule that maximizes the idle times between the task executions while ensuring that they do not overlap in time. This will allow an evolution margin for task budget times, should it be required in the future. We first consider the uniprocessor scheduling problem for which we propose an approximation algorithm inspired from Game Theory. In this algorithm, tasks take turns in some fixed order and at its turn a task selects its offset to maximize its own utility function which is related to evolution margins of the tasks. We prove the convergence of the algorithm to an equilibrium point where no task has any incentive to unilaterally deviate. Although the equilibrium point need not necessarily be unique, we prove that there exists at least one equilibium point that is also optimal. We also provide an efficient scheme to compute the best-response offset of a task. We then show that this best-response algorithm can be naturally extended to the multiprocessor case by allowing tasks to select a processor in addition to an offset on this processor. Numerical experiments show that this algorithm is much quicker than an exact algorithm presented in prior work while at the same time it generates periodic schedules with modest relative errors.

We investigate the price of anarchy of a load balancing game with K dispatchers. The service rates and holding costs are assumed to depend on the server, and the service discipline is assumed to be processor-sharing at each server. The performance criterion is taken to be the weighted mean number of jobs in the system, or equivalently, the weighted mean sojourn time in the system. For this game, we first show that, for a fixed amount of total incoming traffic, the worst-case Nash equilibrium occurs when each player routes exactly the same amount of traffic, i.e., when the game is symmetric. For this symmetric game, we provide the expression for the loads on the servers at the Nash equilibrium. Using this result we then show that, for a system with two or more servers, the price of anarchy, which is the worst-case ratio of the global cost of the Nash equilibrium to the global cost of the centralized setting, is lower bounded by K/(2¿K-1) and upper bounded by ¿K, independently of the number of servers.

This paper studies a topical capacitated network design problem that arises in the telecommunication industry. In this problem, given point-to-point demand between various pairs of nodes, a minimum cost survivable network must be designed by installing capacitated equipments (routers, line cards, ...) on nodes as well as link facilities on arcs. This realistic problem finds its motivation in the rapidly developing field of telecommunication networks and the introduction of fiber-optic technology. It is, in particular, faced by the network designer whenever a new network is set up. To the best of our knowledge, this is the first work that addresses this capacitated network design problem where equipments, such as routers and lines cards, have to be settled on network nodes. We present a Tabu Search heuristic to find a solution that minimizes the total network cost. Numerical results are provided for randomly generated networks and networks coming from real-word applications.

Session Initiation Protocol (SIP) is a new signaling protocol used to establish and release sessions between end users. Using SIP over MPLS networks offers new possibilities to enhance network performance and QoS (Quality of Service) perceived by users. In this paper we evaluate a session level approach to enhance QoS in DiffServ domain. We implement scheduling mechanisms for TCP sessions based on mean rate, size and duration. Dynamic declassing of TCP sessions and bandwidth sharing with WFQ system are discussed and tested. These mechanisms are implemented in the SIP Proxy server of the SIP architecture.