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.

The emerging LoRa technology is quickly becoming the de facto standard for Low Power Wide Area Networks upon unlicensed frequencies. Herein, the LoRaWAN medium access sets up a lightweight network architecture able to connect very low power devices to the Internet. Traffic flows in such deployments can be variable, or even unpredictable, depending on the needs of the monitoring applications using the network. As an example, to track air quality in cities, some applications can trigger an increased need of fine grained pollution data during the daytime. However, the network capacity is currently limited by the default LoRaWAN pure ALOHA access scheme. A time synchronized scheduled access would considerably improve the achievable throughput, at the cost of an increased power consumption for synchronization duties. In such a context, this contribution introduces the traffic-aware energy efficient Medium Access Control (TREMA) protocol for LoRa networks, capable of seamlessly switching between asynchronous and synchronous schemes according to the probed traffic variations. TREMA ultimately increases the maximum capacity of LoRa deployments while always selecting the most energy efficient access scheme.

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 consider the problem of allocating a wireless channel to mobile users moving on a straight road. The objective is to maximize a given function of the total data transmitted. We develop a model within the multi-armed bandit framework and formulate an optimization problem under the constraint that at most one user can be served at a time. We solve the relaxed optimization problem, in which one user is served on the average, and show it to be indexable. A simple and easy-to-compute expression is given for the Whittle index. We then propose a heuristic policy for the original optimization problem using Whittle's index policy. The proposed heuristic is shown to perform well compared to some other heuristics in various settings including dynamic scenarios with arrivals of new users and the presence of heterogeneous users.

Fragmentation of expensive resources, e.g., the spectrum for wireless services, between providers can introduce inefficiencies in resource utilization and worsen overall system performance. In such cases, resource pooling between independent service providers can be used to improve performance. However, for providers to agree to pool their resources, the arrangement has to be mutually beneficial. The traditional notion of resource pooling, which implies complete sharing, need not have this property. For example, under full pooling, one of the providers may be worse off and hence has no incentive to participate. In this paper, we propose partial resource sharing models as a generalization of full pooling, which can be configured to be beneficial to all participants. We formally define and analyze two partial sharing models between two service providers, each of which is an Erlang-B loss system with the blocking probabilities as the performance measure. We show that there always exist partial sharing configurations that are beneficial to both providers, irrespective of the load and the number of circuits of each of the providers. A key result is that the Pareto frontier has at least one of the providers sharing all its resources with the other. Furthermore, full pooling may not lie inside this Pareto set. The choice of the sharing configurations within the Pareto set is formalized based on the bargaining theory. Finally, large system approximations of the blocking probabilities in the quality-efficiency-driven regime are presented.

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.

Low Power Wide Area Networks (LPWAN) technologies have recently triggered many research efforts and standardization activities due to the inherent possibility of both providing long range wireless communications and guaranteeing a long life for very cheap sensing devices. At the same time, the increasing interest of telco operators into such kind of networks is due to the wide range of applications that can be supported by LPWAN, including low power radiolocation. Among the available LPWAN access schemes, LoRaWAN protocols enable a hierarchical network structure over sub-gigahertz unlicensed spectra, with coordinated gateways listening for data delivered by battery-operated end-devices. A proper positioning scheme for gateways enables radiolocation duties through multilateration. However, the LoRaWAN Aloha-based capacity puts an implicit restriction on the radiolocation performances, while explicit duty cycle policies further limit the resource availability on unlicensed frequencies. To characterize the throughput of low power radiolocation applications, this contribution introduces a scalable and detailed probability model, while validating the same through a large simulation campaign. The results clearly show that the availability of multiple channel enhances the capacity of LoRaWAN networks while insuring predictable time delay between consecutive successful radiolocation events.

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.

Load balancing with various types of load information has become a key component of modern communication and information systems. In many systems, characterizing precisely the blocking probability allows to establish a performance trade-off between delay and losses. We address here the problem of giving robust performance bounds based on the study of the asymptotic behavior of the insensitive load balancing schemes when the number of servers and the load scales jointly. These schemes have the desirable property that the stationary distribution of the resulting stochastic network depends on the distribution of job sizes only through its mean. It was shown that they give good estimates of performance indicators for systems with finite buffers, generalizing henceforth Erlang's formula whereas optimal policies are already theoretically and computationally out of reach for networks of moderate size.

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.

In this paper we obtain the scaling law for the mean broadcast time of a file in a P2P network with an initial population of N nodes. In the model, at Poisson rate lambda a node initiates a contact with another node chosen uniformly at random. This contact is said to be successful if the contacted node possesses the file, in which case the initiator downloads the file and can later upload it to other nodes. In a network with altruistic nodes (i.e., nodes do not leave the network) we show that the mean broadcast time is O(log(N)). In a network with free-riding nodes, our main result shows that a O(log(N)) mean broadcast time can be achieved if nodes remain connected to the network for the duration of at least one more contact after downloading the file, otherwise a significantly worse O(N) time is required to broadcast the file.

We consider an uplink power control problem where each mobile wishes to maximize its throughput (which depends on the transmission powers of all mobiles) but has a constraint on the average power consumption. A finite number of power levels are available to each mobile. The decision of a mobile to select a particular power level may depend on its channel state. We consider two frameworks concerning the state information of the channels of other mobiles: (i) the case of full state information and (ii) the case of local state information. In each of the two frameworks, we consider both cooperative as well as non-cooperative power control. We manage to characterize the structure of equilibria policies and, more generally, of best-response policies in the non-cooperative case. We present an algorithm to compute equilibria policies in the case of two non-cooperative players. Finally, we study the case where a malicious mobile, which also has average power constraints, tries to jam the communication of the other mobile. Our results are illustrated and validated through various numerical examples.

We study an adaptive window protocol (AWP) with a general increase and decrease profile in the presence of window dependent random losses. We derive a steady-state Kolmogorov equation and obtain its solution in analytic form. We obtain some stochastic ordering relations for a protocol with different bounds on window. A closed form necessary and sufficient stability condition using the stochastic ordering for the window process is established. Finally, we apply the general results to particular TCP versions such as NEW Reno TCP, scalable TCP and Highspeed TCP. We observe that Highspeed TCP can be used to approximate almost any kind of window behavior by varying only one design parameter.

The multiplicative increase multiplicative decrease (MIMD) congestion control algorithm in the form of scalable TCP has been proposed for high speed networks. We study fairness among sessions sharing a common bottleneck link, where one or more sessions use the MIMD algorithm. Losses, or congestion signals, occur when the capacity is reached but could also be initiated before that. Both synchronous as well as asynchronous losses are considered. In the asynchronous case, only one session suffers a loss at a loss instant. Two models are then considered to determine which source looses a packet: a rate dependent model in which the packet loss probability of a session is proportional to its rate at the congestion instant, and the independent loss rate model. We first study how two MIMD sessions share the capacity in the presence of general combinations of synchronous and asynchronous losses. We show that, in the presence of rate dependent losses, the capacity is fairly shared whereas rate independent losses provide high unfairness. We then study inter protocol fairness: how the capacity is shared in the presence of synchronous losses among sessions some of which use additive increase multiplicative decrease (AIMD) protocols whereas the others use MIMD protocols.

We study a decision problem faced by an energy limited wireless device that operates in discrete time. There is some external arrival to the device's transmit buffer. The possible decisions are: a) to serve some of the buffer content; b) to reorder a new battery after serving the maximum possible amount that it can; or c) to remain idle so that the battery charge can increase owing to diffusion process (which is possible in some commercially available batteries). We look at open and closed-loop controls of the system. The closed-loop control problem is a using the framework of Markov decision processes. We address both finite and infinite horizon discounted costs as well as average cost minimization problems. Without using any second order characteristics, we obtain results that include i) optimality of bang-bang control, ii) the optimality of threshold based policies, iii) parametric monotonicity of the threshold, and iv) uniqueness of the threshold. For the open-loop control setting we use recent advances in application of multimodular functions to establish optimality of bracket sequence based control.

In this paper, we propose a protocol for routing in Bluetooth scatternets. The protocol uses the available battery power in the Bluetooth (BT) devices as a cost metric in choosing the routes. We evaluate the throughput performance as a function of packet arrival rate and number of piconets. A throughput of about 120 kbps/piconet is shown to be achieved in a 5-piconet scatternet. We propose two techniques, namely a) battery power level based master-slave switch and b) distance based power control, to increase the network lifetime in scatternets. The master-slave switch technique is motivated by the fact that a piconet master has to handle the packet transmissions to/from all its slaves, and hence may drain its battery soon. We propose a role switching idea where each BT device in a piconet may have to play the master role depending on its available battery power. In the second technique, we propose that the BT devices choose their transmit powers based on their distances from their respective masters. Our performance results show that a considerable gain in network lifetime can be achieved using these two power saving techniques.

In this paper, we analyze the performance of battery power management schemes in wireless mobile devices using a queueing theory approach. We model the battery as a server with finite service capacity and data packets as customers to be served. With an intent to exploit the recharging capability of the battery when left idle, we allow the battery to go on intentional vacations during which the battery can recharge itself. The recharge thus built up can effectively increase the number of customers served (in other words, battery life can be extended). Such improved battery life performance would, however, come at the expense of increased packet delay performance. We quantify the battery life gain versus delay performance trade-off in this approach through analysis and simulations. By considering a continuous recharge model of the battery, we derive expressions for the number of customers served and the mean delay for an M/GI/1 queueing system without and with server vacations. We show that allowing intentional vacations during busy periods helps to increase battery life, and that this approach can be beneficial when applied to the traffic of delay-tolerant applications. We also propose a packet delay constrained power saving algorithm that will exploit the recharge phenomenon when packet delay constraints are imposed.