学位论文 > 优秀研究生学位论文题录展示

基于动态负载均衡的选播路由算法的研究

作　者: 王葳
导　师: 薛建生
学　校: 辽宁大学
专　业: 计算机软件与理论
关键词: 选播路由蚁群算法负载均衡流量分配
分类号: TP393.02
类　型: 硕士论文
年　份: 2011年
下　载: 26次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机技术和网络技术的迅速发展,各种类型的网络应用出现在我们生活中,满足并更激发人们对于网络服务的需求,使网络服务需求量呈指数增长。然而正是由于网络服务需求量的高速增长,导致网络服务容量相对匮乏,为了增强服务的可用性,网络服务提供商引入复制服务器技术,将具有同样内容的多个服务器分布在不同网络位置,用户就近获取所需的服务,提高互联网中信息流动效率。然而新的问题随之而来,如何才能将用户导向“最近”的服务器,同时动态均衡复制服务器间的负载,选播路由技术的出现就是为了解决这一问题。同时,网络中激增的服务流量给网络链路造成极大的压力,从而导致网络链路的拥塞。尽管这样紧张的网络状况对于一些传统的非实时网络应用影响不大,但是却严重影响实时业务的服务质量,降低用户对网络服务的满意度,继而限制和影响网络服务运营商的长期发展和效益。在当今动态复杂的网络环境中,如何将用户请求导向最佳复制服务器位置,为用户提供“更快”“更好”的网络服务,同时均衡复制服务器间以及网络链路的负载,并能够对网络状况变化迅速做出反应,动态负载均衡的路由技术逐渐成为当今研究的重要问题。动态负载均衡的路由技术包括两个关键的功能模块,首先需要选择最佳服务器并且计算一组相应的路由路径,最后在得到的候选路径间合理地动态地分配流量。于是,针对于选播路由策略和流量分配策略的改进成为当今研究热点。由于网络应用的复杂性,加之用户对于网络服务质量需求的不断提高,当前网络中的路由问题一般是多QoS约束问题,当涉及到两个或两个以上相加或相乘规则合成的约束时,寻找路由便属于NP完全问题。当今学者多采用启发式算法来解决多QoS约束的选播路由问题,并有国内学者将蚁群算法形象地应用在选播路由问题上并取得较为良好的运算结果。但是由于蚁群算法的早熟收敛特性,使最终得出的路径并非全局最优并且大大浪费运算时间,同时路径收敛也使选播路径过分集中于某些链路,造成了部分链路负载过重而其他链路空闲的负载不均衡状况。无论是网络上的链路还是选播服务器,如果不能有效均衡负载,不仅不能充分利用网络资源,而且重载链路或者服务器的拥塞问题还会引发用户丢包、时延较大等,严重影响用户的访问质量。于是,论文设计一种基于动态负载均衡的路由算法,包括以下两个主要功能模块:1.基于动态负载均衡的路由首先需要计算出一组候选路径。在路由发现过程中,为解决启发式算法普遍存在的早熟收敛问题,本文提出在蚁群算法中适时地插入差分进化算法的变异操作,利用差分进化算法受控参数少、鲁棒性强、易与其他算法混合,同时具有强大的全局寻优能力的特点,用来拓展蚁群算法的搜索空间,使选播路径均匀分布。本论文策略不是保留一条最优路径进行数据传输,而是计算出一组较优候选路径,采用多路径并行传输的技术,将流量分散到多条路径上,实现负载均衡,提高网络吞吐量及服务的可靠性。2.针对如何在上述策略计算出的一组较优候选路径上合理分配流量问题,本文对经典的基于分组水平和基于流水平的流量分割粒度进行合理的折衷,并改进了FLARE方法在同一个流的相邻分组到达间隔很小而路径间最大最小时延差较大时存在负载不均衡问题。本论文充分利用各条路径间的传输时延差,设计一种改进的FLARE(Improved FLARE,I-FLARE),将对流的分割粒度设置得更小,并为当前分组选取符合传输时延要求的负载最轻的候选路径进行转发,从而在保证分组顺序的前提达到网络上路径间的动态负载均衡。论文最后采用NS-2网络模拟器对设计的基于动态负载均衡的选播路由算法的两个功能模块分别做了仿真实验。实验结果分析证明,基于混合策略的选播路由算法可以在寻径陷入早熟收敛时有效的增加种群多样性,使算法跳出收敛并具有较强的全局搜索能力。本文设计的I-FLARE可以在保证同一流的分组有序到达目的节点同时动态均衡网络路径间的负载。改进策略大大提高了网络性能。

全文目录

摘要  4-6
ABSTRACT  6-12
图表目录  12-13
第1章绪论  13-20
  1.1 研究背景  13-15
  1.2 研究现状  15-17
    1.2.1 选播路由  15-16
    1.2.2 流量分配技术  16-17
  1.3 研究意义  17-18
  1.4 论文的工作和内容安排  18-20
第2章动态负载均衡路由相关技术分析  20-31
  2.1 选播技术研究  20-23
    2.1.1 选播定义  20-21
    2.1.2 选播服务的实现  21-23
  2.2 多QoS 约束的路由问题  23-24
    2.2.1 QoS 路由  23-24
    2.2.2 多QoS 约束问题  24
  2.3 蚁群优化算法在选播问题上的应用  24-27
    2.3.1 蚁群优化算法分析  24-25
    2.3.2 蚁群算法在选播问题上的应用  25-27
    2.3.3 蚁群算法存在问题  27
  2.4 差分进化算法分析  27-29
  2.5 多路径路由概述及分析  29-30
  2.6 小结  30-31
第3章基于混合策略的 QoS 选播路由算法  31-39
  3.1 蚁群优化算法在选播问题上的应用  31-32
  3.2 QoS 选播路由问题模型  32-33
  3.3 算法描述  33
  3.4 实现过程  33-38
    3.4.1 预处理部分  33-34
    3.4.2 蚁群搜索  34-35
    3.4.3 选择操作  35
    3.4.4 路径收敛判定标准  35-36
    3.4.5 插入变异操作的位置  36-37
    3.4.6 变异操作  37-38
  3.6 小结  38-39
第4章基于流分片转发的流量分配策略  39-48
  4.1 基于流分片转发  39-41
  4.2 I-FLARE 问题模型  41-42
  4.3 动态的分割向量  42-44
  4.4 分组-路径映射机制  44-47
    4.4.1 映射表问题  44-45
    4.4.2 分组保序问题  45
    4.4.3 动态负载均衡问题  45-47
  4.5 小结  47-48
第5章仿真测试与结果分析  48-55
  5.1 NS-2 原理概述  48-49
  5.2 仿真结果的分析与比较  49-54
    5.2.1 改进后的ACO-DE 网络仿真  49-51
    5.2.2 改进后的I-FLARE 性能仿真  51-54
  5.3 小结  54-55
第6章总结与展望  55-57
  6.1 结论  55-56
  6.2 进一步工作的方向  56-57
致谢  57-58
参考文献  58-60
攻读学位期间发表的学术论文及参加科研情况  60-61

相似论文

多导弹协同作战突防效能评估及组合优化算法研究,TJ760.1
基于蚁群算法的电梯群优化控制研究,TU857
动态环境下移动对象导航系统相关技术的研究,TP301.6
基于改进蚁群算法的机器人路径规划研究,TP242
改进的蚁群算法及其在TSP上的应用研究,TP301.6
随机路由在无线传感器网络中的研究与应用,TN929.5
基于免疫机制蚁群算法的电力系统无功优化研究,TP18
基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
高校教务管理网上选课系统优化研究,TP393.09
基于Linux集群系统的负载均衡算法研究及在Webgis中的应用,TP393.05
基于物理拓扑感知的Chord算法研究,TP393.02
电渣炉过程控制系统的设计及优化控制,TP273
LTE-A异构网络中的自组网技术研究,TN929.5
基于一种新经济模型的异构网络选择算法,TN929.5
基于QoS的无线Mesh网络路由协议及相关技术的研究,TN929.5
Ad Hoc网络中分簇路由算法的研究,TN929.5
构建分布式系统的关键技术研究与实现,TP338.8
图像信息处理机的图像处理方法研究,TP391.41
基于S2SH框架的雅砻江虚拟研究中心系统研究与设计,TP311.52
基于负载均衡的混合型应用层组播模型研究,TP393.02
智能光网络中路由选择算法的研究,TN929.1