（通信与信息系统专业论文）mplste中基于扩展igp的最小干扰路由算法研究.pdf

l ? 1 i | | i | | | f i | i f | i i f | 舢| f f l f f f | f | | | y 18 4 4 2 2 9 at h e s i sf o rt h ed e g r e eo fm a s t e ri nt e l e c o m m u n i c a t i o n sa n di n f o r m a t i o n s y s t e m s r e s e a r c ho nm i n i m u mi n t e r f e r e n c er o u t i n g a l g o r i t h m b a s e do ne x t e n d e di g pi nm p l st e n e t w o r k s b yh u a n g j u n s u p e r v i s o r ：a s s o c i a t ep r o f e s s o r d ul i n o r t h e a s t e r nu n i v e r s i t y j a n u a r y 2 0 0 8 l 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示 谢意。 学位论文作者签名： 璜缆 e l 期：? 癜，z 乡秒 ， 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名：童使 签字日期： 导师签名： 签字日期： l i 东北大学硕士论文 摘要 m p l st e 中基于扩展i g p 的最小干扰路由算法研究 摘要 互联网为世界带来了革命性的变化，但新兴的语音、视频等多媒体业务对网络提 出了更高的要求。仅仅依靠添加网络设备，增大网络容量的方式是难以满足需求的。 因此，在增加网络资源的同时更需要改进当前的网络传输技术。m p l s 技术是基于网 络发展的需求以及众多成熟技术的使用经验而提出的，它将第二层与第三层紧密结合 到一起，充分发挥了第二层交换和流量管理上的优势，同时兼具第三层路由、寻径灵 活的优势。 由于口流量缺乏可预见性和可管理性，因而对于运营商而言，在现有基础上控制 好占8 0 以上的业务流是至关重要的。为此网络中的流量工程( t r a f f i ce n g i n e e r i n g ， t e ) 从提出之日起就倍受研究学者们的重视，它的实施可以直接用于缓解网络拥塞和 对网络资源的合理分配。此外，它也可以间接实现网络的q o s 保证。本文正是围绕流 量工程技术而展开，结合已有路径计算算法研究了m p l s 在流量工程上的优势，以及 m p l st e 在提高网络性能和解决q o s 保证问题方面所做出的贡献。 通过仔细分析最小干扰路由算法( m i r a ) 及以利用流量特征信息、增加准入控制和 关键链路重新定位为分类的各种改进型最小干扰方案，本文提出了一种新的最小干扰 选路算法n m i r a 。该算法分为离线和在线两个阶段：离线优化预分配，即利用优 化式对网络进行计算，根据不同级别对链路预分配带宽，为在线阶段建立可选路径库； 在线动态路由选路，即采用接纳控制机制避免业务请求的莽撞接入，利用最短最窄选 路方法定位多条关键链路，并根据链路上各业务类型的已用与可用带宽比值来计算链 路权重，对所选路径进行跳数约束，旨在实现最小干扰目的的同时降低算法的复杂度。 仿真结果表明，n m i r a 算法通过合理选路能够将业务流分担到不同路径上，有效地 避免了网络拥塞，并在请求拒绝率和总的可用带宽方面的性能明显优于m h a 和c s p f 算法。 关键词：多协议标记交换；流量工程；基于约束的路由；显示路由 i l - 东北大学硕士学位论文 a b st r & c t r e s e a r c ho nm i n i m u mi n t e r f e r e n c er o u t i n g a l g o r i t h m b a s e d0 1 1 e x t e n d e di g pi nm p l st en e t w o r k s a bs t r a c t i n t e r n e tb r i n g st h er e v o l u t i o n a r yc h a n g ef o rt h ew o r l d ，h o w e v e rt h em u l t i m e d i as e r v i c e s u c ha st h er i s i n gv o i c ea n dv i d e oc a l lf o rm o r ed e m a n d i t sh a r dt om e e tt h en e e dj u s tb y e q u i p p i n gm o r ei n f r a s t r u c t u r e st oe x t e n dt h ec a p a c i t yo ft h en e t w o r k h e n c e ，i t sm o r e i m p o r t a n tt oi m p r o v et h ec u r r e n tt r a n s m i s s i o nt e c h n o l o g yw h i l ea d d i n gt h en e t w o r k s o u r 。e m il si sp r o p o s e db a s e do nt h ed e m a n df o rn e t w o r kd e v e l o p m e n ta sw e l la st h e a p p l i c a t i o ne x p e r i e n c eo fm a n ym a t u r et e c h n o l o g i e s i tc o m b i n e st h es e c o n dl a y e rw i t ht h e t h i r dl a y e rt o g e t h e r , w h i c hm a k e sf u l lu s eo ft h ea d v a n t a g eo ft h es w i t c hf u n c t i o na n dt r a f f i c m a n a g e m e n to ft h es e c o n dl a y e rw h i l em a k i n gt h er o u t i n gf u n c t i o no ft h et h i r dl a y e rg e tf u l l p l a y s i n c ei pi sl a c ko fp r e d i c t a b i l i t ya n da d m i n i s t r a b l e ，i ti si m p o r t a n tt oc o n t r o lo v c t 舳 t r a f f i co i lt h ec u r r e n tf o u n d a t i o nf o rt h en e t w o r ko p e r a t o r s f r o mt h ep r o p o s e dd a t e ，t r a f f i c e n g i n e e r i n ga t t r a c t sm u c ha t t e n t i o nf r o mt h ea c a d e m i ci n d u s t r ys i n c ei tc a na l l e v i a t et h en e t c o n g e s t i o nd i r e c t l ya n dd i s t r i b u t et h en e t w o r kr e s o u r c er e a s o n a b l y i na d d i t i o n ，i tc a ne u s u r e t h eo o si n d i r e c t l y t h ep a p e rs t a r t e da r o u n dt r a f f i ce n g i n e e r i n gt e c h n o l o g yw h i l ei t r e s e a r c h e do nt h ea d v a n t a g e si nm p l st r a f f i ce n g i n e e r i n ga n ds t u d i e dm p l st em a k e c o n t r i b u t i o nt oi m p r o v i n gt h en e tp e r f o r m a n c ea n ds o l v i n go o sg u a r a n t e ec o m b i n i n g e x i s t i n gm u t i n ga l g o r i t h m an e wm i n i m u mi n t e r f e r e n c er o u t i n ga l g o r i t h mn m i r aw a sp r e s e n t e dv i ac a r e f u l l y a n a l y z i n gm i n i m u mi n t e r f e r e n c er o u t i n ga l g o r i t h m( m 姒)a n di t sc u r r e n ti m p r o v e d 妣m e sw h i c hw e l cc l a s s i f i e da su t i l i z i n gt r a f f i cp r o f i l ei n f o r m a t i o n , a d d i n ga d m i s s i o n c o n t r o la n dr e c o n f i r m i n gc r i t i c a ll i n k s t h i sa l g o r i t h mw a sc o m p o s e do fo f f - l i n ep h a s ea n d o n l i n ep h a s e t h ef o r m e ro p t i m i z e st h ep r e - d i s t r i b u t i o n t h a ti st os a y , i to p t i m i z e st h e n e t w o r ku s i n gt h eo p t i m i z a t i o nf o r m u l a sa n dr e a l i z e sp r e - d i s t r i b u t e db a n d w i d t ha c c o r d i n g t ot h ed i f f e r e n tl e v e l s ，t h e nb u i l d st h es e l e c t a b l el i n k ss e tf o ro n l i n er o u t i n gp h a s e t h el a t t e r r e a l i z e sd y n a m i cr o u t i n g , n a m e l y , t h eo n - l i n er o u t i n gp h a s ea d o p t sa na d m i s s i o nc o n t r o l m e c h a n i s ma n du t i l i z e ss h o r t e s t n a r r o w e s tr o u t i n gm e t h o dt og ot oaf e wc r i t i c a ll i n k s i t c o m p u t e sl i n k sw e i g h tb a s e do nt h er a t i oo fu s e da n du s a b l eb a n d w i d t hf o ra l lt y p e so f t r a f f i ci no r d e rt ol o w e rt h ea l g o r i t h mc o m p l e x i t ya n da c h i e v et h ep u r p o s eo fm i n i m u m 1 h 东北大学硕士学位论文a b s t f a c t i n t e r f e r e n c ea tt h es a m et i m e s i m u l a t i o nr e s u l t sh a v ei n d i c a t e dt h a tt h en m i r a p e r f o r m e d b e t t e rt h a nt h et r a d i t i o n a la l g o r i t h m ss u c ha sm h a , c s p fe t ci na s p e c t so fn e t w o r k r e q u e s t r e j e c t i o nr a t i oa n dt h et o t a lu s a b l eb a n d w i d t hv i aa d o p t m gr e a s o n a b l er o u t i n ga n ds h a r i n g k e yw o r d s ：m 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 ；e x p l i c i tr o u t i n g 东北大学硕士学位论文 目录 独创性声明 摘要 目一录 一 m 簧；章绪论。1 1 1 课题的研究背景1 1 2 国内外相关技术发展现状2 1 3 论文的组织结构3 第二章流量工程及其m p l s 技术5 2 1 流量工程5 2 1 1 流量工程的目标5 2 1 2 流量工程的发展历史6 2 2m p l s 技术及其流量工程7 2 2 1m p l s 产生背景7 2 2 2m p l s 技术。9 2 2 3m p l s 实现流量工程的优势1 3 2 3 习区章卅卜结1 4 第三章m p l st e 体系及流量工程算法研充。1 5 3 1m p l st e 的体系结构。1 5 3 1 1 路径计算模块1 6 3 1 2 信息发布模块1 7 3 1 3 信令模块1 7 3 1 4 分组转发模块2 0 3 2 流量工程典型算法分析和研究2 2 3 2 1 流量工程选路算法要求2 2 3 2 2p b r 算法2 2 3 2 3m p l s 网络中基于约束的多径流量工程方案。2 3 3 2 4 其它算法间的特征比较2 3 3 3 本章小结一2 4 第四章最小千扰算法研究与改进。一。2 5 4 1 最小干扰算法一2 5 4 1 1 最小干扰算法思想与设计2 5 v 东北大学硕士学位论文 目录 4 1 2 各类改进算法分析2 6 4 2n m i r a 算法的提出2 9 4 2 1 网络模型 4 2 2n m i k a 算法思想3 0 4 2 3 离线算法3 2 东北大学硕士学位论文第一章绪论 1 1 课题的研究背景 第一章绪论 随着时间的推移，计算机网络得到了飞速的发展。从孤立的主机到局域网络、到 当前全球范围的i n t e r a c t 网为我们提供了丰富的资源互联网已成为我们生活中不可 缺少的组成部分。传统网络在用户数量和业务类型上都相对较少，但随着网络的极大 发展以及各种新兴媒体的出现，目前的网络已经难以满足大众的需求。这样就引起了 一个问题：一方面是用户要求网络能够提供高质量的端到端服务；另一方面是网络资 源总量相对有限，网络瓶颈闯题仍然存在新兴的语音、视频、网络游戏等媒体更是 在带宽、延迟、抖动方面对网络有苛刻的要求。依靠当前。尽力而为一( b e s t 。e f f o r t ) 的 网络服务难以满足服务质量( q u a l i t yo fs e r v i c e ，o o s ) t l l 保证的需求。 为了满足q o s 及目前网络面临的问题可以从两个方面进行考虑：一是增大网络的 容量；二是进行网络资源的合理调配。前者不能在根本上解决问题，而且它属于粗放 性投入，容易造成浪费；后者则在网络资源相对有限的情况下有效地利用了网络资源， 保证了o o 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 f z , z i 技术为o o s 保证提供了可能。同时，它也是下一代网络( n e x tg e n e r a t i o nn e t w o r k , n g n ) t 4 z 的核心技术。 早期的流量工程只是通过简单地设置链路度量值来实现的，这种方式在网络规模 比较小的情况下能够应付但随着网络规模的不断增大，所承载的业务流不断增多， 仅仅依靠设置链路度量是难以满足要求的，甚至由于所设度量值的不合理导致网络的 不稳定。为了克服上述问题，人们引入了a t m 技术，利用a t m 面向连接的特性，在 骨干网上实施流量工程。基于a t m 核心的网络采用了i p - o v e r - a t m 的覆盖模式，即 在a t m 网络上运行口网，路由器在a t m 网络的边缘环绕，每个路由器通过一系列 经由a t m 网络中配置的永久虚电路( p v c ) 与其他路由器进行通信。 引入的a t m 技术在缓解网络配置不合理的同时也暴露出了其不足之处。由于 i p - o v e r - a t m 涉及两个网络之间的交互，这不仅增加了网络的复杂性，而且需要进行 信元转换，增加了额外的开销，造成资源的浪费。随着核心路由器的发展，a t m 骨干 网络将逐步被更高性能的路由器所取代。因此，如何在今后的口网络中实行流量工程 l 东北大学硕士学位论文第一章绪论 也成了i s p 面临的重要问题之一。 m p l s 的出现为解决这个问题提供了可能。m p l s 技术是当前最为看好的高速骨 干网络技术，它融合了交换技术和路由技术的优点，是第二层和第三层技术的集成。 m p l s 通过一个固定长度的标记进行转发处理，优于传统口网中的路由转发机制。同 时，m p l s 中引入了显示路由( e x p l i c i tr o u t i n g ，e r ) 技术，通过网络管理员配置、路由 算法计算设置得到显示路径。利用显示路径可以将“繁忙 链路上的业务流转移到“空 闲 链路上来，实现负载的均衡，达到了流量工程的目的。 1 2 国内外相关技术发展现状 近年来，对流量工程框架和算法的研究主要集中在o s p f 、i s i s 和m p l s 这三个 协议上1 5 6 1 。o s p f 和l s i s 是目前网络中使用最为广泛的两种内部网关协议，正t f 也 针对以上两种协议实现流量工程进行了扩展。o s p f i s i 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 流量工程的一些草案和标准。参照这些标准，国内外针对 m p l s 流量工程的研究也在逐渐增多。目前，对m p l s 流量工程的研究主要集中在优 化算法的研究上。最宽最短路径( w s p , w i d e s t s h o r t e dp a t l l ) 算法【7 1 、最短最宽路径( s w p , s h o r t e s t w i d e s tp a t l l ) 算法1 7 l 通过在高带宽和最短路径之间作出优选，性能上优于最小 跳数( m i - i a ，m i n , h o p g o r i t h m ) 算法，但它们都容易造成部分链路拥塞而空闲资源应 用不充分。基于度量的算法1 8 ，9 j ，文献【8 】中所介绍算法本质上是从最短路径算法改进而 来，不同之处在于增加了带宽约束、资源颜色和跳数约束，从而改善负载的不均衡， 提高网络的吞吐量；文献【9 】中的算法引入了代价函数，该算法提出将时延、丢包率和 带宽建立反比关系，费用与带宽建立正比关系，用跳数反映资源的占用情况，即同样 的数据流穿过的跳数越多其资源消耗就越大。综合根据l s p 的跳数和时延进行流量分 配来达到流量转移的目的，在一定程度上避免了网络拥塞，但这两种算法都没有考虑 q o s 保证问题。最小干扰路由算法( m i r a , m i n i m u mi n t e r f e r e n c er o u t i n ga l g o r i t h m ) 算 法【加】则以最大化所有节点对之间最小的最大流为目标，降低网络的请求拒绝率，但 m i r a 存在将关键链路定位于单个源、目的节点对和计算复杂度高等缺点。这些算法 在特定的环境下实现了流量工程的需要，但仍有值得改进的地方。根据网络q o s 保证 2 东北大学硕士学位论文第一章绪论 的要求，出现了多约束问题( 加性、乘性、凹性约束问题) ，文献【1 0 】对该问题进行了分 析，解决两个或两个以上约束优化问题是一个完全n p 问题，而这些问题大部分不能 在多项式时间内获得最优解。因此，为了解决网络优化问题同时兼顾算法的实际可用 性，许多近似算法和启发式算法被提出。文中第三、四章将对部分算法进行详细研究 和对比。 1 3 论文的组织结构 论文的组织结构： 第一章绪论。对论文的研究背景和现状进行了阐述。 第二章流量工程及其m p l s 技术。详细阐述了流量工程，对流量工程的发展进 行了叙述，并从m p l s 框架结构下分析m p l st e 的优势。 第三章m p l st e 体系及流量工程算法研究。阐述了网络中的流量控制机制，研 究实现m p l st e 的主要结构，对目前已有的流量工程算法进行比较，分析其适用环 境和优缺点 第四章最小干扰算法研究与改进。叙述了最小干扰算法的基本思想，对已有改进 算法进行研究和分析，结合已有算法，改进性地提出了新的最小干扰路由选路算法。 给出网络模型并对所提出算法的离线部分和在线路由部分进行详细描述。 第五章n m i r a 算法仿真及结果分析。介绍了优化工具l i n d o 和网络仿真软件 n s 2 ，对仿真软件进行扩展以实现所提出的算法，建立网络环境、进行仿真实验得出 仿真数据并进行分析。 结束语对全文工作进行了总结，并对今后的研究工作进行了展望。 3 东北大学硕士学位论文 第一章绪论 东北大学硕士学位论文第二章流量工程及其m p l s 技术 第二章流量工程及其m p l s 技术 2 1 流量工程 2 1 1 流量工程的目标 流量工程( t r a f f i ce n g i n e e r i n g ) 1 1 d 3 】是一个与网络运营商密切相关的技术。它主要涉 及网络性能评价和性能优化，通过对网络中所含业务的测量、统计、建模和控制来达 到优化的目的。流量工程可以定义为是一种能将业务流映射到实际物理通路上，同时 又可以自动优化网络资源以实现特定应用程序服务性能要求的、具有宏观调节和微观 控制能力的网络工程技术。通过t e 的应用，达到高效智能化应用网络资源的目的和 灵活的对网络服务需求变化响应的能力就目前流量工程的应用而言，它主要包括两 个关键点，负载均衡与网络恢复。口流量工程的应用目的就是要解决如何有效实现尽 力而为的传统口服务与q d s 的统一。 从本质上说，流量工程是一种网络控制技术在实施流量工程的网络中包含了一 系列的网络互联设备、网络性能监测系统和网络配置管理系统。通常，这样的网络是 由以下三部分组成t 需求系统( 流量) 、约束系统( 网络互联单元) 、响应系统( 网络协议 和处理) 根据这三个部分的职能，流量工程的处理过程可以分为以下四个阶段，如图 2 1 所示。 是 扩充容量 配置控制 图2 1 流量工程处理模型 h g 2 1p r o c e s s i n gm o d e lo f t e ( 1 ) 第一阶段将控制策略模型化。控制策略的制定依赖于网络环境、代价结构、 - 5 - 东北大学硕士学位论文 第二章流量r t t j t 其m p l s 技术 运行约束条件、收益模型等。 ( 2 ) 第二阶段通过一系列的监测系统观测网络状态，根据结果做出反馈。处理过 程包括数据转化、数据传输等。 ( 3 ) 第三阶段是流量工程实现的重要部分，对业务流进行定性描述，并对网络状 态进行分析。找出影响网络性能的瓶颈和症结所在，利用该结果对网络进行性能优化、 运行控制以及网络的设计和容量的规划。 ( 4 ) 第四阶段网络性能优化处理。优化过程通过控制行为完成，使网络达到控制 策略所预期的状态。控制行为包括调整与资源相关的属性和约束条件、调整流量管理 参数和与路由有关的参数等。 流量工程应该是一个自动优化的过程，所以尽可能地减少人为干预，通过上述四 个阶段反复运行来达到网络性能的优化。 2 1 2 流量工程的发展历史 在早期，i s p 为了满足用户的需求，首先要建立大量互联的物理网络，然后再将 用户的数据映射到物理网络中。这些过程都是根据i g p 和e g p 路由协议来实现的， 但它们往往造成数据流的拥塞。在规模较小的网络中通过管理员手动配置相关参数可 以实现分流以及局部的负载均衡。但随着网络规模的进一步扩大和客户的要求增多， 人为管理难以实现流量工程的需求。因此，i s p 必须寻找一种方法来解决如何提供有 效的网络服务。 当前，可以较好地解决由于i g p 不完备所引起的问题的方法是使用重叠模型，例 如基于a t m 的m 。重叠模型根据底层提供的实际物理拓扑进行任意的虚拟拓扑延伸。 虚拟拓扑通过虚电路( v m u a tc i r c u i t , v q 构建而来，这些虚电路对i g p 路由协议来说， 表现与真实的物理链路一样。此外，重叠模型还提供了一些其他重要的服务，以支持 面向业务和面向资源的控制。主要有： 在v c 级上基于约束的路由 支持显示v c 通路的管理配置 通路压缩 呼叫接纳控制功能 业务整形与流量策略功能 v c 的生存性 这些新增的功能使各种流量工程策略有可能实现。事实上，在9 0 年代中期，a t m 为i s p 提供了解决日益增长的流量负载所需带宽问题，采用a i m 可以对网络的流量 进行控制。随着网络不断的扩大化，带宽需求爆炸式的增长，a t m 的劣势也逐渐显现 6 东北大学硕士学位论文 第二章流量工程及其m p l s 技术 出来。基于a t m 的重叠模型涉及两个不同的网络：底层的基础a t m 设施和重叠在它 上的逻辑m 网。重叠的网络模型增加了网络管理的复杂性，而不同网络间的交互存在 协同性问题另外，a t m 接口与新的光纤带宽的增长不能保持一致，这使得a t m 路 由器高速接口商业化十分困难鉴于以上问题以及流量工程的初衷，m p l s 作为能够 很好地解决流量工程问题的新技术被提出。 2 2m p l s 技术及其流量工程 2 2 1m p l s 产生背景 2 2 1 1 交换技术与路由技术 从电话交换到当今的数据交换、综合业务数字交换，交换技术经历了人工交换到 自动交换的过程。从交换技术的发展史中可以看到数据交换经历了电路交换、报文 交换、分组交换等几个发展过程。 ( 1 ) 电路交换是计算机终端之间进行通信时，一方发起呼叫，独占一条物理线路 当交换机完成接续，对方收到发起端的信号，双方即可进行通信。在整个通信的过程 中双方一直占有该电路。它的特点是实时性好，时延小，交换设备成本较低。但同时 也带来了线路利用率底，电路持续时间长，不同类型终端用户不能通信等缺点因此， 它适合于信息量大、长报文，经常使用的固定用户之间的通信 ( 2 ) 报文交换将用户的报文存储在交换机的存储器中，当输出电路空闲时就把报 文发向接收交换机或终端，它以“存储转发一方式在网内传输数据报文交换的优点 是中继电路利用率高，可以多个用户同时在一条线路上传送，可实现不同速率、不同 规程的终端间互通。但它存储和转发的过程需要占用大量的交换机内存和外存资源， 同时也造成很大的传输延迟。报文交换适用于传输报文较短、实时性要求较低的网络 用户间的通信 ( 3 ) 分组交换是在_ 存储转发片基础上发展起来的。它兼有电路交换和报文交换 的优点。分组交换在传输线路上采用动态复用技术进行传输。通过将原始数据分割成 一定长度的小的数据快即分组。对每个分组进行标示后，在物理链路上采用动态复用 技术进行存储和转发，到达目的端后再去掉分组头并将各数据字段按顺序重新组装成 完整的报文。分组交换能实现高可靠性、高质量的传输，它也为不同种类的终端相互 通信提供了方便由于采用了“存储转发 的工作方式，传输过程中每个分组的传输 延时可达几百毫秒，而且在传送分组时需要占用交换机一定的资源，所以分组交换不 适合于在实时性要求高、信息量大的场合使用。 7 东北大学硕士学位论文第二章流量工程及其m p l s 技术 路由技术是一个端到端的问题，所有的数据报都带有源地址和目的地址。所有分 组都通过中间的网络设备进行独立选路，对分组的确认只在目的端进行，即分组丢失 时，它必须从初始发送者重传到最终的目的节点。路由技术其实上是有两个基本的活 动组成，即传输信息单元( 也称作数据包) 和最优路径选择。其中，数据包的传输和交 换相对较为简单和直接，而路由的确定则较为复杂一些，这个过程通常由路由协议来 完成，它主要完成如下两个工作： 网络状态信息的收集和更新。 基于所收集的信息为新的连接找到一个最优的路径。 从表2 1 中可以得出交换技术和路由技术的异同。 表2 1 交换技术和路由技术 table 2 1s w i t c h i n ga n dr o u t i n gt e c h n o l o g y 交换路由 路径在建立时建立可以在完全无连接的状态下工作 简单的表查询有复杂的路由算法 通过信令对表进行维护 路由表的维护是通过协议来完成的 没有失序的传输有可能在传输过程中出现失序 路径丢失也许连接也就丢失没有连接的丢失 比单纯的选路快会造成很大的处理延时 2 2 1 2m p l s 的出现 传统口技术的优点是有灵活的路由体系，采用非面向连接的尽力而为服务方式， 适合于非实时信息的传输，但传统的口技术对延迟、带宽等q o s 质量无法保证，也 就不能很好地满足语音、视频等实时信息的传输要求：a t m 是宽带通信网络的核心技 术，是一种面向连接的传输技术，它综合了分组交换和电路交换的优点，具有良好的 q o s 服务保证，支持语音、数据和图像通信，缺点是其连接建立信令过于复杂，路由 灵活性不高，在传输较短的一般性数据时效率不高。因此，将口和a t m 结合起来成 为了一个业界关注的方案。 在对口和a t m 融合的研究中出现了l a n e 、i p o a 、m p o a 、a r i s 、t a gs w 玎c h 等技术【2 1 ，它们在解决局部问题上有各自的优势。这些技术虽然利用了a t m 高速交换 的特性，但要么没有充分利用a t m 的q o s 特性，要么就是过于复杂和标准不完善。 例如，l a n e 和m p o a 技术都只适应于小规模网络。i p o a 在不同子网间的互联需要 使用传统的路由器，这使得吞吐量和延迟问题依然存在，此外它只限于处理a t m 上 的m 业务，只支持较小规模的网络。同时，为了支持多种数据传输承载技术和对未来 业务需求的满足，i e t f 提出了m p l s 技术。 8 东北大学硕士学位论文 第二章流量工程及其m p l $ 技术 2 2 2m p l s 技术 t-、 、，一、f 。 2 2 2 1m p l s 网络的组成 m p l s 网络中包含很多组件，主要包括： 1 标记交换路由器( l s r ) 标记交换路由器与一个通用的口交换机类似，它具有第三层转发分组和第二层交 换分组的功能。它也运行传统口路由选路协议并可以执行一个特殊控制协议来与领接 的l s r 协商f e a 标记的绑定信息。一个l s r 可以是一个传统的交换机( 如灯m ) 扩充 p 选路或升级为一个支持m p l s 的路由器。l s r 是m p l s 系统中的核心部件，m p l s 中l s r 的选路过程如下： ( 1 ) 执行标准路由传播协议，以获得网络拓扑。 ( 2 ) 为每个f e c 分配一个标记 ( 3 ) 执行l d p ，并根据从其他节点获得的标记信息建立标记信息库( u b ) ( 4 ) 后续分组获得l i b 中相应的标记，按照指定动作进行处理，沿相应的l s p 传输。 2 标记边缘路由器( l e r ) l e r 位于m p l s 网络的边缘部分，它主要完成连接m p l s 域和非m p l s 域以及不 同m p l s 域的功能。并实现对业务进行分类、分发标记( 作为出口l e r 时) 、剥去标记 等。此外，它甚至可确定业务类型，实现策略管理，接入流量工程控件等工作 3 转发等价类( 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 中将具有相同转发处理方式( 相同目的地址、相同的转发路径、具有相同的 服务级别等) 的分组归为一类，这种类别就称为转发等价类【1 4 1 。属于相同的转发等价类 的分组在m p l s 网络中将获得完全相同的处理。在标记分配过程中，各种等价类对应 于不同的标记，在m p l s 网络中，各个节点将通过分组的标记来识别分组所属的转发 等价类。转发等价类的划分方式非常灵活，可以是源地址、目的地址、源端口、目的 端口、协议类型、v p n 等的任意组合。例如在传统的采用最长匹配算法的口转发中， 到同一个目的地址的所有报文就是一个转发等价类。 4 标记 一个长度固定，只具有本地意义的标志它用于唯一的表示一分组所属的f e c ， 决定标记分组的转发方式。 图2 2 是m p l s 网络中分组头的格式，其中s h i m 即“垫片刀部分包括如下四个域t l a b e l 域：占2 0 b i t s ，携带了标记的真实值。 e x p 域：占3 b i t s ，用于实验，缺省可以设为c o s ( o a s so f s e r v i c e ) 域，提供了 9 东北大学硕士学位论文 第二章流量工程及其m p l s 技术 一种服务类型机制，可以影响分组在网络中传输时的排队和丢弃。 s 域：即栈底指示比特，占l b i t ，为1 时表明本条目为标记堆栈中最后一条， 否则其值为0 。 1 1 1 佃m et ol i v e ) 域：即生存时间，占8 b i t s ，它是分组在网络中生存时间值 的编码。 图2 2m p l s 网络中的分组头格式 f i g 2 2p a c k a g e sh e a d e rf o r m a ti nm p l sn e t w o r k s 5 标记分发协议( l o p ) 该协议是m p l s 的控制协议，负责f e c 的分类，标记的分配，以及分配结果的传 输及l s p 的建立和维护等。标记分发协议( l d p ) 是在m p l s 网络中定义的【1 5 】，专门用 于标记交换路由器( l s r ) 之间交换“标记转发等价类( f e c ) ”绑定信息以便建立和维护 标记交换路径p ) 的控制信令。 l s r 间通过l d p 会话交换的信息有如下几种： ( 1 ) 发现消息( d i s c o v e r ym e s s a g e s ) ：正在网上的l s r 周期性地用组播方式广播自 己( 以非连接的u d p 方式) 给所有连在同一子网上的其他路由器，以声明和维护它的存 在。 ( 2 ) 会话消息( s e s s i o nm e s s a g e s ) ：建立、维护和终止l d p 会话。 ( 3 ) 公布消息( a d v e r t i s e m e n tm e s s a g e s ) ：创建、改变和删除f e c 对应的标记。 ( 4 ) 通知消息( n o t i f i c a t i o nm e s s a g e s ) ：主要用于通知对等方某个事件的发生，如某 些事件发生错误、对其他消息的处理情况以及l d p 会话的状态等。 6 标记交换路径( l s p ) l s p 是指具有一个特定f e c 的分组，在传输经过的标记交换路由器集合构成的传 输通路。它由m p l s 节点建立，目的是采用一个标记交换转发机制转发一个特定的f e c 分组。 7 标记信息库( u b ) l i b 是保存在一个l s r ( l e r ) q b 的连接表，在l s r 中包含有f e c 标记绑定信息和 关联端口以及媒体的封装信息l i b 通常包括下面的内容：入、出口端口；入、出口 标记；f e c 标示符；下一跳l s r ；出口链路层封装等 8 标记合并 】0 东北大学硕士学位论文第二章流量工程及其m p l s 技术 对于某一相同f e c 的标记分组，将不同的入标记替换为同一个出标记继续转发的 过程，减少标记资源的消耗。 7 “。“ - ： 9 流( s t r e a m ) 属于同一个f e c 的一组分组流，它们流经同一个节点，从相同的通道传输，并以 相同的方式转发到目的地，它们在m p l s 网络中被称为“流束 。 1 0 上游l s r 与下游l s r 一个分组由一个路由器发往另一个路由器时，发送方的路由器为上游路由器，接 收方为下游路由器。 1 1 t l v ( t y p el e n g t hv a l u e ) 类型、长度、值，m p l s 消息中的子结构，类似于其他协议中各种消息内的对象 2 2 2 2m p l s 网络体系结构 虽然i po v e ra t m 技术在一定时期解决了网络拥塞和流量工程问题，但随着网络 的发展，它的不足之处也凸现出来为了将第二层的交换和第三层的路由技术有效结 合起来，i e t f 通过综合众多技术后建立了m p l s 标准来实现这一目的。 m p l s 引入了一种固定长度标记的面向连接的转发方式，目前主要应用于基于p 的网络。在o s i 网络七层参考模型中，m p l s 处于数据链路层和网络层之间的位置。 m p l s 首先根据某种特定的映射规则在网络入口l e r 处将数据流分组头和