基于层次策略的动态负载均衡算法研究

论文题目: 基于层次策略的动态负载均衡算法研究

论文类型: 硕士论文

论文专业: 计算机软件与理论

作者: 丁逸

导师: 邓建明

关键词: 分布式系统,负载均衡,层次策略,拓扑,网孔,超立方,网状

文献来源: 东南大学

发表年度: 2005

论文摘要: 随着计算机及网络技术的发展,大规模并行分布式处理系统得到了广泛的应用。对于一个分布式系统而言,多个节点之间如何进行动态的任务分配调度,即动态负载均衡,在很大程度上影响着系统的性能,因而具有较高的理论研究价值和应用前景,受到了人们长期的关注。近年来,各国研究人员对此进行了大量的研究,提出了一系列的动态负载均衡算法。但这些算法并没有完全解决目前存在的问题,因此仍有必要对分布式系统的动态负载均衡进行进一步的研究。本文对负载均衡所涉及的各个方面,包括概念、分类、特点、算法机制、驱动策略、难点、算法步骤等进行了详细的讨论,总结了负载均衡的研究现状,同时还重点分析比较了现有的多个静态和动态负载均衡算法,指出了它们各自的特点和缺陷。在上述讨论的基础之上,本文从网络基础体系结构——拓扑出发,通过对常见的网孔、超立方和网状拓扑进行逻辑上的改造,根据本文中所给法则将物理拓扑划分为多个物理区域并指定每个区域的信息中心节点,必要时对这些信息中心节点组成的二级逻辑分区再指定二级信息中心节点,依此类推,最后使得物理拓扑形成逻辑上的层次结构。通过推导和计算可以证明,网络上的通信经这样的层次处理后,能够从局部区域扩展到整体,确实减少了很多基础的通信开销。基于上述的层次方法,本文提出了一个新的动态负载均衡算法,能够较好解决已有算法的诸如稳定性不够、应用比较单一、通用性不够等缺陷和不足。在此基础之上,本文还提出了一个基于预测的算法机制,该机制能够应用于均衡算法使得节点负载信息能够被准确及时的获取,从而为任务的迁移提供更好的依据;并由此建立了一个基于预测的层次负载均衡模型。算法的主要思想是通过各个局部区域的优化达到系统整体的接近最优化并特别考虑了任务之间的相互关系和系统内节点性能可能存在的差异;算法还通过改进传统的驱动策略,使用新的任务调度规则,在改善底层通信的基础上,使得系统减少了较多的额外开销,提高了算法的效率。该算法的主要特点是:⑴自适应参数可调。算法不是单一的使用某种驱动策略,而是在系统运行过程中动态调整负载阈值和参数,视用户对系统的要求选择参数值,从而获得更好的性能表现。⑵系统稳定,不会出现颠簸。算法中局部区域的使用,使得节点处理机上任务的迁移首先在内部区域上进行,必要时再进行区域之间的迁移;同时算法改进了以往的驱动策略,迁移必须从重载节点到轻载节点,目的性强,避免了一些效率不高的迁移和对节点不必要的打扰。⑶简单实用。算法没有采用基于人工智能理论等耗费较大的调度方法,而是使用局部优化带动全局优化的思想方法和较有针对性的“极端”任务调度方法,除了增加一定空间耗费和任务迁移本身带来的通信路径上的开销外,额外开销比较少。⑷具有较好的通用性。算法可以适用于目前最常见的网孔和超立方拓扑构成的同构、异构分布式系统,也可以推广到最一般的网状拓扑。论文还通过实验比较和实例分析验证了层次策略负载均衡算法的正确性和有效性。因此,本文提出的层次策略负载均衡算法确实能够比较有效和灵活地解决分布式系统的负载均衡问题,从而弥补了现有算法存在的一些缺陷。

论文目录:

摘要

Abstract

第一章引言

1.1 研究背景

1.2 论文的目标

1.3 论文的研究内容和组织结构

第二章分布式系统动态负载均衡

2.1 负载均衡问题概述

2.1.1 负载均衡的概念

2.1.2 负载均衡的分类与特点

2.1.3 负载均衡的算法机制

2.2 动态负载均衡算法的驱动策略

2.2.1 接收者驱动策略

2.2.2 发送者驱动策略

2.2.3 混合（双向）驱动策略

2.3 分布式系统动态负载均衡难点

2.3.1 动态负载均衡常见问题

2.3.2 动态负载均衡算法的要求

2.4 动态负载均衡算法的步骤

2.4.1 负载信息的收集

2.4.2 决策

2.4.3 任务迁移的实现

2.5 分布式系统负载均衡模型

2.6 现有分布式系统动态负载均衡策略

2.6.1 静态分配策略/算法

2.6.2 代表性动态负载均衡策略

第三章分布式系统网络拓扑与层次方法

3.1 网络拓扑

3.1.1 网络拓扑简介

3.1.2 网络拓扑构造的研究

3.2 网孔的层次构造与分析

3.2.1 网孔的基本结构

3.2.2 网孔的层次划分

3.3 超立方体的层次构造与分析

3.4 网状拓扑的层次构造与分析

第四章层次策略动态负载均衡研究

4.1 层次方法基本思想

4.2 mesh 拓扑的层次划分

4.3 hypercube 拓扑的层次划分

4.4 使用层次策略的负载均衡算法

4.5 基于预测的层次负载均衡模型

4.6 算法性能研究和实例分析

第五章总结与展望

5.1 本文工作的小结

5.2 待完善的工作

参考文献

致谢

发布时间: 2007-06-11

参考文献

[1].基于集群的动态反馈负载均衡算法的研究[D]. 魏钦磊.重庆大学2013
[2].基于聚类的动态自适应负载均衡算法研究[D]. 王晨冉.哈尔滨工程大学2016
[3].基于优化负载均衡算法的任务调度系统的研究与实现[D]. 朱晨晨.电子科技大学2014
[4].分布式海量数据储存系统负载均衡算法的优化设计与实现[D]. 许俊红.电子科技大学2013
[5].服务器集群中基于动态反馈的负载均衡算法[D]. 庄旻轩.大连理工大学2014
[6].分布式交通网络仿真平台的动态负载均衡算法研究及应用[D]. 张萌洁.电子科技大学2015
[7].分布式交通网络仿真的负载均衡算法研究及设计[D]. 陈满屯.电子科技大学2014
[8].轻量级MapReduce负载均衡算法研究[D]. 王泽洲.西南交通大学2017
[9].移动医疗APP系统研究与实现[D]. 高鹏.西安电子科技大学2017
[10].兰州市WebGIS系统设计与实现[D]. 贺全进.兰州大学2007

基于层次策略的动态负载均衡算法研究

猜你喜欢