（计算机软件与理论专业论文）基于负载均衡的mpls流量工程路由选择算法研究.pdf

牛南帅范人学颂i 学位论文 中文摘要 摘要 传统的i p 网络路由体系，无论是距离路由矢量协议( r i p ) 还是链路状态协议 ( 如内部网关协议i g p 的o s p f 与i s - i s ) ，都只能提供数据的可达性服务，不具备 全网资源利用的调节能力这些路由算法只根据网络的拓扑选择最短路径，因此 会导致一部分链路拥塞，而另一部分链路闲置，这就容易造成网络负载分布的不 平衡，极大地浪费了网络资源 在这种情况下，基于m p l s ( 多协议标签交换) 的流量工程技术应运而生m p l s 是一种介于第二层和第三层之问的标签交换技术，它使i p 网络具备高速交换、流 量控制以及q o s 能力m p l s 流量工程使用约束路由计算所需的路径，然后利用显 式路由技术使l s p ( 标记交换路径) 按照指定的路径建立约束路由技术可以根据 q o s 需求、拓扑结构和链路状态信息建立l s p ，从而使网络资源得到合理的利用 m p l st e 的关键问题是l s p 的分布优化问题，本文针对其n p - h a r d 特性，提 出了一种基于遗传算法的求解方法。同时配置了一组l s p 本算法山两个部分组 成，首先利用改进的d i j k s t r a 算法进行路由预计算，然后以剩余带宽均方差为优 化目标函数，利用遗传算法进行求解。遗传算法采用自然数编码的方法，以提高 搜索效率仿真结果表明，本算法在一定程度上改善了网络资源的利用情况，避 免了网络拥塞。达到了负载均衡的目的与此同时，本算法还克服了一条一条配 黄l s p 产生的“顶端优势”问题，能以任意顺序建立l s p 关键词：多协议标签交换，流量工程，遗传算法，负载均衡 牛南帅范人学顾i ：学位论文英文摘要 a b s t r a c t t h et r a d i t i o n a lr o u t ep r o t o c o l so ft h ei pn e t w o r k , s u c ha st h er o u t i n gi n f o r m a t i o n p r o t o c o lo u l ) 缸l dt h el i n ks t a t u sp r o t o c o l ( f o re x a m p l e , t h co s p fa n di s i so ft h e i n t e m a lg a t e w a yp r o t o c 0 1 i e i g p ) , 锄p r o v i d eo n l yt h ed a t a - r e a c h a b l e 靶l v i c e t h e s y s t e md o e sn o th a v et h ec a p a b i l i t yi nu t i l i z i n gt h ep , t o b a ln e t w o r kr l ：5 0 l l l c e s t h e s e r o u t ea l g o r i t h m ss e l e c it h es h o r t e s tp a t ha c c o r d i n gt ot h en e t w o r kt o p o l o g yo n l y h e n c e s o m l ：l i n k s 眦c o n g e s t e d , b u to t h e rl i n k sa 坞i d l e a sar e s u l t , t h en e t w o r kl o a di sn o t b a l a n c e d , w h i c hg r e a t l yw a s t e st h en e t w o r k r c s 0 1 1 r c c s t h et r a f f i ce n g i n e e r i n gf i e ) t e c h n o l o g yb a s e d0 1 1t h em u l t i p r o t o c o ll a b e ls w i t c h ( m i t s ) i sd e v d o l h lt os o l v et h ea b o v e - m e n t i o n e dp r o b l e m t h em p l si sal a b e l s w i t c ht e c h n o l o g yb c t w c c nt h es e c o n dl a y e ra n dt h et h i r dl a y e r w i t ht h om p l s t e c h n o l o g y , t h ei pn e t w o r kh a st h ec a p a b i l i t i e so f h i g h - s p e e ds w i t c h , t r a f f i cc o n t r o l ，a n d q o s t or e a l i z et h em p l st e c a l c u l a t e s t h er e q u i r e d p a t hb yu s i n g t l l e c o n s t r a i n t - b a s e dr o u t i n g , a n dt h e nc r e a t e st h el a b e ls w i t c hp a t h ( is p ) a c c o r d i n gt o t h es p e c i f i e dp a t hb y 璐i n gt h ee x p l i c i tr o u t et e c h n o l o g y t h ec o n s t r a i n t b a s e dr o u t i n g t e c h n o l o g ye n a b l e sy o ut oc a l c u l a t el s p sa c c o r d i n gt ot h eo o sr e q u i r e m e n t s ，t o p o l o g y s t r u e t u r o , a n dl i n ks t a t u si n f o r m a t i o n , t h u sr e a s o n a b l yu s i n gt h en e t w o r kr 】渤u r ! 雌 t h ek e yp r o b l e mo f t h em p l st ei st h eo p t i r n i z o dd i s t r i b u t i o no fl s p s t h i sp a p e r p r o v i d e sas o l u t i o nb a s e do nt h eg e n e t i ca l g o r i t h ma c c o r d i n gt ot h en p - h a r df e a t u r ea n d c o n f i g u r e sag r o u po fl s p s t h i sa l g o r i t h mi n e - c a l c u l a t e st h er o u t eb yu s i n gt h e i m p r o v e m e n td i j k s t r aa l g o r i t h m ，a n dt h e nt a k i n gt h ea v e r a g ef a n g c h ao fr e s i d u a l b a n d w i d t ha s 柚o b j e c t i v ef u n c t i o n s ag e n e t i ca l g o r i t h mi sd e s i g n e dt os l o v et h e p r o b l e m t h eg e n e t i ca l g o r i t h m u s c st h en a t u r a ln u m b e rc o d i n gm e t h o d ，w h i c h i n c r e a s e st h es e a r c he f f i c i e n c y t h es t i m u l a t i o nr e s u l t sp l o 、偿t h a tt h i sa l g o r i t h m e f f e c t i v e l yi m p r o v e st h eu s a g eo f t h en e t w o r ki c s o u i r c i 器a n da v o i d sn e t w o r kc o n g e s t i o n , t h u sl e a d i n gt ot h el o a db a l a n c e i na d d i t i o n , t h i sa l g o r i t h ms o l v e st h ep r o b l e mo f t o p a d v a n t a g e c a u s e db yt h ec o n f i g u r a t i o no fl s p st h a ti sp e r f o r m e do n eb yo n e i t 渤 i - 产南帅范大学硕i 学位论文 英史摘爱 k e y w o r d $ ：m p l s ，t r a f f i ce n g i n e e r i n g , g e n e t i ca d g m i t h m , l o a db a l a n c e 1 1 1 牛南帅箍人学顾i + 学位论文 第一章绪论 第一章绪论 1 1 研究背景 自从1 9 9 1 年力维网( 唧) 推出，促使i n t e r n e t 商用化之后，i n t e r n e t 便以 惊人的速度发展随着i n t e r n e t 的蓬勃发展，网络通信业务从电话、数据向视频、 多媒体等宽带业务方向发展，人们对网络所提供的延迟、带宽等q o s 能力的要求 越来越高解决这个问题的一个最直接的办法就是对网络进行扩容，但是这并不 能从根本上解决网络性能下降的问题这是因为早期i n t e r n e t 在选取路由时， 仅仅依据最短路径( s h o r t e s tp a t hf i r s t ) 的方法，这种工作方式带来了下列问题： ( 1 ) 不同源的最短路径在某些链路上重叠，导致某些链路拥塞。 ( 2 ) 某一条从源到目的地的流量需求超出了最短路径的容量，网络仍然选择这 条路，而不选择源与目的地f b j 的一条比较长的、资源没得到充分使用的路径。 也就是说，网络所面临的并不是资源的绝对不足，而是由于资源的不合理分 配和利用所造成的不足q o s 体系并不能解决由于流量的不合理分布而带来的诸 多网络性能下降问题，因此，如何高效、合理地利用有限的网络资源。成为目前 研究的主要课题。 为了解决这种由于负载分布不均衡而引起的网络拥塞，提出了流量工程( t e ， t r a f f i ce n g i n e e r i n g ) 的概念晗对。流量工程就是一种能将业务流量映射到实际 链路上，同时又可以自动优化网络资源以实现特定应用程序服务性能要求，具有 宏观调节和微观控制能力的网络工程技术其主要目的是将业务流合理分配到现 有的网络拓扑结构上，以优化网络资源的利用，提高网络性能。流量工程目前被 认为是m p l s 网络的最重要的应用之一”。 m p l s ( 多协议标签交换) 是一种可以在多种第二层媒质上进行标签交换的网络 技术，是专门为i p 设计的，这一技术结合第二层的交换和第三层路由特点，将第 二层的基础设施和第三层的路由有机地结合起来。第三层的路由在网络的边缘实 施，而在m p l s 的网络核心采用第二层交换，从而使i p 网络具备高速交换、流量 控制以及q o s 能力。m p l , 8 的显式路由技术允许完全控制数据在网络的传输路径， 可以在传送分组之前即预先建立满足一定约束的标记交换路径( l s p ) ，因此可以综 牛南帅范人学顾i 。学位论文 第一章绪论 合考虑全局业务流量需求，网络拓扑与链路状况，建立优化l s p ，可以很容易地 对网络的流量进行规划，而且能很方便地实施。 1 2 研究成果和意义 本文归纳了作者在做论文期间获得的m p l s 、遗传算法、流量工程算法方面的 知识和研究成果在介绍m p l s 流量工程的基础上本文提出了一种基于负载均衡 的m p l s 流量工程路由选择算法。该算法分为两部分：首先，运用改进的d i j k s t r a 算法进行路由预计算，然后利用遗传优化算法进行求解本算法主要完成了以下 一些工作：在路出的预计算方面采用了改进的d i j k s t r a 算法( 即在网络原拓扑 结构上进行了系列剪裁) ，并给出具体实现方法；遗传算法的编码采用自然数 编码法，克服了通常的n x n 的一维二进制编码编解码复杂，效率低的问题； 以剩余带宽均方差作为遗传算法的优化目标函数，达到了均衡网络流量分布的目 的；克服了一条一条配置l s p 产生的。顶端优势”问题，即先配置的l s p 有更 多的资源可以利用这些研究为网络资源的优化提供了一些新的思路和方法。对 流量工程的实施有一定的意义 1 3 全文内容安捧 本文的内容安排如下：第一章在介绍最短路径导致网络资源分配不合理的基 础上引入了m p l s 流量工程的概念，同时指出了本文的研究成果和内容安 誓；第二 章介绍了咿l s 流量工程，主要从流量工程的基本概念和原理、m p l s 网络的基本 原理、基于m p l s 的流量工程等几方面进行论述；第三章是遗传算法综述，分别从 遗传算法简介、遗传算法的运算过程、遗传算法的数学模型、遗传算法的基本实 现技术几方面加以阐述；第四章首先分析了目前一些m p l st e 路由选择算法的不 足，接着给出m p l st e 路由数学模型，并详细介绍本文算法的设计与实现过程， 最后对算法复杂度进行分析；第五章则对第四章提出的算法进行仿真验证。仿真 结果表明，本论文提出的算法在一定程度上改善了网络资源的利用情况，达到了 负载均衡的目的；第六章回顾总结了全文，并提出今后还需继续研究的相关问题 牛南师范人学顾i 。学位论文第一二章m p l s 流量t 程 第二章肝l s 流量工程 2 1 流量工程基本概念和原理 2 1 1 流量工程的必要性 传统的i p 网络体系，如内部网关协议i g p 的0 s p f 与r i p 、外部网关协议e g p 的b g p 4 等，只能提供数据传输的可达性服务，不具备全网资源利用的调节能力 这些路由算法只根据网络的拓扑选择最短路径，因而会导致一部分链路上的业务 量已接近容限，而另一部分链路却几乎闲置，从而引起网络局部严重拥塞和网络 资源利用率大大下降。许多比最短路径略长，但是负载更轻的潜在路径并不能够 有效地被利用起来，从而造成网络资源的不均衡利用。从整体上降低网络设备的 利用率嘲因此，网络中需要一种控制流量分布的机制，以期以最小的代价最 大化地利用现有网络设备的投资 2 1 2 流量工程的定义嘲 流量工程是一种可用来控制网络资源，提高网络性能。解决上述问题的网络资 源调控技术流量工程的目的是提高优化网络性能，般慌束，它包含技术应用 和科学的原则去测量、模型化、特性化控制因特网的业务。 当前，对流量工程的定义没有一个统一的标准，这罩对流量工程所作的定义 为：流量工程就是一种能将业务流量映射到实际链路上，同时又可以自动优化网 络资源以实现特定应用程序服务性能要求、具有宏观调节和微观控制能力的网络 工程技术 2 1 3 流量工程性能目标 流量工程目i j 己成为大型a s 系统必不可少的功能，从网络流量的观点来看， 流量工程的功能可以看作是网络中业务流量分布的优化当考虑流量工程的性能 目标时，我们可以将流量分成两类：面向应用的性能对象与面向网络性能的对象 ( 1 ) 面向应用的性能对象棚 这是一种与每种特定应用服务流的流量特性相关的对象，它与q 0 s 相关并试 图从以下几方面改善网络性能：端到端的分组发送延迟、分组延迟抖动、服务响 应时白j 。面向业务流的性能目标包括了业务流q o s 的增强。对单个的类型、尽力 牛南帅范大学颂i 。学位论文 第二章m p l s 流量t 程 而为的i n t e r n e t 服务模型来说，面向业务流关键性能目标有：分组丢失的最小化、 延迟的最小化、吞吐量最大化和增强服务级的协定。在单一的尽力而为服务类型 下，分组丢失最小化是面向业务流的最重要目标之一面向业务流的性能统计， 如峰值、峰值分组延迟、延迟抖动、丢失率和最大分组传输延迟等，可能会对将 来的i n t e r n e t 十分有用。 ( 2 ) 面向网络的性能对象“1 这是一个与网络资源相关的对象，它试图改善网络的如下性能：网络资源利 用率和网络吞吐量。面向资源的性能目标包括了资源使用优化的各个方面，有效 的网络资源管理是实现面向资源优化使用目标的手段特别是人们都认为要确保 网络各组成部分要均衡使用，避免有些部分过度使用而拥塞，与此同时另一部分 则闲置带宽是当今网络最重要的资源之一，因此，流量工程的一个中心功能就 是有效管理和使用带宽 2 1 - 4 流量工程的实现原理 当前，减少无效资源配置引起的拥塞可以通过负载均衡( 1 0 a db a l a n c i n g ) 策 略“1 实现这种策略的目标是：通过有效的资源配簧，最小化最大拥塞或最小化 最大资源使用当捌塞最小化后，包丢失、传输延迟将下降，集成带宽将增加， 由此，终端用户会感到网络的服务质量提高了运行网络的优化问题实际上是一 个系统控制问题，为了实现负载均衡策略，需要对网络的资源和业务量进行控制 硅y 改控制策略入n修改控制策略? 、 制定控制策略 观测网络状态 确定流精和网络状态特，征 生 t ，则以进化 过程中所得到的具有最大适应度的个体作为最优解输出。终止运算。 3 3 基本遗传算法的数学模型 基本遗传算法( s i m p l eg e n e t i ca l o g r i t h m ，简称s g a ) 是一种群体型操作， 该操作以群体中的所有个体为对象，只使用基本遗传算予、交叉算子和变异算子， 其遗传进化操作过程简单，容易理解，是其他一些遗传算法的基础，它不仅给各 种遗传算法提供了个基本框架，同时也具有一定的应用价值。基本遗传算法可 表示为： s g a - ( c ，e ，p 0 ，m ，中，f ，v ，t ) c 一个体的编码方法： e 一一个体适应度评价函数； p 一一初始种群； 牛南师范人学颂i 学位论文第三章遗传算j 土 卜一种群大小； 中一选择算子； r 一交叉算子； v 一一变异算子； t 一遗传运算终止条件； 基本遗传算法有下述4 个运行参数需要提i ；i 设定： m ：群体大小，即群体中所含个体的数量，一般取为2 0 1 0 0 ； t ：遗传运算的终止进化代数，一般取为1 0 0 5 0 0 ： p c ：交叉概率，一般取为o 4 o 9 9 ； p - ：变异概率，一般取为0 0 0 0 1 0 1 3 4 遗传算法的基本实现技术 3 4 1 染色体编码 编码是应用遗传算法时首要解决的问题，也是设计遗传算法的一个关键步骤。 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到 遗传算法所能处理的搜索空h j 的转换方法就称为编码而由遗传算法解空问向问 题空间的转换称为解码。 遗传算法的编码就是解的遗传表示，编码方法除了决定个体的染色体捧列形 式之外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方 法。针对一个具体应用问题如何设计一种完美的编码方案一直是遗传算法应用难 点之一。 d ej o n g 依掘模式定理，提出了较为客观明确的编码规则：有意义的积木 块编码规则，即所定编码应当易于生成与所求问题相关的短距和低阶的积木块； 最小字符集编码规则，所定编码应采用最小字符集以使问题得到自然的表示或 描述。近年来一些学者从理论上证明了推导最小字符集编码规则时存在的错误， 指出了大符号集编码可提供更多的模式，研究了二迸制编码和十进制编码在搜索 能力和保持群体稳定性上的差异，结果表明二进制编码比十进编码搜索能力强， 但不能保持稳定性 由于遗传算法应用的广泛性，迄今为止人们已提出很多种不同的编码方法， 牛南帅范人学硕f 学位论文第三章遗传算法 总的来说可以分为三大类：二进制编码方法、符号编码方法和浮点数编码方法 3 4 2 适应度函数 适应度是衡量个体优劣的标志，它是执行遗传算法。优胜劣汰”的依据。因 此，适应度也是驱使遗传算法向前发展的动力 适应度函数的设计主要应满足以下条件： ( 1 ) 单值，连续、非负、最大化。这个条件很容易理解和实现 ( 2 ) 合理、一致性要求适应度值反映对应解的优劣程度，这个条件的达成往 往比较难以衡量 ( 3 ) 计算量小适应度函数设计应尽可能简单，这样可以减少计算时日j 和空b j 上的复杂性，降低计算成本 ( 4 ) 通用性强适应度对某类具体问题，应尽可能通用，最好无需使用者改变 适应函数中的的参数。 3 4 3 选择 选择( s e l e c t i o n ) 又称复制( r e p r o d u c t i o n ) ，是在群体中选择生命力强的个体 产生新的群体的过程遗传算法使用选择算子_ 柬对群体中的个体进行优胜劣汰操 作，根掘每个个体的适应度值大小选择，适应度较高的个体被遗传到下一代群体 中的概率较大；适应度较低的个体被遗传到下一代群体中的概率