In large storage systems, files are often coded across several servers to improve reliability and retrieval speed. We consider a system of @math servers storing files using a Maximum Distance Separable code (cf. li2016mean ). Specifically, each file is stored in equally sized pieces across @math servers such that any @math pieces can reconstruct the original file. File requests are routed using the Batch Sampling routing scheme. I.e. when a request for a file is received, a centralized dispatcher routes the job into the @math -shortest queues among the @math for which the corresponding server contains a piece of the file being requested. We study the long time behavior of this class of load balancing mechanisms. In particular, it is shown that the ODE system that describes the mean field limit of the occupancy measure process has a unique fixed point which is stable. This fixed point corresponds to a distribution on @math of queue lengths with tails that decay super-exponentially. Upper and lower bounds on the decay rate are provided. Finally, we show that the unique invariant measure of the Markov occupancy measure process converges to the Dirac measure concentrated at the unique fixed point of the ODE system, establishing the interchangeability of the @math and @math limits.
Load balancing mechanisms similar to the type considered here have been studied in many works. Specifically, the Join-the-Shortest-Queue (JSQ), Join-the-Idle-Queue (JIQ), and Power-of- @math (also known as the supermarket model) routing schemes have garnered quite a bit of attention (see @cite_6 @cite_5 @cite_4 @cite_8 @cite_13 @cite_7 @cite_12 @cite_10 @cite_9 and references therein). The papers @cite_6 @cite_2 were the first to study the tail behavior of the fixed point of the ODE system associated with the Power-of- @math routing scheme, showing that in steady-state the fraction of queues with lengths exceeding @math decay super-exponentially in @math , a large improvement over the exponential rate for the setting where jobs are routed to servers uniformly at random. Later works on a similar theme include @cite_4 @cite_3 @cite_9 . In all these works, the authors study fluid and diffusion approximations for various types of load balancing mechanisms. In each case, stable fixed points are identified for the LLN limit and the interchangeability of limit property is established.
@cite_4 @cite_7 @cite_8 @cite_10 @cite_9 @cite_6 @cite_3 @cite_2 @cite_5 @cite_13 @cite_12
2963728009 2015774390 2560633844 2080634500
We consider load balancing in a network of caching servers delivering contents to end users. Randomized load balancing via the so-called power of two choices is a well-known approach in parallel and distributed systems. In this framework, we investigate the tension between storage resources, communication cost, and load balancing performance. To this end, we propose a randomized load balancing scheme which simultaneously considers cache size limitation and proximity in the server redirection process. In contrast to the classical power of two choices setup, since the memory limitation and the proximity constraint cause correlation in the server selection process, we may not benefit from the power of two choices. However, we prove that in certain regimes of problem parameters, our scheme results in the maximum load of order @math (here @math is the network size). This is an exponential improvement compared to the scheme which assigns each request to the nearest available replica. Interestingly, the extra communication cost incurred by our proposed scheme, compared to the nearest replica strategy, is small. Furthermore, our extensive simulations show that the trade-off trend does not depend on the network topology and library popularity profile details. In a Fork-Join (FJ) queueing system an upstream fork station splits incoming jobs into N tasks to be further processed by N parallel servers, each with its own queue; the response time of one job is determined, at a downstream join station, by the maximum of the corresponding tasks' response times. This queueing system is useful to the modelling of multi-service systems subject to synchronization constraints, such as MapReduce clusters or multipath routing. Despite their apparent simplicity, FJ systems are hard to analyze. This paper provides the first computable stochastic bounds on the waiting and response time distributions in FJ systems. We consider four practical scenarios by combining 1a) renewal and 1b) non-renewal arrivals, and 2a) non-blocking and 2b) blocking servers. In the case of non blocking servers we prove that delays scale as O(logN), a law which is known for first moments under renewal input only. In the case of blocking servers, we prove that the same factor of log N dictates the stability region of the system. Simulation results indicate that our bounds are tight, especially at high utilizations, in all four scenarios. A remarkable insight gained from our results is that, at moderate to high utilizations, multipath routing 'makes sense' from a queueing perspective for two paths only, i.e., response times drop the most when N = 2; the technical explanation is that the resequencing (delay) price starts to quickly dominate the tempting gain due to multipath transmissions. We consider a system of @math identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate @math . 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 @math randomly selected server pools. This assignment strategy is called the JSQ @math scheme, as it resembles the power-of- @math version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case @math . 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 @math . We use the coupling to derive the fluid limit in case @math and @math as @math , along with the associated fixed point. The fluid limit turns out to be insensitive to the exact growth rate of @math , 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 @math , 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( @math ) and O( @math ), respectively. In this paper, we study the performance characteristics of simple load sharing algorithms for heterogeneous distributed systems. We assume that nonnegligible delays are encountered in transferring jobs from one node to another. We analyze the effects of these delays on the performance of two threshold-based algorithms called Forward and Reverse. We formulate queuing theoretic models for each of the algorithms operating in heterogeneous systems under the assumption that the job arrival process at each node in Poisson and the service times and job transfer times are exponentially distributed. The models are solved using the Matrix-Geometric solution technique. These models are used to study the effects of different parameters and algorithm variations on the mean job response time: e.g., the effects of varying the thresholds, the impact of changing the probe limit, the impact of biasing the probing, and the optimal response times over a large range of loads and delays. Wherever relevant, the results of the models are compared with the M M 1 model, representing no load balancing (hereafter referred to as NLB), and the M M K model, which is an achievable lower bound (hereafter referred to as LB).