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

多业务量矩阵下TE算法性能研究

作　者: 戴晓忠
导　师: 王晟
学　校: 电子科技大学
专　业: 通信与信息系统
关键词: 流量工程多业务量矩阵启发式算法 K最短路
分类号: TP393.01
类　型: 硕士论文
年　份: 2010年
下　载: 26次
引　用: 0次
阅　读: 论文下载

内容摘要

近十年来,Internet得到了引人注目的发展。随着Internet的快速发展,网络规模和业务量急速增长,用户对网络性能的要求也越来越高,这对网络服务商提出了严峻的挑战,如何满足客户的需求迫在眉睫。流量工程应运而生。流量工程是一种具有重要价值的网络优化技术,它通过优化网络资源的利用率来避免网络拥塞。传统的流量工程算法针对的均为精确的业务量矩阵,通过多商品流问题就可以解决。实际上要想精确的获取业务量信息是很困难的,对于规模巨大的Internet,其业务又时常改变,在动态改变的业务量矩阵或不确定业务量矩阵的环境中寻找一组有效的,鲁棒的路由方案是很多大型ISP网络运营商不得不关注的问题。这种动态性或不确定性可以用多个业务量矩阵来表示,也即多业务量矩阵下流量工程的求解。本文主要研究的是多业务量矩阵中TE算法相关问题。第二章主要讨论了多业务量矩阵TE算法中性能指标问题,主要包含了最差性能,平均性能以及它们之间的折中性能,通过设计平均性能与最差性能权重和因子来控制折中性能,并发现利用该因子获得的最优化问题具有某些特殊的特性,即平均性能是折中因子的非递减连续函数,最差性能是折中因子的非递增连续函数。并强调了后面章节考虑的性能指标是最差性能。第三章为基于OSPF/IS-IS多业务量矩阵下TE算法的研究,首先讨论了单业务量矩阵下的基于OSPF/IS-IS路由优化的问题,传统算法均为NP-hard问题,然后扩展到多业务量矩阵下的路由优化,设计了多套不同的启发式算法来求解。并着重分析了其中一种算法的性能因子,并发现该算法中K最短路算法K的取值,迭代次数对算法性能有很大的影响。第四章讨论了采用ECMP分流机制下多业务量矩阵算法的研究。也是从单业务量矩阵最优化扩展而来,设计了多套算法,并着重分析其中一种算法的性能因子。第五章首先讨论了多业务量矩阵下如何求解满足运营商性能要求的路由方案,通过设计一种启发式算法用于求解一套满足要求的方案。当一套路由不能满足要求时,则需使用多套路由方案,然后着重分析了在多套路由下如何通过监控最少的链路信息最快的切换路由。最后,本文还考虑了多业务量矩阵的合并算法。

全文目录

摘要  4-5
ABSTRACT  5-13
第一章引言  13-21
  1.1 课题研究背景  13-19
  1.2 国内外研究进展  19-20
  1.3 本文中的工作以及论文结构  20-21
第二章多业务量矩阵TE 算法性能指标研究  21-31
  2.1 简介  21
  2.2 多业务量矩阵TE 算法中性能指标研究  21-26
    2.2.1 控制变量  22-23
    2.2.2 多业务量矩阵下平均性能与最差性能  23
    2.2.3 平均性能与最差性能的折中  23-25
    2.2.4 最差性能与平均性能折中控制手段  25-26
    2.2.5 平均性能与最差性能折中优化LP 描述  26
    2.2.6 最差性能与平均性能的选择  26
  2.3 仿真实验  26-28
  2.4 实验结果及数据分析  28-29
  2.5 本章小结  29-31
第三章基于OSPF/IS-IS 多业务量矩阵TE 算法性能研究  31-43
  3.1 简介  31-32
  3.2 单业务量矩阵单路径路由优化问题研究  32-34
    3.2.1 单路径路由优化ILP 描述  32-33
    3.2.2 单路径路由优化问题  33-34
  3.3 多业务量矩阵下单路径路由优化问题研究  34-37
    3.3.1 改变单条链路权重方案  34-35
    3.3.2 改变多条链路权重方案  35-37
    3.3.3 启发式算法链路权重的调整方案  37
  3.4 仿真实验设计  37-41
    3.4.1 验证算法的简单实验  37-38
    3.4.2 实验框架以及实验拓扑结构  38-39
    3.4.3 算法分析和比较  39-41
  3.5 实验结论  41-42
  3.6 本章小结  42-43
第四章基于ECMP 多业务量矩阵TE 算法性能研究  43-56
  4.1 简介  43
  4.2 ECMP 单业务量矩阵下TE 算法研究  43-45
    4.2.1 ECMP 最短路路由优化ILP 描述  43-44
    4.2.2 多路径路由优化问题  44-45
  4.3 ECMP 多业务量矩阵下TE 算法研究  45-50
    4.3.1 启发式算法设计  45-48
    4.3.2 ECMP 多路径分流原理  48-50
  4.4 仿真实验  50-55
    4.4.1 验证算法的简单实验  50
    4.4.2 实验框架以及实验拓扑结构  50-51
    4.4.3 算法分析和比较  51-55
  4.5 实验结论  55
  4.6 本章小结  55-56
第五章多路由方案切换以及多业务量矩阵下满足性能要求算法研究  56-68
  5.1 简介  56
  5.2 多业务量矩阵下满足性能要求的路由方案研究  56-61
    5.2.1 问题的提出  56
    5.2.2 单路径路由满足性能要求的路由方案  56-57
    5.2.3 ECMP 多业务量矩阵下满足性能要求的路由方案  57
    5.2.4 仿真实验  57-61
  5.3 多路由方案下最优切换路由方案研究  61-66
    5.3.1 问题的提出  61
    5.3.2 多路由切换  61-63
    5.3.3 仿真实验  63-66
  5.4 实验结论  66
  5.5 本章小结  66-68
第六章多业务量矩阵合并算法研究  68-77
  6.1 简介  68-69
  6.2 多业务量矩阵合并算法  69-71
    6.2.1 问题的提出  69
    6.2.2 算法设计  69-70
    6.2.3 cluster 算法  70-71
  6.3 仿真实验  71-72
  6.4 实验结果及数据分析  72-75
  6.5 实验结论  75-76
  6.6 本章小结  76-77
第七章结束语  77-78
  7.1 本文的贡献  77
  7.2 需要改进的地方  77-78
致谢  78-79
参考文献  79-81
攻硕期间取得的研究成果  81-82

多业务量矩阵下TE算法性能研究

内容摘要

全文目录

相似论文