On the Analysis of Randomized Load Balancing Schemes
On the Analysis of Randomized Load Balancing Schemes
复制标题
DOI：
10.1007/s002240000122
复制
发表时间：
1997-06
影响因子：
0.5
通讯作者：
M. Mitzenmacher
中科院分区：
文献类型：
--
作者：
M. Mitzenmacher
众所周知，简单的随机负载平衡方案可以有效地平衡负载，同时只产生很小的开销，这使得这种方案对实际系统很有吸引力。本文对几种动态随机负载均衡方案进行了新的分析。与以前的分析不同，我们没有假设在均衡状态下每个服务器都独立于其他服务器。我们的工作扩展了之前对超市模型的分析，该模型抽象了一个简单、有效的负载平衡方案，其中工作到达一个大型并行处理器系统。在这个模型中，客户到达一个有n个服务器的系统，作为速率为An， J< 1的泊松流，服务需求呈指数分布，平均值为1。每个客户从n个服务器中独立地、均匀地随机选择d个服务器，并根据先进先出（FIFO）协议选择客户最少的服务器。我们希望了解系统在平衡状态下的行为。在这里，我们研究了几种变体，包括恒定的服务时间和阈值模型，其中客户最多连续做出d个选择，直到找到一个低于设定阈值的选择。我们的方法包括研究有限的、确定性的模型，当服务器数量n趋于无穷大时，这些模型代表了这些系统的行为。我们工作的重要结果包括证明这些确定性系统稳定或指数收敛于不动点的有用的一般定理。我们还证明，在我们研究的几个相关模型中，允许客户进行两种选择而不是只有一种选择，会导致客户在系统中花费的预期时间呈指数级提高。
It is well known that simple randomized load balancing schemes can balance load effectively while incurring only a small overhead, making such schemes appealing for practical systems. In this paper, we provide new analyses for several such dynamic randomized load balancing schemes. Unlike previous analyses, we do not assume that in equilibrium each server is stoehastically independent from other servers.Our work extends a previous analysis of the supermarket model, a model that abstracts a simple, efficient load balancing scheme in the setting where jobs arrive at a large system of parallel processors. In this model, customers arrive at a system of n servers as a Poisson stream of rate An, J< 1, with service requirements exponentially distributed with mean 1. Each customer chooses d servers independently and uniformly at random from the n servers, and is served at the choice with the fewest customers according to the First In First Out (FIFO) protocol. We wish to understand how the system behaves in equilibrium. Here we examine several variations, including constant service times and threshold models, where a customer makes up to d successive choices until finding one below a set threshold. Our approach involves studying limiting, deterministic models representing the behavior of these systems as the number of servers n goes to infinity. Important results of our work include useful general theorems for showing that these deterministic systems are stable or converge exponentially to fixed points. We also demonstrate that allowing customers two choices instead of just one leads to exponential improvements in the expected time a customer spends in the system in several of the related models we study.