面向异构网络的动态负载均衡算法及其收敛性分析
doi: 10.3724/SP.J.1146.2012.01360
A Diffusion-based Dynamic Load Balancing Algorithm for Heterogeneous Networks and Its Convergence Analysis
-
摘要: 资源共享是分布式计算的核心问题,平衡负载是实现资源共享的基本手段。现有的负载均衡算法多局限于同构网络,伴随计算终端多元化的发展趋势,面向异构网络的负载均衡需求也不断增加。该文基于经典的扩散算法,提出一种适用于异构网络环境的新的动态负载均衡算法,并通过严格的数学方法证明了算法中各结点可收敛于平衡点。实验结果表明,该算法的收敛性能优于Rotaru等人(2004)提出的GDA算法,并且对于网状网络、星型网络和花环网络等经典结构都有良好的收敛性,即便在随机生成的网络结构中,仍然保持了较快的收敛速度。Abstract: Resource sharing is one of the key issues of distributed computing, and load balancing is the fundamental approach to sharing scarce resource in a distributed computing system. However, the existing load balancing methods are mostly confined to the homogeneous networks. With the diversity of the computing terminals, there is increasing requirement for the study of load balancing toward the heterogeneous networks. In this paper, a diffusion-based dynamic load balancing algorithm is proposed for the heterogeneous networks and it is proved with mathematical strictness that all nodes will converge to the excepted balanced point. The numerical results show that the algorithm is better than the GDA algorithm proposed by Rotaru et al. (2004) and has ideal convergence property over many network topologies including Mesh, Star and Tours etc. And it converges rather fast even in a randomly generated network.
点击查看大图
计量
- 文章访问数: 2468
- HTML全文浏览量: 133
- PDF下载量: 1079
- 被引次数: 0