Optimal Load Balancing with Locality Constraints
Optimal Load Balancing with Locality Constraints
复制标题
具有局部性约束的最佳负载平衡
DOI：
10.1145/3428330
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Srikant, R.
中科院分区：
文献类型：
--
作者：
Weng, Wentao;Zhou, Xingyu;Srikant, R.
云平台中的应用激发了在作业服务器约束和服务器异构性下有效负载平衡的研究。在本文中，我们研究二部图上的负载平衡，其中左节点对应于作业类型，右节点对应于服务器，每条边表示服务器可以服务的作业类型。因此，边代表局部性约束，即任意作业只能在包含某些数据和/或机器学习（ML）模型的服务器上提供。该系统中的服务器可以具有异构的服务速率。在此设置中，我们研究了名为加入最快的最短队列 (JFSQ) 和加入最快的空闲队列 (JFIQ) 的两种策略的性能，它们是加入最短队列和加入空闲队列的简单变体，其中关系被打破以支持最快的服务器。在“连通性”图条件下，我们证明当服务器数量趋于无穷大时，JFSQ 和 JFIQ 在平均响应时间上是渐近最优的。除了渐近最优性之外，我们还获得了有限大小系统的平均响应时间的上限。我们进一步表明，连通性条件可以通过具有相对稀疏连通性的随机二部图构造来满足。
Applications in cloud platforms motivate the study of efficient load balancing under job-server constraints and server heterogeneity. In this paper, we study load balancing on a bipartite graph where left nodes correspond to job types and right nodes correspond to servers, with each edge indicating that a job type can be served by a server. Thus edges represent locality constraints, i.e., an arbitrary job can only be served at servers which contain certain data and/or machine learning (ML) models. Servers in this system can have heterogeneous service rates. In this setting, we investigate the performance of two policies named Join-the-Fastest-of-the-Shortest-Queue (JFSQ) and Join-the-Fastest-of-the-Idle-Queue (JFIQ), which are simple variants of Join-the-Shortest-Queue and Join-the-Idle-Queue, where ties are broken in favor of the fastest servers. Under a "well-connected'' graph condition, we show that JFSQ and JFIQ are asymptotically optimal in the mean response time when the number of servers goes to infinity. In addition to asymptotic optimality, we also obtain upper bounds on the mean response time for finite-size systems. We further show that the well-connectedness condition can be satisfied by a random bipartite graph construction with relatively sparse connectivity.
登录
查看更多内容
基于拉动的负载平衡系统中的大流量延迟最优性
DOI：
--
发表时间：
2018
期刊：
Proceedings of the ACM on Measurement and Analysis of Computing Systems
影响因子：
--
作者：
Xingyu Zhou;Jian Tan;N. Shroff
通讯作者：
N. Shroff
Halfin-Whitt 机制中加入最短队列模型的稳态分析
影响因子：
1.7
作者：
Anton Braverman
通讯作者：
Anton Braverman
非均匀负载平衡系统中d幂选择的吞吐量和延迟最优性
影响因子：
1.1
作者：
Hurtado-Lange, Daniela;Maguluri, Siva Theja
通讯作者：
Maguluri, Siva Theja
多服务器系统中 Power-of-d 负载平衡的普遍性
影响因子：
--
作者：
Debankur Mukherjee;S. Borst;J. V. van Leeuwaarden;P. Whiting
通讯作者：
P. Whiting
Halfin-Whitt 渐近体制中灵活服务器系统平稳分布的紧度
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
A. Stolyar
通讯作者：
A. Stolyar