P2P网络负载调度的超图划分算法  

Hypergraph Partitioning Algorithm for Load Scheduling of P2P Network

作　　者：于丰[1] 刘威[1] 李鹏[2] 

机构地区：[1]沈阳建筑大学网络中心,辽宁沈阳110168 [2]沈阳建筑大学信息与控制工程学院,辽宁沈阳110168

出　　处：《沈阳建筑大学学报（自然科学版）》2014年第5期953-960,共8页Journal of Shenyang Jianzhu University：Natural Science

基　　金：国家自然科学基金项目(61272253)

摘　　要：目的解决P2P用户数量持续增多时,网络节点异质性造成的负载不均衡问题,提高节点和带宽利用率.方法基于超图的动态划分思想和排队论的理论证明,将网络划分为若干个小区域的集合,利用定义的超级节点对本区域内的节点进行管理.每个区域随机选取另一个区域共同进行超图的2路划分过程,使划分后的区域总负载保持一致.通过每个小区域的节点负载平衡来获得整个网络负载的相对平衡.结果实验结果表明,采用负载均衡算法的网络节点利用率有了明显改善,而且能在更短的时间内调整至均匀分布状态.在连接数较高的情况下,网络仍然能够保持较好的稳定性.结论基于超图划分的负载调度方案可以使系统的局部范围处于平衡状态,进而实现P2P网络整体的负载均衡.It is known when the number of P2P users continually increase, the problem of load im- balance caused by node heterogeneity will appear in the network and the utilization rate of band- width will decrease. To solve this problem, this paper proposed a hypergraph partitioning algo- rithm. Based on the dynamic partitioning ideas of hypergraph and the queuing theory, the network was divided into several small regions. The nodes in local regions were managed by defined super- node. Every region randomly selected another region to cooperate a 2-way division process of hy- pergraph, so as to keep the consistency of total regions. Then the relative balance of whole network can be obtained by the node balance in each region. Simulation results show that the utilization rate of nodes can be improved significantly and nodes can be adjusted to a uniform distribution state in a shorter period of time. Under higher number of connections, the network still works well with stability and robustness. Conclusion is that using the proposed algorithm can make the local regionsof system in the balance state and realize the total load balancing of P2P network.

关 键 词：P2P 负载均衡 超图 超级节点 KL算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]