基于二部图最大匹配的动态负载均衡算法  

Dynamic load balancing algorithm based on maximum matching of bipartite graph

作　　者：周磊 孟利民[1] 周立鹏 蒋维 Zhou Lei;Meng Limin;Zhou Lipeng;Jiang Wei(College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023;College of Information Science and Technology, Zhejiang Shuren University, Hangzhou 310015)

机构地区：[1]浙江工业大学信息工程学院,杭州310023 [2]浙江树人大学信息科技学院,杭州310015

出　　处：《高技术通讯》2020年第8期798-804,共7页Chinese High Technology Letters

基　　金：国家自然科学基金(61871349);浙江省基础公益(LY18F010024,LQ19F010013)资助项目。

摘　　要：负载均衡算法是服务器集群的核心技术之一,其关键在于如何将任务均衡地分配至各个服务器,为此提出了一种基于二部图最大匹配的动态负载均衡算法。该算法以服务器所执行任务的任务量与实际完成时间的比值作为服务器的负载指标,并将负载指标实时反馈给集群系统中的管理服务器。根据待分配任务的任务量和期望完成时间以及各个服务器的负载指标,构建服务器与任务的二部图,并采用Edmonds的匈牙利算法求解二部图的最大匹配,最后按匹配结果将任务实时发送至对应服务器。实验结果表明,该算法拥有较好的负载均衡效果且更快地完成所有任务。Load balancing algorithm is one of the core technologies of server cluster,and its key is how to distribute tasks evenly to each server node.Therefore,a dynamic load balancing algorithm based on maximum matching of bipartite graph is proposed.In this algorithm,the ratio of the amount of tasks performed by the server to the actual completion time is taken as the load index of the server,and the load index is feedback to the management server in the cluster system in real time.For tasks to be allocated,a bipartite graph of servers and tasks is constructed,according to the quantity and expected completion time of tasks and the load index of each server.Then the Hungarian algorithm of Edmonds is used to find the maximum matching of the bipartite graph,and the task is sent to the corresponding server according to the matching result in the end.The experimental results show that this algorithm has better load balancing effect and can complete all tasks faster.

关 键 词：动态负载均衡 任务分配 服务器集群 二部图 最大匹配 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]