基于非对称balls-into-bins的高效平衡负载分配模型

在大规模数据中心和P2P覆盖网络等复杂网络负载平衡分配中,前人提出了多种多样的负载分配方法,但许多方法为了达到更好的平衡负载指标,追求越来越复杂的算法,使得时间复杂度和算法复杂度很难控制在合理的范围之内。本文在研究了经典balls-into-bins、Azar balls-into-bins和balls into non-uniformbins等模型的基础上,提出了一种新颖高效的非对称balls-into-bins平衡负载分配模型,该模型具有异构的balls、异构的bins,以及不同的bin选择概率,能以很高的概率将最大负载均衡地控制在合理的范围内,通信负载很小,且具有很好的可扩展性,通过拓展,该模型在负载平衡的诸多领域都将有广阔的应用空间。

An efficient and balanced load allocation model based on non-uniform balls-into-bins

In balanced load allocation problem in complex systems like large-scale data center and P2P overlay network, the various load allocation methods have been proposed. But in order to achieve better balanced load index, many methods are in pursuit of more and more complicated algorithms. Which make the time and algorithm complexity hard to control. Based on the study of the original balls-into-bins model, Azar balls-into-bins model and balls into non-uniform bins model, the paper brings forward an efficient and balanced non-uniform balls-into-bins load allocation model, which is provided with heterogeneous balls, heterogeneous bins and different bin selection probabilities. The model can achieve rational largest load with high probabilities, in a little time and algorithm complexity cost. The model is extensible and can be applied in lots of domains.