（计算机科学与技术专业论文）mpls流量工程约束路由算法及系统实现技术研究.pdf

国防科学技术夫学研究生院学位论文 摘要 当前，由于i n t e m e t 迅速发展，网络规模和流量不断增长，导致网络资源不足及网 络拥塞问题日益严重，而各种新的多媒体业务的出现又对网络的服务质量( q o s ) 提出 了新的要求。流量工程( t e ) 就是为了解决这些问题而提出的，它希望在已有网络资源 的基础上，通过优化网络资源利用，来达到减小拥塞、提高网络性能的目的。然而目前 的流量工程技术存在扩展性差、管理复杂等局限，难以适应网络的发展，迫切需要一种 新的技术应用于流量工程。m p l s 技术是当前为业界所普遍推崇的下一代流量工程主流 技术，本文对基于m p l s 的流量工程( m p l s t e ) 进行了深入的研究与分析，着重于其关 键技术一约束路由算法与m p l s t e 的系统实现问题。 首先介绍了m p l s 技术的基本原理，给出了流量工程的基本概念和数学定义，在此 基础上分析了如何基于m p l s 技术实现流量工程，并总结了m p l s t e 的优越性。 其次，对m p l s t e 中的约束路由算法进行了深入研究，归类分析了当前的约束路 由算法，并在现有的动态约束路由算法的基础上，提出了一种满足流量工程要求的动态 约束路由算法t e r a 。通过对算法进行仿真实验，表明该算法在满足带宽约束的基础上， 在获得了高业务吞吐量的同时实现了网络负载平衡，较好地满足了流量工程要求。 本文还归纳了m p l s t e 的系统实现方式，针对集中服务器方式提出了一种区分服 务感知的集中式m p l s 流量工程实现框架d m t e 。该框架可以根据业务特点对不同的业 务类型采用不同的约束路由算法和准入控制，可以更有效地保证了业务q o s ，提高了网 络利用率。 最后，本文对基于路由器方式的m p l s t e 实现技术进行了研究，着重介绍了开发 的t e m i b 和c r l d p 两大软件模块。 关键词m p l s ，流量工程，约束路由，服务质量，c r l d p ，区分服务感知流量工程 t e m i b 第t页 国防科学技术夫学研究生院学位论文 a b s t r a c t t o d a y , t h ei n c e s s a n tg r o w t ho ft h en e t w o r ks c a l ea n dt r a f f i c ，a sar e s u l to fr a p i de v o l u t i o n o ft h ei n t e r a c t , h a sm a d et h ep r o b l e mo fn e t w o r kr e s o u r c el a c ka n dn e t w o r kc o n g e s t i o nm o r e a n dm o r es e r i o u s f u r t h e r m o r e ，n e wm u l t i m e d i aa p p l i c a t i o n sr e q u i r et h en e t w o r kt op r o v i d e q u a l i t yo fs e r v i c e ( q o s ) g u a r a n t e e s s o ，t r a f f i ce n g i n e e r i n g ( t e ) i sp r o p o s e df o rt h a t i t s p u r p o s e sa r e t om i n i m i z et h ec o n g e s t i o na n di m p r o v et h en e t w o r kp e r f o r m a n c et h r o u g h o p t i m i z i n gr e s o u r c eu t i l i z a t i o no f t h ee x i s t i n gn e t w o r k s h o w e v e r , t h ec u r r e n tt e c h n o l o g yo f t ei sl i m i t e db yi t si n h e r e n te x p a n s i b i l i t ya n da d m i n i s t r a t i o nc o m p l e x i t ya n dc a nn o ta d a p t w e l lt ot h eg r o w t ho fn e t w o r k i ti su r g e n tt os e e kak i n do fn e wt e c h n o l o g yt oa p p l yt ot e m p l sh a sb e e nr e g a r d e da st h em o s tp r o m i s i n gt e c h n o l o g yf o rt e i nt h i sp a p e r , w es t u d y m u c ho nm p l s b a s e dt r a f f i ce n g i n e e r i n g ( m p l s - t e ) a n de m p h a s i z eo nc o n s t r a i n t - b a s e d r o u t i n g ( c b r ) a l g o r i t h m ，a n ds y s t e mi m p l e m e n t a t i o nf o rm p l s t e f i m t ，t h ep r i n c i p l eo fm p l s ，t h ec o n c e p t i o na n dm a t h e m a t i cd e f i n i t i o no ft ea r e i n t r o d u c e d i nt h i sf o u n d a t i o n ，w ea n a l y s eh o wt oa p p l ym p l st ot ea n dt h ea d v a n t a g eo f m p l s t ei sc o n c l u d e d t h e n ，t h ee x i s t i n gc b ra l g o r i t h m sa r ec l a s s i f i e da n da n a l y s e d an e wd y n a m i cc b r a l g o r i t h r n - t e r ai sp r o p o s e db a s e do i lc u r r e n tp r i m a r yd y n a m i ca l g o r i t h m s t h es i m u l a t i o n r e s u l t ss h o wt h a tt e r an o to n l ya c h i e v e sh i g ht h r o u g h p u tb u ta l s ob a l a n c e st r a f f i cl o a dw i t h b a n d w i d t hg u a r a n t e e t h em e t h o do fs y s t e m i m p l e m e n t a t i o nf o rm p l s t e i sa l s os u m m e du p ，a n da c e n t r a l i z e di m p l e m e n t a t i o nf r a m eo fm p l s - b a s e dd i f l s e r v - a w a r et r a f f i ce n g i n e e r i n g - d m t e i sg i v e dt oc e n t r a l i z e ds e r v e rw a y , w h i c hc a l lg u a r a n t e eq o sa n di m p r o v en e t w o r ku t i l i z a t i o n u s i n gd i f f e r e n tr o u t i n ga l g o r i t h ma n da d m i s s i o nc o n t r o la c c o r d i n gt os p e c i a l i t yo fd i f f e r e n t s e r v i c e s f i n a l l y , t h ei m p l e m e n t a t i o nt e c h n o l o g yo fm p l s t eb a s e do nr o u t e ri ss t u d i e d t w o i m p l e m e n t e dm o d u l e s ，w h i c ha r ec r l d pa n dt e m i b ，a r em a i n l yd e s c r i b e d k e y w o r d sm p l s ，t r a f f i ce n g i n e e r i n g ，c o n s t r a i n t b a s e dr o u t i n g ，q o s ，c r l d p d i t t s e r v a w a r et r a f f i ce n g i n e e r i n g ，t e m i b 第 1 i 页 国防科学技术大学研究生院学位论文 图目录 图1 1 “鱼”型网络问题l 图1 2 基于路由度量的t e 2 图1 3i p o v e r - a t m 覆盖模型3 图2 1m p l s 标签格式7 图2 2m p l s 节点结构8 图3 1 负载函数曲线2 6 图3 2 仿真拓扑模型2 7 图3 3l s p 请求拒绝数2 8 图3 4 最大链路利用率2 8 图4 1 集中服务器方式m p l s t e 逻辑结构3 0 图4 2 基于路由器的m p l s t e 实现方式3 l 图4 3r a t e s 系统结构一3 2 图4 4t e q u i l a 架构3 3 图4 5d m t e 框架结构3 5 图4 6 在线l s p 路由模块3 6 图5 1m p l s t e 路由器实现框架一3 9 图5 2t e m i b 模块主体结构4 0 图5 _ 3t u n n e l 入口t e m m 流程一4 5 图5 4t u n n e l 出口t e m i b 流程4 6 图5 5c r - l d p 建立l s p 过程4 7 图5 6 显式路由处理流程5 2 图5 7 标签映射消息处理流程5 3 第 i v 页 独仓q 性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：丛竖煎量王蕉约塞整直簋洼丞丞统塞垫技苤盟蠢 学位论文作者签名：型垫：日期：弘。r 年2 月弘日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内客编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在怨密后适用本授权- t t 。) 学位论文题目： 坠! 坚煎量三堡垫塞竖由簋选区丞统塞望茧本盈窥 学位论文作者签名：型之：日期：弘畸年，z 月7 , 日 作者指捌雠：3 驻魄郇年m 渺 国防科学技术夫学研究生院学位论文 第一章绪论 1 1课题研究背景 近年来，随着i n t e m e t 的迅速发展，其网络规模和所承载的业务流量不断增长，平均 每个月网络规模增长1 0 左右，每6 9 个月网络流量翻一番。同时由于网络技术的发展 与融合，出现了“e v e r y t h i n go v e ri p ”的局面，在i p 网络上提供数据、语音、视频流等多 种不同特性的应用的需求越来越大i lj ，而且这些业务的传递不再仅仅需要具有可达性，而 更多的要求保证业务的服务质量( q u a l i t yo fs e r v i c e ，q o s ) 。但是另方面，带宽等网络 资源的增长速度却远远落后，并且由于i p 路由协议本质上是无连接的，只是基于目的i p 地址利用最短路算法选择路径，忽略了网络可用链路容量和业务本身的要求，因此会导致 整个网络利用率的非最佳特征。这即是常说的“鱼”型网络问题。例如图1 1 所示网络， r l 到r 9 和r 2 到r 8 的业务流在最短路径算法的情况下都选择r 3 r 4 - r 5 路径，导致 r 3 - r 4 - r 5 过载，而同时r 3 一 r 6 一 r 7 一 r 5 却闲置不用。“鱼”型网络问题既浪费了网络 资源，同时又造成网络拥塞，影响业务性能。 k 6 r 7 图1 1 “鱼”型网络问题 在这种情况下，为了节省投资、获得最大收益，i s p ( i n t e m e ts e r v i c ep r o v i d e r ，i n t e m e t 服务提供商) 就需要最大限度的利用现有的基础设施，来为用户提供可靠的服务。而为了 在网络中提供这样的能力，就需要实施流量工程( t r a f f i ce n g i n e e r i n g ，t e ) 。流量工程【2 】 目的是实现对网络中业务流的精确控制，在满足业务流q o s 要求的前提下使网络资源尽可 能合理使用，避免出现网络拥塞；同时能够接入更多的业务，提高全网利用率，降低网络 运营成本。可以说，网络流量的不断增长和对资源的渴求是实施流量工程的内在因素资 源的优化利用和i s p 投资回报率的提高是实施流量工程的外在因素。当前，流量工程已经 国防科学技术大学研究生院学位沦文 越来越引起人们的重视，i t u t 、i e t f 以及各大网络设备厂商都非常关注流量工程问题， i e t f 还为此专门成立了t e 工作组。 1 2研究现状 早期的流量工程只是通过简单的改变路由度量值来实现，图1 2 描述了这种方式的一 个简单例子。假设网络a 发送了大量数据给网络c 和网络d ，参考图1 _ 2 所示的路由度量 值，链路1 和链路2 可能发生阻塞，因为a c 和a d 的业务都将选择这些链路，而同 时链路4 空闲。如果我们把链路4 的度量值改为2 ，a d 的流量将转移至链路4 ，a c 的业务仍留在链路1 和2 ，这样就平衡了链路负载，避免了拥塞。基于度量值改变方式的 t e 在网络规模较小时还可以应付，但随着网络规模的不断扩大，由于网络中路由的交互作 用，部分链路度量的改变常常会影响到网络中的其他路径，导致全网范围的、无法意料的 流量抖动。而且这种方式并不能克服i p 路由协议只基于拓扑驱动而不考虑业务负载要求的 固有局限，无法真正达到全网的优化配置。 pl络a辩络b 站i i 嚣a i | l j 嚣0 掰臻d瓣络c 路 i 馨b - - 1 路l “器c 图1 2 基于路由度量的t e 为了克服以上问题，人们引入了a t m 技术，利用a t m 面向连接的特性，在骨干网上 实施流量工程。基于a t m 核心的网络采用了一种i p o v e r - a t m 的覆盖模型，即i p 运行在 a t m 网络上，路由器在a t m 网络的边缘环绕，每个路由器通过一系列经由a t m 物理拓 扑配置的永久虚电路( p v c ) 与其他路由器通信。p v c 就象逻辑电路一样工作，为边缘路 由器提供连接。路由器并不能直接访问a t m 结构中p v c 的具体物理拓扑信息，路由器仅 了解特定的p v c 就像出现在两个路由器之间的简单的点到点电路。如图1 3 所示。 第2 页 国防科学技术大学研究生院学位论文 p w l p v c 2 图1 3i p o v e r - a t m 覆盖模型 基于a t m 的核心网完全支持流量工程，因为它可以对p v c 进行明确路由。p v c 的路 由是通过在网络底层的物理拓扑上提供随机的虚拟拓扑实现的，而在网络底层的物理拓扑 上，通过对p v c 进行路由以使业务分配到所有链路上，以致链路被平均使用。这种实现避 免了业务全部汇集到低花费路由上去，从而不会造成链路的过分使用或未充分使用。但是 i p o v e r - a t m 方式的一个最根本的局限性是它需要对两个不同的网络进行管理：a t m 基础 结构和逻辑的i p 覆盖。不仅增加了网络的复杂性，而且需要进行信元转换，加倍了开销， 造成资源浪费；而且随着核心路由器技术的发展，a t m 骨干网将逐渐被路由器所取代。因 此，如何在未来的i p 网络实现流量工程就成为i s p 面临的一大问题。 m p l s ( m u l t i p r o t o c o ll a b e ls w i t c h i n g ，多协议标记交换) 技术的出现很好的解决了这 个问题。m p l s 是当前被普遍看好的高速骨干网络技术，它综合了面向连接的转发技术和 面向无连接的路由技术，是第二层和第三层技术的集成。基于m p l s 的流量工程 ( m p l s - t e ) 克服了i p 路由的根本缺陷，同时又具有a t m 的面向连接特性。它利用显示 路由技术，网管员可以配置或下层协议自动配置数据包在网络中经过的路径，而不受传统 的逐级路由的限制，可以很好的解决以往存在的问题，被认为是目前流量工程的最好解决 方案，也是目前网络研究的热点之。 对于m p l s t e ，目前i e t f 的m p l s 和t e 两个工作组都已经提出了一些相关的r f c 和大量的i n t e m e t 草案，如r f c 2 7 0 2 描述了在m p l s 网络中实施流量工程的要求，r f c 3 3 4 6 总结了m p l s t e 的适应性。i t u - t 和m p l s 论坛也都分别把m p l s t e 作为重点的研究工 作之一。各大网络设备厂商也在致力于这方面的研究，包括c i s c o 、l u c e n t 、j u n i p e r 等都 己声称在产品中支持m p l s t e ，l u c e n t 还在全美2 3 个大城市间的n e t 2 0 0 0 试验网上进行 了m p l s t e 的系统实验。然而，目前虽然m p l s t e 的标准已初步完善，但一些相关技术 仍在发展中，如约束路由等，而且国内的研究多停留在理论阶段，对于m p l s t e 的实现 涉及较少，这些都有待于进一步研究。 第3 页 户 举“留 乎 国防科学技术大学研究生院学位论文 1 3本文的主要工作 本文以核心路由器工程项目为背景，在作者参与m p l s 相关协议研制的基础上，对基 于m p l s 的流量工程进行了深入的研究。主要完成了以下工作： ( t ) 在对m p l s 技术和流量工程做了全面了解的基础上，对基于m p l s 实现流量工程进行 了深入研究。 f 2 )对m p l s t e 的关键技术之一一约束路由算法进行了深入分析，提出了一种满足流量 工程要求的动态约束路由算法，该算法在满足带宽的基本约束下，在获得较高业务吞 吐量的同时实现了网络负载平衡。 f 3 )归纳了m p l s t e 的系统实现方式，分为基于集中服务器方式和基于路由器方式。在 对当前集中服务器实现方式研究的基础上提出了一种区分服务感知的集中式m p l s 流量工程实现框架。它同时集成了离线优化和在线路由并且根据业务特点对不同的业 务类型采用不同的约束路由算法和准入控制，可以更有效地保证业务q o s ，同时减少 拥塞、提高网络利用率，较好的满足了i s p 要求。 ( 4 ) 参与了m p l s - t e 在核心路由器中的工程实现，主要实现了c r - l d p ( c o n s t r a i n t - b a s e d r o u t i n gl a b e ld i s t i l b u t i o np r o t o c o l ，基于约束路由的标签分配协议) 和t e m i b ( t r a 茄c e n g i n e e r i n gm a n a g e m e n ti n f o r m a t i o nb a s e ，流量工程管理信息库) 两大软件模块。 第一章， 第二章， 第三章， 第四章， 第五章， 第六章 1 4本文的组织结构 主要介绍课题的研究背景、研究现状和本文的主要工作。 首先介绍了m p l s 技术原理，然后给出了流量工程的概念和数学描述，最后 分析了如何基于m p l s 实现流量工程及优势所在。 对m p l s t e 中的约束路由算法进行了深入研究，归类分析了当前主要的约 束路由算法，并提出了一种满足流量工程要求的动态约束路由算法t e r a ， 给出了算法分析与仿真结果。 归纳了m p l s t e 的实现方式，针对集中服务器方式提出了一种区分服务感 知的集中式m p l s 流量工程实现框架d m t e 。 对基于c r - l d p 协议的m p l s - t e 路由器实现技术进行了研究，详细介绍了 c r l d p 和t e m i b 两部分模块的实现技术。 对全文的工作进行总结，提出下一步的研究内容。 第4页 国防科学技术大学研究生院学位论文 1 5本文的研究成果 本文对基于m p l s 的流量工程进行了深入的研究与分析，提出了一种满足流量工程要 求的动态约束路由算法，仿真结果表明算法在满足带宽的基本约束下，获得了高业务吞吐 量同时实现了网络负载平衡：提出了一种区分服务感知的集中式m p l s 流量工程实现框架， 它根据业务特点对不同的业务类型采用不同的约束路由算法和准入控制，可以更有效地保 证业务q o s ，同时减少拥塞、提高网络利用率；在核心路由器上实现了基于c r l d p 协议 的m p l s 流量工程系统的c r - l d p 和t e m i b 两大软件模块。 国防科学技术人学研究生院学位论文 第二章m p l s 与流量工程 2 1m p l s 概述 m p l s 诞生之初是为了解决i p o v e r - a t m 覆盖模型的种种弊端。最初，人们想到既然 i p 技术和a t m 技术各有自己的优势，是不是可以把i p 灵活的控制能力和a t m 的高速转 发性能结合起来呢? 于是，最早在1 9 9 6 年i p s i l o n 公司基于这一思想( 目前已被n o k i a 收 购) 推出了i ps w i t c h i n g 3 1 协议，该协议一经推出立即引起巨大的震动，由此引发了路由器 技术的革命，各公司开始纷纷提出自己的方案。如c i s c o 公司的t a gs w i t c h i n 9 1 4 1 方案，i b m 的a r i s 5 i ( a g g r e g a t er o u t e b a s e d1 ps w i t c h ) 方案，t o s h i b a 的c s r 6 】( 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 ”为基础，并联合 i b m 和t o s h i b a 公司，向i e t f 提交了一套解决草案，即m p l s 。1 9 9 7 年4 月i e t f 的m p l s 工作组正式成立。 2 1 1m p l s 定义 m p l s t4 7 1 是一项利用绑定在i p 包中的标签在网络中进行数据包转发的技术，它不仅支 持网络层的多种协议，还可以兼容第二层上的多种链路层技术。m p l s 把第二层交换技术 和第三层路由技术结合在了一起，其主要目的是建立一个具有更好性能更高稳定性的灵活 和易于扩展的网络架构。 在m p l s 网络中，数据包转发是基于4 字节的短标签，它不同于常规m 路由基于最 长地址匹配查找的h o p - b y - h o p 的数据包转发方式。在常规的i p 路由中，每个节点都要独 立分析i p 包头，并基于目的地址做出路由决策。而在m p l s 中，只是在分组进入网络的 边缘节点处对i p 包头进行分析，为数据包分配标签。每个数据包被沿着预先建立的标签交 换路径转发，后续节点不再分析i p 包头，只根据标签内容做出如何转发数据包的决定。在 每一跳上，标签交换路由器去掉数据包中已有的标签并为之绑定一个新的标签，这个新的 标签指明数据包被转发的下一跳。在m p l s 网络出口边界路由器上，数据包中的标签被去 掉，并被按一般的方式转发到它的目的地。 第 6 页 国防科学技术大学研究生院学位论文 2 1 2m p l s 常用术语 下面，我们首先介绍m p l s 的一些基本概念和术语。 r 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 网络中获得的处理方式是完全相同的。 f e c 可根据多种信息设置，提供一个粗糙的或者精细的转发类度。例如：目的子网、 目的子网和服务类型组合、源和目的子网组合、特殊的q o s 需求、或虚拟专网( v p n ) 识别号。 f 2 1l a b e l ：标签，也成为标记，是被用来标示一个f e c 的3 2 比特固定长度的标识符，通 常仅有本地意义。被附加在特定数据包上的标签，代表了该数据包被分配的f e c 。在 a t m 的情况下，标签被放置在a t m 包头中的v c i 或者v p i 字段中；其他第二层技 术，如以太网、令牌环、f d d i 和点到点连接，不能利用其第二层地址字段来携带标 签，这些技术可以通过在网络层和链路层之间加入垫层包头( s h i mh e a d e r ) 来携带标 签，如图2 2 所示。垫层标签包头的使用可以允许大多数的第二层技术支持m p l s 嗍。 i l a b c i x p t t l l a b e l ：lm p l s 辜i i e x p ：寓骚能 l 一 o - ，| 1h 一s + s ：线戚k 盘 l 一_ - 一 - 一一一，一， r 1 l ：曩行列州 、 一，一一。 i 第二层也尖 s h i m鹅一璎也文第蝈瞪包头数探 i 擞务豢j ；孽 图2 1 m p l s 标签格式 ( 3 ) 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 网络的核心交换设备，位于 m p l s 网络内部，它提供标签交换、标签分配功能。 ( 4 ) l e r ( l a b e ls w i t c h i n ge d g er o u t e r ) ：标签交换边界路由器，m p l s 网络同其他网络的 边缘设备，它提供流量分类和标签的映射( 作为入口) 、标签的移除( 作为出口) 功 能。 ( 5 ) 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 s p 是单向 的，这意味着数据包可以在归途中走一条不同的返回路径。l s p 的建立支持两种方式： 独立控制和有序控制。独立控制方式下，每一个l s r 独立决定标签分配建立l s p ： 而在有序控制方式下，标签分配是从l s p 的入口到出口或相反方向以一种有序的方式 国防科学技术大学研究生院学位论文 控制建立l s p 。l s p 路由可以根据动态拓扑生成或是采用显式路由( e r l s p ) 。动态 拓扑生成的方法是通过访问每一个l s r 中活动的路由协议建立的，对于路由表中的 每一项，都会产生一个标签映射。从流量工程的角度来讲，动态拓扑生成的l s p 路由 并未提供优越性，我们主要关心的是e r - l s p 。e r l s p 路由可以称为源路由，源节点 包含一个用于l s p 建立的路径向量，该向量明确列出了转发过程中的每一跳的路由。 在流量工程中，e r l s p 的路由一般在l s p 的源点通过约束路由算法计算得到或由管 理员指定，也可以通过路出服务器计算出结果，然后发送到源点l e r 上。 r 6 、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 ) ：标签分配协议，用来在m p l s 网络中的l s r 设备 之间发布标签绑定信息。m p l s 定义了专门的标签分配协议一l d p 6 】，另外为支持显 式路由，i e t f 又定义了c r - l d p i l 7 】和r s v p _ t e l l 8 1 ( 带有流量工程扩展的资源预留协 议) 。其中l d p 和c r l d p 运行在t c p 上，而r s v p - t e 运行在u d p 上。标签的分 配可以通过多种模式进行，如主动提供的下游标签分配与按需提供的下游标签分配。 2 1 3m p l s 节点结构 m p l s 节点包括两个结构平面嘲：m p l s 控制平面和m p l s 转发平面。除了可以交换 带有标签的数据包外，m p l s 节点还可以执行第三层路由选择。图2 2 显示了一个m p l s 节点的基本结构。 拄嘲卜晰 输入i p 数掘乜 输 绗酥驾阳 教槲毡 转牲p 蝴 司塑生丝塾壅卜l 一- , 咂q 蛩i 悻抟转毁限息枉l 一一 _-。_-_- 、l 撺 l i 遗抖悄息 交投 酥嚣糯定岱息 蹙授 瓣m i p 教攥色 虢；2 l 、麓l j 薮掣也 图2 t 2 m p l s 节点结构 m p l s 控制平面通过运行路由选择协议和标签分配协议来维护路由转发信息表和标签 转发信息表内容。路由选择协议一般选择o s p f 和i s i s ，因为它们能给每一个m p l s 节点 提供一个完整的网络视图。如果要支持流量工程，还需扩展o s p f 和i s i s 协议，不仅发 第8页 国防科学技术大学研究生院学位论文 布链路可达性信息，还要增加链路的资源属性。标签分配协议可以选用l d p 或者支持流量 工程的c r l d p 和r s v p t e 。m p l s 控制平面一般还包括流量工程模块、虚拟专用网模块 和q o s 模块等。 m p l s 转发平顽负责根据路由转发信息表和标签转发信息表( l f i b ) 来转发数据包。 l f i b 由一系列的条目组成，每一个条目含有一个入标签和一个或者多个子条目，l f i b 根 据入标签值进行索引查找。每一个子条目由一个出标签、出接口和下一跳地址构成。在 个条目内的各个子条目可以拥有相同的或者不同的出标签。多个子条目主要用来支持多播 转发。 2 1 4m p l s 优势 最初人们认为m p l s 可明显的增强l s r 的转发性能，因为m p l s 提供的精确查找要 比由i p 采用的最长匹配查找快。但是，最近芯片技术的进步使基于a s i c 的路由查询引擎 与m p l s 的运行速度相当。 其实m p l s 技术的真正优势在于它提供了路由( 即控制) 和转发间的完全分离 9 1 。这 种分离允许只使用单一的转发算法一m p l s 便可对多种服务和业务类型进行配嚣。将来， 当i s p 需要开发一种新的增值业务时，m p l s 转发结构可以被保留，新的业务可通过修改 控制部分将业务流指定到不同的f e c ，然后在将f e c 映射到特定的满足要求的l s p 而简 单的建立。为业务流指定f e c 可以根据多种策略进行配置，例如可以根据目的地址、源地 址、应用的类型、特殊的q o s 需求、v p n 识别号等，或以上策略的任意组合。而l s p 的 选路也可以配置为满足不同应用的需要，例如l s p 可以设计为经过的跳数最少、满足特定 的带宽要求、支持定的性能要求、避开潜在的拥塞点等等。 m p l s 控制与转发完全分离的特点为控制数据流在网络中的分布带来了极大的灵活 性，这给目前的i n t e m e t 带来了许多好处： ( 1 ) 应用于流量工程：利用m p l s 的显式路由技术，可以对网络上的特定流量显式的设定 一条或多条路径，也可以为某类流量设定性能特性参数。对于带宽没有被充分利用的 路径，这个特性可以优化带宽利用率。m p l s 流量工程克服了以往流量工程实现技术 的不足，是目前流量工程的最佳+ 解决方案。 ( 2 ) 应用于虚拟专用网络：利用m p l s 技术，服务提供商可以利用其现有的体系结构，在 骨干网上为多个客户创建基于第三层技术的虚拟专用网络，而不需要用户端再另外实 施加密技术或特别的应用程序。 第 9 页 国防科学技术人学研究生院学位论文 ( 3 )支持服务质量保证：由于m p l s 引入了面向连接特性，因此可提供与a t m 技术相同 的服务质量保证能力，可以给用户提供多样化的质量保证：同时m p l s 又与i p 网络 紧密集成，不存在管理复杂性问题。 ( 4 ) 集成i p 网和a t m 网：大多数运营商的网络目前都采用了i p o v e r - a t m 覆盖模型，这 种实现方式存在着扩展性和管理复杂性问题。利用m p l s 技术，运营商可以把a t m 的控制平面移a 至i i 第三层，因此简化了网络的控制管理以及网络的复杂性。这项技术 提供了良好的扩展性，消除了承载i p 流量时a t m 信元标识的额外负载。 ( 5 )简化i p v 6 的部署：因为m p l s 为i p v 4 所应用的转发算法可以被直接应用在支持i p v 6 的路由选择协议中。 2 2流量工程介绍 随着i n t e m e t 的不断发展，多种业务需求的不断增加，i p 网络拥塞的问题变得越来越 严重。如何高效、合理的利用有限的网络资源实现多种业务的需求，成为i s p 面临的主要 问题。而流量工程就是用来解决此问题的一种网络技术。 2 2 1 基本概念 流量工程【lo j 是一种能将业务流映射到实际物理通路上，同时又可以自动优化网络资源 以实现特定应用程序服务性能要求的、具有宏观调节和微观控制能力的网络工程技术。有 效、可靠地运行网络，同时优化网络资源的使用和提高业务的服务性能，是实现流量工程 的目标。由于i n t e r n e t 商业化和竞争性的加剧以及网络资源的局限性，使得流量工程己经成 为许多大型自治系统不可缺少的功能。从网络流量的观点来看，流量工程的功能可以看作 是网络中业务流量分布的优化：从i s p 的角度来看，流量工程的功能是使网络资源得到合理 利用和网络性能得以优化；从用户的角度看，流量工程的功能是保证用户的q o s 得到满足。 2 2 2 数学描述 从理论上讲，流量工程问题包含解决优化和满足约束两方面问题。其数学描述定义如 下： 令操作符t 代表流量工程的处理，对于一个给定的网络g ( v ，e ) ，流量需求用抽象 参数p ( i c l ) 表示，定义所有需求的笛卡儿乘积d = hd ，那么一特定的需求d 可以 l e ， 第 l o 页 国防科学技术大学研究生院学位论文 用向量表示为：d z ( z ，巩，砖) d 。d 的确切含义依赖具体的实际情况，比如，z 口可 以代表一给定源目的地址数据流的集合。同理，我们可以用另一参数x 。表示资源利用的具 体情况，定义流量映射的笛卡儿乘积= n 一。进一步定义局c x 表示满足流量需求d j e ， 约束的流量映射子空间。综上所述，流量工程问题可以定义为： 对某一网络g ( v ，e ) 和给定的需求d d ，决定最优化映射x + ，满足 s 1 f ( x + ) f ( x )v x 局( f 代表优化函数)( 2 1 ) 即用流量工程操作t 表示为：t ( d ) = x ( 2 2 ) 因此，流量工程问题实质上就是对一特定的需求d ，如何找出一个满足需求约束的优 化映射x 的问题1 。 2 2 3 性能指标 流量工程的性能指标可以分为两类1 2 1 ： ( 1 ) 面向业务 ( 2 ) 面向资源 面向业务的性能指标是一种与特定应用的流量特性相关的指标，它与提高业务流的服 务质量有关。在目前只有单一服务类别的、尽力而为的i n t e r n e t 流量模型中，面向业务的 性能指标包括对分组丢失的最小化、对时延的最小化、对吞吐量的最大化以及对服务等级 协定( s l a ) 的增强等。在这一流量模型中，使分组丢失最小化是最重要的性能指标。而在 未来的区分服务i n t e r n e t 中，一些与统计数据有关的面向流量的性能指标( 如时延峰值变 化等) 也将会越来越重要。 面向资源的性能指标是一个与网络资源相关的指标，它试图改善网络性能，包括优化 资源利用的各个方面，如网络资源利用率、网络吞吐量等。对网络资源进行有效的管理是 达到面向资源性能指标的重要途径。通常我们希望确保网络资源均衡使用，避免有些路径 过分使用而拥塞，而另一些网络资源却没有得到充分的利用。带宽是当前网络上的一种非 常重要的资源。因此，流量工程的一项中心任务就是对带宽资源进行有效的管理。 无论是面向资源的还是面向业务的流量工程，它们首要的性能指标都是拥塞的最小 化，而负载均衡是优化网络性能的重要策略。 第1 1页 里堕型堂垫查查堂竺茎竺堕堂垡丝苎 2 2 4 主要功能 流量工程通过把流量有效地映射到网络的实际物理链路上以获得特定的性能目标，这 要求对路由功能进行精确的控制。因此，流量工程的最重要功能就是计算和建立从一个节 点到另一个节点的转发路径，这条路径必须满足业务流的q o s 要求，同时也要满足网络容 量和策略要求。具体来说，流量工程应实现以下功能： ( 1 ) 调节网络中容易发生拥塞的点即瓶颈点的流量到其它通路上去。 ( 2 ) 当发生部分节点或链路失效时能提供精确的重路由控制。 ( 3 ) 平衡全网负荷。 ( 4 ) 降 氐i s p 的网络使用费用，提高它们的竞争力 ( 5 ) 增强面向业务流的网络性能特性，如减少分组丢失，减少拥塞时间，尽可能提高吞吐 量等。 ( 6 ) 增强网络性能的统计功能以支持更进步的性能改善。 2 3基于m p l s 的流量工程 2 3 1m p l s 用于流量工程 m p l s 的一个最主要应用就是用于流量工程，利用m p l s 所具有的面向连接特性，可以 为业务指定满足特定需求的优化路径，而不受传统逐跳路由的限制。m p l s 具备了 i p - o v e r a t m 覆盖模型所实现的各种流量工程能力，并且它与i p 紧密集成，其成本与可扩 展性较之覆盖模型更为理想。更重要的是，它可以实现流量工程功能的自动化。 目前，m p l s t e 的一般实现方法是利用约束路由计算或网管员指定显式路径，通过标 签分配协议根据显式路径在网络中建立标签交换路径，利用标签交换路径进行数据转发。 从功能上来看，主要包括四部分内容【1 3 】： ( 1 ) 信息收集 信息收集单元主要用来收集网络中的链路状态和带宽信息，提供给路径选择单元使 用。这部分可通过定义i g p ( i n t e d o rg a t e w a yp r o t o c o l ，内部网关协议) 扩展或网络测量来 实现。收集的信息保存在流量工程数据库( t r a f f i ce n g i n e e r i n gd a t a b a s e ，t e d ) 中，为路 径选择单元计算转发路径所使用。 ( 2 ) 路径选择 第 1 2 页 国防科学技术大学研究生院学位论文 m p l s t e 的路径选择既要考虑业务的需求约束，还要使网络性能优化，是实现 m p l s t e 的核心部分。路径选择单元主要通过对t e d 使用约束路由算法来计算出一条满 足条件的l s p 路径，这条l s p 路径可表