Optimal Load Balancing in Bipartite Graphs
Optimal Load Balancing in Bipartite Graphs
复制标题
二分图中的最优负载均衡
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
R. Srikant
中科院分区：
文献类型：
--
作者：
Wentao Weng;Xingyu Zhou;R. Srikant
云平台中的应用激发了在作业服务器约束和服务器异构性下有效负载平衡的研究。在本文中，我们研究二部图上的负载平衡，其中左节点对应于作业类型，右节点对应于服务器，每条边表示服务器可以服务的作业类型。因此，边代表局部性约束，即每个作业只能在包含某些数据和/或机器学习（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., each job can only be served at servers which contained 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.
登录
查看更多内容
非均匀负载平衡系统中d幂选择的吞吐量和延迟最优性
影响因子：
1.1
作者：
Hurtado-Lange, Daniela;Maguluri, Siva Theja
通讯作者：
Maguluri, Siva Theja
通过 D 选择功率负载均衡实现零延迟
DOI：
--
发表时间：
2018
期刊：
IEEE International Conference on Computer Communications
影响因子：
--
作者：
Liu, Xin;Ying, Lei
通讯作者：
Ying, Lei
具有一般服务器作业类兼容性的队列中 JSQ 的稳定性
影响因子：
1.2
作者：
Cruise J
通讯作者：
Cruise J
使用 Coxian™2 分布式服务时间进行负载平衡的稳态分析
DOI：
10.1002/nav.21986
发表时间：
2021
期刊：
Naval Research Logistics (NRL
影响因子：
--
作者：
Liu, Xin;Gong, Kang;Ying, Lei
通讯作者：
Ying, Lei
具有按比例公平带宽共享的连接级数据传输模型中的大流量延迟不敏感
DOI：
10.1145/3199524.3199565
发表时间：
2018
期刊：
ACM SIGMETRICS Performance Evaluation Review
影响因子：
--
作者：
Wang, Weina;Maguluri, Siva Theja;Srikant, R.;Ying, Lei
通讯作者：
Ying, Lei