Search

We investigate the tail asymptotics of the response time distribution for the cancel-on-start (c.o.s.) and cancel-on-completion (c.o.c.) variants of redundancy-d scheduling and the fork–join model with heavy-tailed job sizes. We present bounds, which only differ in the pre-factor, for the tail probability of the response time in the case of the first-come first-served discipline. For the c.o.s. variant, we restrict ourselves to redundancy-d scheduling, which is a special case of the fork–join model. In particular, for regularly varying job sizes with tail index-$$\nu $$ ν the tail index of the response time for the c.o.s. variant of redundancy-d equals -$$\min \{d_{\mathrm {cap}}(\nu -1),\nu \}$$ min { d cap ( ν - 1 ) , ν } , where $$d_{\mathrm {cap}} = \min \{d,N-k\}$$ d cap = min { d , N - k } , N is the number of servers and k is the integer part of the load. This result indicates that for $$d_{\mathrm {cap}} < \frac{\nu }{\nu -1}$$ d cap < ν ν - 1 the waiting time component is dominant, whereas for $$d_{\mathrm {cap}} > \frac{\nu }{\nu -1}$$ d cap > ν ν - 1 the job size component is dominant. Thus, having $$d = \lceil \min \{\frac{\nu }{\nu -1},N-k\} \rceil $$ d = ⌈ min { ν ν - 1 , N - k } ⌉ replicas is sufficient to achieve the optimal asymptotic tail behavior of the response time. For the c.o.c. variant of the fork–join ($$n_{\mathrm {F}},n_{\mathrm {J}}$$ n F , n J ) model, the tail index of the response time, under some assumptions on the load, equals $$1-\nu $$ 1 - ν and $$1-(n_{\mathrm {F}}+1-n_{\mathrm {J}})\nu $$ 1 - ( n F + 1 - n J ) ν , for identical and i.i.d. replicas, respectively; here, the waiting time component is always dominant.

We consider a large-scale service system where incoming tasks have to be instantaneously dispatched to one out of many parallel server pools. The user-perceived performance degrades with the number of concurrent tasks and the dispatcher aims at maximizing the overall quality-of-service by balancing the load through a simple threshold policy. We demonstrate that such a policy is optimal on the fluid and diffusion scales, while only involving a small communication overhead, which is crucial for large-scale deployments. In order to set the threshold optimally, it is important, however, to learn the load of the system, which may be unknown. For that purpose, we design a control rule for tuning the threshold in an online manner. We derive conditions which guarantee that this adaptive threshold settles at the optimal value, along with estimates for the time until this happens. In addition, we provide numerical experiments which support the theoretical results and further indicate that our policy copes effectively with time-varying demand patterns., Comment: 51 pages, 6 figures

Service systems often face task-server assignment-constraints due to skill-based routing or geographical conditions. Redundancy scheduling responds to this limited flexibility by replicating tasks to specific servers in agreement with these assignment constraints. We gain insight from product-form stationary distributions and weak local stability conditions to establish a state space collapse in heavy traffic. In this limiting regime, the parallel-server system with redundancy scheduling operates as a multi-class single-server system, achieving full resource pooling and exhibiting strong insensitivity to the underlying assignment constraints. In particular, the performance of a fully flexible (unconstrained) system can be matched even with rather strict assignment constraints., 53 pages, 4 figures

We establish mean-field limits for large-scale random-access networks with buffer dynamics and arbitrary interference graphs. While saturated-buffer scenarios have been widely investigated and yield useful throughput estimates for persistent sessions, they fail to capture the fluctuations in buffer contents over time, and provide no insight in the delay performance of flows with intermittent packet arrivals. Motivated by that issue, we explore in the present paper random-access networks with buffer dynamics, where flows with empty buffers refrain from competition for the medium. The occurrence of empty buffers thus results in a complex dynamic interaction between activity states and buffer contents, which severely complicates the performance analysis. Hence we focus on a many-sources regime where the total number of nodes grows large, which not only offers mathematical tractability but is also highly relevant with the densification of wireless networks as the Internet of Things emerges. We exploit time scale separation properties to prove that the properly scaled buffer occupancy process converges to the solution of a deterministic initial-value problem, and establish the existence and uniqueness of the associated fixed point. This approach simplifies the performance analysis of networks with huge numbers of nodes to a low-dimensional fixed-point calculation. For the case of a complete interference graph, we demonstrate asymptotic stability, provide a simple closed-form expression for the fixed point, and prove interchange of the mean-field and steady-state limits. This yields asymptotically exact approximations for key performance metrics, in particular the stationary buffer content and packet delay distributions. The methodological framework that we develop easily extends to various model refinements as will be illustrated by several examples.

We consider networks where each node represents a server with a queue. An active node deactivates at unit rate. An inactive node activates at a rate that depends on its queue length, provided none of its neighbors is active. For complete bipartite networks, in the limit as the queues become large, we compute the average transition time between the two states where one half of the network is active and the other half is inactive. We show that the law of the transition time divided by its mean exhibits a trichotomy, depending on the activation rate functions., 32 pages

We consider a system of $N$ identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda(N)$. Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution, or discarded. The execution times are assumed to be exponentially distributed with unit mean, and do not depend on the number of other tasks receiving service. However, the experienced performance (e.g. in terms of received throughput) does degrade with an increasing number of concurrent tasks at the same server pool. The dispatcher therefore aims to evenly distribute the tasks across the various server pools. Specifically, when a task arrives, the dispatcher assigns it to the server pool with the minimum number of tasks among $d(N)$ randomly selected server pools. This assignment strategy is called the JSQ$(d(N))$ scheme, as it resembles the power-of-$d$ version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case $d(N) = N$. We construct a stochastic coupling to bound the difference in the system occupancy processes between the JSQ policy and a scheme with an arbitrary value of $d(N)$. We use the coupling to derive the fluid limit in case $d(N) \to \infty$ and $\lambda(N)/N \to \lambda$ as $N \to \infty$, along with the associated fixed point. The fluid limit turns out to be insensitive to the exact growth rate of $d(N)$, and coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit corresponds to that for the JSQ policy as well, as long as $d(N)/\sqrt{N} \log(N) \to \infty$, and characterize the common limiting diffusion process. These results indicate that the JSQ optimality can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O($N$) and O($\sqrt{N}/\log(N)$), respectively., Comment: 48 pages, 3 figures, companion paper of arXiv:1612.00723

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.

Drone base stations can help safeguard coverage and provide capacity relief when cellular networks are under stress. Examples of such stress scenarios are events with massive crowds or network outages. In this paper we focus on a disaster scenario with emergence of a traffic hotspot, where agile drone positioning and load management is a critical issue. In order to address this challenge, we propose and assess a data-driven algorithm which leverages real-time measurements to dynamically optimize the 3D position of the drone as well as a cell selection bias tuned for optimized load management. We compare the performance with three benchmark scenarios: i) no drone; ii) a drone positioned above the failing site; and iii) a drone with a statically optimized position and cell selection bias. The results demonstrate that the proposed algorithm significantly improves the call success rate and achieves close to optimal performance.

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.

Redundancy scheduling has emerged as a powerful strategy for improving response times in parallel-server systems. The key feature in redundancy scheduling is replication of a job upon arrival by dispatching replicas to different servers. Redundant copies are abandoned as soon as the first of these replicas finishes service. By creating multiple service opportunities, redundancy scheduling increases the chance of a fast response from a server that is quick to provide service and mitigates the risk of a long delay incurred when a single selected server turns out to be slow. The diversity enabled by redundant requests has been found to strongly improve the response time performance, especially in the case of highly variable service requirements. Analytical results for redundancy scheduling are unfortunately scarce however, and even the stability condition has largely remained elusive so far, except for exponentially distributed service requirements. In order to gain further insight in the role of the service requirement distribution, we explore the behavior of redundancy scheduling for scaled Bernoulli service requirements. We establish a sufficient stability condition for generally distributed service requirements, and we show that, for scaled Bernoulli service requirements, this condition is also asymptotically nearly necessary. This stability condition differs drastically from the exponential case, indicating that the stability condition depends on the service requirements in a sensitive and intricate manner.

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.

We examine a queue-based random-access algorithm where activation and deactivation rates are adapted as functions of queue lengths. We establish its heavy traffic behavior on a complete interference graph, which turns out to be highly nonstandard in two respects: (1) the scaling depends on some parameter of the algorithm and is not the $N/N^2$ scaling usually found in functional central limit theorems; (2) the heavy traffic limit is deterministic. We discuss how this nonstandard behavior arises from the idleness induced by the distributed nature of the algorithm. In order to prove our main result, we developed a new method for obtaining a fully coupled stochastic averaging principle., Comment: 40 pages

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.

The use of drone base stations offers an agile mechanism to safeguard coverage and provide capacity relief when cellular networks are under stress. Such stress conditions can occur for example in case of special events with massive crowds or network outages. In this paper we focus on a disaster scenario with emergence of a hotspot, and analyze the impact of the drone position (altitude, horizontal position) and selection bias on the network performance. We determine the optimal settings of these control parameters as a function of the hotspot location, and demonstrate that the optimized values can drastically reduce the fraction of failed calls.

A key option to further increase mobile network capacity is to deploy dense cellular networks (DCNs). This densification of cellular networks raises challenging issues though, as it likely increases the spatial variation and temporal fluctuations in load. To harness the full potential of DCNs, cell selection algorithms must take these varying load conditions into account. In this paper we study the optimal user association in DCNs based on a Linear Program (LP). Since several system parameters tend to be unknown and time-varying in practice, we develop a dynamic, self-organizing, and load-aware cell selection algorithm: the Shadow Price Assignment (SPA) algorithm. Our algorithm realizes an optimal user association without explicit knowledge of the system parameters by using a parsimonious set of dynamically adapted control parameters. We establish convergence of the control parameters under suitable assumptions. For larger systems the convergence may be slower, and we propose a local clustering approach to further improve the user-perceived performance in systems with many APs. Extensive simulations confirm that the SPA algorithm substantially outperforms conventional approaches.

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 a system with several job types and two parallel server pools. Within the pools the servers are homogeneous, but across pools possibly not in the sense that the service speed of a job may depend on its type as well as the server pool. Immediately upon arrival, jobs are assigned to a server pool, possibly based on (partial) knowledge of their type. In case such knowledge is not available upon arrival, it can however be obtained while the job is in service; as the service progresses, the likelihood that the service speed of this job type is low increases, creating an incentive to execute the job on different, possibly faster, server(s). Two policies are considered: reroute the job to the other server pool, or replicate it there.We determine the effective load per server under both the rerouting and replication policy for completely unknown as well as partly known job types. We also examine the impact of these policies on the stability bound, which is defined as the maximum arrival rate of jobs for which the effective load per server is smaller than one. We demonstrate that the uncertainty in job types may significantly reduce the stability bound, and that for (highly) unbalanced service speeds full replication achieves the largest stability bound. Finally, we discuss how the use of threshold-based policies can help improve the expected latency for completely or partly unknown job types.

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.

This is a survey on polling systems, focussing on the basic single-server multi-queue polling system in which the server visits the queues in cyclic order. The main goals of the paper are: (i) to discuss a number of the key methodologies in analyzing polling models; (ii) to give an overview of recent polling developments; and (iii) to present a number of challenging open problems.

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.

Inspired by reliability issues in electric transmission networks, we use a probabilistic approach to study the occurrence of large failures in a stylized cascading line failure model. Such models capture the phenomenon where an initial line failure potentially triggers massive knock-on effects. Under certain critical conditions, the probability that the number of line failures exceeds a large threshold obeys a power-law distribution, a distinctive property observed in empiric blackout data. In this paper, we examine the robustness of the power-law behavior by exploring under which conditions this behavior prevails.

Due to the rising concerns of energy consumption in wireless networks, base station (BS) sleeping strategies were introduced to save energy in low traffic scenarios. In this paper we analyse a weighted trade-off between energy consumption and user-perceived performance in dense cellular networks. We present an optimization problem representing this trade-off and derive properties of its optimal solutions. Using these properties we design a self-organizing strategy that dynamically (online) makes load-aware user association and BS operation decisions. Our strategy is self-organizing in the sense that it does not need any information or optimization beforehand, it simply relies on real-time load measurements at the BSs and user-reported SINR values. We furthermore present extensive simulation results, demonstrating the effectiveness of our self-organizing strategy and the impact of increased energy consumption on the user-perceived performance.

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 the stability condition 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 condition 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 extensions to scenarios with heterogeneous servers., To appear in proceedings of ValueTools 2020

We consider load balancing in service systems with affinity relations between jobs and servers. Specifically, an arriving job can be assigned to a fast, primary server from a particular selection associated with this job or to a secondary server to be processed at a slower rate. Such job–server affinity relations can model network topologies based on geographical proximity, or data locality in cloud scenarios. We introduce load balancing schemes that assign jobs to primary servers if available, and otherwise to secondary servers. A novel coupling construction is developed to obtain stability conditions and performance bounds. We also conduct a fluid limit analysis for symmetric model instances, which reveals a delicate interplay between the model parameters and load balancing performance.

We consider the problem of provisioning slices in 5G cellular networks and study two MAC scheduling methods for achieving slice rate and resource share constraints. The first uses an additive adjustment to the standard Proportional Fair scheduler weight and optimizes utility subject to the slice constraints. The second uses a multiplicative adjustment and achieves fairness between the users within a slice in addition to satisfying the slice constraints. We provide a comprehensive analysis of the tradeoffs between utility and fairness for the simple case of constant channel rates and use simulations to illustrate that similar effects hold for typical 3gpp channel models.

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 present an overview of scalable load balancing algorithms which provide favorable delay performance in large-scale systems, and yet only require minimal implementation overhead. Aimed at a broad audience, the paper starts with an introduction to the basic load balancing scenario, consisting of a single dispatcher where tasks arrive that must immediately be forwarded to one of N single-server queues. A popular class of load balancing algorithms are so-called power-of-d or JSQ(d) policies, where an incoming task is assigned to a server with the shortest queue among d servers selected uniformly at random. This class includes the Join-the-Shortest-Queue (JSQ) policy as a special case (d=N), which has strong stochastic optimality properties and yields a mean waiting time that vanishes as N grows large for any fixed subcritical load. However, a nominal implementation of the JSQ policy involves a prohibitive communication burden in large-scale deployments. In contrast, a random assignment policy (d=1) does not entail any communication overhead, but the mean waiting time remains constant as N grows large for any fixed positive load. In order to examine the fundamental trade-off between performance and implementation overhead, we consider an asymptotic regime where d(N) depends on N. We investigate what growth rate of d(N) is required to match the performance of the JSQ policy on fluid and diffusion scale. The results demonstrate that the asymptotics for the JSQ(d(N)) policy are insensitive to the exact growth rate of d(N), as long as the latter is sufficiently fast, implying that the optimality of the JSQ policy can asymptotically be preserved while dramatically reducing the communication overhead. We additionally show how the communication overhead can be reduced yet further by the so-called Join-the-Idle-Queue scheme, leveraging memory at the dispatcher.

Network slicing provides a key functionality in emerging 5G networks, and offers flexibility in creating customized virtual networks and supporting different services on a common physical infrastructure. This capability critically relies on a MAC scheduler to deliver performance targets in terms of aggregate rates or resource shares for the various slices.A crucial challenge is to enforce such guarantees and performance isolation while allowing flexible sharing to avoid resource fragmentation and fully harness channel variations. In the present paper we propose a MAC scheduler which meets these objectives and preserves the basic structure of utility-based schedulers such as the Proportional Fair algorithm in terms of per-user scheduling metrics. Specifically, the proposed scheme involves counters tracking the aggregate rate or resource allocations for the various slices against pre-specified targets, and computes offsets to the scheduling metrics accordingly. This design provides transparency with respect to other scheduling modules, such as link adaptation and beam-forming.We analytically establish that the proposed scheme achieves optimal overall throughput utility subject to the various slicing constraints. In addition, extensive 3GPP-compliant simulation experiments are conducted to assess the impact on best-effort applications and demonstrate substantial gains in overall throughput utility over baseline approaches.

We develop a gradient algorithm for optimizing the performance of product-form networks through online adjustment of control parameters. The use of standard algorithms for finding optimal parameter settings is hampered by the prohibitive computational burden of calculating the gradient in terms of the stationary probabilities. The proposed approach instead relies on measuring empirical frequencies of the various states through simulation or online operation so as to obtain estimates for the gradient. Besides the reduction in computational effort, a further benefit of the online operation lies in the natural adaptation to slow variations in ambient parameters as commonly occurring in dynamic environments. On the downside, the measurements result in inherently noisy and biased estimates. We exploit mixing time results in order to overcome the impact of the bias and establish sufficient conditions for convergence to a globally optimal solution. We discuss our algorithm in the context of different systems, including queueing networks, loss networks, and wireless networks. We also illustrate how the algorithm can be used in such systems to optimize a service/cost trade-off, to map parameter regions that lead to systems meeting specified constraints, and to achieve target performance measures. For the latter application, we first identify which performance measures can be controlled depending on the set of configurable parameters. We then characterize the achievable region of performance measures in product-form networks, and finally we describe how our algorithm can be used to achieve the target performance in an online, distributed fashion, depending on the application context.

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.

As the Internet-of-Things (IoT) emerges, connecting immense numbers of sensors and devices, the continual growth in wireless communications increasingly manifests itself in terms of a larger and denser population of nodes with intermittent traffic patterns. A crucial issue that arises in these conditions is how to set the activation rates as a function of the network density and traffic intensity. Depending on the scaling of the activation rates, dense node populations may either result in excessive activations and potential collisions, or long delays that may increase with the number of nodes, even at low load. Motivated by the above issues, we examine optimal activation rate scalings in ultra-dense networks with intermittent traffic sources. We establish stability conditions, and provide closed-form expressions which indicate that the mean delay is roughly inversely proportional to the nominal activation rate. We also discuss a multi-scale mean-field limit, and use the associated fixed point to determine the buffer content and delay distributions. The results provide insight in the scalings that minimize the delay while preventing excessive activation attempts. Extensive simulation experiments demonstrate that the mean-field asymptotics yield highly accurate approximations, even when the number of nodes is moderate.

The development of 5G wireless networking is flourishing, introducing major paradigm shifts and key new technologies such as Radio- over-Fiber (RoF). A fundamental concept for achieving the 5G design objectives is dynamically allocating frequencies, sub-bands and wavelengths. While these allocation problems have been extensively studied in wireless and optical domains in isolation, the combination has received little attention so far. However, with the advances in software-defined radio access networking and RoF technologies, there is increasing need and scope for joint optimization across the two domains, in order to harness the full potential of these networks. Motivated by these observations, we introduce a model for jointly optimal sub-band and wavelength allocation in pico-cell networks where virtual access points (APs) transmit via remote radio heads (RRHs) connected through RoF technology. We specifically account for the optical network topology, which introduces a distinct set of constraints in both the optical and wireless domain. Since the resulting load balancing problem is NP-hard, we introduce a heuristic for obtaining a stabilizing allocation which provides all RRHs with sufficient spectrum capacity to deal with their load. Numerical experiments demonstrate that the heuristic provides near-optimal solutions.

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.

Network densification has emerged as a powerful paradigm to boost spectral efficiency and accommodate the continual rise in demand for wireless capacity. The corresponding reduction in cell sizes also results however in greater spatial and temporal uncertainty and variation in traffic patterns and more extreme and unpredictable interference conditions. These features create unprecedented challenges for efficient allocation of spectral resources compared to conventional cellular networks. As a further challenge, the allocation of spectral resources needs to be jointly optimized with the assignment of wavelengths in the optical backhaul of Radio-over-Fiber (RoF) networks, which are increasingly used in dense deployments and indoor environments. Motivated by these issues, we develop online algorithms for joint radio frequency and optical wavelength assignment in RoF networks. The proposed algorithms rely on load measurements at the various access points, and involve configurable thresholds for triggering (re)assignment of spectral resources. We provide a detailed specification of a system implementation, and conduct extensive simulation experiments to examine the behaviour in various scenarios and assess the impact of key parameters. The results in particular demonstrate that the proposed algorithms are capable of maintaining adequate load levels for spatially heterogeneous and time-varying traffic conditions, while providing favourable throughput performance.

The Blockchain paradigm provides a popular mechanism for establishing trust and consensus in distributed environments. While Blockchain technology is currently primarily deployed in crypto-currency systems like Bitcoin, the concept is also expected to emerge as a key component of the Internet-of-Things (IoT), enabling novel applications in digital health, smart energy, asset tracking and smart transportation. As Blockchain networks evolve to industrial deployments with large numbers of geographically distributed nodes, the block transfer and processing delays arise as a critical issue which may create greater potential for forks and vulnerability to adversarial attacks. Motivated by these issues, we develop stochastic network models to capture the Blockchain evolution and dynamics and analyze the impact of the block dissemination delay and hashing power of the member nodes on Blockchain performance in terms of the overall block generation rate and required computational power for launching a successful attack. The results provide useful insight in crucial design issues, e.g., how to adjust the ‘difficulty-of-work’ in the presence of delay so as to achieve a target block generation rate or appropriate level of immunity from adversarial attacks. We employ a combination of analytical calculations and simulation experiments to investigate both stationary and transient performance features, and demonstrate close agreement with measurements on a wide-area network testbed running the Ethereum protocol.

We consider scheduling in networks with interference constraints and reconfiguration delays, which may be incurred when one service schedule is dropped and a distinct service schedule is adopted. Reconfiguration delays occur in a variety of communication settings, such as satellite, optical, or delay-tolerant networks. In the absence of reconfiguration delays it is well known that the celebrated Max-Weight scheduling algorithm guarantees throughput optimality without requiring any knowledge of arrival rates. As we will show, however, the Max-Weight algorithm may fail to achieve throughput optimality in case of nonzero reconfiguration delays. Motivated by the latter issue, we propose a class of adaptive scheduling algorithms which persist with the current schedule until a certain stopping criterion is reached, before switching to the next schedule. While earlier proposed Variable Frame-Based Max-Weight (VFMW) policies belong to this class, we also present Switching-Curve-Based (SCB) policies that are more adaptive to bursts in arrivals. We develop novel Lyapunov drift techniques to prove that this class of algorithms under certain conditions achieves throughput optimality by dynamically adapting the durations of the interswitching intervals. Numerical results demonstrate that these algorithms significantly outperform the ordinary Max-Weight algorithm, and that SCB policies yield a better delay performance than VFMW policies.

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.

As electric transmission networks continue to increase in complexity and volatility, there is a growing potential for cascading failure effects to cause major blackouts. Understanding these effects and assessing the risks involved is of critical importance in operating the electric grid and maintaining high reliability. Analysis of empirical data suggests that blackout sizes obey a power-law with exponents that vary across data sets. For a particular macroscopic cascading failure model, such power-law behavior was also observed with one specific exponent. Motivated by the variation in the exponents revealed by empirical blackout data, we extend this cascading failure model with a network splitting mechanism. We demonstrate the impact of the latter feature on the power-law exponent of the blackout size. Moreover, we identify the most likely scenario for a severe blackout to occur. These insights provide crucial steps towards a deeper understanding of more complex network splitting scenarios.

Random-access algorithms such as the CSMA protocol provide a popular mechanism for distributed medium access control in large-scale wireless networks. Mean-field analysis has emerged as a convenient approach to obtain tractable performance estimates in such networks, but a critical limitation of the classical set-up is that all nodes are assumed to belong to a finite number of classes. We consider spatial mean-field limits which do not involve such a requirement, characterized in terms of a set of partial-differential equations, and in particular examine the fixed points of these equations for some specific network configurations. We discuss how the fixed points can be used to obtain estimates for key performance metrics, and present simulation experiments to demonstrate the accuracy of these estimates.

We consider dense wireless random-access networks, modeled as systems of particles with hardcore interaction. The particles represent the network users that try to become active after an exponential back-off time, and stay active for an exponential transmission time. Due to wireless interference, active users prevent other nearby users from simultaneous activity, which we describe as hardcore interaction on a conflict graph. We show that dense networks with aggressive back-off schemes lead to extremely slow transitions between dominant states, and inevitably cause long mixing times and starvation effects. Keywords: Hitting times, Mixing times, Starvation phenomena, Throughput analysis, Wireless random-access networks

Cascading failure models are typically used to capture the phenomenon where failures possibly trigger further failures in succession, causing knock-on effects. In many networks, this ultimately leads to a disintegrated network where the failure propagation continues independently across the various components. In order to gain insight into the impact of network splitting on cascading failure processes, we extend a well-established cascading failure model for which the number of failures obeys a power-law distribution. We assume that a single line failure immediately splits the network in two components and examine its effect on the power-law exponent. The results provide valuable qualitative insights that are crucial first steps toward understanding more complex network splitting scenarios.

Emerging 5G networks will not only offer higher link rates, but also integrate a variety of Radio Access Technologies (RATs) in order to provide ultra-reliable broadband access to a wide range of applications with high throughput and low latency requirements. SDN-enabled dynamic path selection is of critical importance in exploiting the collective transmission resources in such heterogeneous multi-RAT environments and delivering excellent user performance. In the present paper we propose the ‘best-rate’ path selection algorithm for multi-RAT networks with various types of traffic flows. The best-rate algorithm accounts for the radio conditions and performance requirements of individual flows as well as the load conditions at the various access points. We analytically establish that the rates received by the various flows under the best-rate path selection, in conjunction with local fair resource sharing at the individual access points, are close to globally Proportional Fair. Detailed simulation experiments demonstrate that the best-rate algorithm achieves significant gains in terms of user-perceived throughput performance over various baseline policies.

Load balancing algorithms play a crucial role in delivering robust application performance in data centers and cloud networks. Recently, strong interest has emerged in Join-the-Idle-Queue (JIQ) algorithms, which rely on tokens issued by idle servers in dispatching tasks and outperform power-of-$d$ policies. Specifically, JIQ strategies involve minimal information exchange, and yet achieve zero blocking and wait in the many-server limit.The latter property prevails in a multiple-dispatcher scenario when the loads are strictly equal among dispatchers. For various reasons it is not uncommon however for skewed load patterns to occur. We leverage product-form representations and fluid limits to establish that the blocking and wait then no longer vanish, even for arbitrarily low overall load. Remarkably, it is the least-loaded dispatcher that throttles tokens and leaves idle servers stranded, thus acting as bottleneck.Motivated by the above issues, we introduce two enhancements of the ordinary JIQ scheme where tokens are either distributed non-uniformly or occasionally exchanged among the various dispatchers. We prove that these extensions can achieve zero blocking and wait in the many-server limit, for any subcritical overall load and arbitrarily skewed load profiles. Extensive simulation experiments demonstrate that the asymptotic results are highly accurate, even for moderately sized systems.

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

We are grateful to Dieter Fiems, Sergey Foss, and Jeongsim Kim and Bara Kim for their kind and valuable comments on our survey paper. Below we briefly reflect on some of their observations. While some of their comments apply to specific facets covered in the survey, quite a few other remarks touch on a variety of threads beyond the central scope that we focused on, illustrating the amazing breadth and depth of the polling literature.

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.

Bandwidth-sharing networks as considered by Roberts and Massoulié [28] (Roberts JW, Massoulié L (1998) Bandwidth sharing and admission control for elastic traffic. Proc. ITC Specialist Seminar, Yokohama, Japan) 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 α-fair bandwidth-sharing strategies achieve stability in such networks provided that no individual link is overloaded. In the present paper we focus on bandwidth-sharing networks where the load on one or several of the links exceeds the capacity. To characterize the overload behavior, we examine the fluid limit, which emerges when the flow dynamics are scaled in both space and time. We derive a functional equation characterizing the fluid limit, and show that any strictly positive solution must be unique, which in particular implies the convergence of the scaled number of flows to the fluid limit for nonzero initial states when the load is sufficiently high. For the case of a zero initial state and a zero-degree homogeneous rate allocation function, we show that there exists a linear solution to the fluid-limit equation, and obtain 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. In addition, we establish uniqueness of fluid-model solutions for monotone rate-preserving networks (in particular tree networks).