论文部分内容阅读
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负载平衡技术在宽带通信网的应用问题时开发的仿真软件平台,给出了重要数据结构以及伪码。最后是全文总结。