Combining Size-Based Load Balancing with Round-Robin for Scalable Low Latency

When dispatching jobs to parallel servers, or queues, the highly scalable round-robin (RR) scheme reduces the variance of interarrival times at all queues to a great extent but has no impact on the variances of service processes. Contrariwise, size-interval task assignment (SITA) routing has little impact on the variances of interarrival times but makes the service processes as deterministic as possible. In this paper, we unify both ‘static’ approaches to design a scalable load balancing framework able to control the variances of the arrival and service processes jointly. It turns out that the resulting combination significantly improves performance and is able to drive the mean job delay to zero in the large-system limit; it is known that this property is not achieved when both approaches are considered separately. Within realistic parameters, we show that the optimal number of size intervals that partition the support of the job size distribution is small with respect to the system size. This enhances the applicability of the proposed load balancing scheme at a large scale. In fact, we find that adding a little bit of information about job sizes to a dispatcher operating under RR improves performance a lot. Under the optimal scaling of size intervals and assuming highly variable job sizes, numerical simulations indicate that the proposed algorithm is competitive with the (less scalable) join-the-shortest-workload algorithm even when the system size grows large.

Related papers:

title: The effect of queue discipline on waiting time variance
abstract: It is usual in the theory of queues to assume that customers are served in the order of their arrival. In some applications (e.g. telephone engineering), however, other forms of queue discipline are more realistic. The precise effect of any such change on the waiting-time distribution of a customer will depend on the procedure envisaged (random service, “last come, first served”, etc.), but it is possible to make certain general statements. Thus it is well known that, under certain conditions, the mean is independent of the queue discipline. The purpose of the present note is to consider the variance of waiting time, and we shall prove that this is a minimum when the customers are served in order of arrival. Thus this is, in a sense, the “fairest” queue discipline. This does not, of course, mean that other procedures may not be justified when different criteria are taken into account.

title: Some inequalities for the queue GI/G/1
abstract: One of the central problems in the theory of queues has been the study of the singleserver queue with various assumptions about the probabilistic nature of the input and service processes. In particular, the queue GI1//1 (in the notation of Kendall (1953)) has been studied by Lindley (1952), and a complete formal solution, under mild analytic conditions, for the equilibrium waiting-time distribution, has been obtained by Smith (1953). This solution is not, however, easy to evaluate except for very special distributions of interarrival and service times. The present paper is concerned with the mean and variance of the waiting time, which are quantities of some practical importance. Inequalities are derived for these moments, both in equilibrium and non-equilibrium conditions. Thus we consider a queueing system in which customers C0, C1, ... arrive and are attended to by a single server in the order of their arrival. The customer Cn waits in the queue for a time Wn, and is then served in a further time 8nWe denote by tn the time elapsing between the arrivals of successive customers Cn, Cn+?, and write n-i UnSntn Un E Ur. (1) r=O

title: Optimal Load Balancing on Distributed Homogeneous Unreliable Processors
abstract: We consider optimal load balancing in a distributed computing environment consisting of homogeneous unreliable processors. Each processor receives its own sequence of tasks from outside users, some of which can be redirected to the other processors. Processing times are independent and identically distributed with an arbitrary distribution. The arrival sequence of outside tasks to each processor may be arbitrary as long as it is independent of the state of the system. Processors may fail, with arbitrary failure and repair processes that are also independent of the state of the system. The only information available to a processor is the history of its decisions for routing work to other processors, and the arrival times of its own arrival sequence. We prove the optimality of the round-robin policy, in which each processor sends all the tasks that can be redirected to each of the other processors in turn. We show that, among all policies that balance workload, round robin stochastically minimizes the nth task completion time for all n, and minimizes response times and queue lengths in a separable increasing convex sense for the entire system. We also show that if there is a single centralized controller, round-robin is the optimal policy, and a single controller using round-robin routing is better than the optimal distributed system in which each processor routes its own arrivals. Again "optimal" and "better" are in the sense of stochastically minimizing task completion times, and minimizing response time and queue lengths in the separable increasing convex sense.

title: On Choosing a Task Assignment Policy for a Distributed Server System
abstract: We consider a distributed server system model and ask which policy should be used for assigning tasks to hosts. In our model each host processes tasks in First-Come-First-Serve order and the task's service demand is known in advance. We consider four task assignment policies commonly proposed for such distributed server systems: Round-Robin, Random, Size-Based, in which all tasks within a give size range are assigned to a particular host, and Dynamic-Least-Work-Remaining, in which a task is assigned to the host with the least outstanding work. Our goal is to understand the influence of task size variability on the decision of which task assignment policy is best. We find that no one of the above task assignment policies is best and that the answer depends critically on the variability in the task size distribution. In particular we find that when the task sizes are not highly variable, the Dynamic policy is preferable. However when task sizes show the degree of variability more characteristic of empirically measured computer workloads, the Size-Based policy is the best choice. We use the resulting observations to argue in favor of a specific size-based policy, SITA-E, that can outperform the Dynamic policy by almost 2 orders of magnitude and can outperform other task assignment policies by many orders of magnitude, under a realistic task size distribution.

title: Asymptotically Optimal Size-Interval Task Assignments
abstract: Size-based routing provides robust strategies to improve the performance of computer and communication systems with highly variable workloads because it is able to isolate small jobs from large ones in a static manner. The basic idea is that each server is assigned all jobs whose sizes belong to a distinct and continuous interval. In the literature, dispatching rules of this type are referred to as SITA (Size Interval Task Assignment) policies. Though their evident benefits, the problem of finding a SITA policy that minimizes the overall mean (steady-state) waiting time is known to be intractable. In particular it is not clear when it is preferable to balance or unbalance server loads and, in the latter case, how. In this paper, we provide an answer to these questions in the celebrated limiting regime where the system capacity grows linearly with the system demand to infinity. Within this framework, we prove that the minimum mean waiting time achievable by a SITA policy necessarily converges to the mean waiting time achieved by SITA-E, the SITA policy that equalizes server loads, provided that servers are homogeneous. However, within the set of SITA policies we also show that SITA-E can perform arbitrarily bad if servers are heterogeneous. In this case we prove that there exist exactly $C!$C! asymptotically optimal policies, where $C$C denotes the number of server types, and all of them are linked to the solution of a single strictly convex optimization problem. It turns out that the mean waiting time achieved by any of such asymptotically optimal policies does not depend on how job-size intervals are mapped to servers. Our theoretical results are validated by numerical simulations with respect to realistic parameters and suggest that the above insights are also accurate in small systems composed of a few servers, i.e., ten.

title: Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems
abstract: We consider the following distributed service model: jobs with unit mean, exponentially distributed, and independent processing times arrive as a Poisson process of rate λ N, with 0<λ<1, and are immediately dispatched to one of several queues associated with N identical servers with unit processing rate. We assume that the dispatching decisions are made by a central dispatcher endowed with a finite memory, and with the ability to exchange messages with the servers. We study the fundamental resource requirements (memory bits and message exchange rate), in order to drive the expected steady-state queueing delay of a typical job to zero, as N increases. We propose a certain policy and establish (using a fluid limit approach) that it drives the delay to zero when either (i) the message rate grows superlinearly with N, or (ii) the memory grows superlogarithmically with N. Moreover, we show that any policy that has a certain symmetry property, and for which neither condition (i) or (ii) holds, results in an expected queueing delay which is bounded away from zero. Finally, using the fluid limit approach once more, we show that for any given α>0 (no matter how small), if the policy only uses a linear message rate α N, the resulting asymptotic (as N->∞) expected queueing delay is positive but upper bounded, uniformly over all λ>1. This is a significant improvement over the popular "power-of-d-choices" policy, which has a limiting expected delay that grows as log ←(1/(1-λ)→) when λ↑ 1.

title: The Power of Two Choices in Randomized Load Balancing
abstract: We consider the following natural model: customers arrive as a Poisson stream of rate /spl lambda/n, /spl lambda/<1, at a collection of n servers. Each customer chooses some constant d servers independently and uniformly at random from the n servers and waits for service at the one with the fewest customers. Customers are served according to the first-in first-out (FIFO) protocol and the service time for a customer is exponentially distributed with mean 1. We call this problem the supermarket model. We wish to know how the system behaves and in particular we are interested in the effect that the parameter d has on the expected time a customer spends in the system in equilibrium. Our approach uses a limiting, deterministic model representing the behavior as n/spl rarr//spl infin/ to approximate the behavior of finite systems. The analysis of the deterministic model is interesting in its own right. Along with a theoretical justification of this approach, we provide simulations that demonstrate that the method accurately predicts system behavior, even for relatively small systems. Our analysis provides surprising implications. Having d=2 choices leads to exponential improvements in the expected time a customer spends in the system over d=1, whereas having d=3 choices is only a constant factor better than d=2. We discuss the possible implications for system design.

title: Asymptotic Optimality of Power-of-d Load Balancing in Large-Scale Systems
abstract: 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.

title: Power-of-d-Choices with Memory: Fluid Limit and Optimality
abstract: In multiserver distributed queueing systems, the access of stochastically arriving jobs to resources is often regulated by a dispatcher, also known as a load balancer. A fundamental problem consist...

title: Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services
abstract: The prevalence of dynamic-content web services, exemplified by search and online social networking, has motivated an increasingly wide web-facing front end. Horizontal scaling in the Cloud is favored for its elasticity, and distributed design of load balancers is highly desirable. Existing algorithms with a centralized design, such as Join-the-Shortest-Queue (JSQ), incur high communication overhead for distributed dispatchers. We propose a novel class of algorithms called Join-Idle-Queue (JIQ) for distributed load balancing in large systems. Unlike algorithms such as Power-of-Two, the JIQ algorithm incurs no communication overhead between the dispatchers and processors at job arrivals. We analyze the JIQ algorithm in the large system limit and find that it effectively results in a reduced system load, which produces 30-fold reduction in queueing overhead compared to Power-of-Two at medium to high load. An extension of the basic JIQ algorithm deals with very high loads using only local information of server load.

title: Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
abstract: AbstractThe model is a service system, consisting of several large server pools. A server’s processing speed and buffer size (which may be finite or infinite) depend on the pool. The input flow of customers is split equally among a fixed number of routers, which must assign customers to the servers immediately upon arrival. We consider an asymptotic regime in which the total customer arrival rate and pool sizes scale to infinity simultaneously, in proportion to a scaling parameter n, while the number of routers remains fixed. We define and study a multi-router generalization of the pull-based customer assignment (routing) algorithm PULL, introduced in Stolyar (Queueing Syst 80(4): 341–361, 2015) for the single-router model. Under the PULL algorithm, when a server becomes idle it sends a “pull-message” to a randomly uniformly selected router; each router operates independently—it assigns an arriving customer to a server according to a randomly uniformly chosen available (at this router) pull-message, if there is any, or to a randomly uniformly selected server in the entire system otherwise. Under Markov assumptions (Poisson arrival process and independent exponentially distributed service requirements), and under subcritical system load, we prove asymptotic optimality of PULL: as $$n\rightarrow \infty $$n→∞, the steady-state probability of an arriving customer experiencing blocking or waiting vanishes. Furthermore, PULL has an extremely low router–server message exchange rate of one message per customer. These results generalize some of the single-router results in Stolyar 
(2015).

title: Allocation of Service Time in a Multiserver System
abstract: Reducing congestion is a primary concern in the design and analysis of queueing networks, especially in systems where sources of randomness are characterized by high variability. This paper considers a multiserver first-come, first-served (FCFS) queueing model where we arrange servers in two stations in series. All arrivals join the first service center, where they receive a maximum of T units of service. Arrivals with service requirements that exceed the threshold T join the second queue, where they receive their remaining service. For a variety of heavy tail service time distributions, characterized by large coefficient of variations, analytical and numerical comparisons show that our scheme provides better system performance than the standard parallel multiserver model in the sense of reducing the mean delay per customer in heavy traffic systems. Our model is likely to be useful in systems where high variability is a cause for degradation and where numerous service interruptions are not desired.

title: Characteristics of deterministic optimal routing for a simple traffic control problem
abstract: This paper deals with a routing problem for a pair of parallel paths connecting a source node and a destination node. The problem is to find the optimal routing that minimizes the average packet delay under the condition that all of the packets' arrival times at the source node as well as all of the packets' sizes are completely deterministic. The numerical solutions of the problem show that the optimal routing assigns most of the short packets to one path and most of the long packets to the other path when the input traffic intensity is high. This new routing assignment is called the fix-queue-based-on-size (FS) policy. It is shown mathematically that the expected average packet delay of the FS policy is smaller than that of the send-to-shortest-delay (SSD) policy if a large number of packets simultaneously arrive at the source node.

title: Surprising results on task assignment in server farms with high-variability workloads
abstract: This paper investigates the performance of task assignment policies for server farms, as the variability of job sizes (service demands) approaches infinity. Our results reveal that some common wisdoms regarding task assignment are flawed. The Size-Interval-Task-Assignment policy (SITA), which assigns each server a unique size range, was heretofore thought of by some as the panacea for dealing with high-variability job-size distributions. We show SITA to be inferior to the much simpler greedy policy, Least-Work-Left (LWL), for certain common job-size distributions, including many modal, hyperexponential, and Pareto distributions. We also define regimes where SITA's performance is superior, and prove simple closed-form bounds on its performance for the above-mentioned distributions.

title: Evaluation of task assignment policies for supercomputing servers: the case for load unbalancing and fairness
abstract: While the MPP is still the most common architecture in supercomputer centers today, a simpler and cheaper machine configuration is appearing at many supercomputing sites. This alternative setup may be described simply as a collection of multiprocessors or a distributed server system. This collection of multiprocessors is fed by a single common stream of jobs, where each job is dispatched to exactly one of the multiprocessor machines for processing. The biggest question which arises in such distributed server systems is what is a good rule for assigning jobs to host machines: i.e. what is a good task assignment policy. Many task assignment policies have been proposed, but not systematically evaluated under supercomputing workloads. We start by comparing existing task assignment policies using a trace-driven simulation under supercomputing workloads. We validate our experiments by providing analytical proofs of the performance of each of these policies. These proofs also help provide much intuition. We find that while the performance of supercomputing servers varies widely with the task assignment policy, none of the above task assignment policies perform as well as we would like.

title: Scalable Web server cluster design with workload-aware request distribution strategy WARD
abstract: We consider a Web cluster in which the content-aware distribution is performed by each of the nodes in a Web cluster. Each server in the cluster may forward a request to another node based on the requested content. We propose a new workload-aware request distribution strategy WARD, that assigns a small set of most frequent files, called core, to be served locally, by any server in a cluster, while partitioning the rest of the files to be served by different cluster nodes. We propose an algorithm, called ward-analysis, to compute the nearly optimal core size. The algorithm takes into account workload access patterns and cluster parameters such as number of nodes, node RAM, TCP handoff overhead, and disk access overhead. Our simulations driven by a realistic workload show that WARD achieves super-linear speedup with increased cluster size. It shows superior performance compared with traditional round-robin strategy (up to 260% increased throughput for a cluster of 16 nodes), and outperforms a pure partitioning strategy based on a cache-affinity requests distribution (up to 50% increased throughput for a cluster of 16 nodes).

title: Task assignment with unknown duration
abstract: We consider a distributed server system and ask which policy should be used for assigning jobs (tasks) to hosts. In our server, jobs are not preemptible. Also, the job's service demand is not known a priori. We are particularly concerned with the case where the workload is heavy-tailed, as is characteristic of many empirically measured computer workloads. We analyze several natural task assignment policies and propose a new one TAGS (Task Assignment based on Guessing Size). The TAGS algorithm is counterintuitive in many respects, including load unbalancing, non-work-conserving, and fairness. We find that under heavy-tailed workloads, TAGS can outperform all task assignment policies known to us by several orders of magnitude with respect to both mean response time and mean slowdown, provided the system load is not too high. We also introduce a new practical performance metric for distributed servers called server expansion. Under the server expansion metric, TAGS significantly outperforms all other task assignment policies, regardless of system load.

title: ADAPTLOAD: effective balancing in clustered web servers under transient load conditions
abstract: We focus on adaptive policies for load balancing in clustered web servers, based on the size distribution of the requested documents. The proposed scheduling policy, ADAPTLOAD, adapts its balancing parameters on-the-fly, according to changes in the behavior of the customer population such as fluctuations in the intensity of arrivals or document popularity. Detailed performance comparisons via simulation using traces from the 1998 World Cup show that ADAPTLOAD is robust as it consistently outperforms traditional load balancing policies, especially under conditions of transient overload.

title: Analysis of SITA queues with many servers and spacetime geometry
abstract: SITA queues were introduced in  as a means for reducing job size variance at individual hosts in a server farm. It turns out that SITA queues are mathematically very interesting. For example, they satisfy a duality that is typical of automorphic forms in number theory. This leads to useful queueing theoretic insights,  and is also related to interesting number theoretic questions, , . In this paper we will consider other aspects of SITA queues which turn out to be related to two dimensional Lorentzian geometry. In particular we will be interested in the behavior of SITA queues as h → ∞. The tail of the waiting time function was studied in detail in . We will concentrate on the average waiting time E(W ), rather than the tail since it leads to some interesting analogy and insights. A SITA queue consists of h hosts, numbered 1, ..., h and a set of cutoffs 0 = s0 1 such that tj(x)/t1(x) = cj for all x. In this case, we again take t1 to be the identity (job sizes are measured by the time they take on host 1).

title: Self-similarity through high-variability: statistical analysis of ethernet LAN traffic at the source level
abstract: A number of recent empirical studies of traffic measurements from a variety of working packet networks have convincingly demonstrated that actual network traffic is self-similar or long-range dependent in nature (i.e., bursty over a wide range of time scales) - in sharp contrast to commonly made traffic modeling assumptions. In this paper, we provide a plausible physical explanation for the occurrence of self-similarity in high-speed network traffic. Our explanation is based on convergence results for processes that exhibit high variability (i.e., infinite variance) and is supported by detailed statistical analyses of real-time traffic measurements from Ethernet LAN's at the level of individual sources.Our key mathematical result states that the superposition of many ON/OFF sources (also known as packet trains) whose ON-periods and OFF-periods exhibit the Noah Effect (i.e., have high variability or infinite variance) produces aggregate network traffic that features the Joseph Effect (i.e., is self-similar or long-range dependent). There is, moreover, a simple relation between the parameters describing the intensities of the Noah Effect (high variability) and the Joseph Effect (self-similarity). An extensive statistical analysis of two sets of high time-resolution traffic measurements from two Ethernet LAN's (involving a few hundred active source-destination pairs) confirms that the data at the level of individual sources or source-destination pairs are consistent with the Noah Effect. We also discuss implications of this simple physical explanation for the presence of self-similar traffic patterns in modern high-speed network traffic for (i) parsimonious traffic modeling (ii) efficient synthetic generation of realistic traffic patterns, and (iii) relevant network performance and protocol analysis.

title: Self-similarity in World Wide Web traffic: evidence and possible causes
abstract: Recently the notion of self-similarity has been shown to apply to wide-area and local-area network traffic. In this paper we examine the mechanisms that give rise to the self-similarity of network traffic. We present a hypothesized explanation for the possible self-similarity of traffic by using a particular subset of wide area traffic: traffic due to the World Wide Web (WWW). Using an extensive set of traces of actual user executions of NCSA Mosaic, reflecting over half a million requests for WWW documents, we examine the dependence structure of WWW traffic. While our measurements are not conclusive, we show evidence that WWW traffic exhibits behavior that is consistent with self-similar traffic models. Then we show that the self-similarity in such traffic can be explained based on the underlying distributions of WWW document sizes, the effects of caching and user preference in file transfer, the effect of user "think time", and the superimposition of many such transfers in a local area network. To do this we rely on empirically measured distributions both from our traces and from data independently collected at over thirty WWW sites.

title: Analyzing distributed Join-Idle-Queue: A fluid limit approach
abstract: In the context of load balancing, Lu et al.  introduced the distributed Join-Idle-Queue algorithm, where a group of dispatchers distribute jobs to a cluster of parallel servers. Each dispatcher maintains a queue of recently idle servers; when a job arrives to a dispatcher, it sends it to a server on its queue, or to a random server if the queue is empty. In turn, when a server becomes idle, it requests to be placed on the queue of a randomly chosen dispatcher.

title: Analysis of SITA policies
abstract: We analyze the performance of Size Interval Task Assignment (SITA) policies, for multi-host assignment in a non-preemptive environment. Assuming Poisson arrivals, we provide general bounds on the average waiting time independent of the job size distribution. We establish a general duality theory for the performance of SITA policies. We provide a detailed analysis of the performance of SITA systems when the job size distribution is Bounded Pareto and the range of job sizes tends to infinity. In particular, we determine asymptotically optimal cutoff values and provide asymptotic formulas for average waiting time and slowdown. We compare the results with the Least Work Remaining policy and compute which policy is asymptotically better for any given set of parameters. In the case of inhomogeneous hosts, we determine their optimal ordering.

title: Joint admission control and resource allocation in virtualized servers
abstract: In service oriented architectures, Quality of Service (QoS) is a key issue. Service requestors evaluate QoS at run time to address their service invocation to the most suitable provider. Thus, QoS has a direct impact on the providers' revenues. However, QoS requirements are difficult to satisfy because of the high variability of Internet workloads. This paper presents a self-managing technique that jointly addresses the resource allocation and admission control optimization problems in virtualized servers. Resource allocation and admission control represent key components of an autonomic infrastructure and are responsible for the fulfillment of service level agreements. Our solution is designed taking into account the provider's revenues, the cost of resource utilization, and customers' QoS requirements, specified in terms of the response time of individual requests. The effectiveness of our joint resource allocation and admission control solution, compared to top performing state-of-the-art techniques, is evaluated using synthetic as well as realistic workloads, for a number of different scenarios of interest. Results show that our solution can satisfy QoS constraints while still yielding a significant gain in terms of profits for the provider, especially under high workload conditions, if compared to the alternative methods. Moreover, it is robust to service time variance, resource usage cost, and workload mispredictions.