（计算机应用技术专业论文）基于离线优化计算的在线路由算法研究.pdf

摘要 摘要 服务提供商在支持d 服务方面面临着挑战，这需要他们能够使现有的网络 具有流量工程管理。服务提供商要求i po v e r a t m 这种方式下的流量工程在纯 结构的网络中也要得到实现，m p l s 正是一种能在a t m 和纯口网共存情况下提 供流量工程的技术。 基于m p l s 流量工程的路由算法研究有很多，但是一般都只考虑了有带宽要 求的业务。在离线优化+ 在线路由的流量工程框架下，本文提出了一种新的应用 离线优化计算结果的在线路由算法，本文提出的新的在线路由算法同时兼顾了 q o s 业务和b e s t - e f f o r t 业务。 本文的流量工程框架主要包括以下三个部分：1 ) 离线优化计算，根据测量 得到的每个源一目的间的聚合业务矩阵，计算出每条链路上分配给每对源目的节 点对的带宽；2 ) 得到路径集合，将离线得到链路带宽分配值转化为源一目的对间 的路径集合，这一步骤也是离线进行的：3 ) 在线路由阶段，在路径集合中，为 q o s 业务和b e s t - e f f o r t 业务进行路由选择，为q o s 业务选择能满足其带宽要求的 比较“短”的路径，为b e s t e f f o r t 业务选择负载较轻的路径。 在n s - 2 仿真软件中，作者实现了这个流量工程框架，并进行了大量的仿真 实验。仿真结果表明，与c s p f ( c o n s t r a i n e d s h o r t e s t p a t h f i r s t ，基于约束的最短 路优先) 相比，使用本文提出的流量工程框架，在保证0 0 s 业务带宽的同时， 大幅度的提高了b e s t - e f f o r t 业务的吞吐量。 关键字：流量工程，m p l s ，离线优化计算，在线路由，q o s 业务，b e s t - e f f o r t 业务。 a b s t r a c t a b s t r a c t i n t e m e ts e r v e rp r o v i d e r sa r ef a c i n gt h ec h a l l e n g eo fs u p p o r t i n gi ps e r v i c e s i n t e m e tt r a f f i ce n g i n e e r i n gi se m e r g i n ga sak e yt o o lt oa c h i e v i n gt h eg o a l s i n t e m e t s e r v e rp r o v i d e r sd e s i r et h a tt r a f f i ce n g i n e e r i n gf o rt h ei po v e ra t m c a ni m p l e m e n ti n i pn e t w o r k s m p l si st h e t e c h n o l o g yo fp r o v i d i n g t r a f f i c e n g i n e e r i n g o nt h e c o e x i s t e n c eo f a i ma n dp u r ei pn e t w o r k s t h e s ea r em a n yr o u t i n ga l g o r i t h m sb a s e do nm p l st r a f f i ce n g i n e e r i n g ，al a r g e n u m b e ro fw t f i c ha r eo n l ys e l e c tp a t h sf o rt h et r a f f i cw i t ht h eb a n d w i d t hr e q u e s t a n e wo n l i n em u t i n ga l g o r i t h m ，w h i c hi st h ea p p l i c a t i o n st ot h er e s u l to ft h eo f f i i n e o p t i m a lc o m p u t i n g ，i sp r o p o s e di nt h i sp a p e ro n t h ef r a m e w o r ko fo f f i i n eo p t i m i z a t i o n a d d i n go n l i n er o u t i n g t h en e wr o u t i n ga l g o r i t h mc a ns e l e c tp a t h sf o rt h eq o s t r a f f i c a n db e s t - e f f o r tt r a f f i c 、 t h ef r a m e w o r ko ft r a f f i ce n g i n e e r i n ga p p e a r e di nt h i sp a p e rh a st h r e em a j o r c o m p o n e n t s ：1 ) o f f l i n eo p t i m a lc o m p u t i n g ，b a s e do nt h ea g g r e g a t et r a f f i cm a t r i x ， w h i c hc a l c u l a t e st h ep r o - a l l o c a t i o no fl i n kc a p a c i t i e sf o rt h ee v e r ys o l , r c e d e s t i n a t i o n p a i r ；2 ) g e t t i n gt h ep a t hs e tf r o mt h er e s u l t o ft h eo p t i m a lc o m p u t i n g , w h i c hi s p e r f o r m e do f f i i n e ；3 ) o n l i n er o u t i n g ，w h i c hs e l e c tp a t h s f o rt h eq o st r a f f i ca n d b e s t - e f f o r tt r a f f i ci nt h ep a t hs e t ，t h eq o st r a 伍cw i l lu s et h es h o r tp a t ht h a tc a r lm e e t t h eb a n d w i d t hr e q u e s to ft h et r a f f i c ，a n db e s t - e f f o r tt r a f f i cw i l lu s et h ep a t hw h i c h l o a d si sl i g h t t h ea l g o r i t h mh a sb e e ni m p l e m e n t e di nn e t w o r k ss i m u l a t e r 2 ( n s - 2 ) t h e s i m u l a t i o nr e s u hs h o wt h a tt h en e wo n h n em u t i n ga l g o r i t h ms i g n i f i c a n t l yo u t p e r f o r m s t h ec s p f ( c o n s t r a i n e ds h o r t e s tp a t hf i r s t ) ，w h i c hg r e a t l yi n c r e a s e st h et h r o u g h p u to f t h eb e s t e f f o r tt r a f f i c s ，a n ds i m u l t a n e o u s l yg u a r a n t e e st h eb a n d w i d t ho ft h eq o s t r a m c s k e yw o r d s ：t r a f f i ce n g i n e e r i n g ，m p l s ，o f f - l i n eo p t i m a lc o m p u t e r ， o n - l i n er o u t i n g ，q o st r a f f i c ，b e s t _ e f f o r tt r a f f i c 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤洼盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：撕签字目期：期f 年 1 月陪日 学位论文版权使用授权书 本学位论文作者完全了解鑫生盘鲎有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名导师签名 长鹋 签字目期：贼年f 月他日 签字日期：加年1 月1 2 日 第一章绪论 第一章绪论 1 1 流量工程的发展和研究现状 在工业界，将业务流映射到现有物理拓扑上的任务被称作流量工程。在 r f c 3 2 7 2r 1 中，给出了流量工程的明确定义，就是与i n te r ：n e t 网络工程进行性能 评价及如何操作p 网络使网络性能优化这两个问题相关的所有知识。一般来说， 它包含了技术的应用、测量的科学准则、模型化、归纳和因特网流量的控制，以 及如何将这些知识和技术应用到实践中来获取一些特定的性能指标。 流量工程的一个主要目的就是在促进有效、可靠的网络操作的同时，优化网 络资源的利用率和流量的性能。由于网络资源的昂贵和因特网激烈的商业竞争的 本质，流量工程已经成为大型自治系统中一个不可缺少的功能。 近年来，对流量工程框架和算法的研究主要集中在o s p f 【2 j 、i s - i s l 3 1 和m p l s ( m u l 邱r o t o c o ll a b e ls w i t c h i n g ，多协议标记交换) 4 】这三个协议上。o s p f 和 i s i s 是现在网络中使用最广泛的两种内部网关协议，而且能在o s p f 上实现的 流量工程算法也能同样在i s i s 上实现。i e t f 已给出了流量工程在o s p f 和i s i s 上扩展的标准【5 】【6 】。针对o s p f i s - i s 协议研究的重点是如何将优化计算得到的结 果转化成链路权值，以达到网络效益的最大化【7 】【引。 m p l s 多协议标记交换融合了口路由技术、a t m 的q o s 及第二层的交换 技术，其中包括a t m 网上承载口业务的模式。它允许为网络的数据流预先建立 一条路径。这些预留的路径占用特殊的网络资源，既可被手工设定为显式路径， 也可根据需要自动生成满足资源约束的路径。 基本上讲，m p l s 类似于a t m 技术，它是专门为口设计的，但同时又支持 a t m 和p o s 等不同的传输媒体。在建立l s p ( l a b e ls w i t c h e dp a t h ，标记交换路 径) 时，根据流量需要和链路承载能力，数据流被映射到相应的路径上。数据流 通过哪条路径转发取决于该数据流被分配了什么样的标记。因此，不同于传统的 p 目的地址，m p l s 中的标记被用于将数据包沿着选好的路径在网络中传送。目 前，m p l s 可用两种控制协议c r - l d p ( c o n s t r a i n t b a s e dl a b e ld i s t r i b u t i o n p r o t o c o l ，居于约束的标记分配协议) 和r s v p ( r e s o u r c er e s e r v a t i o np r o t o c o l ， 资源预留协议) 建立路径，他们在支持流量工程时具有同等的效力。另外，这两 种控制协议均支持隐式路由和显式路由。 m p l s 拥有多项有利于实现流量工程的优点：( 1 ) 通过手工的网管配置或是 下层协议的自动配置，可以很容易的建立起不受传统逐跳路由协议限制的显式 l s p ，( 2 ) l s p 可以被高效的维护，( 3 ) 流量主干可以被使用并被映射到l s p 上， ( 4 ) 可以给流量主干规定一套属性来调整流量主干的行为，( 5 ) 可以给各种网 第一章绪论 络资源规定一套属性，以便对以上建立的l s p 通过的流量主干加以限制，( 6 ) 既可以对业务进行聚集，也可以对业务进行分割，而基于传统的路由协议的p 转发只支持基于目的地址业务聚集，( 7 ) 可以较容易的实现“约束路由”，( 8 ) m p l s 流量工程的开销要比其他的流量工程技术( 如o v e r l a y 技术) 小的多。另 外，通过显式标记交换路径，m p l s 可以在现有的i n t e m e t 路由模型中实现准电 路交换功能。 以下3 个r f c ，即基于m p l s 的流量工程要求1 9 】、流量工程在m p l s 上应 用状态以及支持具有区分服务意识的m p l s 流量工程的要求l 给出了流量工 程在m p l s 上实现的一些要求和标准。 正因为m p l s 拥有很多有利于实现流量工程的优点，所以各种基于资源使 用和流量性能的优化算法能在m p l s 框架中有效实现。m p l s 流量工程算法的研 究一般集中在优化算法的研究上。本文作者的研究也是基于m p l s 协议的。 1 2 背景和动机 本论文的课题背景是天津市应用基础研究计划项目“基于m p l s 的动态路 由算法研究”。研究的主要内容是在m p l s 网络的基础上，研究适合口网络特点 和网络中业务要求的面向连接的流级路由算法和框架。 作者的研究是文献 2 6 1 的工作的深入。文献 2 6 】提出了一种动态建立有带宽 保证路由的框架，这种框架并没有考虑到没有带宽保证的流如何建立，本文提出 了一种在线路由算法，这种路由算法是在离线优化的基础上，根据业务的特点， 使用不同的路由策略，既给有带宽要求的业务( q o s 业务) 提供有带宽保证的路 由，又提高了没有明确带宽要求的业务( b e s t - e f f o r t 业务) 的总传输能力。 1 3 论文的主要工作 本论文的主要工作如下： 1 提出了一种将离线优化计算得到的链路带宽分配值转化为路径集合的算 法。并且在n s 3 4 】中实现了该算法。 2 提出了一种具有服务区分意识的在线路由算法，此算法依据上面提到的 路径集合，首先将路径集合里的路径按照路径长度和带宽排序，根据不同的业务 要求( 有q o s 要求和b e s t e f f o r t 业务) ，选取适当的路径。在n s t 3 4 1 中实现了该 算法，给出了相应的仿真实验和结果分析。 第一章绪论 1 4 论文结构 论文第二章介绍了m p l s 协议；第三章对近年来基于m p l s 流量工程的研 究做了综述。第四章首先给出了本文流量工程框架中，离线优化计算的公式，然 后提出了一种将离线计算得到的链路带宽分配结果转化为路径集合的算法，并介 绍了本文提出的具有服务区分意识的在线路由算法，该算法兼顾了q o s 业务和 b e s t e f f o r t 业务的特点，为q o s 业务提供有带宽保证的服务，并提高了b e s t - e f f o r t 业务能够使用的最大带宽，论文的第五章给出了相应的实验和对实验结果的分 析。第六章总结全文，并提出了对今后研究的展望。 析。第六章总结全文，并提出了对今后研究的展望。 第二章m p l s 协议 第二章m p l s 协议 m p l s 是一种可以在多种第二层媒质上进行标记交换的网络技术。这一技术 结合了第二层的交换和第三层路由的特点，将第二层的基础设施和第三层的路由 有机地结合起来。第三层的路由在网络的边缘实施，而在m p l s 的网络核心采 用第二层交换。 m p l s 通过在每一个节点的标记交换来实现包的转发。它不改变现有的路由 协议，并可以在多种第二层的物理媒质上实施，目前有a t m 、f r ( f r a m er e l a y 帧中继) 、e h e m e t 以及p p p 等媒质。 通过m p l s ，第三层的路由可以得到第二层技术的很好补充，充分发挥第二 层良好的流量设计管理以及第三层 h o p - b y - h o p ( 逐跳寻径) ”路由的灵活性。 2 1m p l s 基本概念 1 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 ，转发等价类) m p l s 实际上是一种分类转发的技术，它将具有相同转发处理方式( 目的地 相同、使用的转发路径相同、具有相同的服务级别等) 的分组归为一类，这种类 别就称为转发等价类。属于相同转发等价类的分组在m p l s 网络中将获得完全 相同的处理。在标记分配过程中，各种等价类对应于不同的标记，在m p l s 网 络中，各个节点将通过分组的标记来识别分组所属的转发等价类。 2 多协议标记交换 1 ) 协议 m p l s 位于传统的第二层和第三层协议之间，其上层协议与下层协议可以是 当前网络中的各种协议。如：i p x ，a p p l e t a l k 等。 2 ) 标记 一个长度固定，作用范围在本地的标志。它用于唯一地表示一个分组所属的 f e c ，决定标记分组的转发方式。 l 2 h e a d e rm p l ss h i mh e a d e ri ph e a d e ru s e rd a t a 、 l a b e l ( 2 0 b i t s )e x ( 3 b i t s ) p s ( 1 b i t s )t t l ( s b i t s ) 图2 - 1m p l s 网络中的分组头格式 4 第二章m p l s 协议 图2 - 1 是m p l s 网络中的分组头的格式，其中m p l s 嵌入分组头的格式如下： l a b e l 域：2 0 b i t s ，标记值。 e x p 域：3 b i t s ，用于实验，大多被设置为c o s ( c l a s so fs e r v i c e ) 域，提供 一种服务分类的机制，影响分组在网络中传输时排队和丢弃算法。 s ( b o t t o mo f s t a c k ) 域：l b i t ，用于支持标记栈的结构，在标记栈最后一个 实体中设置为1 ，其他标记实体置为0 。 t t l ( t i m et ol i v e ) 域：8 b i t s ，记录分组的存活时间。 3 ) 交换 通过f e c 的划分与标记的分配，m p l s 的标记在网络中进行交换，建立一 条虚电路。 3 标记栈 是一组标记的级联。 4 标记分组 包含了m p l s 标记封装的分组。标记可以使用专用的封装格式，也可以利 用现有的链路层封装，如：觚m 的v c i 和v p i 。 5 l s r ( l a b e ls w i t c h i n g r o u t e r ，标记交换路由器) 支持m p l s 协议的路由器，是m p l s 网络中的基本元素。 6 l s p ( l a b e ls w i t c h e dp a t h ，标记交换路径) 使用m p l s 协议建立起来的分组转发路径，由标记分组源l s r 与目的l s r 之间的一系列l s r 以及它们之间的链路构成，类似于a t m 中的虚电路。 7 上游l s r 与下游l s r 一个分组由一个路由器发往另一个路由器时，发送方的路由器为上游l s r ， 接收方为下游l s r 。 8 l i b ( l a b e li n f o r m a t i o nb a s e ，标记信息库) 由f e c - t o l a b e l 绑定构成，类似于路由表，包含各个标记所对应的各种转发 信息。 9 l d p ( l a b e l d i s t r i b u t i o n p r o t o c o l ，标记分配协议) 该协议是m p l s 的控制协议，相当于传统网络的信令协议，负责f e c 的分 类，标记的分配，以及分配结果的传输及l s p 的建立和维护等。 1 0 。l d pp e e r s ( 标记分发对等实体) 进行l d p 操作的l s r 为标记分发对等实体。 1 1 标记合并 对于某一相同f e c 的标记分组，将不同的入口标记替换为相同的一个出口 标记继续转发的过程，减少标记资源的消耗。 第二章m p l s 协议 1 2 t i ( t y p el e n g t hv a l u e ) m p l s 消息中的子结构，类似于其它协议中各种消息内的对象。 2 2m p l s 工作流程 m p l s 是一种特殊的转发机制，它为进入网络中的m 数据包分配标记，并 通过对标记的交换来实现p 数据包的转发。标记作为疋包头在网络中的替代品 存在，在网络内部，m p l s 在数据包所经过的路径沿途通过交换标记( 而不是看 i p 包头) 来实现转发；当数据包耍退出m p l s 网络时数据包被解开封装，继续按 照p 包的路由方式到达目的地 图2 - 2 包转发流程图 如图2 - 2 所示，m p l s 网络包含一些基本的元素。在网络边缘的节点称为l e r ( l a b e le d g er o u t e r ，标记边缘路由器) ，而网络的核心节点就称为l s r 。l e r 节 点在m p l s 网络中完成的是皿包的进入和退出过程；l s r 节点在网络中提供高 速交换功能。在m p l s 节点之间的路径就叫做l s p ，一条l s p 可以看作是一条 贯穿网络的单向隧道。 m p l s 的工作流程可以分为几个方面：网络的边缘行为、网络的中心行为以 及如何建立标记交换路径。 1 网络的边缘行为 当p 数据包到达一个l e r 时，m p l s 第一次应用标记。首先，l e r 要分析 口包头的信息，并且按照它的目的地址和业务等级加以区分。 在l e r 中，m p l s 使用了f e c 的概念，将输入的数据流映射到一条l s p 上。 简单地说，f e c 就是定义了一组沿着同一条路径、有相同处理过程的数据包。这 就意味着所有f e c 相同的包都可以映射到同一个标记中。 对于每一个f e c ，l e r 都建立一条独立的l s p ，穿过网络，到达目的地。 数据包分配到一个f e c 后，l e r 就可以根据l i b 来为其生成一个标记。标记信 第二章m p l s 协议 息库将每一个f e c 都映射到l s p 下一跳的标记上。如果下一跳的链路是a t m ， 则m p ls 将使用a t mv c c 里的v c i 作为标记转发数据包，l e r 检查标记信息 库中的f e c ，然后将数据包用l s p 的标记封装，从标记信息库所规定的下一个 接口发送出去。 2 网络的核心行为 当一个带有标记的包到达l s r 的时候，l s r 提取入口标记，同时以它作为 索引在标记信息库中查找。当l s r 找到相关信息后，取出出口标记，并由出口 标记代替入口标记，从标记信息库中所描述的下一跳接口送出数据包。 最后，数据包到达了m p l s 域的另一端，在这一点，l e r 剥去封装的标记。 仍然按照坤包的路由方式将数据包继续传送到目的地。 3 如何建立标记交换路径 建立l s p 的方式主要有两种： ( 1 ) h o 口b y h o p ”路由 一个h o p b y - h o p 的l s p 是所有从源节点到一个特定目的站点的p 树的一 部分。对于这l s p ，m p l s 模仿碑转发数据包的面向目的地的方式建立了一组 树。 从传统的疋路由来看，每一台沿途的路由器都要检查包的目的地址，并且 选择一条合适的路径将数据包发送出去。而m p l s 则不然，数据包虽然也沿着 d 路由所选择的同一条路径进行传送，但是它的数据包头在整条路径上从始至 终都没有被检查。 在每一个节点，m p l s 生成的树是通过一级一级为下一跳分配标记，而且是 通过与它们的对等层交换标记而生成的。交换是通过l d p 的请求以及对应的消 息完成的。 ( 2 ) 显式路由 m p l s 最主要的一个优点就是它可以利用流量设计“引导”数据包，比如避免 拥塞或者满足业务的q o s 等。m p l s 允许网络的运行人员在源节点就确定一条 显式路由的l s p ( e x p l i c i t r o u t e l a b e ls w i t c h e d p a t h , e r - l s p ) ，以规定数据包将 选择的路径。与h o p - b y - h o p 的l s p 不同，e r - l s p 不会形成p 树。e r l s p 从 源端到目的端建立一条直接的端到端的路径，如图2 3 所示。 第二章m p l s 协议 2 3 标记分配协议 图2 3 e r - l s p 目前主要研究三种标记分配协议：基本的标记分配协议( l d p ) f 1 “、基于约 束的l d p ( c r - l d p ) 1 3 1 和扩展r s v p ( r s v p t e ) 【1 4 1 。 l d p 是基本的m p l s 信令与控制协议，它规定了各种消息格式以及操作规 程，l d p 与传统路由算法相结合。通过在t c p 连接上传送各种消息，分配标记、 发布 映射，建立维护标记转发表和标记交换路径。但如果需要支持 显式路由、流量工程和q o s 等业务时，就必须使用后两种标记分配协议。 c r - l d p 是l d p 协议的扩展，它仍然采用标准的l 工) p 消息，与l d p 共享 t c p 连接，c r - l d p 的特征在于通过网管制定或是在路由计算中引入约束参数的 方法建立显式路由，从而实现流量工程等功能。 r s v p 本来就是为了解决t c p i p 网络服务质量问题而设计的协议，将该协 议进行扩展得到的r s v p t e 也能够实现各种所需功能，在协议实现中将r s v p 作用对象从流转变为f e c ，降低了颗粒度，也就提高了网络的扩展性。 c r l d p 和r s v p t e 在功能上比较相似，但在协议实现上有着本质的区别， 难以实现互通，故而必须做出选择。 c r l d p 和r s v p t e 差别主要体现下面六个方面： 1 ) 与l d p 协议互联的简单性 由于c r - l d p 是l d p 的扩展，所以信令机制和消息结构均与l d p 相同，因 而l d p c r l d p 在m p l s 域内提供了一个统一、完整的用于标记分配和l s p 建 立的信令系统，二者的结合可以大大提高网络运行效率、降低网络运行成本。而 r s v p t e 只能采用下游按需标记分配模式，如果m p l s 域内需要采用其它标记 分配模式，则网络必须同时运行r s v p t e 与l d p ，这将大大增加网络的管理难 度与运行成本。 2 ) 可靠性 第二章m p l s 协议 c r l d p 通过t c p 端口来保证信令的可靠传递，而r s v p - t e 利用u d p 端 口传递信令信息，因而无法保证信息的可靠传输。当节点发生拥塞或故障时，如 果通知消息丢失，发生故障的l s p 隧道可能要等到刷新消息过期之后才会进行 重新路由；此时r s v p - t e 提供的路径挤占、故障恢复以及重新路由等功能将无 法有效实施。此外，由于r s v p t e 缺乏流控机制，当网络发生故障时，极有可 能出现控制消息数量失控的现象，进而导致网络的进一步拥塞甚至瘫痪。 3 ) 扩展性 c r l d p 用于建立、维护和拆除l s p 的信令消息结构简单、数量小，因而便 于网络管理和诊断。由于c r l s p 中节点数的增加并不影响c r l d p 的工作特性， 因而扩展性能很好。而r s v p 最显著的缺陷就是必须通过更新消息以维护路径的 软状态，网络可扩展性很差。 4 1 对于区分服务的支持 c r - l d p 通过明确规范节点的p h b ( p e rh o pb e h a v i o r , 每一跳行为) ，利用 灵活配置的流量参数可有效支持区分服务。r s v p 的设计初衷是服务于综合业务 模型，因而仅适用于边缘网络或企业网。虽然r s v p t e 也可支持区分服务，但 r s v p 信令只能采用共享明确( s h a r e d e x p l i c i t ，s e ) 类型预留网络资源，同时要 求网络中的设备必须支持可控负载服务( c o n t r o l l e d - l o a ds e r v i c e ，c l s ) 。在骨干 网中，各节点使用的性能参数与所能提供的服务质量千差万别，因此r s v p 很难 实现真正的端到端的服务质量保证。 5 ) 对a t m 的支持 m p l s 在a t m 上的应用是i e t f 发展m p l s 技术最主要的目的之一。a t m 是一种面向连接的技术，而r s v p 作为一种路由器技术属于面向无连接的技术。 同时，r s v p t e 是面向接收者的，而a t m 与c r - l d p 则都是基于发送者的，且 a t m 使用的q o s 参数与c r - l d p 中q o s 的定义十分相似。显然，在与a t m 技 术的结合上，同属面向连接型技术的c r l d p 具有更大的优势。 6 ) 发展前景 由于r s v p t e 对传统r s p v 协议的修改非常大( 包括对软状态、更新机制、 合并链路预留资源机制) 。基于后向兼容性的考虑，r s v p t e 的开发始终受到原 有的r s v p 协议机制的限制。由于r s v p 协议实现复杂，因而在多厂商设备互 连时很难实现互通。相对而言，c r - l d p 是一种真正开放、全新的标准，其开发 不必考虑后向兼容性，所以对于c r l d p 的制定与发展易于国际标准化。 2 4 m p l s 路由 本节详细介绍了与流量工程相关的两种路由方式：显示路由( e x p l i c i t r o u t i n g ，e r ) 和居于约束( c o n s t r a i n t - b a s e dr o u t i n g ，c r ) 的路由。 - 9 第二章m p l s 协议 2 4 1 显示路由 显示路由提供了从入口到出口准确的步骤次序。m p l s 中的标记交换路径可 以被设置成跟随显示路径，比如说，一组p 地址的列表。然而，并不需要列出 全部。 举个例子，路由只需说明最初的几步跳跃。当最后一步被明确说明的跳跃完 成后，标记交换路径路由过程使用跳跃式( h o p b y h o p ) 路由。一条显示路由的 组成可能要比指定说明的正好数少。节点的组合，可以抽象地看成一个逻辑节点， 可以被当作路由中单独的一步表现出来。例如，通过使用一个口前缀，而不是 一个精确的地址。标记交换路径必须在这个逻辑节点中路由一些节点，当做下一 次跳跃。在形成由显示路由提供的下次跳跃之前，路由过程可能包含在逻辑节点 中的几次跳跃。 显示路由也可以包含自治系统( a u t o n o m o u ss y s t e m ，a s ) 。这就允许标记 交换路径可以经过那些超出标记交换路径创始者的管理之外的网络区域。在形成 由显示路由提供的下一次跳跃之前，路由过程可以包括一些在自治系统中的跳 跃。 显示路径可以被分为”精确”和”不精确”两类。一条精确的显示路由必须包括 那些唯一的节点、由显示路由提供的逻辑节点或自治系统，并且必须按照安排好 的次序使用它们。一条不精确的路由必须包括所有的跳跃，并且保持一定的顺序， 但它也可以包括一些为了完成跳跃而必须添加的跳跃。一旦一条不精确的路由被 确定，路由可以被修改( 作为跳跃式路由时可以) ；或者路由可以被”牵制” ( p i n n e d ) ，这样就不会改变路由。 显示路由有一个独特的用处：约束标记交换路径沿着一条路径传送数据，这 条路径与路由协议提供的路径不同。它还可以被用来在一个繁忙的网络上分散流 量，在i 嘲络有故障或拥挤的地方绕行路由，或者提供预先分配的冗余标记交换路 径来防止网络故障。 2 4 2 约束路由 一条标记交换路径选择的路由，可以是由经入口标记交换路由器选择的需求 来约束决定的。显示路由就是约束路由的一个例子，在显示路由中，约束的是标 记交换路径有可能经过的核心路由器的次序。其他类型的约束，可以由关于流量 的描述所强加，包括带宽、延迟、资源等级和优先级。 种方法是让入口标记交换路由器计算整个基于约束的路由，和有关当前网 络状态的信息。这使得一个满足约束的显示路由产生了。 第二章m p l s 协议 另一种方法是跳跃式路由的变异。在每个标记交换路由器上，下一次跳跃的 计算，是由路由器所持有的有关本地资源可用性的信息决定的。 如果路由的部分信息不可用( 比如说，经过自治系统时) ，两种方法被组合 使用。在这种情况下，路由的某一部分可以被不精确的提供，在必要的地方，使 用约束的方法来显示路由。 2 5m p l s 流量工程 m p l s 流量工程就是通过在网络中建立一条、数条、甚至全连接的l s p 、对 网络流量进行调度的方法实现网络流量的均衡。通常在网络中有一些链路可能负 荷饱满甚至超负荷，另外有一些链路却流量较少，在建立进行流量旁路的l s p 的时候，就需要绕开负荷较大的链路，而选择负荷较小的链路。如此就可以有目 的的把流量从负荷大的链路转移到负荷较小的链路，从而达到平衡网络流量的目 的。 m p l s 流量工程支持带宽约束：对于有带宽要求的l s p ，支持m p l s 的流量 工程可以计算出一条满足带宽要求的l s p 。 m p l s 流量工程可以支持l s p 的抢占：对于带宽较大的l s p ，或比较重要的 用户，我们可能希望它有较高的抢占优先级，可以去抢占其它的l s p 的资源。对 于一些不是非常重要的l s p 则可以被抢占。同样，一些l s p 在建立好了以后可 能就不希望它被抢占。 2 6 本章总结 m p l s 的主要目的是为下一代的多用户，多服务的i n t e r a c t 骨干网络提供一 种路由交换的技术基础。它的主要特征为高性能，可灵活扩展，能最大可能地满 足用户对服务质量的需求。i n t e r n e t 网络的飞速发展也为m p l s 的发展带来了十 分显著的推动作用。 m p l s 技术也为一些目前i p 网络急待提供的应用服务如流量工程( t r a f f i c e n g i n e e r i n g ，t e ) 、虚拟专n ( v i r t u a lp r i v a t en e t w o r k ，v p n ) ，服务类别质量保证 ( c l a s so fs e r v i c e ，c o s ) 等提供了套更为合理有效的解决方案。 第三章流量工程算法综述 第三章流量工程算法综述 流量工程的目标是优化网络资源的使用和流量的性能，这一章介绍了p b r 、 m i r a 等比较经典的流量工程算法。然后针对现在口网络中的业务现状，分析 了这些算法存在的问题，并提出了本文的流量工程框架。 3 1 流量工程算法综述 所有的流量工程算法都有明确的优化目标，或最小化拥塞，或最小化网络成 本，或者使网络传输尽可能多的业务等等 基于m p l s 的流量工程算法的框架主要有两种：一种是离线优化+ 在线路 由算法：另一种是在线路由算法。下面即将介绍的p b r 和d b r 等都属于离线优 化+ 在线路由的框架，m i r a 等则是在线路由算法。 3 1 1p b r p b r ( p r o f i l eb a s e dr o u t i n g ，基于特征的路由) 【婚 是一种有带宽保证的动态 路由算法。p b r 的主要思想就是通过s l a ( s e r v i c el e v e la g r e e m e n t s ，服务级别 约定) ，测量网络中所有源一目的节点对之间的聚集业务需求，即“t r a f f i c p r o f i l e ”， 将测量结果作为对将来业务需求分布的一个粗略预测。“t r a f f i cp r o f i l e 用一个 四元组( c l a s s l d ，s ，t r , b f ) 表示，其中c l a s s l d 表示业务的类别，马是从源节点 到目的节点的聚集带宽需求。p b r 以测量得到的“t r a f f i cp r o f i l e ”作为多物 品网络流( m u l t i c o m m o d i t yn e t w o r kf l o w ) 1 6 】问题的输入，计算出链路上的带 宽分配，以此作为在线路由阶段业务进入的准入阙值。 。p b r 算法主要包括两个阶段： 1 ) 离线计算阶段，也就是优化计算阶段。 2 ) 在线路由阶段 在p b r 中，假设网络不能满足所有业务的带宽需求。p b r 离线阶段的优化 计算目标是在网络中寻找路径，使网络能够传送尽量多的业务流。 在线路由阶段，p b r 根据多物品流计算得到的链路带宽分配结果，用类似 “最短路”的算法，为业务选路。当某个源目的节点对间某种业务的带宽需求 超过了分配给它的最大带宽，此业务将被拒绝进入。 p b r 可以保证长期的资源利用效率。但是如果为某一业务类分配的资源被 耗尽，即使网络中存在足够新的业务请求使用的资源，这一类的新的业务请求也 第三章流量工程算法综述 会被拒绝。当实际的“t r a f f i cp r o f i l e ”与预测的“t r a 伍cp r o f i l e ”相差甚远的话， p b r 的效果可能会非常的差，许多本来能够进入的业务被拒绝，而预期会有的 业务又没有到来，造成网络的利用率低下。 3 1 2d b r d b r ( d e s i g n - b a s e dr o u t i n g ，基于设计的路由) 1 7 】是基于设计的路由算法。 基于设计的意思是，从源节点到目的节点的路径集是经过设计的。在离线计算之 前，每对源目的节点间的路径条数已经是确定好的，离线计算的结果就是输出 指定条数的显示路由，每条显示路由有一个确定的带宽值。这些计算得到的路由 信息存储在d b r 服务器里，当有业务请求到来时，d b r 服务器返回一条满足条 件的显示路由。 d b r 离线计算的优化目标是最小化带宽一长度，即本文所说的最小化网络成 本( 第四章有较为详细的介绍) 。 文【1 7 】根据离线计算需要输入的业务矩阵的三种不同形式给出了相应的优 化公式。这三种业务矩阵形式分别是静态的准确业务矩阵、静态的按正态分布随 机模型产生的业务矩阵、动态的泊松到达的业务请求，其对应的优化公式的优化 目标都是相同的，只是在约束条件上有所不同，在以随机模型产生的业务矩阵为 输入的优化公式里，与以准确业务矩阵为输入的优化公式相比，多了一个概率约 束条件，即源目的节点对问路径总带宽值以一定的概率达到业务所要求的带宽 需求，而不是百分百的满足业务要求带宽。以泊松到达的业务请求信息为输入的 优化公式中，多了一个对于业务阻塞概率的约束，通过这个约束条件，将业务请 求的阻塞概率限制在一定范围内。 3 1 3i n t e m e t 流量工程中的显示路由算法 文 1 8 给出了以最小化拥塞为优化目标的形式化公式。最小化拥塞的优化目 标指最小化最大链路利用率。链路利用率定义为：链路已用带宽链路总带宽。 如果最小化拥塞的输入是聚集业务需求矩阵，则最小化拥塞公式计算出来每 对源目的节点在每条链路上的带宽分配，也是聚集的，即源目的节点对中的所 有业务共享计算得到的链路带宽分配。因此，虽然计算结果使得业务需求被分割 到多条路径上，但具体到单个业务流的时候，被分割到多条路径上的几率并不大。 文e 1 8 以此为依据，提出了在不拆分单个业务流的情况下，一种基于重路由 ( r e m u t i n g ) 的启发式路由算法： 基于重路由的启发式路由算法，以最小化拥塞公式计算出来的带宽分配结果 为起点，依次考虑每个业务流被分割到多条路径上的可能性，将可能被分割的业 第三章流量工程算法综述 务进行重路由，使其所有的分组在网络中传输时，使用同一条路径，即避免业务 流被分割。 在文 1 8 l e o 提出的基于重路由的启发式路由算法中，在对可能被分割的业务 流进行重路由时，首先考虑那些预分配结果中使用高利用率链路的业务流，首先 重路由这些业务流，因为这些业务流决定着链路的最大利用率。最小化拥塞的优 化目标是最小化最大链路利用率，所以基于重路由的启发式路由算法也必须以此 为优化的目标。 3 1 4m p l s 网络中基于约束的多径流量工程方案 文 1 9 中提出了一种基于约束的多径流量工程方案，在给定业务分割比例的 情况下，利用最小化拥塞公式计算出业务的传输路径。然后将计算结果发布到边 缘路由器( l e r ) ，在业务到来的时候，在