Kristen Gardner
Abstract
In multi-server systems, selecting to which server to dispatch an arriving job is a key factor influencing system response time. One of the most widely studied policies is Join-the-Shortest-Queue (JSQ), which is known to minimize mean response time in certain settings [7]. Many variants on JSQ have been proposed, including JSQ-d, under which a job is dispatched to the shortest queue among d servers selected uniformly at random [3, 5]; Join-Idle-Queue (JIQ), under which the dispatcher knows which servers are idle but not the queue lengths of non-idle servers [2]; and others.
The vast majority of work analyzing JSQ and related policies makes a key assumption: that the system is homogeneous, meaning that all servers have the same speed. This assumption is inaccurate in most modern computer systems. Server heterogeneity can arise, e.g., when a server farm consists of several generations of hardware, or when many virtual machines contend for resources on the same physical machine. Unfortunately, the wealth of results about how best to dispatch in homogeneous systems does not translate well to heterogeneous systems. Policies like JSQ-d and JIQ, which can achieve near-optimal performance in homogeneous systems, can lead to unacceptably high response times and even instability in heterogeneous systems [4, 8].
- S. Banawan and N. Zeidat. A comparative study of load sharing in heterogeneous multicomputer systems. In Proceedings. 25th Annual Simulation Symposium, pages 22--31. IEEE, 1992.Google Scholar
Digital Library
- Y. Lu, Q. Xie, G. Kliot, A. Geller, J. Larus, and A. Greenberg. Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services. Performance Evaluation, 68(11):1056--1071, 2011.Google ScholarDigital Library
- M. Mitzenmacher. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, 12(10):1094--1104, 2001.Google ScholarDigital Library
- A. Stolyar. Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems, 80(4):341--361, 2015.Google ScholarDigital Library
- N. Vvedenskaya, R. Dobrushin, and F. Karpelevich. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problemy Peredachi Informatsii, 32(1):20--34, 1996.Google Scholar
- W. Whitt. Deciding which queue to join: Some counterexamples. Operations research, 34(1):55--62, 1986.Google ScholarDigital Library
- W. Winston. Optimality of the shortest line discipline. Journal of Applied Probability, 14(1):181--189, 1977.Google ScholarCross Ref
- X. Zhou, F. Wu, J. Tan, Y. Sun, and N. Shro". Designing low-complexity heavy-traffic delay-optimal load balancing schemes: Theory to algorithms. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):39, 2017.Google ScholarDigital Library
Index Terms
- Smart Dispatching in Heterogeneous Systems
Recommendations
Minimizing slowdown in heterogeneous size-aware dispatching systems
Performance evaluation reviewWe consider a system of parallel queues where tasks are assigned (dispatched) to one of the available servers upon arrival. The dispatching decision is based on the full state information, i.e., on the sizes of the new and existing jobs. We are ...
Minimizing slowdown in heterogeneous size-aware dispatching systems
SIGMETRICS '12: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer SystemsWe consider a system of parallel queues where tasks are assigned (dispatched) to one of the available servers upon arrival. The dispatching decision is based on the full state information, i.e., on the sizes of the new and existing jobs. We are ...
Optimal state-free, size-aware dispatching for heterogeneous M/G/-type systems
Performance 2005We consider a cluster of heterogeneous servers, modeled as M/G/1 first-come first-serve queues with different processing speeds. A dispatcher that assigns jobs to the servers takes as input only the size of the arriving job and the overall job-size ...
Reviews
Mohammad Sadegh Kayhani Pirdehi
For modern computing platforms, heterogeneous processing nodes are the reality. Moreover, most traditional job assignment algorithms, which are designed for homogeneous systems, are not efficient for heterogeneous platforms. For the sake of gaining the least response time, this paper investigates how to best dispatch the arriving jobs in heterogeneous systems, where the available servers have different processing speeds. The introduction presents well-known job dispatching policies like join-the-shortest-queue (JSQ), its variant JSQ- d (the server is chosen among d randomly selected servers), and join-idle-queue. Emphasizing their inefficiency in heterogeneous platforms, "power-of- d " policies are introduced. The paper presents techniques to smartly manage the utilization of faster processing nodes in heterogeneous systems by selecting which servers to be polled and how to assign the arrived jobs to them. In this manner, knowing the speed of polled servers is the key factor of performance. System modeling is included; k servers are divided into fast and slow servers with exponentially distributed service times. Two scenarios are examined and analyzed. In the first scenario, to evaluate response time, a heterogeneous version of JSQ is detailed. The servers are distinguished based on fast or slow, and the job assignments on idle fast, idle slow, and no idle fast orders. In order to determine the system's response time, the authors use a deterministic limiting system and a differential equation system to model behavior. The second scenario considers a set of servers without any prior knowledge of speed. After a period of random job assignments, servers with more accomplished jobs are assigned higher priority for polling and job assignments. Based on innovations from system results, JSQ- d with accomplishment sampling (JSQ-DAS) is a nice idea. While the paper is good, it could be improved by including an analytical discussion of JSQ-DAS.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments