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

宽带通信网中Valiant负载平衡技术研究

作　者: 章小宁
导　师: 李乐民
学　校: 电子科技大学
专　业: 通信与信息系统
关键词: Valiant负载平衡交换机 WDM光网络保护整数线性规划
分类号: TN915.142
类　型: 博士论文
年　份: 2007年
下　载: 267次
引　用: 0次
阅　读: 论文下载

内容摘要

Valiant负载平衡技术来源于多处理器领域，其实质为每个结点将分布式系统赋予的任务均匀分配给其他所有结点处理，使得整个系统的负载趋于平衡，从而提高了整个系统的效率。近年来，随着Internet数据业务量的爆炸式增长以及服务质量(QoS，Quality of Service)要求的不断提高，十分有必要对宽带通信网的整体架构、选路算法以及核心节点的实现方式等方面进行改进创新，以满足网络业务的高速增长和动态变化。相应地Valiant负载平衡技术应用于宽带通信网中，为宽带通信网的相关研究产生了新的思想和新的方法。本文研究了Valiant负载平衡技术在宽带通信网中的应用问题，主要围绕以下两个方面展开：(1)Valiant负载平衡的两级交换机：(2)WDM光网络中Valiant负载平衡的鲁棒选路算法。Valiant负载平衡交换机分为两级交换结构，第一级交换结构连接输入和中间输入，起分散负载的作用，第二级交换结构连接中间输入和输出，将负载最终送到输出端口。Valiant负载平衡交换机具有良好的扩展性；同时可以提供100％吞吐量保证。但是，Valiant负载平衡交换机的基本结构会出现分组乱序的情况，这将导致网络交换性能的下降。在第二章中，作者提出了一种在两级Valiant负载平衡交换机中保证分组顺序到达的BPS(Blank Packet Stuff)算法。BPS算法通过向输入队列中填充分组从而形成满帧，使得分组顺序通过交换机。BPS算法具有良好的交换特性(平均时延及吞吐量)，同时也是一种分布式算法，各个端口可以独立地进行操作。在WDM网状网中，静态／动态条件下传统的选路和波长分配(RWA)算法适用于光路业务量／速率矩阵确知的情况，然而在实际应用中往往难于估计。第三章研究了WDM网状网在单粒度光路连接请求(即连接请求的带宽等于一个波长的带宽)的Hose不确定业务模型下Valiant负载平衡的鲁棒选路问题。本章的研究共分以下三个方面。(1)针对静态Hose不确定业务模型下全网总代价最小的优化设计问题，作者在整数线性规划(ILP，Integer Linear Programming)的基础上，提出了MRUF(Maximizing Resource Utilizaiton First)的启发式算法。MRUF算法从最大化资源利用率的角度出发计算负载分配向量，从而有效地在WDM网状网中建立了全连接的虚拓扑，使得该虚拓扑能为静态Hose不确定业务模型下所有的业务量矩阵都能提供100％的网络吞吐量。(2)针对Valiant负载平衡的鲁棒选路算法下的WDM网状网的抗毁设计问题，作者基于专用通道保护(Dedicated Path Protection)的方式，提出了TMRUF(Two-Step MRUF)的启发式算法。计算机仿真表明TMRUF算法在提供鲁棒性保护的同时具有较小的全网总代价。(3)针对逻辑全连接的光交换网络在动态Hose不确定模型下的鲁棒选路问题，基于Valiant负载平衡机制，作者提出了LBADF(Load Balancing with Adjustable Distribution Fraction)算法。LBADF算法根据网络中当前各条链路上空闲光路的数目对Valiant负载平衡机制中的分配系数进行即时动态地调整，从而达到了优化网络性能的目的。在WDM网状网中，传统的业务量疏导(Traffic Grooming)算法适用于不同粒度连接请求的业务量矩阵确知的情况，然而在实际应用中往往很难估计业务量矩阵。第四章研究了WDM网状网在多粒度带宽连接请求(即连接请求的带宽不尽相同，都小于一个波长的带宽)的Hose不确定业务模型下Valiant负载平衡的鲁棒选路问题。本章的研究共分以下两个方面。(1)针对多粒度连接请求条件下的全网总代价最小的优化设计问题，考虑到网络中存在多种不同粒度的连接请求并且连接请求不可再分的情况，作者提出了Hose模型分解(Hose Model Separation)的方法，将Hose不确定业务模型分为不同粒度的Hose子模型，并且分别为它们计算负载分配向量。作者提出了IMRUF(Improved MRUF)的启发式算法，并通过计算机仿真验证了算法的有效性。(2)针对OC-1连接请求条件下的Hose模型吞吐量最大的优化设计问题，作者提出了SBR&MRUF(Shortest Balanced Routing & MRUF)的启发式算法。SBR&MRUF算法对于短距离路径的节点对采用最短路径的方法，对于长距离路径的节点对采用平衡选路的方法，因此SBR&MRUF算法具有较优的网络性能。第五章研究了基于IP的光网络在Hose不确定模型下的网络规划问题，其目标为在保证Hose不确定模型鲁棒选路的前提下建立最小代价网络。作者考察了几种适用于Hose不确定模型鲁棒选路的基本网络结构，包括传统的以电路交换为基础的单跳选路的网络结构，以点到点电路连接为基础的多跳选路的网络结构，和最新的Valiant负载平衡的两跳选路的网络结构；并针对Valiant负载平衡的两跳选路的网络结构提出了新的NSRLB(Non-Uniform Selective Randomized LoadBalancing)算法。NSRLB算法拥有较好的时延和时延抖动特性，同时与单跳结构的VPN树，多跳结构的VPN树以及两跳结构的随机负载平衡算法和选择性随机负载平衡算法相比，具有较小的网络代价。为验证、评估本文所提各种算法的性能，作者自行开发了相关软件仿真平台软件，并利用这仿真平台考察了各种算法的性能。第六章介绍了在研究Valiant负载平衡技术在宽带通信网的应用问题时开发的仿真软件平台，给出了重要数据结构以及伪码。最后是全文总结。

全文目录

中文摘要  5-8
Abstract  8-12
目录  12-15
简略字表  15-16
算法缩略字表  16-17
第一章绪论  17-43
  1.1 Valiant负载平衡交换机  18-32
    1.1.1 下一代路由器交换结构概述  18-20
    1.1.2 Valiant负载平衡交换机结构概述  20-23
      1.1.2.1 虚通道流控制技术  20-22
      1.1.2.2 Valiant负载平衡交换机基本结构  22-23
    1.1.3 Valiant负载平衡交换机性能分析  23-29
      1.1.3.1 Valiant负载平衡交换机吞吐量分析  23-25
      1.1.3.2 Valiant负载平衡交换机时延分析  25-29
    1.1.4 Valiant负载平衡交换机的应用模型  29-31
    1.1.5 Valiant负载平衡交换机小结  31-32
  1.2 WDM光网络中的Valiant负载平衡的鲁棒选路算法  32-40
    1.2.1 WDM光网络概述  32-36
      1.2.1.1 WDM技术的出现和发展  32-33
      1.2.1.2 从点到点传输系统到WDM智能光网络  33-35
      1.2.1.3 WDM光网络研究概况  35-36
    1.2.2 现有鲁棒选路算法用于WDM光网络中的缺陷  36-38
    1.2.3 Valiant负载平衡的鲁棒选路算法  38-40
  1.3 全文主要贡献与内容安排  40-43
第二章 Valiant负载平衡交换机分组有序算法研究  43-55
  2.1 研究背景  43-45
  2.2 空白分组填充(BPS)算法  45-54
    2.2.1 输入部分  46-47
    2.2.2 中间输入部分  47-49
    2.2.3 输出部分  49
    2.2.4 BPS算法特点  49-50
    2.2.5 仿真分析  50-54
  2.3 本章小结  54-55
第三章 WDM网状网在单粒度光路连接请求条件下的Valiant负载平衡的鲁棒选路算法研究  55-87
  3.1 研究背景  55-59
    3.1.1 WDM网状网中RWA算法概述  55-56
    3.1.2 WDM网状网中Hose不确定业务模型下的鲁棒选路算法  56-58
    3.1.3 本章的工作安排  58-59
  3.2 WDM网状网在单粒度连接请求条件下基于最小全网总代价的静态鲁棒选路算法研究  59-73
    3.2.1 问题描述  59
    3.2.2 ILP描述  59-64
    3.2.3 启发式算法  64-67
      3.2.3.1 最小路径代价优先算法  65-66
      3.2.3.2 最大资源利用率优先算法  66-67
    3.2.4 Valiant负载平衡鲁棒选路中有效业务量矩阵的配置方法  67-68
    3.2.5 仿真与分析  68-72
    3.2.6 结论  72-73
  3.3 WDM网状网在静态鲁棒选路算法下的抗毁设计  73-78
    3.3.1 问题描述  73-75
    3.3.2 启发式算法  75-76
      3.3.2.1 OMRUF算法  75-76
      3.3.2.2 TMRUF算法  76
    3.3.3 仿真与分析  76-78
    3.3.4 结论  78
  3.4 全连接光网络在单粒度连接请求条件下的动态鲁棒选路算法研究  78-87
    3.4.1 问题描述  78-79
    3.4.2 分配系数可调的负载平衡选路算法  79-84
      3.4.2.1 ILP描述  80-81
      3.4.2.2 启发式算法  81-84
    3.4.3 仿真与分析  84-86
    3.4.4 结论  86-87
第四章 WDM网状网在多粒度带宽连接请求条件下的valiant负载平衡的鲁棒选路算法研究  87-113
  4.1 研究背景  87-89
    4.1.1 WDM网状网中业务量疏导概述  87-88
    4.1.2 本章的工作安排  88-89
  4.2 WDM网状网在多粒度连接请求条件下基于最小全网总代价的静态鲁棒选路算法研究  89-106
    4.2.1 问题描述  89-90
    4.2.2 Hose模型分解  90-94
    4.2.3 ILP描述  94-97
    4.2.4 启发式算法  97-98
    4.2.5 仿真与分析  98-102
    4.2.6 基于Hose模型分解的启发式算法的改进和仿真分析  102-105
    4.2.7 结论  105-106
  4.3 WDM网状网在OC-1粒度连接请求条件下基于最大Hose模型吞吐量的静态鲁棒选路算法研究  106-113
    4.3.1 问题描述  106
    4.3.2 ILP描述  106-108
    4.3.3 启发式算法  108-110
      4.3.3.1 SPR算法  108-109
      4.3.3.2 BR算法  109
      4.3.3.3 SBR算法  109-110
      4.3.3.4 启发式算法中的剩余步骤  110
    4.3.4 仿真与分析  110-112
    4.3.5 结论  112-113
第五章基于IP的的光网络基本结构中鲁棒选路算法研究  113-122
  5.1 研究背景  113
  5.2 不同网络结构下针对Hose不确定模型的鲁棒选路算法  113-116
    5.2.1 单跳/多跳选路的网络结构下的鲁棒选路算法  114
    5.2.2 Valiant两跳选路的网络结构下的鲁棒选路算法  114-116
  5.3 问题描述  116
  4.4 非均匀选择性随机负载平衡的鲁棒选路算法  116-118
  5.5 仿真与分析  118-121
  5.6 结论  121-122
第六章本文研究中采用的仿真平台  122-131
  6.1 概述  122
  6.2 OPNET计算机仿真软件介绍  122-126
    6.2.1 仿真软件的总体框架  122-123
    6.2.2 输入节点模块  123-124
    6.2.3 交换级节点模块  124
    6.2.4 中间输入节点模块  124-125
    6.2.5 仿真模块的应用描述  125-126
  6.3 VC计算机仿真软件介绍  126-131
    6.3.1 仿真软件的总体框架  126-128
    6.3.2 重要伪码  128-131
第七章全文总结  131-135
  7.1 研究工作总结  131-133
  7.2 展望  133-135
致谢  135-136
参考文献  136-146
个人简历  146-147
本文作者在读博期间发表、录用和投出的文章  147-149
攻读博士期间参加的科研项目  149
攻读博士期间获得的奖励  149

宽带通信网中Valiant负载平衡技术研究

内容摘要

全文目录

相似论文