The class of Join-Idle-Queue load balancing algorithms was designed for Cloud service data centers. These algorithms have low overhead and achieve high performance for low to medium loads. In high load scenarios several variations have been proposed to improve the performance. These improvements either put work on the critical path or require two-way communication. In this paper we investigate the impact of adding redundant tokens to the Join-Idle-Queue load balancing algorithm to improve the performance under high loads. This approach is orthogonal to the existing approaches and does not add work on the critical path or require two-way communication. The communication overhead of this approach is upper bounded by one message per job. To assess the performance of the Join-Idle-Queue algorithm with redundant tokens we develop a fluid model that yields numerical results in a fraction of a second and is highly accurate for large systems. Further, the Join-Idle-Queue algorithm with redundant tokens is compared and combined with the so-called early threshold variation to demonstrate that adding redundant tokens is more effective than introducing an early threshold.

Distributed Join-Idle-Queue load balancing is known to achieve vanishing waiting times in the large-scale limit provided that the number of dispatchers remains fixed, while the number of servers tends to infinity. When the number of dispatchers$m$scales to infinity together with the number of servers$n$, “such that$r=n/m$remains fixed, the large-scale performance of Join-Idle-Queue load balancing is less clear as waiting times no longer vanish. In this paper we first discuss some existing mean field models for distributed Join-Idle-Queue load balancing with$r=n/r\mathrm{r}$fixed and explain why the well-known model introduced in [1] is not exact in the large-scale limit. The inexactness is caused by mixing two variants of distributed Join-Idle-Queue load balancing: a variant with and one without token withdrawals. Next we introduce mean field models for Join-Idle-Queue load balancing with token withdrawals, where an idle server places a token at a dispatcher with the shortest among$d$randomly chosen dispatchers. The introduced mean field models imply that in case of phase type distributed service times and a total job arrival rate of$\lambda n < \gamma$, the response time of a job corresponds to that in a standard M/PH/1 queue with load$\lambda q_{(}$. The value of$q0$can be determined numerically and depends on$\lambda, \uparrow$. and$d$Jbut not on the job size distribution (apart from its mean). This simple behavior is due to the token withdrawals and is lost if such withdrawals do not take place. We present simulation experiments that suggest that the unique fixed point of the introduced mean field models provides exact results in the large-scale limit.

In large-scale distributed systems, balancing the load in an efficient way is crucial in order to achieve low latency. Recently, some load balancing policies have been suggested which are able to achieve a bounded maximum queue length in the large-scale limit. However, these policies have thus far only been studied in case of exponential job sizes. As job sizes are more variable in real systems, we investigate how the performance of these policies (and in particular the value of these bounds) is impacted by the job size distribution. We present a unified analysis which can be used to compute the bound on the queue length in case of phase-type distributed job sizes for four load balancing policies. We find that in most cases, the bound on the maximum queue length can be expressed in closed form. In addition, we obtain job size (in)dependent bounds on the expected response time. Our methodology relies on the use of the cavity process. That is, we conjecture that the cavity process captures the behaviour of the real system as the system size grows large. For each policy, we illustrate the accuracy of the cavity process by means of simulation.

Joining the shortest or least loaded queue among d randomly selected queues are two fundamental load balancing policies. Under both policies the dispatcher does not maintain any information on the queue length or load of the servers. In this paper we analyze the performance of these policies when the dispatcher has some memory available to store the ids of some of the idle servers. We consider methods where the dispatcher discovers idle servers as well as methods where idle servers inform the dispatcher about their state. We focus on large-scale systems and our analysis uses the cavity method. The main insight provided is that the performance measures obtained via the cavity method for a load balancing policy with memory reduce to the performance measures for the same policy without memory provided that the arrival rate is properly scaled. Thus, we can study the performance of load balancers with memory in the same manner as load balancers without memory. In particular this entails closed form solutions for joining the shortest or least loaded queue among d randomly selected queues with memory in case of exponential job sizes. Moreover, we obtain a simple closed form expression for the (scaled) expected waiting time as the system tends towards instability. We present simulation results that support our belief that the approximation obtained by the cavity method becomes exact as the number of servers tends to infinity.

Our interest lies in load balancing jobs in large scale systems consisting of multiple dispatchers and FCFS servers. In the absence of any information on job sizes, a popular load balancing method is the SQ($d$) policy, which uses queue length information reported by the servers to assign incoming jobs. When job sizes are highly variable, using only queue length information is clearly suboptimal and performance can be improved if some indication can be provided to the dispatcher about the size of an ongoing job. In a FCFS server measuring the attained service time of the ongoing job is easy and servers can therefore report this attained service time together with the queue length when queried by a dispatcher. In this paper, we propose and analyse a variety of load balancing policies which improve the SQ($d$) policy by exploiting both the queue length and attained service time to assign jobs, as well as policies for which only the attained service time of the job in service is used. We present a unified analysis for all these policies in a large scale system under the usual asymptotic independence assumptions. The accuracy of the proposed analysis is illustrated using simulation. We present extensive numerical experiments which clearly indicate that a significant improvement in waiting (and thus also in response) time may be achieved by using the attained service time information on top of the queue length of a server. Moreover, the policies which do not make use of the queue length still provide an improved waiting time for moderately loaded systems.

Work sharing and work stealing are two scheduling paradigms to redistribute work when performing distributed computations. In work sharing, processors attempt to migrate pending jobs to other processors in the hope of reducing response times. In work stealing, on the other hand, underutilized processors attempt to steal jobs from other processors. Both paradigms generate a certain communication overhead and the question addressed in this paper is which of the two reduces the response time the most given that they use the same amount of communication overhead. Prior work presented explicit bounds, for large scale systems, on when randomized work sharing outperforms randomized work stealing in case of Poisson arrivals and exponential job sizes and indicated that work sharing is best when the load is below φ-1 ≈ 0.6180, with φ being the golden ratio. In this paper we revisit this problem and study the impact of the job size distribution using a mean field model. We present an efficient method to determine the boundary between the regions where sharing or stealing is best for a given job size distribution, as well as bounds that apply to any (phase-type) job size distribution. The main insight is that work stealing benefits significantly from having more variable job sizes and work sharing may become inferior to work stealing for loads as small as 1/2 + ε for any ε > 0.

In this paper we study how to estimate the back-off rates in an idealized CSMA network consisting of n links to achieve a given throughput vector using free energy approximations. More specifically, we introduce the class of region-based free energy approximations with clique belief and present a closed form expression for the back-off rates based on the zero gradient points of the free energy approximation (in terms of the conflict graph, target throughput vector and counting numbers). Next we introduce the size kmaxclique free energy approximation as a special case and derive an explicit expression for the counting numbers, as well as a recursion to compute the back-off rates. We subsequently show that the size kmaxclique approximation coincides with a Kikuchi free energy approximation and prove that it is exact on chordal conflict graphs when kmax= n. As a by-product these results provide us with an explicit expression of a fixed point of the inverse generalized belief propagation algorithm for CSMA networks. Using numerical experiments we compare the accuracy of the novel approximation method with existing methods.

Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to replicate a request so that it joins the queue at multiple servers. The request is considered complete as soon as any one of its copies completes. Redundancy allows us to overcome serverside variability-the fact that a server might be temporarily slow due to factors such as background load, network interrupts, and garbage collection to reduce response time. In the past few years, queueing theorists have begun to study redundancy, first via approximations, and, more recently, via exact analysis. Unfortunately, for analytical tractability, most existing theoretical analysis has assumed an Independent Runtimes (IR) model, wherein the replicas of a job each experience independent runtimes (service times) at different servers. The IR model is unrealistic and has led to theoretical results that can be at odds with computer systems implementation results. This paper introduces a much more realistic model of redundancy. Our model decouples the inherent job size (X) from the serverside slowdown (S), where we track both S and X for each job. Analysis within the S&X model is, of course, much more difficult. Nevertheless, we design a dispatching policy, Redundant-to-Idle-Queue, which is both analytically tractable within the S&X model and has provably excellent performance.

Carrier-sense multiple access/collision avoidance networks have often been analyzed using a stylized model that is fully characterized by a vector of back-off rates and a conflict graph. Furthermore, for any achievable throughput vector θ⃗, the existence of a unique vector ν⃗(θ⃗) of back-off rates that achieves this throughput vector was proven. Although this unique vector can in principle be computed iteratively, the required time complexity grows exponentially in the network size, making this only feasible for small networks. In this paper, we present an explicit formula for the unique vector of back-off rates ν⃗(θ⃗) needed to achieve any achievable throughput vector θ⃗ provided that the network has a chordal conflict graph. This class of networks contains a number of special cases of interest such as (inhomogeneous) line networks and networks with an acyclic conflict graph. Moreover, these back-off rates are such that the back-off rate of a node only depends on its own target throughput and the target throughput of its neighbors and can be determined in a distributed manner. We further indicate that back-off rates of this form cannot be obtained in general for networks with non-chordal conflict graphs. For general conflict graphs, we nevertheless show how to adapt the back-off rates when a node is added to the network when its interfering nodes form a clique in the conflict graph. Finally, we introduce a distributed chordal approximation algorithm for general conflict graphs, which is shown (using numerical examples) to be more accurate than the Bethe approximation.

Garbage collection is known to have a profound impact on SSD performance as it strongly influences the write amplification. Another key value that impacts the write amplification is the amount of over-provisioning, which lowers the write amplification at the cost of reducing the user-visible storage capacity. Write amplification occurs as the valid pages that remain on a block selected by garbage collection need to be copied to a free block before an erasure can take place. Some of these valid pages may however belong to a deleted file and therefore copying them is redundant. To avoid copying deleted data, the operating system can issue a Trim command to invalidate pages whenever a file is deleted. Prior analytical studies on the write amplification in SSDs assumed that no trimming takes place. In this paper we generalize a number of mean field models to assess the impact of trimming on the write amplification. Using these models we argue that the write amplification in a (large) system with trimming can be determined by analyzing a system without trimming that uses a larger over-provisioning factor (and modified hot fraction, in case of hot and cold data). Using numerical results we further show that trimming cold data results in a more significant reduction in the write amplification compared to trimming hot data.

CSMA/CA networks have often been analyzed using a stylized model that is fully characterized by a vector of back-off rates and a conflict graph. We present an explicit formula for the unique vector of back-off rate needed to achieve any achievable throughput vector provided that the network has a chordal conflict graph. These back-off rates are such that the back-off rate of a node only depends on its own target throughput and the target throughput of its neighbors and can be determined in a distributed manner. We also introduce a distributed chordal approximation algorithm for general conflict graphs which is shown (using numerical examples) to be more accurate than the Bethe approximation.

In this paper we study the performance of a family of cache replacement algorithms. The cache is decomposed into lists. Items enter the cache via the first list. An item enters the cache via the first list and jumps to the next list whenever a hit on it occurs. The classical policies FIFO, RANDOM, CLIMB and its hybrids are obtained as special cases. We present explicit expressions for the cache content distribution and miss probability under the IRM model. We develop an algorithm with a time complexity that is polynomial in the cache size and linear in the number of items to compute the exact miss probability. We introduce lower and upper bounds on the latter that can be computed in a time that is linear in the cache size times the number of items.

In this paper, we compare the performance of the pull and push strategies in a large homogeneous distributed system. When a pull strategy is in use, lightly loaded nodes attempt to steal jobs from more highly loaded nodes, while under the push strategy, more highly loaded nodes look for lightly loaded nodes to process some of their jobs. Given the maximum allowed overall probe rate R and arrival rate λ, we provide closed-form solutions for the mean response time of a job for the push and pull strategy under the infinite system model. More specifically, we show that the push strategy outperforms the pull strategy for any probe rate % > 0 when λ2+ 4(R+1) √ (R+1). We also show that under the infinite system model, a hybrid pull-and-push strategy is always inferior to the pure pull or push strategy. The relation between the finite and infinite system model is discussed, and simulation results that validate the infinite system model are provided.

Large distributed systems benefit from the ability to exchange jobs between nodes to share the overall workload. To exchange jobs, nodes rely on probe messages that are either generated by lightly-loaded or highly-loaded nodes, which corresponds to a so-called pull or push strategy. A key quantity of any pull or push strategy, that has often been neglected in prior studies, is the resulting overall probe rate. If one strategy outperforms another strategy in terms of the mean delay, but at the same time requires a higher overall probe rate, it is unclear whether it is truly more powerful. In this paper we introduce a new class of rate-based pull and push strategies that can match any predefined maximum allowed probe rate, which allows one to compare the pull and push strategy in a fair manner. We derive a closed form expression for the mean delay of this new class of strategies in a homogeneous network with Poisson arrivals and exponential job durations under the infinite system model. We further show that the infinite system model is the proper limit process over any finite time scale as the number of nodes in the system tends to infinity and that the convergence extends to the stationary regime. Simulation experiments confirm that the infinite system model becomes more accurate as the number of nodes tends to infinity, while the observed error is already around 1% for systems with as few as 100 nodes.

Garbage collection (GC) algorithms play a key role in reducing the write amplification in flash-based solid state drives, where the write amplification affects the lifespan and speed of the drive. This paper introduces a mean field model to assess the write amplification and the distribution of the number of valid pages per block for a class C of GC algorithms. Apart from the Random GC algorithm, class C includes two novel GC algorithms: the d-Choices GC algorithm, that selects d blocks uniformly at random and erases the block containing the least number of valid pages among the $d$ selected blocks, and the Random++ GC algorithm, that repeatedly selects another block uniformly at random until it finds a block with a lower than average number of valid blocks. Using simulation experiments we show that the proposed mean field model is highly accurate in predicting the write amplification (for drives with $N=50000$ blocks). We further show that the d-Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small d values, e.g., d = 10, and offers a more attractive trade-off between its simplicity and its performance than the Windowed GC algorithm introduced and analyzed in earlier studies. The Random++ algorithm is shown to be less effective as it is even inferior to the FIFO algorithm when the number of pages $b$ per block is large (e.g., for b ≥ 64).

We consider an asynchronous all optical packet switch (OPS) where each link consists of N wavelength channels and a pool of C ≤ N full range tunable wavelength converters. Under the assumption of Poisson arrivals with rate λ (per wavelength channel) and exponential packet lengths, we determine a simple closed-form expression for the limit of the loss probabilities Ploss(N) as N tends to infinity (while the load and conversion ratio σ=C/N remains fixed). More specifically, for σ ≤ λ2 the loss probability tends to (λ2-σ)/λ(1+λ), while for σ > λ2 the loss tends to zero. We also prove an insensitivity result when the exponential packet lengths are replaced by certain classes of phase-type distributions. A key feature of the dynamical system (i.e., set of ODEs) that describes the limit behavior of this OPS switch, is that its right-hand side is discontinuous. To prove the convergence, we therefore had to generalize some existing result to the setting of piece-wise smooth dynamical systems.

In applying matrix-analytic methods to M/G/1-type and tree-like quasi-birth-death (QBD) Markov chains, it is crucial to determine the solution to a (set of) nonlinear matrix equation(s). This is usually done via iterative methods. We consider the highly structured subclass of triangular M/G/1-type and tree-like QBD Markov chains that allows for an efficient direct solution of the matrix equation.

Recently, tree algorithms have been combined with successive interference cancellation to achieve a substantially higher maximum stable throughput (MST). All previous work assumed either a single or an unbounded number of signal memory locations, with MSTs of 0.662 and 0.693, respectively. In this paper, we address the gap between these two algorithms by designing and analyzing two novel general k-signal memory location algorithms.

In this paper we introduce a mean field model to analyze an optical switch equipped with both wavelength converters (WCs) and fiber delay lines (FDLs) to resolve contention in OBS networks. Under some very general conditions, that is, a general burst size distribution and any Markovian burst arrival process at each wavelength, this model determines the minimum number of WCs required to achieve a zero loss rate as the number of wavelengths becomes large. The mean field result is exact as the number of wavelengths goes to infinity and turns out to be very accurate for systems with (a few) hundred wavelengths, commonly occurring when using wavelength division multiplexing (WDM). Moreover, we show that if the number of WCs is underdimensioned, (i) periodic system behavior may occur (with the period being the greatest common divisor of the burst lengths) and (ii) increasing the number of WCs may even worsen the loss rate under the often studied minimum horizon allocation policy (as opposed to the minimum gap policy). Finally, we further demonstrate that in terms of the loss rate, including (more) FDLs may have little or no effect on the number of WCs required to achieve a near-zero loss, especially for higher loads.

A new class of multiple access algorithms for systems without feedback is introduced and analyzed. A finite population of users is assumed, where each user transmits a packetRtimes within the nextNtime slots (and all packets have an equal length of one slot). To improve the performance achieved by randomly selecting theseRslots, user codes are invoked such that any two users will only transmit simultaneously in at most one slot, i.e., 2-(N,R, 1) designs. We argue that in most cases, the set of user codes can be generated easily using cyclic designs and provide a method to selectTuser codes from the set of user codesSN,Rin case the user population consists ofT<|SN,R|users. We further demonstrate how larger populations, withT>|SN,R|, can still benefit from these user codes in two different manners. Closed formulas that express the success probability of a packet are provided for all population setups. Finally, a comparison with the random selection strategy demonstrates the performance gain realized by the new multiple access algorithms and some engineering rules to optimize the performance are provided.

A simple numerical procedure is presented to determine the maximum stable throughput (MST) of various tree algorithms with free access by defining an associated multitype branching process such that the criticality of the branching process corresponds to the stability of the tree algorithm. More precisely, a bisection algorithm is proposed that only requires the computation of the dominant eigenvalue of the expectation matrix of the branching process, the size of which is typically below 20, at each step. Using this novel approach, many existing results on free-access tree algorithms are reproduced without much effort (e.g., channels with/without noise, variable length packets, interference cancellation, etc.). Furthermore, in an almost plug-and-play manner, the MST of the free access equivalent of many existing results on tree algorithms with blocked access is established (e.g., channels with capture, control signals, multireception capabilities, etc.). The method can be applied to the class of independent and identically distributed (i.i.d.) arrival processes, which includes the Poisson process as a special case. Apart from determining the MST, the probability that a sizeicollision is resolved in a finite amount of time when the arrival rate exceeds the MST can also be computed. Some limitations of the proposed methodology are discussed as well.

In this paper we present a new theoretical model to assess the performance of a class of batch scheduling orders in a forward DVB-S2 satellite link. The scheduling order in a DVB-S2 link will determine the order in which IP packets are transmitted to the receivers and thus determines the amount of required padding and sub-optimal transmissions. The validity of the model is investigated by various simulation runs which show a very close agreement with the theoretical model. Using this model we also identify the optimal scheduling order within this class of orders, given that some mild and realistic conditions on the modulation and coding schemes apply.

We present a detailed analysis of the maximum channel utilization and loss performance in an optical buffer having access to a single outgoing channel. Such a system, consisting of a number of fiber delay lines, can only realize a discrete set of delays to resolve output port contention. This leads to an underutilization of the channel capacity, which reduces overall performance. The framework considered in this paper greatly simplifies the assumptions made in previous work, which allows us to study the impact of a variety of new parameters on the performance, e.g., the burstiness of the arrival process and the correlation of consecutive burst lengths. Moreover, we present exact results for both the channel utilization and loss rate in such a system using matrix analytic methods. We show that carefully choosing the granularity parameter can, in some cases, make a substantial difference when trying to realize lower buffer losses or a high channel utilization. Optimal values of the granularity parameter are shown to be closely related to the optical burst length distribution.

A contention resolution scheme for an uplink contention channel in a wireless access network is presented. The scheme consists of a tree algorithm, namely the identifier splitting algorithm (ISA), combined with a polling scheme. Initially, ISA is used, but at a certain level of the tree, the scheme switches to polling of the stations. This scheme is further enhanced by skipping a few levels in the tree when starting the algorithm (both in a static and a dynamic way) and by allowing multiple instants simultaneously. An analytical model of the system and its variants leads to the evaluation of its performance, by means of the delay density function and the throughput characteristics. This model is used to investigate the influence of the packet arrival rate, the instant at which the ISA scheme switches to polling, the starting level of the ISA scheme, and the use of multiple instances on the mean delay, the delay quantiles, and the throughput.

This paper determines packet level performance measures of a MAC protocol for a wireless ATM local area network. A key characteristic of the MAC protocol is the identifier splitting algorithm with polling, a contention resolution scheme used to inform the base station about the bandwidth needs of a mobile station when no piggybacking can be used. We consider higher layer packets that are generated at the mobile station and investigate the influence of the traffic characteristics of the packet arrival process on the efficiency of the protocol and on the delay that packets experience to access the shared medium.