网格环境下的分布式负载均衡算法研究

网格环境下的分布式负载均衡算法研究

1网格环境负载均衡网格计算是一种新的分布计算方法。目标是在网络环境中建立一个虚拟组织，并通过内部空间的资源共享和合作，以满足复杂应用程序中大规模计算的需求。但是由于网格中各站点的处理能力和容量不均衡,作业的到达模式不一致,从而造成有的站点大量的资源被闲置,有的站点却负载过重,这就要解决网格环境下负载均衡的问题。网格环境的主要特性有:可扩展性、异构性以及大量的传输延迟,负载均衡算法要达到两个目标:第一,提高资源利用率;第二,降低平均作业响应时间。这就要求负载均衡算法能够动态预测各站点负载状况,使新到达的作业可以被委派到空闲的站点或者负载较轻的站点;另一方面,对处理能力强的站点委派较多的作业。提出的负载均衡算法综合考虑了网格站点的负载状况和处理能力。对于网格中的每个站点,根据处理能力和传输延迟,创建网格站点集群,从而解决负载委派和作业再分配。在负载均衡算法中,通过创建站点负载指数表来缓存同伴站点的负载信息,从而减少了负载预测时的传输成本。通过仿真实验分析了该分布式动态负载均衡算法的性能,从实验结果来看,该算法有效地降低了作业平均响应时间。2系统模型2.1网格层作业调度器的结构网格系统是由多个计算结点组成,这些计算结点可以是个人主机、工作站、超级计算机等,各计算结点是异构的,它们的体系结构、操作系统、处理能力可能各不相同,这就需要一种具有负载均衡功能的作业调度程序根据各计算结点处理能力的差异来分配作业,所以采用三层网格体系结构:网格层、站点层、结点层,分别表示为G层、S层、N层。网格层作业调度器负责网格站点之间的负载控制,G层由网络互联的站点集和S组成,G=(s网格站点的处理能力是由其包含的计算结点决定的,可以表示为该站点内各计算结点的平均CPU处理速度。网格系统的异构性决定了各站点在处理能力上可能各不相同。例如,站点s2.2通信模型如果消息在两个站点对(s2.3作业阵列的执行对任意站点s假设在每一个站点有一个全局等候作业队列,队列中的作业等待被委派到该站点下的某个计算结点执行。只有在全局等候作业队列中作业才可以被负载迁移,用GJQ(s3实时负载分配算法动态负载均衡算法根据一定的位置策略可以分为发送方触发、接收方触发、对称触发算法3.1差异网点选择在网格系统中,各站点s的处理能力存在较大差异,通过站点集群算法产生处理能力相当的站点集群。算法随机选择m个处理能力存在较大差异的站点作为引用站点集S。这种选择方法是出于一种直觉,即如果各站点的处理能力相当,则距离接近。相似的一些方法也已经被广泛采用在应用站点集群方法之前,被引用的站点首先按照APW降序排列。对每个网格站点s上述方法只是一个近似方法,在度量近距离网格站点时,效果不佳,但通过实验发现,该方法却适合于该文所研究的负载均衡,这是因为负载均衡不需要精确度量,下面就是如何用C3.2本地网点负载指数设计定义1同伴站点调度程序利用站点集群方法为站点s当一新站点进入网格系统时,调度程序首先为该站点寻找同伴站点集PSet,根据站点处理能力采用一种启发式的方法寻找同伴站点,一般选择比本地站点处理能力更强的站点作为同伴,主要考虑异构站点。本地站点加入同伴站点集后,向邻接的同伴站点发送请求得到邻接同伴站点的负载指数消息,并把本地站点的负载指数发送到各邻接同伴站点。本地站点维护一个按负载指数从大到小排列的邻接同伴队列Q定义2负载指数设计动态负载均衡算法的一个很重要的问题是如何确定负载指数来度量当前某个站点的负载情况,Kunz∀sTET定义3执行成本传统方法在计算结点上作业的执行成本时只考虑负载指数,但是在网格环境下作业在执行前输入数据、传输过程中的通信成本、作业执行完输出结果,不同作业在这些方面所花费的时间成本差异较大,这也对负载均衡算法造成显著影响,所以在计算作业执行成本时也要考虑这些因素。如果某计算结点的负载较重,但作业到该结点的通信成本较低,则作业发送到该结点执行的效率可能更高。∀sIT(j定义4执行受益率当作业j3.3两组项负载指数和负载指数每个网格站点中都保存一个负载指数表,该表包含两个数组项,即负载指数和负载指数采样时间点。初始化时,利用站点集群策略构造多集群网格系统G的同伴站点集PSet,G=(PSet当站点s算法1是s算法14负载均衡优化在具有较多异构站点的网格环境下,通过变化不同的系统负载,采用该文给出的算法,仿真结果如图3所示。主要的参数ρ是平均系统负载,ρ=平均作业到达率/平均作业处理率,通过调整作业到达的平均时间间隔1/λ来获取该参数。图3显示了如下4种作业调度算法在不同系统负载情况下,平均作业响应时间之间的差距。(1)Local:所有作业在源站点处理(2)Random:随机选择一个站点处理新到达的作业(3)Best-Neighbor负载均衡算法(表示为BN):新到达的作业在源站点或邻居站点处理,不断地在邻居站点之间调整负载,如果源站点负载过重,则新作业被重新委派到一个邻居站点。实验中比较了该算法和Local算法、随机选择算法(用Random表示)、BN负载均衡算法在处理负载均衡时的效率。由图3可以观察出,负载较高时,4种算法的平均响应时间ART都较高。当平均系统负载逐渐增高时,4种算法的ART的差距逐渐增大,这是因为,系统负载较高时,该文的算法(用DLB表示)把新到达的作业分派到处理速度更高、负载最低的同伴站点处理,这样就减少了平均作业响应时间,所以DLB算法的执行效率更高。5动态负载均衡算法网格作为一种新型的分布式计算环境,不同于传统的分布式计算系统,主要表现在网格具有可扩展性、异构性以及大量的通信延迟,这些特征也对网格环境下的负载均衡造成显著影响,为了解决这些问题,提出了一种分散的动态负载均衡算法。通过仿真,比