（通信与信息系统专业论文）mpls网络动态流量工程关键技术研究.pdf

摘要 摘要 随着信息技术的快速发展，人类对图像、语音、视频等多媒体信息的需求量 急剧上升，对网络带宽和高速互联能力的要求越来越高。m p l s ( m u l t i p r o t o c o l l a b e ls w i t c h i n g ) 网络由于能够提供快速路由和交换而得到了广泛的认同。根据 正盯的定义，业务i t 程t 2 】( t r a 伍ce n g i n e e r i n g ，t e ) 是一种可以提高或优化网络 性能的工具。具体来讲，就是将流量合理地分配到网络链路上以提高网络整体性 能指标。m p l s 的出现为实现t e 提供了便利。m p l s 网络通过显式路由计算出l s p ( l a b e ls w i t c h e dp a t h ) ，网络汇聚节点将收到的数据包根据事先定好的策略转发到 相应l s p 。数据包在l s p 上传输不再像m 网络那样基于跳到跳路由，而是根据定 义好的l s p 直接被转发。为了提高m p l s 网络资源利用率和容错度，通常源宿节 点对之间有多条平行l s p 。m p l s 业务量工程的一个关键问题是：如何将汇聚的流 量合理的分配到各条平行l s p 上，达到网络性能的最优化。本文研究正是针对这 一问题：“动态平行多路径流量工程” 本文工作主要包括以下三个方面：第一，改进现有平行路动态m a t e 3 】算法， 使其性能更优；第二，提出支持多业务的m s m a t e 算法，能够为不同类型的业 务提供有区分的服务；第三，研究现有的各种动态分流机制，并提出了更适应于 平行路b u r s t 动态分流机制的实现方法。 在本文第二章，作者详细描述了动态算法m a t e 的原理和实现过程，指出了在 实现中应该注意的问题，并提出改进意见。然后提出对l s p 路径进行预先规划的 思想，以进一步提高动态业务量工程性能。作者首先采用k 最短路算法进行动态 规划，并研究其性能。在此基础上，本文提出了最小化最大链路重叠度的线性规 划模型。最后通过仿真实验比较两种规划方法的性能。 在本文第三章，作者研究了支持多种业务的动态t e 算法。多条平行路径可以 按照延时、丢包率等参数划分为不同类型的路径集。对于延时要求严格的语音数 据可在延时路径集上传输；而对于丢包率要求严苛的数据业务可在丢包率小的路 径集上传输。从而在保障业务q o s 的前提下，同时实现对全网性能的优化。 在本文第四章，作者研究了动态平行路算法中必须用到的分流机制。分别基 于包、基于流和基于动态哈希数据流这几种机制进行了对比研究，进而提出了针 对准确性更高，包乱序程度更小的b u r s t 流量分配机制的实现方法。 摘要 本文第五章是对全文的全面总结，同时提出了下一步工作方向。 关键词：流量工程，在线动态算法，路径规划，分流机制 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , d e m a n d sf o rm u l t i m e d i a i n f o r m a t i o ns u c ha sg r a p h i c s ，a u d i oa n dv i d e oi n c r e a s ei nh i g hs p e e d ，w h i c hp u tag r e a t c h a l l e n g eo nb a n d w i d t ha l l o c a t i o ns t r a t e g yi nc o m m u n i c a t i o nn e t w o r k s t of a c et h i s c h a l l e n g e ，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 ) i sp r o p o s e d i nm p l sn e t w o r k s ， t r a f f i ci s a g g r e g a t e di n t ol a b e ls w i t c h i n gp a t h s ( l s p ) ，w h i c hi s c a l c u l a t e da n d d e p l o y e di na d v a n c ea sa t a m e l f r o ms o u r c er o u t e rt od e s t i n a t i o nr o u t e r t h e s e e x p l i c i tr o u t i n g a p p r o a c hi sm u c hm o r ef l e x i b l ea n de f f i c i e n tt h a n t r a d i t i o n a l h o p - b y - h o pi pr o u t i n gs t r a t e g y t oa c h i e v eh i g hu t i l i z a t i o na n df a u l t - t o l e r a n c e ，u s u a l l y m u l t i p l ep a r a l l e ll s pp a t h sa r ec o n s t r u c t e db e t w e e na n yn o d ep a i ri nm p l s n e t w o r k s a sar e s u l t ，t h ee d g er o u t e rh a st od e t e r m i n et h es p l i r i n go ft r a f f i ca m o n ga l lt h e s e p a r a l l e l l s p s t od e t e r m i n et h eb e s ts p l i r i n gs c h e m ew h i c hm a k e st h en e t w o r k p e r f o r m a n c eo p t i m a li so f t e nt r e a t e da sas u b c a t e g o r yo f1 h 施ce n g i n e e r i n g ( t e ) p r o b l e m i nt h i st h e s i s ，d y n a m i ct ea p p r o a c hi nt h i sc o n t e x ti sr e s e a r c h e di nd e t a i l m a j o rc o n t r i b u t i o no ft h i st h e s i si sa sf o l l o w ：f i r s t l y , t h ef a m o u sm a t ea l g o r i t h mi s i m p r o v e dt h r o u g ha no f f - l i n ep a t hp l a n n i n gp h a s e s e c o n d l y , ad y n a m i ct es c h e m e ， c a l l e dm s - m 闰陋，i sp r o p o s e dt oi m p o v et h en e t w o r kp e r f o r m a n c ei nm u l t i s e r v i c e e n v i r o n m e n t f i n a l l y , t h eg r a n u l a r i t yo ft r a f f i cs p l i r i n gi ss t u d i e d ，w h i c ht u r l l so u tt ob e t h em o s ti m p o r t a n ti m p l e m e n t a t i o ni s s u ei nd y n a m i ct ec o n t e x t i n c h a p t e r2 ，t h em a t ea l g o r i t h m i ss t u d i e di nd e t a i l ，a n ds o m ep o s s i b l e i m p r o v e m e n ti ss u g g e s t e d t h e n ，t h eo f f - l i n ep a t hp l a n n i n gp h a s ei sp r o p o s e da sa l l e n h a n c e m e n tt ot h eo r i g i n a lm a t ea l g o r i t h m 。朊c o n s i d e r e dt w os t r a t e g i e sf o rs o l v i n g p a t hp l a n n i n gp r o b l e m n ef i r s to n eu s ek - s h o r t e s tp a t ha l g o r i t h ma n dt h es e c o n do n e f o r m u l a t et h ep r o b l e mi na l li n t e g e rl i n e a rp r o g r a m m i n g ( i l p lm o d e l t h ep e r f o r m a n c e o ft h e s es t r a t e g i e si sc o m p a r e dt h r o u g he x t e n s i v es i m u l a t i o n i nc h a p t e r3 ，ad y n a m i ct ea l g o r i t h mi n m u l t i s e r v i c ee n v i r o n m e n t ，w h i c hw e c a l l e di tm u l t i s e r v i c em a t e ( m s m a t e ) ，i sp r o p o s e d t h ep a r a l l e lp a t h sb e t w e e na s p e c i f i cn o d ep a i ra r ed i v i d e di n t od i f f e r e n tt y p e so fp a t hs e t sa c c o r d i n gt om e i rd e l a y , l o s sr a t ea n dj i t t e r f o rd e l a y - s e n s i t i v et r a f f i c ( e g ，p a c k e tv o i c e ) ，t h ep a t h sw h i c hh a s i i l a b s t r a c t p a t hd e l a yl e s st h a nag i v e nt h r e s h o l d ( e g ，5 0 m s ) i su s e d o nt h eo t h e rh a n d ， 1 0 s s - s e n s i t i v e 纰l 伍ci sc a r r i e do l lt h ep a t h sw h i c hh a se n d t o e n d1 0 s sr a t e1 0 w e rt h a na g i v e nt h r e s h o l d ( e 。g ，5 ) i nt h i sf r a m e w o r k ，d i f f e r e n to b j e c t i v ei su s e df o rd i f f e r e n t p a t hs e t f o re x a m p l e ，f o rt h ep a t h sc a r r y i n gp a c k e tv o i c et r a f f i cw et r yt oi l l i i l i m i z e t h e i ra v e r a g ed e l a y , a n df o rt h ep a t h sc a r r y i n gf t pt r a f f i cw et r yt om i n i m i z et h e i r a v e r a g el o s sr a t e i nt h i sw a y , w eh o p et h a tn o to n l yt h eq o sr e q u i r e m e n tf o re a c h s p e c i f i ct r a f f i ct y p ei ss a t i s f i e d ，b u ta l s ot h eb e s tn e t w o r kp e r f o r m a n c ec a r lb ea c h i e v e d i nc h a p t e r4 ，a ni m p o r t a n ti s s u e ，n a m e l yt h eg r a n u l a r i t yo ft r a f f i c s p l i t t i n g ，i s s t u d i e d f i r s t l y , a n a l y s i s a n d c o m p a r i s o n o fs o m e t y p i c a ls t r a t e g i e s ，s u c h a s p a c k e t - b a s e d ，f l o w - b a s e d ，a n dd y n a m i c - h a s h - b a s e da l g o r i t h m s ，a r ep r e s e n t e d b a s e do n t h ei n s i g h tg a i n e di nt h ea n a l y s i s ，w ep r o p o s ean o v e lm e c h a n i s m ，c a l l e db u r s t - b a s e d s p l i t t i n g ，t oi m p r o v et h ep e r f o r m a n c ei nt e r m so fa c c u r a c yo fs p l i t t i n gr a t i oa n dt h e o c c u r e n c eo fr e o r d e r i n ge v e n t s f i n a l l y , w ec o n c l u d ea n dm e n t i o na r e a so ff u t u r ew o r ki nc h a p t e r5 k e y w o r d s ：t r a f f i ce n g i n e e r i n g ，o n - l i n ed y n a m i ca l g o r i t h m ，p a t hp l a n n i n g ， t r a 佑cs p l i t t i n gm e c h a n i s m i v 图表目录 图表目录 图1 1m p l s 协议体系2 图1 2m p l s 网络结构。2 图1 3m p l s 数据包封装格式3 图1 - 4m p l s 标签交换过程3 图1 5 流量工程实例5 图1 - 6 流量工程分类体系6 图1 7 域内域间流量工程6 图l 。8 离线t e 功能模块8 图2 1m a t e 实现逻辑框图1 7 表2 1m a t e 实现数据状态表l8 图2 2 用b o o t s t r a p 技术计算均值2 2 图2 3m a t e 仿真拓扑模型2 3 图2 - 4i n g r e s s 节点模型2 4 图2 5p r o c e s s 模型2 4 图2 - 6 原始m a t e 仿真结果2 5 图2 7 改进m a t e 仿真结果2 5 图2 8k 最短路网络拓扑2 7 图2 - 9 第一步：算出所有点到目的点最短路2 8 图2 1 0 第二步：k 最短路算法回溯过程2 8 图2 1 1 实验网络拓扑2 9 图2 1 2k 最短路算法计算的路径3 0 图2 1 3 最小化最大l i n k 重叠度模型下的路径3 0 图3 1m s m a 砸流程图3 4 图3 2m s m a t e 网络示例3 4 表3 1m s m a t e 和m a t e 实验结果3 5 图3 3 自适应门限设置算法实验拓扑3 7 表3 2 延时门限平均延时抖动关系3 7 图3 4 门限平均延时关系3 8 图3 5 门限抖动关系3 8 图4 1 基于b i n 的r o u n d r o b i n 分流机制4 1 图4 2 基于流分配机制实现流程4 3 图4 3 静态哈希分流过程4 3 图4 4 动态哈希过程4 4 图4 5 网络中b u r s t 分流实例4 5 图4 6b u r s t 的形成4 5 图4 7b u r s t 分流机制4 6 v i i i 图表目录 图4 8b u r s t 分流机制发送数据包过程4 6 图4 9 流量分配仿真拓扑4 7 图4 1 0 节点1 的进程模型4 8 图4 11 a 周期为p 】时的分流错误率4 8 图4 1 1 b 周期为p l 时的包乱序率4 9 图4 1 2 a 周期为p 2 时的分流错误率4 9 图4 1 2 b 周期为p 2 时的包乱序率5 0 i x 缩略语表 缩略语表 a s y n c h r o n o u st r a n s f e rm o d e 异步传输模式 e x p l i c i tr o u t i n g 显式路由 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 r a m er e l a y帧中继 i n t e m e te n g i n e e r i n gt a s kf o r c e互联n - r 程任务组 i n t e g e rl i n e a rp r o g r a m m i n g 整数线性规划 i n t e r n c tp r o t o c o l网际协议 l a b e le d g er o u t e r标签边缘路由器 l a b e ld i s t r i b u t i o np r o t o c o l标签分发协议 l a b e li n f o r m a t i o nb a s e标签信息库 l i n e a rp r o g r a m m i n g线性规划 l a b e ls w i t c h e dp a t h标签交换路径 l a b e ls w i t c h i n gr o u t e r标签交换路由器 m u l t i p a t ha d a p t i v et r a f f i ce n g i n e e r i n g多路径自适应流量工程 m u l t i p r o t o c o ll a b e ls w i t c h协议标签交换 o p e ns y s t e mi n t e r c o n n e c t i o nr e f e r e n c em o d e l 开放式互联参考模型 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资源预约协议 r e s o u r c ep r o v i s i o n i n gc y c l e资源分配周期 t r a f f i ce n g i n e e r i n g流量工程 x 一 状 眦 职 肼 耻 口 呶 肼 皿 脚 弧 一 一 一 眦 亿 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 虢司址日期：渺年z 月尸日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 毕址 导师签名： 日期：沙， 第一章绪论 第一章绪论 随着大规模网络应用的发展，因特网服务提供商( i s p , i n t e r n e ts e r v i c ep r o v i d e r ) 的骨干网上数据流量巨增。传统口网络基于跳到跳的材尽力而为 服务模型，难 以满足需求，比如当承载语音业务时，可靠性必须到达传统电信网水平，才可以 保证此业务需求。多协议标签交换【1 】( 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 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 ，i s p 可以预先规划流量的路径，从而避免产生拥塞链路或者拥塞节点， 可以解决部分资源利用过载，而其他资源空闲的问题，使得已有的资源得到充分 利用。 1 1m p l s 网络概述 1 1 1 基本介绍 m p l s 网络作为一种高性能的电信网络，在两个远端节点之间建立了“虚拟路 径 ，在此路径上可以封装各种协议的数据包，将承载的数据包高速地从网络一个 节点发送到下一个节点。 m p l s 网络中，在入口节点l e r ( l a b e le d g er o u t e r ) 上为每个数据包打上标 签，在中间节点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 网络减少了与数据链路层的关联性，可以使用下层任意技 术，比如，a t m 、帧中继、s o n e t 和以太网。m p l s 处于o s i ( o p e ns y s t e m i n t e r c o n n e e t i o n ) 模型的数据链路层和网络层之间的2 5 层。协议层次模型如图1 。l 所示。 电子科技大学硕士学位论文 m p l s 采用标准分组处理方式对第三层分组进行转发，利用标签交换对第二层 分组进行交换。在m p l s 网络中，从p 分组到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 ) 的映射在l e r 上处理，l e r 为输入的数据包生成一个固定长度标签，将此标签打 在数据分组头部。m p l s 在引入了标签机制后，将选路和转发分开，标签表示了一 个数据分组通过网络的路径。 i p m p l s e t h e r n e t f r a m er e l a y ! a t m ：p p p ! e t c 物理层 图1 1m p l s 协议体系 图1 - 2m p l s 网络结构 m p l s 网络由中间的标签交换路由器l s r 和网络边缘的标签入口路由器l e r 组成。l s r 可以看作是a t m 交换机与传统路由器的结合，有两部分组成：控制单 元和交换单元；l e r 用来分析上层数据包头，用于决定对应的传输级别和标签交 换路径( l a b e ls w i t c h e dp a t h ) 。m p l s 网络如图1 2 所示。 1 1 2 工作原理 当数据包进入m p l s 网络的l e r 时，通过路由表查询后分配到相应的转发等 价类中，并且用固定长度的l a b e l 对该转发等价类标识和编码，同时将此标签添加 到数据包头部( 包格式如图1 3 所示) ，所以当此数据包进入网络后，数据包信息 不会再被后续l s r 进行索引路由操作。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 s r 出口 2 第一章绪论 端使用新的l a b e l 替换原来的l a b e l 。这样携带着新l a b e l 的数据沿着l s p 向下一 个l s r 节点转发，直到目的l e r 。图1 4 演示了数据包在m p l s 网络中转发过程。 m p l s 协议中的l a b e l 只具有本地意义，用于标识一个f e c 具体编码和封装方 式，可以参考m p l s 的l a b e l 封装草案【4 】，在草案中对逐跳的数据包转发机制做了 图1 - 3m p l s 数据包封装格式 l a b e l ：一个固定长度的m p l s 标签 e x p ：实验使用，目前作为i p q o s 的映射 p s ：堆栈指示 t 】飞：生存时间 详细说明，包括数据包如何选择下一跳，如何在l s r 中完成l a b e l 分配、转发和 替换操作。一般情况下，l s p 建立在基于标准d 路由协议上，比如，开放最短路 径优先协议( o s p f 5 1 ，o p e ns h o r t e s tp a t hf i r s t ) 。除此之外，m p l s 还可以为l e r 的l a b e l 映射方式提供多种算法，充分体现了其路由技术的灵活性。 图1 - 4m p l s 标签交换过程 m p l s 框架结构和a t m 有许多相似之处。m p l s 网络功能可以抽象为两个平 面：1 ) 控制平面，包括m p l s 信令l d p 6 】( l a b e ld i s t r i b u t i o np r o t o c 0 1 ) 和路由， 负责整个l s p 的建立，拆除、保护、重新建立和重路由，是整个m p l s 的核心。 2 ) 数据平面，负责数据的封装数据以及转发，更多地与各数据链路层媒介的配合。 因为m p l s 不是一个独立的网络，只是处于两个网络中间的一种技术，所以没有 管理平面。 3 电子科技大学硕士学位论文 m p l s 技术与其他技术相比较有如下突出特点： 1 ) 支持显式路由 显式路由和口源路由技术非常相似，但是其中又存在差异。口源路由技术要 求传输的口数据包头部携带整个路径的口地址，这种方式将导致网络传输开销呈 几何数增大，因而难在实际应用中发挥作用。m p l s 网络中只在建立某条l s p 时 才要求在标签分发协议的数据包中携带路径信息；而在具体传输每个数据包时只 需要添加所分配的标签，数据包将根据建立好的l s p 发往目的节点，这样网络开 销将变小，传输速度变快，所以显式路由技术被m p l s 网络广泛使用。 2 ) 可扩展性 当前很多网络采用i po v e r a t m f r 重叠模式组网模式。这种方式不管是对路 由协议的影响，还是对管理大量虚拟电路时所造成的负担，都存在一定局限性。 m p l s 网络中，标签分配协议仅仅在相邻l s r 的对等实体之间通信，每个l s r 都 可以通过网络层拓扑来计算出相应的l s p ，这样有效地解决了在重叠网络中因为 全连接网带来的n 2 条逻辑链路问题。 3 ) 与l i n k 无关 m p l s 可以方便地实现多种协议统一。m p l s 技术不但支持多种网络层的技术， 而且和下层具体l i i l k 技术没有密切关系，可以兼容x 2 5 、f r 、a t m 、点到点协 议、s d h 、d w d m 等。这样，m p l s 平台将不同的网络传输技术统一起来。 4 ) 方便实现流量工程 在传统基于跳到跳的口网络中，当口数据包选择一个路径后，无论路径上的 l i n k 是否拥塞，p 数据包都将沿着固定l i n k 传输，这将导致网络中某些资源过度 使用，而另一些资源被闲置，网络整体效率下降。在m p l s 网络中，预先建立的 l s p 可以控制数据包在网络中传送的路径，预防数据包的盲目行为，到达避免热 点l i n k 和节点，实现网络资源合理使用。 1 2 流量工程概述 1 2 1 基本介绍 因特网正在经历巨大转变，从点到点的“尽力而为业务转向支持多种业务网 络，同时带来巨大流量增加。由于网络硬件的迅速发展，近年来因特网添加物理 4 第一章绪论 设备( 快速交换和路由设备，以及高容量链路) 费用一直在下降。因此，网络服 务提供商可以通过部署高速大容量链路来满足流量增加，但是当前这种策略只适 用于核心网络，同时带来成本增加。全球因特网流量增加仅通过这种方式已不能 满足需求。通过对网络流量的测量可以知道，瓶颈链路不仅存在于域内，而且也 存在域间，所以网络服务提供商应该采取有效措施对域内和域间资源进行统一优 化来消除瓶颈链路。在文献【7 】中流量工程的定义：处理大规模网络口性能评估和 优化的工程。在文献 8 中对流量工程更直接地解释为：“将流量放在带宽可用处”。 因此，流量工程的本质是：一种有效地路由优化方法来加强网络服务能力而不会 造成网络拥塞。 图1 5 说明了一个简单的t e 例子。每条链路的容量为1 0 m b p s ，有三个流从a 节点灌入，目的节点为c 。如果应用传统的最短路径路由方法，那么所有的流量都 将从a _ c 流过，因此导致此链路上的利用率到达1 8 0 ( 6 3 1 0 ) 。如果三个流量 如图1 5 b 所示那样流经不同的链路，流量将会均分到网络中而不至于造成链路拥 塞。从这个例子可以看出使用流量工程将路径优化后的结果比原来最短路径的方 法大大提高了网络的服务能力。 当前流量工程主要从两方面研究：1 ) 用t e 方式保证q o s 。现在很多业务不仅 对带宽有需求，而且对端到端延时、抖动和丢包率都有相应的要求。这些q o s 需 求迫使i s p 通过流量工程来满足。2 ) 用t e 实现容错机制。由于因特网上链路或 节点常常发生错误，流量工程应该保障当网络发生故障时，最小化网络错误所引 起的性能变坏。 弋 一6 m l g s 一一：i p ，j r 嗡酗讹 b ed b ed 图1 - 5 流量工程实例 a ) - - 个业务使用相同的路径，造成链路过载。 b ) 通过t e 方法，将三个业务导向不同的路径，到达网络负载均衡。 5 弋一彳 电子科技大学硕士学位论文 1 2 2 流量工程分类 根据研究和应用的需求，本文将流量工程路可以系统如下分类。这里从以下 几个方面来分类t e ，分别进行归纳总结。如图1 - 6 所示流量工程的分类体系。 1 ) 从优化业务量的范围划分：域内t e 和域问t e 。 2 ) 从路由实现机制上划分：基于p 的t e 和基于m p l s 的t e 。 3 ) 从时间和流量变化情况划分：在线t e 和离线t e 。 4 ) 从流量类型上划分：单播t e 和多播t e 。 图1 - 6 流量工程分类体系 1 2 2 1 域内和域间的t e 域内t e 目标：在一个a s ( a u t o n o m o u ss y s t e m ) 内的边界路由器之间优化流量路由， 使得a s 域内网络性能最优。 域间t e 目标：如何最优的选择i n g r e s s 和e g r e s s 节点以使域间的流量穿过本地a s 。 如果业务量可以有多个边界路由器进入或者离开本地a s ，域间t e 目标：“在本地a s 内哪个边界路由器将被用来作为路由流量的入口 和出口节点，以优化网络资源的利用率”。 1 01 01 0l 图1 7 域内域间流量工程 图1 7 举例说明了域内和域间流量工程的差异。域内流量工程仅仅考虑节点对 间的路径优化问题，例如，流量如何在1 0 1 0 1 0 3 和l o 1 0 1 0 1 间的a 、b 两条路 6 第一章绪论 径上分流：域间流量工程关注边界路由器的选择。例如，流向自治域a s 2 0 0 的流 量，如何选择1 0 1 0 1 0 1 和1 0 1 0 1 0 2 这两个边缘出口路由器。 1 2 2 2 基于m p l s 和口的t e m p l s 流量工程概念首先是在m p l s 网络中提出。通过智能地建立起l s p 路 径，m p l s 网络可以提供有效的流量优化。 优点：显式路由，流量在l s p 上可以任意分配，路由和转发机制非常灵活。 缺点：与口相比可扩展性( s c a l a b i l i t y ) 和鲁棒性( r o b u s t n e s s ) 不好。 原因：流量必须流经专门建好的l s p 路径。 1 ) l s p 总数的最大复杂度o ( n 2 ) ，意味着在大型网络中的建路成本高。 2 ) m p l s t e 中需要路径保护机制，工作路径如果出错，流量不会自动的 切换到其他路径上。 口流量工程：首先由f o r t z 9 提出。基本思想：根据网络拓扑和业务量需求来改 变路由协议中用到的链路权重，以使域内流量满足目标。不像在m p l s 可以使用 显式路由，口网络只能通过改变路由协议的链路权重来影响流量的整体路由方式。 缺点：分流不灵活，存在多路径时只能等分流，不支持显式路由和任意分流。 优点：可扩展性和容错性好。 原因：1 ) 不需要建立l s p ，避免路径开销。 2 ) 一旦路径或者链路有错误发生，口包可以通过其他最短路径自动转 发，不需要提供明确的备份路径。 1 2 2 3 离线和在线的t e 分类标准：业务量矩阵( t m ，t r a f f i cm a t r i x ) 类型和对业务操作时间。 l ：离线流量工程：i s p 在路由优化之前预测t m 。 当前预测t m 的两种方法：1 ) 根据预先协商的服务级别 s e r v i c el e v e ls p e c i 6 c a t i o n ( s l s ) 。 2 ) 周期性监控测试网络。 图1 8 说明了离线t e 的模块： 离线流量工程中资源分配周期r p c ( r e s o u r c ep r o v i s i o n i n gc y d e ) 一般情况下 可能是一天、一周、一月，主要依据用户签订、修改、终止s l s 。 缺点：网络或者流量发生变化时缺乏实时自适应性，例如，流量b u r s t 或者链 路发生错误等，这些不可预知的事件可能导致离线t e 性能变差。 7 电子科技大学硕士学位论文 s l s e s o 1 h 衢c f o r e c a s t 匠 o !竺里竺! ! 竺! ! 竺竺n 图1 8 离线t e 功能模块 2 ：在线流量工程：i s p 不需要预测t m ，对流量的变化做出快速反应，在线t e 一般几小时甚至几分钟就执行一次重新分配资源动作。 关键技术：在没有人为干预的情况下，如何保证收敛。 优化目标：实时优化使当前网络性能最优，同时保证网络未来可以接受更多的 未知流量而不会出现较大的拥塞。 做法：1 ) 尽量合理分配流量，保证未来随机进入的流量可以满足需求。 2 ) 在某些情况下，为了到达全网性能最优，如果新进入的流量需要， 为已存在的流量重新找路。但是这样带来的问题：如果涉及大规模的 流量重路由，这些竞争资源的流量将导致网络服务质量的瞬时下降。 存在问题t 由于t m 不确定，在线t e 基于当前网络状态对未来流的处理存在 大量不确定因素。 改进方法：将在线和离线t e 结合，互取长度。离线t e 给出总体趋势指导， 在线t e 在此基础上动态调整。 1 3 历史和研究应用现状 目前，多协议标签交换框架和基本概念已经形成，同时也得到越来越多人的认 同，通信设备制造商也已经研发制造出多种m p l s 设备。m p l s 技术被认为是未 来三网合一的关键，是口网络从“无连接”到“有连接”的过渡。美国许多互联网服 务供应商在其网络中使用m p l s 技术，在中国一些大型i s p 也已建立了m p l s 宽 带互联网，这些将为大规模实施和应用m p l s 网络提供广阔前景。 1 3 1 发展历史 9 0 年代，路由器技术发展远远落后于网络发展的速度和规模，转发效率底下， 不能提高q o s 保证。因为当时路由器查找算法使用最长匹配原则，必须使用软件 l“i-瓜一警 卜l口型山 第一章绪论 查找。a t m 技术摒弃了繁琐的路由查找，改为简单的快速的标签交换，将具有全 局意义的路由表改为只有本地意义的标签表，但是信令过于复杂，无法与p 很好 融合以及在局域网中的劣势表现导致只能做碑的链路层使用，局限性大。为了实 现快速交换并且兼容原有技术，1 9 9 6 年i p s i l o n 公司提出了一种专门在a t m 网上 传输口分组的技术：i ps w i t c h i n g ；思科公司将其发展成不仅仅局限于a t m 网络 的技术，命名：l a b e ls w i t c h i n g 。1 9 9 7 年i e t f 成立m p l s 小组。 1 3 2 研究现状 从i e t f 有关m p l s 的草案和r f c 可以知道，现在m p l s 已经完成了体系搭 建，正在完善相关的组播、q o s 、第二层v p n 、t e 等子课题。 i e t fm p l s 工作组围绕m p l s t e 制定了相应的规范，主要内容有m p l s t e 的两种信令协议资源预留协议( r s ，) 和受限路由标记分发协议( c r u ) p ) 的消息说明、实施方法和规范等，以及对内部网关协议o s p f i s i s 的扩展，以适 应于m p l s t e 。 b e l l 实验室集中研究m p l s 流量工程显式路由算法，这是实施m p l s 流量 工程的关键，y u f e iw a n g 等人提出了使用启发式算法【lo 】解决流量工程中的显式路 由的方法，用数学优化方法解决选路问题。该问题可以描述为：按照流量工程的 要求，使全网链路的最大利用率最低( 即流量工程要求的链路消耗最低) ，这即为 优化问题的目标函数；同时，保证所有链路的带宽均满足其上的流量要求，即没 有物理链路过载，这是优化问题的约束条件。算法的难点在于解决所谓“分歧问 题刀，即入口结点必须分割流量到多个显式路由，按照流量工程的要求，显然希望 每个入口结点仅有一条显式路由符合约束条件，因此需要将之转化为“无分歧问 题”。“无分歧问题”是n p h a r d 的，可以使用启发算法求解，但该算法的实现比较 复杂，需要进行性能优化。 j u n i p e r 公司提出解决m p l s t e 的体系模型、各层之间定义接口，该模型