Search

A key challenge in designing load balancing strategies is to achieve low delay in large-scale systems while only using minimal communication overhead. Motivated by these issues, we introduce a novel scheme in which the dispatcher becomes aware of idle servers without any explicit communication from either side, using absence of messages at predefined time instants. The proposed scheme achieves provably vanishing queueing delays while using strictly less than one message per job on average.

Load balancing plays a critical role in efficiently dispatching jobs in parallel-server systems such as cloud networks and data centers. A fundamental challenge in the design of load balancing algorithms is to achieve an optimal trade-off between delay performance and implementation overhead (e.g. communication or memory usage). This trade-off has primarily been studied so far from the angle of the amount of overhead required to achieve asymptotically optimal performance, particularly vanishing delay in large-scale systems. In contrast, in the present paper, we focus on an arbitrarily sparse communication budget, possibly well below the minimum requirement for vanishing delay, referred to as the hyper-scalable operating region. Furthermore, jobs may only be admitted when a specific limit on the queue position of the job can be guaranteed. The centerpiece of our analysis is a universal upper bound for the achievable throughput of any dispatcher-driven algorithm for a given communication budget and queue limit. We also propose a specific hyper-scalable scheme which can operate at any given message rate and enforce any given queue limit, while allowing the server states to be captured via a closed product-form network, in which servers act as customers traversing various nodes. The product-form distribution is leveraged to prove that the bound is tight and that the proposed hyper-scalable scheme is throughput-optimal in a many-server regime given the communication and queue limit constraints. Extensive simulation experiments are conducted to illustrate the results.

Motivated by emerging Internet-of-Things (IoT) applications and smart building environments, we analyze the performance of large-scale symmetric polling systems where the number of queues grows large. We consider a scenario in which the total arrival rate is kept fixed and the individual switch-over time and service time distributions remain the same. This asymptotic regime leads to cycles of infinite length and queue lengths with non-trivial distributions. We show that for most traditional service policies the scaled cycle times converge to a deterministic value in the limit, which in turn implies that the queue lengths at the various nodes become asymptotically independent. Using these insights, we find that the behavior of individual queues simplifies to that of a discrete-time bulk service queue in the limit, so that the marginal queue length and waiting-time distributions become considerably easier to analyze. Additionally, we propose a new flexible k -limited service discipline aimed at striking a good balance between short mean queue lengths and predictable cycle times for deadline-critical applications.

We investigate the stability condition for redundancy- d systems where each of the servers follows a processor-sharing (PS) discipline. We allow for generally distributed job sizes, with possible dependence among the d replica sizes being governed by an arbitrary joint distribution. We establish that for homogeneous servers the stability condition for the associated fluid-limit model is characterized by the expectation of the minimum of d replica sizes being less than the mean interarrival time per server. In the special case of identical replicas, the stability condition is insensitive to the job size distribution given its mean, and the stability threshold is inversely proportional to the number of replicas. In the special case of i.i.d. replicas, the stability threshold decreases (increases) in the number of replicas for job size distributions that are NBU (NWU). We also discuss the extension to heterogeneous servers. For heavy-tailed job sizes we characterize the tail behavior of the response time distribution. In particular, for regularly varying job sizes with tail index − ν it is shown that the tail index of the response time equals − ν and − d ν for identical and i.i.d. replicas, respectively.

A classical sampling strategy for load balancing policies is power-of-two, where any server pair is sampled with equal probability. This does not cover practical settings with assignment constraints which force non-uniform sampling. While intuition suggests that non-uniform sampling adversely impacts performance, this was only supported through simulations, and rigorous statements have remained elusive. Building on product-form distributions for redundancy systems, we prove the stochastic dominance of uniform sampling for a four-server system as well as arbitrary-size systems in light traffic.

A Network Inventory Manager (NIM) is a software solution that scans, processes and records data about all devices in a network. We consider the problem faced by a NIM that can send out a limited number of probes to track changes in a large, dynamic network. The underlying change rate for the Network Elements (NEs) is unknown and may be highly non-uniform. The NIM should concentrate its probe budget on the NEs that change most frequently with the ultimate goal of minimizing the weighted Fraction of Stale Time (wFOST) of the inventory. However, the NIM cannot discover the change rate of a NE unless the NE is repeatedly probed.We develop and analyze two algorithms based on Reinforcement Learning to solve this exploration-vs-exploitation problem. The first is motivated by the Thompson Sampling method and the second is derived from the Robbins-Monro stochastic learning paradigm. We show that for a fixed probe budget, both of these algorithms produce a potentially unbounded improvement in terms of wFOST compared to the baseline algorithm that divides the probe budget equally between all NEs. Our simulations of practical scenarios show optimal performance in minimizing wFOST while discovering the change rate of the NEs.

We consider job dispatching in systems with N parallel servers. In redundancy- d policies, replicas of an arriving job are assigned to d ≤ N servers selected uniformly at random (without replacement) with the objective to reduce the delay. We introduce a quite general workload model, in which job sizes have some probability distribution while the speeds (slowdown factors) of the various servers for a given job are allowed to be inter-dependent and non-identically distributed. This allows not only for inherent speed differences among different servers, but also for affinity relations. We further propose two novel redundancy policies, so-called delta-probe- d policies, where d probes of a fixed, small, size Δ are created for each incoming job, and assigned to d servers selected uniformly at random. As soon as the first of these d probe tasks finishes, the actual job is assigned for execution – with the same speed – to the corresponding server and the other probe tasks are abandoned. We also consider a delta-probe- d policy in which the probes receive preemptive-resume priority over regular jobs. The aim of these policies is to retain the benefits of redundancy- d policies while accounting for systematic speed differences and mitigating the risks of running replicas of the full job simultaneously for long periods of time. Analytical and numerical results are presented to evaluate the effect of both probing policies on the job latency, and to illustrate the potential performance improvements.

Random-access algorithms such as the CSMA protocol provide a popular mechanism for distributed medium access control in wireless networks. In saturated-buffer scenarios the joint activity process in such random-access networks has a product-form stationary distribution which provides useful throughput estimates for persistent traffic flows. However, these results do not capture the relevant performance metrics in unsaturated-buffer scenarios, which in particular arise in an IoT context with highly intermittent traffic sources. Mean-field analysis has emerged as a powerful approach to obtain tractable performance estimates in such situations, and is not only mathematically convenient, but also relevant as wireless networks grow larger and denser with the emergence of IoT applications. A crucial requirement for the classical mean-field framework to apply however is that the node population can be partitioned into a finite number of classes of statistically indistinguishable nodes. The latter condition is a severe restriction since nodes typically have different locations and hence experience different interference constraints. Motivated by the above observations, we develop in the present paper a novel mean-field methodology which does not rely on any exchangeability property. Since the spatiotemporal evolution of the network can no longer be described through a finite-dimensional population process, we adopt a measure-valued state description, and prove that the latter converges to a deterministic limit as the network grows large and dense. The limit process is characterized in terms of a system of partial-differential equations, which exhibit a striking local-global-interaction and time scale separation property. Specifically, the queueing dynamics at any given node are only affected by the global network state through a single parsimonious quantity. The latter quantity corresponds to the fraction of time that no activity occurs within the interference range of that particular node in case of a certain static spatial activation measure. Extensive simulation experiments demonstrate that the solution of the partial-differential equations yields remarkably accurate approximations for the queue length distributions and delay metrics, even when the number of nodes is fairly moderate.

Load balancing algorithms play a vital role in enhancing performance in data centers and cloud networks. Due to the massive size of these systems, scalability challenges, and especially the communication overhead associated with load balancing mechanisms, have emerged as major concerns. Motivated by these issues, we introduce and analyze a novel class of load balancing schemes where the various servers provide occasional queue updates to guide the load assignment. We show that the proposed schemes strongly outperform JSQ( d ) strategies with comparable communication overhead per job, and can achieve a vanishing waiting time in the many-server limit with just one message per job, just like the popular JIQ scheme. The proposed schemes are particularly geared however towards the sparse feedback regime with less than one message per job, where they outperform corresponding sparsified JIQ versions. We investigate fluid limits for synchronous updates as well as asynchronous exponential update intervals. The fixed point of the fluid limit is identified in the latter case, and used to derive the queue length distribution. We also demonstrate that in the ultra-low feedback regime the mean stationary waiting time tends to a constant in the synchronous case, but grows without bound in the asynchronous case.

We consider the problem of optimal rate allocation and admission control for adaptive video streaming sessions in wireless networks with user dynamics. The central aim is to achieve an optimal tradeoff between several key objectives: maximizing the average rate utility per user, minimizing the temporal rate variability, and maximizing the number of users supported. We derive sample path upper bounds for the long-term net utility rate in terms of either a linear program or a concave optimization problem, depending on whether the admissible rate set is discrete or continuous. We then show that the upper bounds are asymptotically achievable in large-scale systems by policies which either deny access to a user or assign it a fixed rate for its entire session, without relying on any advance knowledge of the duration. Moreover, the asymptotically optimal policies exhibit a specific structure, which allow them to be characterized through just a single variable, and have the further property that the induced offered load is unity. We exploit the latter insights to devise parsimonious online algorithms for learning and tracking the optimal rate assignments and establish the convergence of these algorithms. Extensive simulation experiments demonstrate that the proposed algorithms perform well, even in relatively small-scale systems.

We examine a canonical scenario where several wireless data sources generate sporadic delay-sensitive messages that need to be transmitted to a common access point. The access point operates in a time-slotted fashion, and can instruct the various sources in each slot with what probability to transmit a message, if they have any. When several sources transmit simultaneously, the access point can detect a collision, but is unable to infer the identities of the sources involved. While the access point can use the channel activity observations to obtain estimates of the queue states at the various sources, it does not have any explicit queue length information otherwise. We explore the achievable delay performance in a regime where the number of sources n grows large while the relative load remains fixed. This scaling is particularly pertinent in Internet of Things (IoT) scenarios, where a key challenge is to achieve low delay when the overall traffic activity is dispersed across massive numbers of highly intermittent sources. We establish that, under any medium access algorithm without queue state information, the average delay must be at least of the order of n slots when the load exceeds some threshold λ* < 1$. This demonstrates that bounded delay can only be achieved if a positive fraction of the system capacity is sacrificed. Furthermore, we introduce a scalable Two-Phase algorithm for low-delay IoT applications which achieves a delay upper bounded uniformly in n when the load is below e -1 , and a delay of the order of n slots when the load is between e -1 and 1. Additionally, this algorithm provides robustness against correlated source activity, which is also prevalent in IoT scenarios.

We consider a system of N parallel queues with unit exponential service rates and a single dispatcher where tasks arrive as a Poisson process of rate λ( N ). When a task arrives, the dispatcher assigns it to a server with the shortest queue among d ( N ) ≤ N randomly selected servers. This load balancing policy is referred to as a power-of- d ( N ) or JSQ( d ( N )) scheme, and subsumes the Join-the-Shortest Queue (JSQ) policy as a crucial special case for d ( N ) = N . We construct a coupling to bound the difference in the queue length processes between the JSQ policy and an arbitrary value of d ( N ). We use the coupling to derive the fluid limit in the regime where λ( N )/ N → λ < 1 and d ( N )→ ∞ as N → ∞, along with the corresponding fixed point. The fluid limit turns out not to depend on the exact growth rate of d ( N ), and in particular coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit in the regime where ( N --λ( N ))/ √ N → β > 0 and d ( N )/ √ N log N → ∞ as N → ∞ corresponds to that for the JSQ policy. These results indicate that the stochastic optimality of the JSQ policy can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O( N ) and O(√ N ), respectively.

Random-access algorithms such as the Carrier-Sense Multiple-Access (CSMA) protocol provide a popular mechanism for distributed medium access control in large-scale wireless networks. In recent years fairly tractable models have been shown to yield remarkably accurate throughput estimates in scenarios with saturated buffers. In contrast, in non-saturated scenarios, where nodes refrain from competition for the medium when their buffers are empty, a complex two-way interaction arises between the activity states and the buffer contents of the various nodes. As a result, the throughput characteristics in such scenarios have largely remained elusive so far. In the present paper we provide a generic structural characterization of the throughput performance and corresponding stability region in terms of the individual saturation throughputs of the various nodes. While the saturation throughputs are difficult to explicitly determine in general, we identify certain cases where these values can be expressed in closed form. In addition, we demonstrate that various lower-dimensional facets of the stability region can be explicitly calculated as well, depending on the neighborhood structure of the interference graph. Illustrative examples and numerical results are presented to illuminate the main analytical findings. Keywords: CSMA protocol; Stability conditions; Throughput performance; Wireless networks

Motivated by challenging resource allocation issues arising in large-scale wireless and wireline communication networks, we study distributed network utility maximization problems with a mixture of concave (e.g., best-effort throughputs) and nonconcave (e.g., voice/video streaming rates) utilities. In the first part of the paper, we develop our methodological framework in the context of a locally coupled networked system, where nodes represent agents that control a discrete local state. Each node has a possibly nonconcave local objective function, which depends on the local state of the node and the local states of its neighbors. The goal is to maximize the sum of the local objective functions of all nodes. We devise an iterative randomized algorithm, whose convergence and optimality properties follow from the classical framework of Markov Random Fields and Gibbs Measures via a judiciously selected neighborhood structure. The proposed algorithm is distributed, asynchronous, requires limited computational effort per node/iteration, and yields provable convergence in the limit. In order to demonstrate the scope of the proposed methodological framework, in the second part of the paper we show how the method can be applied to two different problems for which no distributed algorithm with provable convergence and optimality properties is available. Specifically, we describe how the proposed methodology provides a distributed mechanism for solving nonconcave utility maximization problems: 1) arising in OFDMA cellular networks, through power allocation and user assignment; 2) arising in multihop wireline networks, through explicit rate allocation. Several numerical experiments are presented to illustrate the convergence speed and performance of the proposed method.

Recent advances have resulted in queue-based algorithms for medium access control which operate in a distributed fashion, and yet achieve the optimal throughput performance of centralized scheduling algorithms. However, fundamental performance bounds reveal that the "cautious" activation rules involved in establishing throughput optimality tend to produce extremely large delays, typically growing exponentially in 1/(1-¿) , with ¿ the load of the system, in contrast to the usual linear growth. Motivated by that issue, we explore to what extent more "aggressive" schemes can improve the delay performance. Our main finding is that aggressive activation rules induce a lingering effect, where individual nodes retain possession of a shared resource for excessive lengths of time even while a majority of other nodes idle. Using central limit theorem type arguments, we prove that the idleness induced by the lingering effect may cause the delays to grow with 1/(1-¿) at a quadratic rate. To the best of our knowledge, these are the first mathematical results illuminating the lingering effect and quantifying the performance impact. In addition extensive simulation experiments are conducted to illustrate and validate the various analytical results. Keywords: Delay performance; Distributed scheduling algorithms; Heavy traffic scaling; Wireless networks

We consider a system of $N$ servers inter-connected by some underlying graph topology $G_N$. Tasks arrive at the various servers as independent Poisson processes of rate $\lambda$. Each incoming task is irrevocably assigned to whichever server has the smallest number of tasks among the one where it appears and its neighbors in $G_N$. Tasks have unit-mean exponential service times and leave the system upon service completion. The above model has been extensively investigated in the case $G_N$ is a clique. Since the servers are exchangeable in that case, the queue length process is quite tractable, and it has been proved that for any $\lambda < 1$, the fraction of servers with two or more tasks vanishes in the limit as $N \to \infty$. For an arbitrary graph $G_N$, the lack of exchangeability severely complicates the analysis, and the queue length process tends to be worse than for a clique. Accordingly, a graph $G_N$ is said to be $N$-optimal or $\sqrt{N}$-optimal when the occupancy process on $G_N$ is equivalent to that on a clique on an $N$-scale or $\sqrt{N}$-scale, respectively. We prove that if $G_N$ is an Erd\H{o}s-R\'enyi random graph with average degree $d(N)$, then it is with high probability $N$-optimal and $\sqrt{N}$-optimal if $d(N) \to \infty$ and $d(N) / (\sqrt{N} \log(N)) \to \infty$ as $N \to \infty$, respectively. This demonstrates that optimality can be maintained at $N$-scale and $\sqrt{N}$-scale while reducing the number of connections by nearly a factor $N$ and $\sqrt{N} / \log(N)$ compared to a clique, provided the topology is suitably random. It is further shown that if $G_N$ contains $\Theta(N)$ bounded-degree nodes, then it cannot be $N$-optimal. In addition, we establish that an arbitrary graph $G_N$ is $N$-optimal when its minimum degree is $N - o(N)$, and may not be $N$-optimal even when its minimum degree is $c N + o(N)$ for any $0 < c < 1/2$., Comment: A few relevant results from arXiv:1612.00723 are included for convenience

A fundamental challenge in large-scale cloud networks and data centers is to achieve highly efficient server utilization and limit energy consumption, while providing excellent user-perceived performance in the presence of uncertain and time-varying demand patterns. Auto-scaling provides a popular paradigm for automatically adjusting service capacity in response to demand while meeting performance targets, and queue-driven auto-scaling techniques have been widely investigated in the literature. In typical data center architectures and cloud environments however, no centralized queue is maintained, and load balancing algorithms immediately distribute incoming tasks among parallel queues. In these distributed settings with vast numbers of servers, centralized queue-driven auto-scaling techniques involve a substantial communication overhead and major implementation burden, or may not even be viable at all. Motivated by the above issues, we propose a joint auto-scaling and load balancing scheme which does not require any global queue length information or explicit knowledge of system parameters, and yet provides provably near-optimal service elasticity. We establish the fluid-level dynamics for the proposed scheme in a regime where the total traffic volume and nominal service capacity grow large in proportion. The fluid-limit results show that the proposed scheme achieves asymptotic optimality in terms of user-perceived delay performance as well as energy consumption. Specifically, we prove that both the waiting time of tasks and the relative energy portion consumed by idle servers vanish in the limit. At the same time, the proposed scheme operates in a distributed fashion and involves only constant communication overhead per task, thus ensuring scalability in massive data center operations., Comment: Accepted in ACM SIGMETRICS, Urbana-Champaign, Illinois, USA, 2017

We examine the impact of torpid mixing and meta-stability issues on the delay performance in wireless random-access networks. Focusing on regular meshes as prototypical scenarios, we show that the mean delays in an L×L toric grid with normalized load ¿ are of the order (1/(1-¿))^L . This superlinear delay scaling is to be contrasted with the usual linear growth of the order 1/(1-¿) in conventional queueing networks. The intuitive explanation for the poor delay characteristics is that (i) high load requires a high activity factor, (ii) a high activity factor implies extremely slow transitions between dominant activity states, and (iii) slow transitions cause starvation and hence excessively long queues and delays. Our proof method combines both renewal and conductance arguments. A critical ingredient in quantifying the long transition times is the derivation of the communication height of the uniformized Markov chain associated with the activity process. We also discuss connections with Glauber dynamics, conductance and mixing times. Our proof framework can be applied to other topologies as well, and is also relevant for the hard-core model in statistical physics and the sampling from independent sets using single-site update Markov chains. Keywords: Wireless random-access networks; Grid topologies, delay scaling; Hitting times; Conductance; Mixing times

When a communication network’s capacity increases, it is natural to want the bandwidth allocated to increase to exploit this capacity. But, if the same relative capacity increase occurs throughout the network, it is also natural to want each user to see the same relative benefit, so the bandwidth allocated remains proportional. We will be interested in bandwidth allocations which scale in this iso-elastic manner and, also, maximize a utility function. In this paper, we present results that show, in many settings, the only iso-elastic utility functions are weighted aa-fair utility functions, which have gained wide popularity in the networking literature. Hence, a control protocol that is robust to the relative increases in network capacity and usage ought to allocate bandwidth in order to maximize a weighted a-fair utility function. Keywords: Resource allocation; Capacity scaling; Iso-elasticity; a-fairness

CSMA is the predominant distributed access protocol for wireless mesh networks. Originally designed for single-hop settings, CSMA can exhibit severe performance problems in multi-hop networks in terms of stability and end-to-end throughput. To ensure a smoother flow of packets, we examine an enhancement referred to as Extra Back-off (EB) flow control. In this enhanced scheme a node remains silent for a certain extra back-off time (imposed on top of the usual back-off time that is part of CSMA) after it has transmitted a packet, to give both the downstream and upstream neighbors the opportunity to transmit. EB flow control entails only a small modification to CSMA, preserving its distributed character. In order to examine the performance of EB flow control, we analyze a novel class of Markov models at the interface between classical tandem queues and interacting particle systems. The results demonstrate that EB flow control provides an effective mechanism for improving the end-to-end throughput performance.

We consider the server scheduling problem in hybrid P2P networks in the context of a fluid model. Specifically, we examine how to allocate the limited amount of server upload capacity among competing swarms over time in order to optimize the download performance experienced by users. For sufficiently high user churn rate, we prove that it is optimal to allocate the full server capacity at all times, and that it does not matter exactly how the capacity is distributed among competing swarms as long as no upload capacity is unnecessarily left unused. While it may seem obvious that it is optimal to allocate the full server capacity, we show that this is not always the case, surprisingly enough when the user churn rate is not high. In that case, throttling the server capacity slows down downloads in the short run, but also boosts the future peer upload capacity, and may thus lead to higher download speeds in the long term.

While the (Egalitarian) Processor-Sharing (PS) discipline offers crucial insights in the performance of fair resource allocation mechanisms, it is inherently limited in analyzing and designing differentiated scheduling algorithms such as Weighted Fair Queueing and Weighted Round-Robin. The Discriminatory Processor-Sharing (DPS) and Generalized Processor-Sharing (GPS) disciplines have emerged as natural generalizations for modeling the performance of such service differentiation mechanisms. A further extension of the ordinary PS policy is the Multilevel Processor-Sharing (MLPS) discipline, which has captured a pivotal role in the analysis, design and implementation of size-based scheduling strategies. We review various key results for DPS, GPS and MLPS models, highlighting to what extent these disciplines inherit desirable properties from ordinary PS or are capable of delivering service differentiation.

Bandwidth-sharing networks as considered by Massoulie and Roberts provide a natural modeling framework for describing the dynamic flow-level interaction among elastic data transfers. Under mild assumptions, it has been established that a wide family of so-called @a-fair bandwidth-sharing strategies achieve stability in such networks provided that no individual link is overloaded. In the present paper we focus on @a-fair bandwidth-sharing networks where the load on one or several of the links exceeds the capacity. Evidently, a well-engineered network should not experience overload, or even approach overload, in normal operating conditions. Yet, even in an adequately provisioned system with a low nominal load, the actual traffic volume may significantly fluctuate over time and exhibit temporary surges. Furthermore, gaining insight into the overload behavior is crucial in analyzing the performance in terms of long delays or low throughputs as caused by large queue build-ups. The way in which such rare events tend to occur, commonly involves a scenario where the system temporarily behaves as if it experiences overload. In order to characterize the overload behavior, we examine the fluid limit, which emerges from a suitably scaled version of the number of flows of the various classes. The convergence of the scaled number of flows to the fluid limit is empirically validated through simulation experiments. Focusing on linear solutions to the fluid-limit equation, we derive a fixed-point equation for the corresponding asymptotic growth rates. It is proved that a fixed-point solution is also a solution to a related strictly concave optimization problem, and hence exists and is unique. We use the fixed-point equation to investigate the impact of the traffic intensities and the variability of the flow sizes on the asymptotic growth rates. The results are illustrated for linear topologies and star networks as two important special cases. Finally, we briefly discuss extensions to models with user impatience.

The Quality-and-Efficiency-Driven (QED) regime provides a basis for solving asymptotic dimensioning problems that trade off revenue, costs and service quality. We derive bounds for the optimality gaps that capture the differences between the true optimum and the asymptotic optimum based on the QED approximations. Our bounds generalize earlier results for classical many-server systems. We also apply our bounds to a many-server system with threshold control., 17 pages, 2 figures, 2 tables

Distributed algorithms such as CSMA provide a popular mechanism for sharing the transmission medium among competing users in large-scale wireless networks. Conventional models for CSMA that are amenable for analysis assume that users always have packets to transmit. In contrast, when users do not compete for medium access when their buffers are empty, a complex interaction arises between the activity states and the buffer contents. We develop a meanfield approach to investigate this dynamic interaction for networks with many users. We identify a time-scale separation between the evolution of the activity states and the buffer contents, and obtain a deterministic dynamical system describing the network dynamics on a macroscopic scale. The fixed point of the dynamical system yields highly accurate approximations for the stationary distribution of the buffer contents and packet delay, even when the number of users is relatively moderate.

We consider a fixed number of streaming sessions which share a bottleneck link with a dynamic population of elastic flows. Motivated by extensive measurement studies, we assume that the sizes of the elastic flows exhibit heavy-tailed characteristics. The elastic flows are TCP-controlled, while the transmission rates of the streaming applications are governed by a so-called TCP-friendly rate control protocol. TCP-friendly rate control protocols provide a promising mechanism for avoiding severe fluctuations in the transmission rate, while ensuring fairness with competing TCP-controlled flows. Adopting the processor-sharing (PS) discipline to model the bandwidth sharing, we investigate the tail distribution of the deficit in service received by the streaming sessions compared to a nominal service target. The latter metric provides an indication for the quality experienced by the streaming applications. The results yield valuable qualitative insight into the occurrence of persistent quality disruption for the streaming users. We also examine the delay performance of the elastic flows by exploiting a useful relationship with a processor-sharing queue with permanent customers.

We derive the sojourn time asymptotics for a multi-class GI/GI/1 queue with regularly varying service requirements operating under the discriminatory processor-sharing (DPS) discipline. DPS provides a natural approach for modelling the flow-level performance of differentiated bandwidth-sharing mechanisms. Under certain assumptions, we prove that the service requirement and sojourn time of a given class have similar tail behaviour, independent of the specific values of the DPS weights. As a by-product, we obtain an extension of the tail equivalence for ordinary processor-sharing (PS) queues to non-Poisson arrivals. The results suggest that DPS offers a potential instrument for effectuating preferential treatment to high-priority classes, without inflicting excessive delays on low-priority classes. To obtain the asymptotics, we develop a novel method which only involves information of the workload process and does not require any knowledge of the steady-state queue length distribution. In particular, the proof method brings sufficient strength to extend the results to scenarios with a time-varying service capacity.

We consider a fluid model fed by two Gaussian processes. We obtain necessary and sufficient conditions for the workload asymptotics to be completely determined by one of the two processes, and apply these results to the case of two fractional Brownian motions.

This paper surveys the M/G/1 queue with regularly varying service requirement distribution. It studies the effect of the service discipline on the tail behavior of the waiting-time and/or sojourn-time distribution, demonstrating that different disciplines lead to quite different tail behavior. The orientation of the paper is methodological: We outline four different methods for determining tail behavior, illustrating them for service disciplines like FCFS, Processor Sharing and LCFS.

We consider a slotted queueing system with C servers (processors) that can handle tasks (jobs). Tasks arrive in batches of random size at the start of every slot. Any task can be executed by any server in one slot with success probability α. If a task execution fails, then the task must be handled in some later time slot until it has been completed successfully. Tasks may be processed by several servers simultaneously. In that case, the task is completed successfully if the task execution is successful on at least one of the servers.We examine the impact of various allocation strategies on the mean number of tasks in the system and the mean response time of tasks. It is proven that both these performance measures are minimized by the strategy which always distributes the tasks over the servers as evenly as possible. Subsequently, we determine the distribution of the number of tasks in the system for a broad class of task allocation strategies, which includes the above optimal strategy as a special case. Some numerical experiments are performed to illustrate the performance characteristics of the various strategies.

Wireless sensor networks require communication protocols for efficiently propagating data in a distributed fashion. The Trickle algorithm is a popular protocol serving as the basis for many of the current standard communication protocols. In this paper we develop a mathematical model describing how Trickle propagates new data across a network consisting of nodes placed on a line. The model is analyzed and asymptotic results on the hop count and end-to-end delay distributions in terms of the Trickle parameters and network density are given. Additionally, we show that by only a small extension of the Trickle algorithm the expected end-to-end delay can be greatly decreased. Lastly, we demonstrate how one can derive the exact hop count and end-to-end delay distributions for small network sizes. Keywords: Analytical model; Markov renewal process; Wireless communication; Gossip protocol; End-to-end delay; Trickle algorithm

Motivated by an application in wireless random-access networks, we study a class of polling systems with Markovian routing, in which the server visits the queues in an order governed by a discrete-time Markov chain. Assuming that the service disciplines at each of the queues fall in the class of branching-type service disciplines, we derive a functional equation for (the probability generating function of) the joint queue length distribution conditioned on a point in time when the server visits a certain queue. From this functional equation, expressions for the (cross-)moments of the queue lengths follow. We also derive a pseudo-conservation law for this class of polling systems. Using these results, we compute expressions for certain system parameters that minimise the total expected amount of work in systems that arise from the wireless random-access network setting. In addition, we derive approximations for those same parameters that minimise a weighted sum of mean waiting times in these systems. Based on these expressions, we also present an adaptive control algorithm for finding the optimal parameter values in a distributed fashion, which is particularly relevant in the context of wireless random-access networks. Keywords: Queue lengths; Binomial service disciplines; Markovian routing; Random routing; Wireless random-access networks

Load balancing mechanisms and scheduling algorithms play a critical role in achieving efficient server utilization and providing robust delay performance in a wide range of networked systems. We will review some celebrated schemes and optimality results which typically assume that detailed state information, e.g. exact knowledge of queue lengths, is available in assigning jobs to queues or allocating a shared resource among competing users. In practice, however, obtaining such state information is non-trivial, and usually involves a significant communication overhead or delay, which is particularly a concern in large-scale networked systems with massive numbers of queues. These scalability issues have prompted increasing attention for the implementation complexity of load balancing and scheduling algorithms as a crucial design criterion, besides the traditional performance metrics. In this talk we examine the delay performance in such networks for various load balancing and scheduling algorithms, in conjunction with the associated implementation overhead. In the first part of the talk we focus on a scenario with a single dispatcher where jobs arrive that need to be assigned to one of several parallel queues. In the second part of the talk we turn to a system with a single resource, e.g. a shared wireless transmission medium, which is to be allocated among several nodes. We will specifically explore the delay scaling properties in a mean-field framework where the total load and service capacity grow large in proportion. The mean-field regime not only offers analytical tractability, but is also highly relevant given the immense numbers of servers in data centers and cloud networks, and dense populations of wireless devices and sensors in Internet-of-Things (IoT) applications. Time permitting, we will also discuss the impact of the underlying network structure and a few open research challenges.

Backlog-based CSMA strategies provide a popular mechanism for distributed medium access control in wireless networks. When suitably designed, such strategies offer the striking capability to match the optimal throughput performance of centralized scheduling algorithms in a wide range of scenarios. Unfortunately, however, the activation rules used in these schemes tend to yield excessive backlogs and delays. More aggressive activation rates can potentially improve the delay performance, but may not allow provable maximum-stability guarantees. In order to gain a fundamental understanding how the shape of the activation function affects the queueing behavior, we focus on a single- node scenario, thus separating the impact of the network topology. We demonstrate that three qualitatively different regimes can arise, depending on how rapidly the activation function increases with the backlog. Simulation experiments are conducted to validate the analytical findings.

Random-access algorithms such as CSMA provide a popular mechanism for distributed medium access control in largescale wireless networks. In recent years, tractable models have been shown to yield accurate throughput estimates for CSMA networks. We consider the saturated model on a general conflict graph, and prove that for each graph, there exists a vector of activation rates (or mean back-off times) that leads to equal throughputs for all users. We describe an algorithm for computing such activation rates, and discuss a few specific conflict graphs that allow for explicit characterization of these fair activation rates. Keywords: CSMA, fixed point, global invertibility, loss networks, Markov processes, random access, throughput, wireless networks

Template-driven scheduling mechanisms provide a simple and robust scheme for sharing a resource among several traffic classes. The performance of such scheduling mechanisms critically relies on the regularity properties of the template. An important application, which motivated our study, arises in the context of weighted round-robin cell scheduling algorithms used for (de)multiplexing the various traffic streams in high-speed switches. In that setting, regularity of the template significantly reduces cell delay and delay variation (jitter), and equally important, the burstiness of the outgoing stream. We propose a measure for quantifying the regularity in terms of the spacing of the slots assigned to the various classes. The proposed criterion is consistent with common regularity notions, while the structural form allows for the computation of an optimal template using a quadratic assignment formulation. We also establish the asymptotic optimality of simple and fast heuristic algorithms in a scenario with a large number of traffic classes. Numerical experiments demonstrate that the heuristic procedures yield excellent results, even if the regime of asymptotic optimality does not strictly apply. Copyright © 1999 John Wiley & Sons, Ltd.

We consider multiple-server polling systems, in which each of the servers visits the queues according to its own cyclic schedule. Such systems appear to completely defy the derivation of exact waiting-time results, which motivates the search for accurate approximations. In the present paper, we derive waiting-time approximations for asymmetric systems with the exhaustive and gated service discipline. The approximations are tested for a wide range of parameter combinations.

Random access schemes are simple and inherently distributed, yet capable of matching the optimal throughput performance of centralized scheduling algorithms. The throughput optimality however has been established for activation rules that are relatively sluggish, and may yield excessive queues and delays. More aggressive/persistent access schemes have the potential to improve the delay performance, but it is not clear if they can offer any universal throughput optimality guarantees. In this paper, we identify a limit on the aggressiveness of nodes, beyond which instability is bound to occur in a broad class of networks.

As the use of wireless sensor networks increases, the need for (energy-)efficient and reliable broadcasting algorithms grows. Ideally, a broadcasting algorithm should have the ability to quickly disseminate data, while keeping the number of transmissions low. In this paper we develop a model describing the message count in large-scale wireless sensor networks. We focus our attention on the popular Trickle algorithm, which has been proposed as a suitable communication protocol for code maintenance and propagation in wireless sensor networks. Besides providing a mathematical analysis of the algorithm, we propose a generalized version of Trickle, with an additional parameter defining the length of a listen-only period. This generalization proves to be useful for optimizing the design and usage of the algorithm. For single-cell networks we show how the message count increases with the size of the network and how this depends on the Trickle parameters. Furthermore, we derive distributions of inter-broadcasting times and investigate their asymptotic behavior. Our results prove conjectures made in the literature concerning the effect of a listen-only period. Additionally, we develop an approximation for the expected number of transmissions in multi-cell networks. All results are validated by simulations.

We characterize the achievable performance of ATM networks in terms of the offered traffic, the admissible region, and the revenue measure. We describe how the boundaries of admissible regions with convex complements may be linearized —thus reducing the admissible region — so as to obtain a convenient loss network representation. Asymptotic results for the achievable performance suggest that the potential reduction in revenue is immaterial in high-capacity networks. Numerical experiments confirm that the actual reduction is typically negligible, even in networks of moderate capacity.

We consider a fixed number of streaming sessions sharing a bottleneck link with a dynamic population of elastic flows. We assume that the sizes of the elastic flows exhibit heavy-tailed characteristics. The elastic flows are TCP-controlled, while the transmission rates of the streaming applications are governed by a so-called TCP-friendly rate control protocol. Adopting the Processor-Sharing (PS) discipline to model the bandwidth sharing, we investigate the tail distribution of the deficit in service received by the streaming sessions compared to a nominal service target. The latter metric provides an indication for the quality experienced by the streaming applications. The results yield valuable qualitative insight into the occurrence of persistent quality disruption for the streaming users. We also examine the delay performance of the elastic flows.

We study the joint queue length distribution of the Discriminatory Processor Sharing model, assuming all classes have phase-type service requirement distributions. We show that the moments of the joint queue length distribution can be obtained by solving linear equations. We use this to study the system in two asymptotic regimes. In the first regime, the different user classes operate on strictly separated time scales. Then we study the system in heavy traffic.

We explore the achievable delay performance in wireless random-access networks. While relatively simple and inherently distributed in nature, suitably designed backlog-based random-access schemes provide the striking capability to match the optimal throughput performance of centralized scheduling mechanisms. The specific type of activation rules for which throughput optimality has been established, may however yield excessive backlogs and delays. Motivated by that issue, we examine whether the poor delay performance is inherent to the basic operation of these schemes, or caused by the specific kind of activation rules. We derive delay lower bounds for backlog-based activation rules, which offer fundamental insight in the cause of the excessive delays. For fixed activation rates we obtain lower bounds indicating that delays and mixing times can grow dramatically with the load in certain topologies as well.

We examine threshold-based transmission strategies for distributed opportunistic medium access in a scenario with fairly general probabilistic interference conditions. Specifically, collisions between concurrent transmissions are governed by arbitrary probabilities, allowing for a form of channel capture and covering binary interference constraints as an important special case. We address the problem of setting the threshold values so as to optimize the aggregate throughput utility of the various users, and particularly focus on a weighted logarithmic throughput utility function (Proportional Fairness). We provide an adaptive algorithm for finding the optimal threshold values in a distributed fashion, and rigorously establish the convergence of the proposed algorithm under mild statistical assumptions. Moreover, we discuss how the algorithm may be adapted to achieve packet-level stability with only limited exchange of queue length information among the various users. We also conduct extensive numerical experiments to corroborate the theoretical convergence results.

We consider a system with two heterogeneous traffic classes, one having light-tailed characteristics, the other one exhibiting heavy-tailed properties. The two traffic classes are served in accordance with the Generalized Processor Sharing (GPS) discipline. GPS-based scheduling algorithms, such as Weighted Fair Queueing (WFQ), have emerged as an important mechanism for achieving service differentiation in integrated-services networks.We determine the workload asymptotics of the light-tailed class for the situation where its GPS weight is larger than its traffic intensity. The GPS mechanism ensures that the workload is bounded above by that in an isolated system with the light-tailed class served in isolation at a constant rate equal to its GPS weight. We show that the workload distribution is in fact asymptotically equivalent to that in the isolated system, multiplied with a certain pre-factor, which accounts for the interaction with the heavy-tailed class. Specifically, the pre-factor represents the probability that the heavy-tailed class is backlogged long enough for the light-tailed class to reach overflow. The results provide crucial qualitative insight in the typical overflow scenario.

Random-access algorithms such as the Carrier-Sense Multiple-Access (CSMA) protocol provide a popular mechanism for distributed medium access control in large-scale wireless networks. In recent years, fairly tractable models have been shown to yield remarkably accurate throughput estimates for CSMA networks. These models typically assume that both the transmission durations and the back-off periods are exponentially distributed. We show that the stationary distribution of the system is in fact insensitive with respect to the transmission durations and the back-off times. These models primarily pertain to a saturated scenario where nodes always have packets to transmit. In reality however, the buffers may occasionally be empty as packets are randomly generated and transmitted over time. The resulting interplay between the activity states and the buffer contents gives rise to quite complicated queueing dynamics, and even establishing the stability criteria is usually a serious challenge. We explicitly identify the stability conditions in a few relevant scenarios, and illustrate the difficulties arising in other cases. Keywords: CSMA protocol; Insensitivity properties; Interference graphs; Random-access algorithms; Stability conditions; Wireless networks.

Introduction: The on-demand delivery of video content is anticipated to show tremendous growth over the next few years, driven by the huge popularity of user-generated video clips and the expansion of VoD libraries. Even stronger growth is likely to be fueled by the proliferation of IPTV services with personalized features such as CatchUp/PauseLive TV and NPVR capabilities. The common characteristic of these ‘time-shifted’ TV services, as well as VoD libraries and sites like YouTube, is that users can select from a vast collection of content material at any time they want. This runs counter to the broadcast paradigm embraced in conventional TV networks, and raises a need for unicast sessions, increasing the overall bandwidth demands by orders of magnitude. Caching strategies provide an effective mechanism for mitigating the massive bandwidth requirements associated with large-scale distribution of personalized high-definition video content. In essence, caching strategies exploit storage capacity to absorb traffic by replicating the most popular content closer to the network edge rather than storing it in a central location. The reduction in the traffic load translates into a smaller required transport capacity and capital expense as well as fewer performance bottlenecks, thus enabling better service quality at a lower price. In the present paper we develop light-weight distributed cooperative content placement algorithms so as to maximize the traffic volume served from cache, and thus minimize the bandwidth cost. As a canonical scenario, we focus on a cluster of distributed caches, connected either directly, or via a parent node, and formulate the content placement problem as an integer linear program in order to obtain a benchmark of the globally optimal performance. Under certain symmetry assumptions, the optimal solution of the relaxed linear program is found to have a rather simple structure. Besides interesting in its own right, the knowledge of the optimal structure offers useful insight for the design of low-complexity cooperative content placement and eviction algorithms. The performance of the proposed distributed algorithms is proved to be within a small constant factor from the performance of an optimal centralized scheme, while requiring only limited knowledge of global popularities, even in asymmetric scenarios. In contrast to [1, 2], we will focus on specific topologies, motivated by real system deployments, and use the insight from the linear program and the simple structure of its optimal solution to develop efficient distributed content placement algorithms with far more favorable performance ratios than the ones in [1, 2].

Over the past few years, the processor-sharing discipline has emerged as a useful paradigm for evaluating the flowlevel performance of elastic data transfers competing for bandwidth on a single bottle-neck link. Bandwidth-sharing networks as considered by Massoulie & Roberts [2] provide a natural extension for modeling the dynamic interaction among competing elastic flows that traverse several links. Bonald & Massoulie [1] showed that a wide class of α-fair bandwidth-sharing policies as introduced by Mo & Walrand [3] achieve stability in such networks under the simple (and necessary) condition that no individual link is overloaded. While stability is arguably the most fundamental performance criterion, flow-level delays and throughputs are obviously crucial metrics too. Although useful approximations and bounds have been obtained, the latter performance metrics have largely remained intractable in all but a few special cases. In particular, it is not well understood to what extent

We consider a system with two service classes with heterogeneous traffic characteristics and Quality-of-Service requirements. The available bandwidth is shared between the two traffic classes in accordance with the Generalized Processor Sharing (GPS) discipline. GPS-based scheduling algorithms, such as Weighted Fair Queueing, provide a popular mechanism for service differentiation among heterogeneous traffic classes. While the performance of GPS for given weights has been thoroughly examined, the problem of selecting weight values that maximize the traffic-carrying capacity, has only received limited attention so far. In the present paper, we address the latter problem for the case of general Gaussian traffic sources. Gaussian models cover a wide variety of both long-range dependent and short-range dependent processes, and are especially suitable at relatively high levels of aggregation. In particular, we determine the realizable region, i.e., the combinations of traffic sources that can be supported for given Quality-of-Service requirements in terms of loss and delay metrics. The results yield the remarkable observation that simple priority scheduling strategies achieve nearly the full realizable region. 1 .