| 引用本文: | 皇甫先鹏,罗雪山.基于非对称balls-into-bins的高效平衡负载分配模型.[J].国防科技大学学报,2013,35(3):67-71.[点击复制] |
| HUANGFU Xianpeng,LUO Xueshan.An efficient and balanced load allocation model based on non-uniform balls-into-bins[J].Journal of National University of Defense Technology,2013,35(3):67-71[点击复制] |
|
| |
|
|
| 本文已被：浏览 7927次 下载 6523次 |
| 基于非对称balls-into-bins的高效平衡负载分配模型 |
| 皇甫先鹏, 罗雪山 |
|
(国防科技大学 信息系统与管理学院， 湖南 长沙 410073)
|
| 摘要: |
| 在大规模数据中心和P2P覆盖网络等复杂网络负载平衡分配中，前人提出了多种多样的负载分配方法，但许多方法为了达到更好的平衡负载指标，追求越来越复杂的算法，使得时间复杂度和算法复杂度很难控制在合理的范围之内。本文在研究了经典balls-into-bins、Azar balls-into-bins和balls into non-uniform bins等模型的基础上，提出了一种新颖高效的非对称balls-into-bins平衡负载分配模型，该模型具有异构的balls、异构的bins，以及不同的bin选择概率，能以很高的概率将最大负载均衡地控制在合理的范围内，通信负载很小，且具有很好的可扩展性，通过拓展，该模型在负载平衡的诸多领域都将有广阔的应用空间。 |
| 关键词: 非对称balls-into-bins 平衡负载分配 复杂系统 |
| DOI： |
| 投稿日期：2012-09-20 |
| 基金项目:国家自然科学基金资助项目(61070216, 71071160, 61170284)；国家部委资助项目；高等学校博士学科点专项科研基金项目(20114307110011)；湖南省研究生创新资助项目(CX2010B022)；国防科大研究生创新资助项目(B100501) |
|
| An efficient and balanced load allocation model based on non-uniform balls-into-bins |
| HUANGFU Xianpeng, LUO Xueshan |
|
(College of Information System and Management, National University of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| In balanced load allocation problem in complex systems like large-scale data center and P2P overlay network, the various load allocation methods is proposed. In order to achieve better balanced load index, many methods, however, are in pursuit of more and more complicated algorithms, which makes 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, at the cost of little time and algorithm complexity. The model is extensible and can be applied in many domains. |
| Keywords: non-uniform balls-into-bins balanced load allocation complex system |
|
|
