（控制理论与控制工程专业论文）基于mpls网络负载均衡优化控制算法的研究与仿真.pdf

大连理工大学硕士学位论文 摘要 传统m 网络的路由体系只能提供数据传输的可达性服务，有的网络资源经常出现 有些链路被过度使用，有些链路却空闲不用的负载不均衡局面，致使网络拥塞，业务的 服务质量q o s ( q u a l i t yo fs e r v i c e ) 也无法得到保证，这说明当前因特网没有动态的路 由调整和灵活的网络控制能力。目前，多协议标记交换技术m p l s ( m u l t i p r o t o c o ll a b e l s w i t c h i n g ) 被公认为是实现流量工程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 网络中实现流量工程t e 的基础上，着重于优化路由问题， 针对传统路由算法存在的局限性，提出了两种路由算法一多约束路由选择的改进遗传 算法和动态多路径负载均衡l d m 改进算法。多约束路由选择的改进遗传算法借助遗传 算法适配函数可实现多目标约束的优势，目标是在满足带宽、时延的基础上，将资源消 耗和负载均衡分布作为优化目标，希望在消耗较少网络资源的同时，使负载尽量分布在 宽裕或空闲资源的链路上，便于今后接纳更多请求。动态多路径负载均衡l d m 改进算 法根据m p l s 支持多路路由特点与现有负载均衡算法单路路由的不足，针对路径负载率 和最小跳数两个o o s 属性而提出的。通过构造可能性系数作为选路标准，用较好候选路 径集代替单一最佳候选路径传输流量。在流量分配中引入与可能性系数相关的负载比例 系数，有利于降低计算的复杂度。 论文针对提出的两种算法分别进行仿真验证，仿真结果表明多约束路由选择的遗传 算法能够提高网络吞吐量，使负载分布更趋于合理，改善网络的传输服务质量，而改进 l d m 算法在流量不断增加状态下仍可有效避免网络拥塞，使网络负载尽量分布均匀达 到合理分配资源的目的，同时对网络路径总延时的减小也得到明显改善。课题的研究从 动态的优化网络路由控制和网络负载的均衡调节的两个方面，对目前网络流量的负载不 均衡而导致网络瓶颈效应局面得到进一步改善，具有现实意义上的应用前景。这样的流 量工程t e 路由方式将 关键词：m p l s t e ；多约束路由；遗传算法；l d m 大连理工大学硕士学位论文 r e s e a r c ha n ds i m u l a t i o no ft h el o a dd i s t r i b u t i o no p t i m a lc o n t r o l a l g o r i t h mb a s e do nm p l s a b s t r a c t t r a d i t i o n a li pr o u t i n gs y s t e mc a np r o v i d ea c c e s s i b i l i t yo fd a t at r a n s m i s s i o ns e r v i c e s ， w h i c ha l w a y sl e a d st ot h eu n b a l a n c e dt r a f f i cd i s t r i b u t i o n ，s o m ef i n k sg e t t i n go v e r - u t i l i z e d , w h i l eo t l i e r sr e m a i n i n gu n d e r u t i l i z e d , w h i c hr e s u l t si nc o n g e s t i o na n dt h eq u a l i t yo fs e r v i c e s n o tg u a r a n t e e d t h a ts h o w st h ep r e s e n ti pn e t w o r kl a c k so ft h em e a n st om a n a g en e t w o r k r e s o u r c ee f f i c i e n t l ya n dc a n n o tm a k ef u l lr e s o u r c eu t i l i z a t i o n a tp r e s e n t , m p l sh a sb e e n r e g a r d e da sap o w e r f u lt o o lt ot r a f f i ce n g i n e e d n g , h o wt or e s o l v et h eq u e s t i o na b o u tt h e o p t i m a lc o n t r o lo fn e t w o r kr o u t i n gb ym p l si sa l w a y sah o tp o i n t b a s i n go ns m v e yt h em e t h o d so fr e a l i z i n gt h et r a f f i ce n i g i n e c r i n g , e m p h a s i z i n gt h e o p t i m a lr o u t i n g , a i m i n ga tt h el i m i t a t i o n so ft r a d i t i o n a lm e t h o d s ，p u t t i n gf o r w a r dt w or o u t i n g a l g o r i t h m s ，a ni m p r o v e dg ao fr o u t i n gm u l t i - l i m i t e da l g o r i t h ma n da l li m p r o v e dd y n a m i c m u l t i p a t hl d ma l g o r i t h m t h ei m p r o v e dg a o fr o u t i n gm u l t i l i m i t e da l g o r i t h mi si nv i r t u eo f t h ea d v a n t a g e so fg a , s a t i s f i e st h en e e d so fb a n d w i d t ha n dd e l a y ，m a k e st h es o u r c ec o 璐u m e a n dd i s t r i b u t i o nl o a db a l a n c i n g 鹤t h eg o a l h o p e sc o n s u m i n gl e s sn e t w o r kr e s o u r c ed i s t r i b u t e t h et r a f f i ci n t ou n d e r u t i l i z e dp a t h ，a c c e p t sm o r er e q u e s t s t h ei m p r o v e dd y n a m i cm u i t i p a t h l d m a l g o r i t h mu s e st h em u l t i p a t hc h a r a c t e ro fm p l s a n dt h es h o r t a g e so fs i n # ep a t hr o u t i n g , a i m sa tt w oo o sa t t r i b u t i o ni n c l u d i n gl o a dr a t ea n dt h el e a s th o p u s i n gt h ep o s s i b i l i t ya s c h o o s i n gp a t h ss t a n d a r d ，t h et r a f f i ci sp r o p o r t i o n e da m o n gaf e w “g o o d p a t h si n s t e a do f r o u t i n gi ta l la l o n gt h e “b e s t ”p a t h t h ep r o p o r t i o na l g o r i t h mc a nr e d u c et h ec o m p l e x i t yo f c a l c u l a t i o n t h ee x p e r i m e n t ss h o wt h ei m p r o v e dg ao fr o u t i n gm u l t i - l i m i t e da l g o r i t h mc a ni m p r o v e t h en e t w o r kt h r o u g h p u t ，r e a s o n a b l ed i s t r i b u t i o nl o a db a l a n d n g , e n h a n c et h eq u a l i t yo f t r a n s m i s s i o ns e r v i c e s ，w h i l et h ei m p r o v e dl d ma l g o r i t h ma l s oc a na v o i dc o n g e s t i o nw h e n t h et r a f f i ci n c r e a s e dr a p i d l y ，g a i nr e s o u r c eu t i l i z a t i o ne f f i c i e n t l y ，a tt h es a m et i m e ，t h e n e t w o r kd e l a yr e d u c e de v i d e n t l y f m mb o t hd y n a m i co p t i m i z a t i o no fn e t w o r kr o u t i n gc o n t r o l a n dt h eb a l a n c en e t w o r kl o a dr e g u l a t i o n ，t h et w oa l g o r i t h m sr e s e a r c h e di nt h i sd i s s e r t a t i o nc a n f u r t h e ri m p r o v en e t w o r kb o t t l e n e c ke f f e c ts i t u a t i o n ，w h i c hh a v et h er e a l i z a t i o nf o r e g r o u n do f a p p l i c a t i o n k e yw o r d s ：m p l st e ；r o u t i n gm u l t i l i m i t e d ；g e n e t i ca l g o r i t h r a ；l d m 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：盘! 量丝日期：2 盟孟：孟 人连理i ：人学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论 文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学 位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理工大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采 用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：查l ：! 坠垫 挪签名：燧叁 丛年一月皿同 大连理工大学硕士学位论文 引言 自从1 9 9 1 年万维网w w w 推出，促使i n t e r a c t 商用化之后，i n t e r n e t 便以惊人的速 度发展，然而随着i n t e m e t 的蓬勃发展以及使用人数的增加，在传统运营商网络中，经 常会出现这样情况，在a 、b 两点之间的多条链路中，其中一部分链路上业务已经接近 容限，而另外一部分链路却几乎闲置；在网络中的某些节点发生拥塞，而另外一部分节 点却几乎没有流量通过。这样的状况既降低了网路性能，又浪费了网络物理资源。流量 工程t e 是一种可用来控制网络资源，提高网络性能，解决上述问题的网络资源调控技 术，多协议标记交换m p l s 技术目前被认为是流量工程的最好解决方案。 对于采用m p l s 实现流量工程 r e ，目前i e t f 的m p l s 和t e 两个工作组都己经提 出了一些相关的r f c ( r e q u e s t f o r c o m m e n t s ) 和大量的i n t e m e t 草案，r r u t 和m p l s 论坛也都分别把m p l s 流量工程作为重点的研究工作之一。很多网络设备厂商像c i s c o ， l u c e n t ，a l c a t e l ，j u n i p e r 等也在致力于这方面的研究，希望在他们的产品中支持流量工 程，例如c i s c oi o s1 2 3 软件已经初具流量工程调节能力。然而，目前虽对采用m p l s 实现流量工程己经提出了一些方案，但尚不成熟，其标准和协议也不完善，仍是研究的 热点和亟待解决难点 “基于m p l s 网络负载均衡优化控制算法的研究与仿真”通过对当前网络现状和局限 性的分析，结合m p l s 流量工程t e 优势，着重阐述了两种不同方式流量均衡算法的设 计与仿真，全文共分四个部分。 第1 章首先介绍了课题研究背景，并在分析传统路由算法存在的局限性基础上，指 出进行流量工程研究的必要性，然后简要介绍目前已有的几种q o s 实现模型和机制，最 后全面阐述了流量工程的发展过程和研究现状，并强调了m p l s 技术实现流量工程的优 势所在。 第2 章对采用m p l s 实现流量工程方案进行研究。对流量工程t e 和m p l s 的基本 原理进行简单介绍后，给出m p l st e 组成部件和用流量工程路由流量需求的过程。 第3 章和第4 章是本论文的重点。第3 章重点对多约束路由选择的遗传算法进行研 究，通过学习路由及受限路由、总结当前遗传算法实现均衡路由的缺陷，提出基于遗传 算法和二叉树遍历思想相结合的多约束路由选择改进遗传算法。 第4 章当单路路由不能满足传输需求时，利用m p l s 多路路由这一典型设置，分析 现有多路径负载均衡算法的优缺点同时，对动态多路径负载均衡l d m 的改进算法进行 详细阐述。 最后总结了课题工作重点及本文主要创新点，并对今后工作进行展望。 基于m p l s 网络负载均衡优化控制算法的研究与仿真 l 概述 1 1 课题背景 在早期基于路由器的核心网络中，流量工程是通过简单地使用路由开销值来实现 的。因为那时无论从路由器数量、链路数量还是业务流量来讲，i n t e m e t 骨干网都是非 常小的，所以，基于开销的控制在那时是足以胜任的，同时在i n t e m e t 普及之前，拓扑 层次也强制业务通过网络中较为确定的路径，不会产生临时“热点”( h o tp o i n t ) 。随着 m 网络进一步发展，越来越多新业务要求口网络不仅能提供信息传输的可靠性、安全 性【卜2 】，而且能对信息传输过程具有可预见性 3 1 ，用户要求他们使用的网络在任何情况下 都能提供相对稳定的优良性能服务。这就迫使因特网服务提供商i s p 改善网络基础设施， 如使用最先进的交换机实现业务处理，采用高带宽光纤介质满足高速数据传输的需要， 但这只能在一定程度上缓解用户数据传输带宽和服务质量q o s ( q u a l i t yo fs e r v i c e ) 保 证的压力。现存的i n t e r n e t 内部网关协议i g p 4 1 的开放式最短路径优先o s p f 与路由信息 协议r i p 和外部网关协议e g p 的边界网关协议b g p 等只能提供可达性服务【5 】，所提供 的控制能力是不能胜任流量工程要求的，因为它们难于对实际的网络性能问题实现有效 的策略管理，不能保证对网络某个部分的调整而不引起网络中其它部分的问题。 实际上，基于最短路径优先s p f 算法的i g p 对i n t e r n e t 里自治系统a s 的拥塞产生 起很大作用。s p f 算法通常只根据简单的度量方法进行通路选择优化，这些协议是拓扑 驱动的，在作路由判决时不考虑带宽可用性和业务流特性，因此，拥塞在多个业务流 在s p f 算法下选中同一条链路或同一个路由器的接口做数据传输：给定的业务流所选 中的传输链路或接口的带宽不能满足业务流需求，两种情况下都很容易发生。这两种情 况的发生更主要表明了网络资源利用的不平衡。 目前造成网络拥塞的原因主要有两个1 6 j ，一个是网络资源不充足，不能满足用户流 量的需求；另一个就是传统路由算法导致的流量集中到部分链路上造成拥塞。对于第一 种拥塞可以通过网络扩容或使用经典的拥塞控制技术解决；对于第二种拥塞，是由负载 分布不均衡引起的，单纯靠增加网络容量，显然不是根本的解决方法，必须通过网络的 调节和控制功能，使流量分布更加合理，才能有效的解决这一问题。传统路由算法之所 以造成拥塞问题，其中一个主要原因是选择路径没有考虑网络当前可用资源状况及业务 流本身要求，只是根据业务流要去往的目的地选择度量值最小的一条路径。而度量值， 目前使用的是静态度量，不能反映网络可用资源的当前状况，这样，在传统路由算法作 用下，多个业务流经过网络传输时，将争夺使用网络资源。如果一段时间内数据包到达 率超过资源的处理能力，那么网络将发生拥塞，拥塞导致到达数据包的延迟，甚至丢弃， 一2 一 大连理工大学硕士学位论文 这将增加整个传输过程的传输时延、时延抖动、丢包率，降低用户的服务质量，以及网 络服务的可预见性。 流量工程就是能够解决此问题的一个强有力工具【_ ”。流量工程是一个控制业务流如 何经过网络，以达到优化网络资源利用、提高网络性能目的过程。通过它可以平衡网络 中不同链路、路由器和交换机之间的不同负载，使所有网络设备既不会过度使用，也不 会未被充分使用，这样即可有效利用整个网络资源，减轻拥塞。当拥塞最小化时，网络 的各项q o s 指标得到改善，分组丢失将减少，传输时延也将缩短，而吞吐量则增大，终 端用户所感受到的网络服务质量会显著增强。 流量工程和q o s 保证之间是密切相关的，流量工程实施有助于o d s 保证的实现， 所以流量工程也是一种q o s 机制，它是一种间接实现q 0 s 的技术。为了保证业务的q o s 要求，流量工程的研究十分必要i s l 。对于服务提供商i s p 来说，经常增加网络基础设施 投资是不现实的，通过流量工程t e ，服务提供商i s p 可在己有网络基础设施投资基础 上，最大限度利用网络资源，提供尽可能好的服务，满足用户的q o s 要求，最终获取更 大的利润，所以流量工程的研究对于网络运营也具有重要的现实意义 1 20 0 s 的实现模型和机制 随着i n t e r a c t 的日益普及发展，它和电信网一样已成为人们生活中应用最大的网络 平台之一。人们对i n t e r a c t 要求不仅只满足于单纯的数据传输，电子商务、口话音业务、 图像传送、视频传输等各种新业务纷至沓来。然而这些业务的出现却暴露了口网络技 术的两个严重缺陷：一个是传统i p 路由技术的吞吐量不高，随着专用集成电路a s i c 敦 术的进步，这可通过设计专用硬件解决；另一个就是传统i p 没有服务质量o o s 保证， 这与计算机网络产生之初只是为传输简单数据业务而采用面向无连接的服务有关。坤网 不能保证业务特定的q o s 要求已经成为口网络向宽带综合服务网络发展的巨大障碍。 很多公司、科研机构以及标准化组织都在从事q o s 方面的研究开发工作。c i s c o 、n o r t e l 、 i b m 、j u n i p e r 等公司都从事这方面的研究与试验，研究活跃的大学有m 1 1 r 、u cb e k l e y 、 s t a n f o r d 、t a x a s 、c o l u m b i a 等，i e t f 、a n s i 、r r u - t 等标准化组织都专门为 q o s 成立了研究工作组。 目前，对于o o s 的研究已经提出了多种服务体系和模型，其中最典型的有以下几种： 综合服务模型i n t s c r v ( i n t e g r a t e ds e r v i c e s ) 、区分服务模型d i f f s e r v ( d i f f e r e n t i a t e d s e r v i c e s ) 、多协议标记交换m p l s 和流量工程t e 掣9 o l 。这些模型从不同的层面上， 以不同方式提供q o s 支持。m p l s 作为一种成功的电信网络技术与计算机网络技术的融 合，在提供q o s 方面具有自己的特点。 基于m p i s 网络负载均衡优化控制算法的研究与仿真 1 3m p l s 流量工程研究现状 网络流量的不断增长、o o s 业务的层出不穷以及l s p 对资源的优化利用可提高投资 回报率，使得流量工程越来越引起人们的重视。当前，i t u - t 、i e t f 、m p l s 和f r a m e r e l a y a l l i a n c 以及各大网络设备厂商都非常关注流量工程问题，i e t f 为此专门成立了t e 工作 组。随着网络技术的发展，流量工程在各个时期的实现方式也不尽相同，但是到目前为 止，在i n t e m e t 中实现流量工程还面临着很多问题。在早期基于路由器的核心网中，采 用基于度量的流量工程为每条链路指定一个度量，负载重的链路指定的度量大，空闲链 路指定的度量小，然后使用最短路径算法，选择一条路径，使该路径上所有链路的度量 和最小。 9 0 年代中期，由于i n t e r a c t 的骨干网采用a t m 交换机，口运行在a t m 网络上， 流量工程也采取口，a 1 m 叠加模型。重叠模型需要对两个网络进行管理，路由和流量工 程分别在不同的系统上完成，路由在路由器上执行，流量工程在a t m 交换机上完成， 这增加了网络管理的复杂性，加大了网络开销。随着近年来路由器的性能提高，i n t e m e t 骨干网变为以高速路由器为核心的网络。为了在无连接的m 网络中引入某种连接的机 制，使数据包在网络中经过的路径得以控制，提出了m p l s 实现流量工程的方案。 m p l s 技术被认为是流量工程的最好解决方案。m p l s 流量工程的主要原理是基于 m p l s 支持“显式路由”在支持m p l s 网络域边缘建立满足业务流需求和网络约束条件 的最短路径，达到优化网络资源和满足业务流要求的流量工程目标。m p l s 提供了完整 的业务流量调节能力，以集成方式具备了完成重叠模型所实现的各种流量工程功能的潜 力，更重要的是，m p l s 为流量工程的自动实现提供了可能性。 目前i e t f 的m p l s 和 r e 两个工作组都己经提出了一些m p l s 流量工程相关的r f c 和大量的i n t e r n e t 草案，如r f c 2 7 0 2 1 1 】描述了在m p l s 网络中实施流量工程的要求， r f c 3 2 7 2 1 12 】对i n t e r a c t 流量工程及其基本原理进行了总结，r f c 3 3 4 6 ”j 描述了m p l s 流 量工程的适应性。r r u t 和m p l s 论坛也都分别把m p l s 流量工程作为重点的研究工作 之一。很多网络设备厂商像c i s c o 、l u c e n t 、a l c a t e l 、j u n i p e r 等也在致力于这方面的研 究，希望在他们的产品中支持流量工程。利用m p l s 实现服务质量q o s 保证也是m p l s 的一个主要应用方面【1 4 】。然而，目前虽然对采用m p l s 实现流量工程和保证服务质量 q o s 己经提出了一些方案，但发展尚不成熟且其标准和协议也不完善，仍处于进一步的 研究阶段。 大连理工大学硕士学位论文 2 基于m p l s 技术的流量工程及其实现模型 2 1 流量工程实现模型 流量工程t e 就是一种能将业务流映射到实际物理通路上，同时又可以自动化网络 资源以实现特定应用程序服务性能要求的、具有宏观调节和微观能力的网络工程技术 u ”。通过流量工程1 e 的应用，达到高效智能化应用网络资源目的和一种灵活对网络服 务需求变化响应的能力。就当前流量工程应用来说，有两个关键点负载均衡与网络 恢复。口流量工程应用目的就是要解决如何实现尽力而为的传统i p 服务与服务质量o o s 的统一。 由于i n t c m c t 商业化和竞争性加剧以及网络资源的局限性，使流量工程已成为许多 大型自治系统不可缺少的功能。从网络流量观点来看，流量工程的功能可看作是网络中 业务流的分布优化：从因特网服务提供商i s p 角度来看，流量工程的功能是使网络资源 合理利用和优化网络性能；从客户角度看，流量工程的功能是保证用户服务质量o o s 得到满足。 2 1 1 流量工程的性能指标 网络的流量工程的性能指标通常可以划分为面向业务和面向资源两个分类【1 6 - z 7 1 2 面向业务的性能指标是一种与特定应用流量特性相关的指标，与提高业务流服务质 量有关，目前只存在于单一服务类别的、尽力而为的i n t e r a c t 流量模型中。包括对分组 丢失的最小化、对延时的最小化、对吞吐量的最大化以及对服务等级协定s i a 的增强 等。在面向业务的流量模型中，分组丢失最小化是最重要的性能指标，而在未来的区分 服务因特网中，与统计数据有关的面向流量性能指标，如时延峰值变化、丢包率等也将 越来越重要。 面向资源的性能指标是一种与网络资源相关的指标，试图改善网络性能，包括优化 资源利用的各个方面，如网络资源利用率、网络吞吐量等。对网络资源进行有效管理是 达到面向资源性能指标的重要途径。通常，希望确保网络资源均衡使用，避免有些路径 过分使用而拥塞，另一些网络资源却没有得到充分利用。带宽是当前网络上的一种非常 重要的资源，因此，流量工程的一项中心任务就是对带宽资源进行有效管理。 2 1 2 流量工程的处理过程 流量工程对面向业务和面向资源的网络都有影响，负载均衡机制能改进每个数据流 的o o s 和网络资源效率，但无法做到同时提高两个性能，例如为保证分组端到端的传输 延时符合要求，就得预留一定带宽，使网络带宽利用率下降，因此，面向业务和面向资 源的网络是一个需折衷的问题，流量工程目的就是在这两个性能指标之间找到一个最优 基于m p l s 网络负载均衡优化控制算法的研究与仿真 平衡点。根据流量工程的目标可以看出，流量工程的问题基本上是一个网络控制问题【l ”。 实施流量工程的网络包括一系列网络互连设备、网络性能监测系统和网络配置管理 工具。流量工程对控制策略做格式化，通过监视系统观测网络状态，勾画着业务流的特 性，然后采取一些动作来驱动网络按所需的方向走。这不但可对当前网络状态的反应采 取相应动作来实现，也可根据网络预期会发生的情况采取预行动去消除将来可能发生的 问题，其实现过程如图2 1 所示。 l 抽象描述网络特性 1 分析实际流量特性 l 模拟真实流量行为 图2 1 流量工程的处理过程 f i g 2 1 t h et r a f f i ce n g i n e e r i n gp r o c e s sm o d e l 第1 个步骤就是测量。测量的过程主要是为得到当前网络状况和是否有新的流量需 求。网络状况的测量还包括对数据进行预处理，如数据转化、数据传输等；新的流量需 求测量包括源地址和目的地址、传送时间、数据包大小和传送要求等流量传输需求自身 的具体描述。 第2 个步骤是建模、分析和模拟。此步骤是对实际的网络特性进行数学抽象、分析， 找出影响网络性能的瓶颈和症结所在，结果用于网络性能优化、网络运行控制、网络设 计等。分析实际流量特性以及应用工具或软件来实际模拟接近真实流量的行为以达到对 网络当前存在问题较为准确的总结。 最后是优化过程。在对当前网络及传输需求抽象和分析基础上，通过控制行为对网 络流量进行调整，达到控制策略所预期的状态。控制行为包括校正与资源相关的属性和 约束条件、校正流量管理参数和与路由相关的参数等。 流量工程应该是一个网络自动优化的过程，整个过程中人工干预部分应尽可能少， 通过以上步骤反复运行来达到网络性能的优化。 2 1 3 模型实现 到目前为止，在i n t e m e t 中实现流量工程存在着两种模型1 9 1 ：面向无连接的t e 模 6 大连理工大学硕士学位论文 型和面向连接的t e 模型。 无连接的模型是基于现有无连接口路由协议的模型，是对现有链路状态或距离矢 量路由协议的扩展。在这种模型中，每个节点独立决定下一跳去向，实现方法大多是通 过改变路由参数或其它间接方法。其中，一种方法是通过改变链路度量值以控制数据流 在网络中的流向，链路的度量值改变后，将触发各个节点重新计算到目的节点的最短路 径，并更新路由表。所以通过设置合适的度量值可引导数据流在网络中遵循我们所期望 的路径进行数据包传输。f o r t z 和t h o m p 提出的通过优化o s p f 度量值1 2 0 l 实现i n t e m e t 流量工程的方案是这种方法典型代表，其思想是根据每条链路的资源利用情况，把链路 度量值模型化为逐段线性递增的函数，链路使用率越大，度量值也就越大，相反，链路 使用率越小，度量值也较小。另一种方法是采用多路路由算法寻找源到目的节点间的多 条路径，并将数据流在这多条路径问分摊，达到均衡网络负载的目的。o s p f 的扩展功 能等价多路径e c m p 2 1 】以及后来的优化多路径0 m p i 捌算法都采用的是这种方法。 无连接的流量工程i e 模型仍然是传统的h o p b y - h o p 路由方式，所以保留了传统口 路由的简单和灵活特性，具有良好的扩展性。但是，这种模型的缺点是容易造成路由抖 动，稳定性差，并且由于面向无连接的模型在本质上仍是最短路径路由，对于流量工程 t e 的实现也只是通过间接改变路由方法来完成，会限制很多流量工程t e 功能的实现。 保证数据传输的可靠性也是流量工程t e 主要目标之一，然而无连接的口路由协议 o s p f 、i s i s 等虽可提供故障发生后的重路由恢复机制，但都必须在路由信息收敛后进 行，收敛时间往往在秒的数量级1 ”- 2 + 1 。在这样的收敛时间内，可能发生路由环路、数据 包错乱顺序以及数据包丢失等一系列我们所不希望的事情。 面向连接的流量工程t e 模型采用某种面向连接的机制实现t e 功能的模型，一般 使用一定的信令协议建立路径，并在发送数据前先进行资源预约，预约完成后才开始真 正传送数据，例如采用a t m 、m p l s 等的实现模型都是面向连接的形式。在这种模型 中，路径通常是由源节点或某些中心节点来决定的，然后使用信令协议在路径上所有节 点间分配路径的标识符( 如m p _ s 中的l a b e l ) ，并就这些标识符在相邻节点间达成一 致，这一系列的标识符决定了数据在网络中的流向，确定了数据的路径，数据在网络中 的转发过程就是一个标识符交换的过程。x i a o 等1 2 5 2 6 】对在美国最大的i s p 之一 g l o b a l c e n t e r 的网络上采用m p l s 实现流量工程进行了研究，实验证明采用m p l s 实现 方式完全可行，并且运行效果良好。这种模型将控制和转发两种功能分离开来，控制基 于全局标识口地址，转发基于本地标识l a b e l ，信令协议将二者联系起来，并在它们之 间达成一致，当引入新的流量工程 r e 功能时只需要在控制平面上做修改即可。面向连 接的流量工程模型提高了网络操作的可靠性，确保流量工程功能的直接实现，但由于是 通过信令协议实现限制了扩展性，目前面向连接的流量工程还只限于在a s 内部实施。 基于m p l s 网络负载均衡优化控制算法的研究与仿真 无连接的流量工程t e 模型可以在已有的o s p f 、i s i s 等协议的基础上实施，与原 有i p 路由模式相一致，这是无连接流量工程t e 模型的一个优势，但是为什么在实际应 用中这种模型却采用的很少呢? 其原因主要有两个方面，一方面这种模型虽可在原有网 络设施上实施，但需要进行软件升级，投资比较大；另一方面由于无连接模型通常是通 过间接方式实现流量工程t e 功能，本质上还是逐级跳路由，无法预先确定数据包在网 络中所走的路径，对数据包的可控能力不强，限制t e 功能的实现。而面向连接的t e 模型通常采用显式路由方式，可沿明确的路径对数据分组转发，便于对数据流的控制以 及复杂t e 功能的实现。因此，目前无论是产业界还是学术界都倾向于采用面向连接的 流量工程t e 模型，特别是随着m p l s 技术成熟和推广，采用m p l s 技术实现流量工程 己经成为业界共识i 2 7 - a 2 1 2 2m p l s 技术优势 多协议标记交换m p l s 技术源于早期的口交换【矧，其目的是将目前的各种口路由 和a t m 交换技术兼容并蓄，以提供一种更具弹性、扩充性以及效率更高的带宽交换路 由器。最早在1 9 9 6 年基于这一思想i p s i l o n 公司( 目前已被n o k i a 收购) 推出了i p s w i t c h i n g 协议，该协议一经推出立即在数据通讯界引起巨大震动，并引发了路由器的技术革命， 各个公司开始纷纷提出自己的方案。c i s c o 公司提出t a gs w i t c h i n g 方案，i b m 提出a r i s ( a g g r e g a t er o u t e b a s e di ps w i t c h ) 方案，t o s h i b a 提出c s r ( c e l ls w i t c h i n gr o u t e r ) 方 案。为形成统一的标准，1 9 9 6 年底c i s c o 公司以其“t a gs w i t c h i n g ”为基础，并结合m m 以及t o s h i b a 公司的研究成果，向i e t f 提交了一套解决办法，即m p l s 斟i 。1 9 9 7 年4 月i e t f 的m p l s 工作组正式成立。 2 2 1 标记的封装 多协议标记交换将第三层的数据包通过一套规程转化成简单灵活的“标记数据包”。 这套规程既要考虑底层链路的特点，同时又要考虑如何传递第三层数据包的信息，如分 组存活时间r r l 、服务质量q o s 等等，这套规程就是“标记的封装”或者叫“标记的编码”。 在m p l s 网络中，标记的封装可有多种形式。在一个非a t m f r 网络环境下，使 用标准s h i m 封装，它位于网络层分组头标之前，链路层封装之后，这个封装相当于在 链路层封装和网络层封装之间加了一层，故而称为“s h i m ”也就是垫层的意思。s h i m 是 一个3 2 b i t s 的值，如图2 2 所示，其中l a b e l 字段占2 0 b i t s ；实验用e x p 字段占3 b i t s ， 用于表示服务等级c o s ：堆栈指示字段s 占1 b i t ，表示是否是标记堆栈；生存期1 几字 段占8 b i t s ，与传统口网中t r l 字段含义相同。 一8 一 大连理工大学硕士学位论文 20b妇3bbl b 虹 g o i t s 图2 2 肝l s 的s h i m 封装 f i g 2 2t h es h i me n c a p s u l a t i o ni nm i l s 2 2 2 _ p l s 工作原理 为了后面更好地阐述问题，首先介绍一些在m p l s 技术中经常使用的概念和术语。 标记l a b e l 也称为标记，是一个简短的、固定长度大小的、具有本地意义的标识符；转 发等价类f e c ( f o r w a r d i n ge q u i v a l e n c ec l a s s ) 是具有相同转发处理方式的组数据分 组，属于同一个f e c 的分组在m p l s 网络中的处理方式完全相同；标记交换路由器l s r ( l a b e ls w i t c h i n gr o u t e r ) 位于m p l s 网络中部的核心交换机，如图2 4 中所示，提供 标记交换和标记分发功能；标记边缘路由器l e r ( l a b e ls w i t c h i n g e d g er o u t e r ) 是m p l s 网络同其它网络的边缘设备，如图2 4 中所示，提供流量分类和标记映射( 作为入口) 和标记移除( 作为出口) 功能；标记交换路径l s p ( l a b e ls w i t c h i n gp a t h ) 用m p l s 协 议建立的分组转发路径，表示源到目的节点一系列l s r 的标记以及链路组成；标记信 息库l i b ( l a b e li n f o r m a t i o nb a s e ) 作用类似路由表，包含各个标记对应的各种转发信 息，每个入口标记对应一个条目，包括出口标记、出口接口等信息；标记分发协议l d p ( l a b e ld i s t r i b u t i o np r o t o c 0 1 ) 相当于传统网络的信令协议，负责标记分发与维护。l d p 是m p l s 专门定义的一种标记分发协议，但i e t f 并没有规定m p l s 只局限于这一种协 议，另外还有几种协议也处于标准化进程之中，如c r l d p 、r s v _ p 的扩展等。 m p l s 是一种基于标记交换的数据转发方式，不同于常规i p 基于最长地址匹配路由 查找的h o p b y h o p 数据包转发方式。在常规i p 路由中，每个节点都独立分析口包头， 后续节点不再分析包头，路由的决策也不仅仅根据口地址，还依据多种参数，如q o s 参数、流量工程服务参数等。 在m p l s 中，所有进入网络的分组都被指定到某个特定f e c ，每一特定f e c 都被 编码为一个短而定长的值，即标记，标记加在分组前成为标记分组，再转发到下一跳。 在后续的每一跳上，不需要再分析分组头，而是用标记作为指针，指向下一跳输出口和 一个新的标记，标记分组用新标记代替旧标记后经指定输出端口转发。 在每个节点处，标记建立是路由协议和m p l s 控制信令共同作用的结果。标记交换 路由器l s r 要完成路由器路由控制功能和标记管理维护功能。l s r 要像通用路由器一 一9 基于m p l s 网络负载均衡优化控制算法的研究与仿真 样完成路由控制，不断更新和维护路由信息库，所采用的路由技术通过标准的第三层路 由协议如b g p 和o s p f 实现，同时标记交换路由器l s r 路由表在m p l s 控制信令作用 下，建立并维护标记信息库l i b 。通常l s r 在标记分发协议l d p 控制下，对标记操作 主要有：标记划分、标记分发、标记维护等。m p l s 网络中的每个节点都必须建立包含 标记绑定信息的标记信息库l i b ，这样，就可利用标记信息库中的信息，根据输入分组 所携带的标记，进行标记转换s w a p ，例如标记入栈、标记出栈、标记替换等，然后利 用第二层的交换机制实现分组转发。对于边缘路由器还要在标记交换路由器的基础之上 增加用于实现f e c 划分、标记绑定以及用于o o s 保证、c o s 分类、流量工程等方面的 控制部件。标记交换路由器的功能模块结构的示意图如图2 3 所示 路由更新 路由协议 i m p l s 控制信令 卜 ( 0 s p f 、b g p )i ( l d p 、c r l d p 、r s v p ) i jl 路由表i - - 标记信息库l i b 入数据流 j i 一一 l 7 l 1” 厂 图2 3l s r 功能模块示意图 f i g 2 3 f u n c t i o nm o d e lo fl s r 在整个m p l s 工作过程中，在m p l s 设备之间运行路由协议，如b g p 、o s p f 等， 通过路由协议获取网络拓扑信息，建立路由表，并根据路由表使用标记分发协议( 可使 用l d p 、c r l d p 或r s v _ p ) 在节点间分发标记信息，建立数据传输通道标记交换 路径l s p 。当一个数据流到达入口l e r 后，l e r 分析数据包的j p 包头，根据它携带的 信息，包括目的地址、c o s 字段等，以及其它一些信息如数据包来自的端口，把数据包 映射到转发等价类f e c 上，再根据它所属的f e c 加上标记。以后的转发过程中，l s r 只根据数据流携带的标记进行查表、交换，不再进行其它处理，直到到达出口l e r ，将 标记移去，恢复原始数据流。 图2 4 是m p l s 转发数据过程的一个例子，m p l s 工作原理可以由图2 4 进行说明。 当i p 数据包到达边缘标记交换路由器l e r l 时，m p l s 第一次应用标记，首先，u m l 要分析i