Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services
Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services
复制标题
DOI：
10.1016/j.peva.2011.07.015
复制
发表时间：
2011-11-01
影响因子：
2.2
通讯作者：
Greenberg, Albert
中科院分区：
文献类型：
--
作者：
Lu, Yi;Xie, Qiaomin;Greenberg, Albert
以搜索和在线社交网络为代表的动态内容网络服务的流行，推动了面向网络的前端越来越广泛。云中的水平扩展因其弹性而受到青睐，负载均衡器的分布式设计非常可取。针对现有的集中式负载均衡算法（如Join-the-Shortest-Queue（JSQ））对分布式调度器通信开销大的问题，提出了一种新的分布式负载均衡算法Join-Idle-Queue（JIQ）。与诸如二次幂之类的算法不同，JIQ算法在作业到达时不会在调度器和处理器之间产生通信开销。我们分析了JIQ算法在大系统的限制，并发现它有效地减少了系统负载，这产生了30倍的减少相比，在中等到高负载的2的幂运算开销。基本JIQ算法的扩展仅使用服务器负载的本地信息来处理非常高的负载。由爱思唯尔公司出版
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. Published by Elsevier B.V.