The Asymptotics of Selecting the Shortest of Two, Improved
The Asymptotics of Selecting the Shortest of Two, Improved
复制标题
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
M. Mitzenmacher;B. Vocking
中科院分区：
文献类型：
--
作者：
M. Mitzenmacher;B. Vocking
我们研究了一种新的、最近提出的基于少量选择的负载平衡方案的变体。静态(散列)设置被建模为一个球和桶的过程。这些球被按顺序放入垃圾桶中，每个球随机选择d个垃圾桶，然后进入球最少的垃圾桶。类似的动态设置被建模为这样一种场景，其中任务以泊松过程的形式到达一组FIFO服务器，并在一个队列中排队等待服务。任务探测银行中的一小部分随机服务器，并在任务最少的服务器上排队。最近有研究表明，以不对称的方式打破平局实际上会提高绩效，而在之前的所有分析中，平局都是随机打破的。我们使用uid极限模型演示了这种改进的本质，提出了进一步的改进建议，并通过模拟验证和量化了改进。
We investigate variations of a novel, recently proposed load balancing scheme based on small amounts of choice. The static (hashing) setting is modeled as a balls-and-bins process. The balls are sequentially placed into bins, with each ball selecting d bins randomly and going to the bin with the fewest balls. A similar dynamic setting is modeled as a scenario where tasks arrive as a Poisson process at a bank of FIFO servers and queue at one for service. Tasks probe a small random sample of servers in the bank and queue at the server with the fewest tasks. Recently it has been shown that breaking ties in a xed, asymmetric fashion, actually improves performance, whereas in all previous analyses, ties were broken randomly. We demonstrate the nature of this improvement using uid limit models, suggest further improvements, and verify and quantify the improvement through simulations.