（电路与系统专业论文）基于MPLS流量工程的路由算法研究[电路与系统专业优秀论文].pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 传统的i p 网络路由体系只能提供数据的可达性服务，不具备全网资源利用的调节能力。 因此容易造成网络负载分布的不平衡，极大地浪费了网络资源。流量工程是一种网络优化 和控制技术，其目标是实现网络性能的优化以及网络资源的合理利用。而多协议标记交换 ( m u l t ip r o t o c o ll a b e ls w i t c h i n g ，m p l s ) 技术运用显式的标记交换路径( l a b e ls w i t c h i n g p a t h ，l s p ) 使得互联网上流量工程的部署变得简单和高效。m p l s 流量工程中的动态路由 算法则是这一技术得以实施的关键因素。 本文首先介绍多协议标记交换技术和流量工程的一些基本概念、基本原理及体系结 构；接着通过对m p l s 流量工程的路由算法的分析与研究，以提高网络吞吐量作为流量工 程目标，在最小干扰路由算法的基础上提出了一种改进的动态路由算法。算法综合考虑了网 络拓扑和流量分布状况，引入次关键链路的概念。不但介绍了改进算法的具体实现、算法 流程，还通过在不同的网络拓扑下，利用m a t l a b 仿真实验对几个典型的性能指标( 网络 最大流和l s p 请求拒绝个数) 进行了仿真，结果显示该算法较最小干扰路由算法具有优越 性。 关键词：多协议标记交换 最小干扰路由算法 流量工程 关键链路 网络最大流 次关键链路 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t t h et r a d i t i o n a lr o u t ep r o t o c o l so ft h ei pn e t w o r kc a l lo n l yp r o v i d et h ed a t a - r e a c h a b l e s e r v i c e t h es y s t e md o e sn o th a v et h ec a p a b i l i t yi nu t i l i z i n gt h eg l o b a ln e t w o r kr e s o u r c e s a sa r e s u l t ，t h en e t w o r kl o a di sn o tb a l a n c e d ，w h i c hg r e a t l yw a s t e st h en e t w o r kr e s o u r c e s t r a f f i c e n g i n e e r i n gi sc o n c e r n e dw i t hp e r f o r m a n c eo p t i m i z a t i o na n dc o n t r o lo fo p e r a t i o n a ln e t w o r k s 。 t h em a j o rg o a lo ft r a f f i ce n g i n e e r i n gi st oo p t i m i z en e t w o r kt r a f f i cp e r f o r m a n c ew h i l e s i m u l t a n e o u s l ya c h i e v i n ge c o n o m i c r e s o u r c eu t i l i z a t i o n m u l t ip r o t o c o ll a b e ls w i t c h i n g ( m p l s ) e n a b l e st h ed e p l o y m e n to fi n t e m e tt r a f f i ce n g i n e e r i n gt ob es i m p l ea n de f f i c i e n tb y u s i n ge x p l i c i tr o u t i n go fl a b e ls w i t c h i n gp a t h a n dd y n a m i cr o u t i n ga l g o r i t h mi sav e r y i m p o r t a n tf a c t o rf o rm p l s t r a f f i ce n g i n e e r i n g i nt h i sp a p e r , w ef i r s ti n t r o d u c eb a s i cc o n c e p t i o n ，p r i n c i p l ea n da r c h i t e c t u r ea b o u tm u l t i p r o t o c o ll a b e ls w i t c h i n ga n dt r a f f i ce n g i n e e r i n g t h e nw ep r o p o s ean e wm o d i f i e dd y n a m i c r o u t i n ga l g o r i t h mb a s e do nm 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 mb ya n a l y z i n ga n d r e s e a r c h i n gm p l st r a f f i ce n g i n e e r i n gr o u t i n ga l g o r i t h m t h eo b j e c t i v eo ft ec o n s i d e r e dh e r ei s t oi n c r e a s en e t w o r kt h r o u g h p u t t h i sa p p r o a c ht a k e si n t oa c c o u n tb o t hn e t w o r kt o p o l o g ya n d t r a f f i cd i s t r i b u t i o ns t a t e ，a l s ob r i n g sf o r t ha ni d e ao fs e c o n d a r yc r i t i c a ll i n k w en o to n l y p r e s e n tt h ed e t a i lr e a l i z a t i o na n da l g o r i t h mp r o c e d u r eo ft h em o d i f i e dr o u t i n ga l g o r i t h m ，b u t v a l i d a t et h ea d v a n t a g eo ft h i sa l g o r i t h mc o m p a r i n gw i t hm 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 mb yc a r r y i n go u tm a t l a bs i m u l a t i o ne x p e r i m e n t su n d e rd i f f e r e n tn e t w o r kt o p o l o g y a n dt h ep e r f o r m a n c eo fr o u t i n ga l g o r i t h mi sa s s e s s e dt w or e p r e s e n t a t i v ep e r f o r m a n c ec r i t e r i a ， s u c ha sn e t w o r km a x i m u mf l o wa n dr e j e c t e dl s p r e q u e s t s k e y w o r d s ：m u l t ip r o t o c o ll a b e ls w i t c h i n gt r a f f i ce n g i n e e r i n g n e t w o r km a x i m u mf l o w 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 mc r i t i c a ll i n k s e c o n d a r yc r i t i c a ll i n k 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：蓝：趟日期：盘亟：垦! 茎 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：陆、禾厶导师签名：闭k 一日期：沙哌名 南京邮电大学硕士研究生学位论文 第一章概述 1 1 课题的研究背景 第一章概述 i n t e m e t 在近些年中的爆炸性增长，为i n t e m e t 服务提供商( i n t e r n e ts e r v i c ep r o v i d e r ，i s p ) 提供了巨大的商业机会，同时也对其骨干网络提出了更高的要求。人们希望i p 网络不仅能 够提供e m a i l 、上网等服务，还能够提供宽带实时性业务。a t m 曾经是被普遍看好的能够 提供多种业务的交换技术，但是由于实际的网络中人们已经普遍采用i p 技术，现有a t m 的 使用也一般都是用来承载i p ，如此人们就希望i p 也能提供一些a t m 一样多种类型的服务。 多协议标记交换( m u l t ip r o t o c o ll a b e ls w i t c h i n g ，m p l s ) 就是在这种背景下产生的一 种技术，它处于数据链路层和网络层之间，使用2 0 位的标记引导数据沿标记交换路径( l a b e l s w i t c h i n gp a t h ，l s p ) 在网络中高速传输和交换【1 】；它吸收了a t m 的v p i v c i 交换一些思想， 无缝地集成t i p 路由技术的灵活性和二层交换的简捷性，在面向无连接的i p 网络中增加了 m p l s 这种面向连接的属性。通过建立合适的m p l s 可以实现对网络流量和资源的合理控 制，满足区分服务( c l a s so fs e r v i c e ，c o s ) 的要求，提供服务质量( q u a l i t yo fs e r v i c e ， q o s ) 的保障，实施流量工程( t r a f f i ce n g i n e e r i n g ，t e ) 。 流量工程是一种通过对网络流量的合理规划来优化网络资源，并可实现特定应用服务 性能要求的网络工程技术【2 3 】，是为了平衡网络的流量负载，根据数据流量来选择路径的过 程【4 】。它是当前计算机网络领域的热点问题之一，其目的是实现对网络中业务流的精确控 制，在满足业务流q o s 要求的前提下使网络资源尽可能合理使用，避免出现网络拥塞，同 时能够接入更多的业务，提高全网利用率，降低网络运营成本。流量工程使得i s p 能够在现 有的网络资源条件下，对它们路由域内的网络流量进行明确的控制，将新增的业务流转移 到潜在的具有更小拥塞的物理路径上，从而平衡网络中各链路、路由器或者交换机上的业 务负载。流量工程的目标是根据网络流量与资源的状态，通过实施合理地控制，使流量均 衡地分布在现有的网络中，从而优化网络的运行性能。它主要包括如何对i n t e m e t 流量进行 测量、识别、建模以及控制的研究。因为m p l s 流量工程的问题最终可以归结为数据流传 输的路径确定问题，即显式路径的确立问题，所以说针对m p l s 网络，研究流量工程动态 路由算法的约束条件和目标函数，从而建立算法的数学模型和算法规则对动态实现基于 m p l s 的流量工程具有特别重要的意义。 南京邮电大学硕士研究生学位论文第一章概述 1 2 课题的研究现状 目前，m p l s 的框架以及基本概念已经形成，并且得到了人们的认可。m p l s 被认为是 未来三网融合的关键技术之一，可以使i p 网从“无连接 向“有连接 过渡。美国的i s p 有很多在它们的网络中采用了m p l s 技术，而在国内，有些国家级的大型i s p 已经建设了基 于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 工作 组的工作重点已经从原理技术的基本实现转移到m p l s 技术的应用中来：主要是面向 m p l s 如何更有效地提供增值服务、m p l s 在局域网中的应用、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 dr o u t i n gl a b e ld i s t r i b u t i o np 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 技术的应用当前已经处于大规模商用阶段。为了发 挥m p l s 技术在实旌流量工程的优势，提出一个成熟的m p l s 流量工程模型成为国内外 许多公司和研究机构的研究目标。 在路由算法研究方面，当前主要的路由算法有最短路径优先( s h o r t e s tp a t hf i r s t ， s p f ) 算法、最宽最短路径( w i d e s ts h o r t e s tp a t h ，w s p ) 算法1 5 】、最短最宽路径( s h o r t e s t w i d e s tp a t h ，s w p ) 算法1 6 】等，但比较有影响力的是新近出现的最小干扰路由算法 ( 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 ) 【列。传统的以最短路径优先为基础的 l s p 选路算法为了实现资源的均衡利用，将网络带宽资源映射到链路权重设定中。如开放 最短路径优先算法( o p e ns h o r t e s tp a t hf i r s t ，o s p f ) 【8 】和受限最短路径优先算法 ( c o n s t r a i n t ss h o r t e s tp a t hf i r s t ，c s p f ) 【9 】分别将链路的权重定义为与链路的容量成反比或 与链路的剩余容量成反比。其中o s p f 算法引导流量使用大容量的链路，有助子负载均衡， 但随着请求的不断到来，导致大容量的链路被拥塞；c s p f 算法是优先利用负载低的链路， 但容易导致业务流选择较长的路径，带来网络资源的更多投入，从而潜在地降低网络总的 带宽接受。在上述算法中，如果每条链路的权重相同，则s p f 算法简化为最4 , g g 数算法 ( m i n i m u mh o pa l g o r i t h m ，m h a ) i t 0 】。m h a 是一种贪婪算法，所有的业务流选用最短 路径，容易引起网络中一些链路成为瓶颈链路。为了均衡网络资源并最小化资源消耗， 2 南京邮电大学硕士研究生学位论文 第一章概述 w s p 算法和s w p 算法一方面将业务流引向高带宽链路，另方面尽量降低路径长度。但 这些算法在为当前业务流选择l s p 时，都没有考虑其对将来l s p 请求的影响，都属于贪 婪算法，在优化网络资源性能上不够理想。k o d i a l a m e 7 1 提出最小干扰路由算法，它利用 m p l s 网络入出节点对信息，在为当前请求选择l s p 时，尽可能地避免干扰其它入出节 点对对将来请求的l s p 建路，从而达到优化网络整体性能的目标。m i r a 提出后，有很 多研究工作在其基础上展开，从不同的角度对其进行了改进。 1 3 课题的研究内容 本课题在研究内容上主要从以下几个方面着手： 1 研究m p l s 的产生背景、工作原理、关键技术及m p l s 的典型应用： 2 研究流量工程的基本概念、实现方式、流量工程的主要结构、在m p l s 上实现流量 工程的基本步骤和流量工程在m p l s 系统上的部署； 3 研究m p l s 流量工程的路由算法，分析现有路由算法的分类，现有路由算法的性能 和特点，重点对新近提出的最小干扰路由算法进行性能分析。然后在m i r a 的基础上提 出一种改进算法，并进行性能分析，最后通过特定网络模型进行模拟仿真比较算法优劣。 1 4 论文内容安排 论文的主要内容分为六章。第一章概述，主要探讨了课题的研究背景、研究现状和研 究内容。第二章多协议标记交换技术，首先简述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 流量 工程结构，最后总结了流量工程在m p l s 系统上的部署的基本步骤。第四章m p l s 流量 工程的路由算法研究，首先简单介绍路由算法的分类和性能指标，然后阐述了m p l s 流 量工程中的几种典型路由算法，分析了它们的优缺点，最后重点介绍最小干扰路由基本算 法的算法思想及原理。第五章一种基于m i r a 的改进算法，首先从不同层面分析现有的 基于m i r a 的改进算法，然后根据关键链路的重新定位类针对m i r a 算法不足提出- k e o 改进算法，最后将改进算法与m i r a 算法在仿真网络上进行相关性能指标的比较和分析。 第六章对总结，主要对本文所做的工作进行总结。 南京邮电大学硕士研究生学位论文 第二章 多协议标记交换技术 第二章多协议标记交换技术 2 1m p l s 的产生背景及其优势 2 1 1m p l s 的产生背景 面向连接的a t m 技术【l 】在传送实时数据时能够保证服务质量q o s ，但a t m 网络未 能取代现有的电信网络和计算机网络，这不仅是因为a t m 网络价格昂贵，用a t m 网络 来替换现有的己投资非常巨大的电信网络和计算机网络是很不现实的，而且还因为a t m 网络和上层的应用结合得很不好，相反，基于i p 的因特网与各种应用已经结合得很好。 a t m 网络必须与i p 网络相结合才有出路。因此出现了一种覆盖模型，它是一种把a t m 看成是数据链路层并在其上面运行i p 协议的方式。在具体实现时，覆盖模型又有传统 i p o a ( c l a s s i c a li po v e ra t m ) ，局域网仿真l a n e ( l a ne m u l a t i o n ) 和m p o a ( m u l t i p r o t o c o lo v e r a t m ) 等几种不同的方案。但这种覆盖模型很难协调i p 和a t m 网络的巨大 差异，这主要是因为：i p 是无连接的，而a t m 是面向连接的；i p 只提供尽最大努力交付 的服务，而a t m 能确保服务质量q o s 。 在这种情况下，i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r c e ，i n t e m e t 工程任务组) 于19 9 7 年成立了m p l s 工作组，旨在开发出一种将第三层的路由选择功能与面向连接的第二层 的交换功能综合在一起的新的协议标准，以便使i p 和a t m 结合得更好些。这种新的协议 的名称是m p l s ，它采用综合模型，能够克服上述的覆盖模型的一些缺点。i e t f 还综合 了许多公司的技术，如c i s c o 公司的标记交换t a g ( t a gs w i t c h i n g ) ，i p s i l o n 公司的i p 交换( i ps w i t c h i n g ) 等。2 0 0 1 年1 月m p l s 终于成为因特网的建议标准 r f c 3 0 3 1 , 3 0 3 2 w - m p l s 。它的特殊功能主要在于支持面向连接的服务质量、支持流量工程， 平衡网络负载、有效地支持虚拟专用网和支持多种网络协议等四个方面。 2 1 2m p l s 的优势 m p l s 的优势在于它提供了路由和转发的分离。这种分离允许只采用单一转发算法便 可对多种服务和流量类型进行配置。将来需要开发一种新的增值服务时，m p l s 转发结构 可以被保留，新的业务可通过更换包被分配到l s p 中的方法而简单地建立。 4 南京邮电大学硕士研究生学位论文 第二章多协议标记交换技术 标记交换利用a t m 交换机的硬件进行分组的高速转发。对i s p 来讲，m p l s 可在核 心网中利用a t m 交换机提供比其它网络更易扩展和管理的操作，避免了路由器对等体可 扩展性问题，还可支持分层结构的网络。与i p a t m 叠加模式中的技术相比，m p l s 具有 许多优点： 1 集成 m p l s 不是i p 和a t m 简单的叠加，而是i p 和a t m 的集成，这使得下层的a t m 结 构对i p 寻路来说是可见的，不再需要i p 和a t m 特性间的映射。m p l s 不需要a t m 的寻 址、路由技术。 2 更高的可靠性 在i p a t m 的叠加模式中，路由器之间建立了一个网状结构，这种方法不易于对路由 表的维护，扩展性差，甚至单条链路间的失效就会引起几个路由器之间的链路失效。而 m p l s 是把i p 的路由性能和a t m 的交换性能结合在一起，解决了a t m 中“r 2 ”个链路 数的问题。 3 直接的服务等级 m p l s 采用a t m 的硬件，应用a t m 排队和缓存机制来提供不同的服务等级，可把 i p 优先级和c o s 直接转换为a t m 论坛规定的服务等级。 4 v p n 的可扩展性和易处理性 v p n ( v i r t u a lp r i v a t en e t w o r k ，虚拟专用网) 服务可为企业建立专用的、基于i p 网络 的服务。在采用m p l s 结构的核心网中，v p n 信息只需在入口和出口节点处处理，数据 分组则同标记一起被传送到业务目的点。一个i p 网络可以支持成百上千个v p n 。 5 减少核心网的负荷 利用m p l s ，把i p 路由表与核心网相隔离。选路只在网络边缘进行，核心网只是根 据标记对应表进行转发，大量的关于选路的信息被屏蔽在核心网络之外。这样就不易发生 拥塞，整个网络更加健壮。 6 流量工程 流量工程可以更加有效地利用资源，均衡网络的负载。当网络拥挤时，根据传送业务 的目的地址、业务类型、业务负荷、当前时间等多个因素，把超负荷链路的业务转移到其 它较空闲的链路上。 南京邮电大学硕士研究生学位论文第二章多协议标记交换技术 2 2m p l s 中的基本概念及组件 2 2 1m p l s 中的基本概念 m p l s 常见的基本概念f 1 2 】总结如下： 1 l a b e l ( 标记) ：标记是一个短的、长度固定的、具有本地意义的标识符，用以表示 传输数据的类别。具体标记的实现是根据实现方式的不同而不同。m p l s 网络可以利用现 有的a t m 设备、帧中继设备来构建，也可以使用专门的m p l s 交换设备来实现，因此标 记也可以用不同的方式表示。标记由报文的头部携带，不包含拓扑信息，只具有局部意义。 2 多协议：指m p l s 位于传统的第二层与第三层协议之间，第三层可以支持i p v 4 、 i p v 6 、i p x 、a p p l e t a l k 等，第二层可以是a t m 、f r 、p p p 等。 3 f e c ( f o r w a r d i n ge q u i v a l e n tc l a s s ，转发等价类) ：用来标识具有相同转发处理方式 的分组，相同转发等价类的分组在m p l s 网络中将获得完全相同的处理。转发等价类的 划分方式非常灵活，可以是源地址、目的地址、源端口、目的端口、协议类型、v p n 等 的任意组合。例如，在传统的采用最长匹配算法的i p 转发中，到同一个目的地址的所有 报文就是一个转发等价类。 4 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 网络中部。 5 l e r ( l a b e le d g es w i t c h i n gr o u t e r ，标记边缘交换路由器) ：接受没有标记的数据分 组( i p 分组) ，并在入口处加入标记。l e r 在网络边缘会移除标记，发送没有标记的分组 到i p 网络的出口，是m p l s 网络同其它网络的边缘设备。 6 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 的标记以及它们之间的链路组成。 7 l d p ( l a b e ld i s t r i b u t i o np r o t o c o l ，标记分发协议) 【1 3 】：m p l s 的控制协议，负责f e c 的分类、标记的分配、分配结果的分发以及l s p 的建立和维护，主要应用于路由拓扑驱 动的l s p 建立。 8 c r l d p ( c o n s t r a i n t b a s e dr o u t i n gl a b e ld i s t r i b u t i o np r o t o c o l ，基于约束的路由标记 分发协议) 1 4 】：为基本的l d p 提供了扩展，用于支持显式路由l s p 的建立以及( 有可能) 沿建立的l s p 预留资源。 9 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 ，资源预留协议) ：这个协议最初是为综合服 6 南京邮电大学硕士研究生学位论文第二章多协议标记交换技术 务类型( i n t s e r v ) 的q o s 制定的一个信令协议，用来完成主机对特定流提出特定q o s 需 求。预留可能在企业网中或因特网上，m p l s 使用扩展的r s v p 作为信令协议来支持核心 的m p l st e e l5 1 。r s v p 在r f c2 2 0 5 和r f c3 2 0 9 进行了标准化。 1 0 l i b ( l a b e li n f o r m a t i o nb a s e ，标记信息库) ：作用类似于路由表，用来存放l s r 通过l d p 协议接收到的各种标记绑定的数据表。其中包含各个标记所对应的各种转发信 息，每个入口标记对应一个条目，包括出口标记、出口接口等信息。 11 流( s t r e a m ) ：沿着同一路径、属于同一f e c 的一组包被视为一个流。 1 2 上游和下游：上游和下游是根据s t r e a m 的流向而定的。上游是指相对于其他路由 器，靠近分组源头的一个路由器。下游是指相对于其他路由器，离分组源头较远的路由器。 当数据分组在网络中传送时，是从一个上游路由器转发到它的下游邻居路由器的。 1 3 m p l s 域：一个运行m p l s 协议的节点的邻接集合，相应于一个自治系统或一个 l s r 管理域。 1 4 m p l s 节点( m p l sn o d e ) ：一个运行m p l s 协议的节点，节点能被m p l s 控制协 议发现、邻接和对话：执行一个或多个路由协议，具有标记调换转发功能：建议具有纯 l 3 层i p 分组的处理能力。 1 5 控制平面( c o n t r o lp l a n e ) ：路由和标记等控制信息交换的逻辑平面。 1 6 数据平面转发平面( d a t ap l a n e f o r w a r d i n gp l a n e ) ：实际进行数据转发的平面。 只有控制平面建立后转发才可以执行。 1 7 标记绑定：标记和f e c ( 前缀) 之间的一种关系。分配的标记本身没有什么意义， 因此没有什么用处。接受者就是通过这种和f e c 的联系，来决定如何把某一个标记分配 给一个收到的数据分组。 m p l s 的具体含义如下【1 6 】：m p l s 是一项利用绑定在i p 包中的标记通过网络进行数 据包转发的技术。在数据帧交换模式下，标记被插入到第二层包头和第三层包头之间：在 信元交换模式下( 如a t m ) ，标记被包含在虚拟路径标识符( v p i ) 和虚拟信道标识符( v c i ) 字段之中。m p l s 把第二层交换技术和第三层路由技术结合在了一起，其主要目标是建立 一个具有更好性能更高稳当性的灵活和易于扩展的网络架构。在m p l s 上可以实施流量 工程和建立v p n ，并能通过多种服务类型来提供服务质量保证。 2 2 2m p l s 组件 在m p l s 体系结构中，控制平面采用无连接方式，它利用现有的i p 网络实现；转发 7 南京邮电大学硕士研究生学位论文第二章多协议标记交换技术 平面，也称为数据平面采用面向连接方式，它可以使用a t m 、帧中继等二层网络。m p l s 使用短而定长的标记来封装分组，在数据平面实现快速转发。在控制平面，m p l s 拥有i p 网络强大灵活的路由功能，满足各种新应用对网络的要求。 m p l s 网络由标记交换路由器l s r 、标记边缘交换路由器l e r 、标记交换路径l s p 和标记分发协议l d p 组成。了解m p l s 组件有助于理解在m p l s 和各种第二层及第三层 协议与设备之间的交互。 1 l s r l s r 是运行m p l s 的网络节点，位于m p l s 网络中部。主要运行m p l s 控制协议和 第三层路由协议，并负责与其它标记交换路由器交换路由信息来建立路由表，实现f e c 与i p 分组头的映射，建立f e c 和标记之间的绑定，分发标记绑定信息，建立和维护标记 转发表等工作。l s r 除了支持标记交换以外，还支持第三层的i p 分组逐跳式转发。 2 l e r l e r 主要完成连接m p l s 域和非m p l s 域以及不同m p l s 域的功能。并实现对业务 进行分类、分发标记、剥去标记等；甚至可确定业务类型，实现策略管理，接入流量工程 控制等工作。l e r 是实现m p l s 网络的关键功能设备之一。 3 l s p l s p 是在两个l s r 之间配置的连接，在其中使用标记交换技术进行数据包转发。一 条l s p 是穿过m p l s 网络的一条特定的流量路径。l s p 的提供是使用l d p 、带有流量工 程扩展的资源预留协议( r s v e t e ) 、基于约束的路由l d p ( c r l d p ) ，或如多协议 b g p 这样的路由选择协议的扩展。 l s p 可以被看作是属于某个f e c 的数据包为了到达它们的目的地而经过的一系列 l s r 路径。l s p 在功能上与a t m 和f r a m er e l a y 虚电路相同，是从入1 ：3 到出口的一个单 向路径。l s p 中的每个节点由l s r 组成。 4 l d p l d p 协议规定标记分发过程中的各种消息以及相关的处理进程。两个使用l d p 交换 f e c 标记绑定的l s r 称之为标记分发对等体。l d p 的主要功能是让l s r 实现f e c 与标 记的绑定，并将这种绑定通知给相邻的l s r ，以使各l s r 间对收到的标记绑定达成共识。 通过l d p ，l s r 可以把网络层的路由信息直接映射到数据链路层的交换路径上，进 而建立起网络层上的l s p 。l d p 是m p l s 网络中用以建立和维护标记绑定的协议。故l d p 信息的可靠性决定了m p l s 网络运行是否可靠。 南京邮电大学硕士研究生学位论文第二章多协议标记交换技术 2 3 m p l s 的工作原理 m p l s 的出现是源于早期的i p 交换，其目的是将目前的各种i p 路由和a t m 交换技 术兼容并蓄，以提供一种更具弹性、扩充性以及效率更高的宽带交换路由器。与标记交换、 a t m 交换等技术类似，m p l s 引入了标记的概念，在m p l s 网中数据的传输靠标记引导。 图2 1 为m p l s 网络工作原理示意图f 17 1 ，从图中可见，一个m p l s 网络的核心结构组成 为：l e r 和l s r 。通过l d p ，l e r 和l s r 、l s r 和l s r 之间完成标记信息的分发。网 络路由信息来自一些共同的路由协议，如开放最短路径优先( o p e ns h o r t e s tp a t hf i r s t ， o s p f ) 、边界网关协议( b o r d e rg a t e w a yp r o t o c o l ，b g p ) ，根据路由信息决定如何完成 交换路径l s p 的建立。当分组( i p 信包、帧中继或a t m 信元) 进入l e r 时，入口l e r 根据输入分组头查找路由表以确定通向目的地的标记交换路径l s p ，把查找到的对应l s p 的标记插入到分组头中，然后将分组输出到标记标识的路径。网络中的节点则完全根据分 组标记进行标记交换式转发，无需再查路由表。出口l e r 则将分组按一定规则转发至目 的地。 ldp 口7 丈d p 出口 l e r 口二口 田 田圈田田 图2 1m p l s 网络工作原理 m p l s 的工作流程具体可以分为几个方面，即网络的边缘行为、网络的中心行为以及 如何建立标记交换路径。 1 网络的边缘行为 当i p 数据包到达一个l e r 时，m p l s 第一次应用标记。首先，l e r 要分析i p 包头 的信息，并且按照它的目的地址和业务等级加以区分。在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 来为其生成一个标记。l i b 将每一个f e c 都映射 到l s p 下一跳的标记上。如果下一跳的链路是a t m ，则m p l s 将使用a t mv c c 里的 v c i 作为标记。转发数据包时，l e r 检查l i b 中的f e c ，然后将数据包用l s p 的标记封 装，从l i b 所规定的下一个接口发送出去。 2 网络的核心行为 当一个带有标记的包到达l s r 的时候，l s r 提取入局标记，同时以它作为索引在l i b 中查找。当l s r 找到相关信息后，取出出局的标记，并由出局标记代替入局标记，从l i b 中所描述的下一跳接口送出数据包。最后，数据包到达了m p l s 域的另一端，在这一点， l e r 剥去封装的标记，仍然按照i p 包的路由方式将数据包继续传送到目的地。 3 如何建立标记交换路径 建立l s p 的方式主要有两种： ( 1 ) “h o pb yh o p ”路由 一个h o pb yh o p 的l s p 是所有从源站点到一个特定目的站点的i p 树的一部分。对 于这些l s p ，m p l s 模仿i p 转发数据包的面向目的地的方式建立了一组树。从传统的i p 路由来看，每台沿途的路由器都要检查包的目的地址，并且选择一条合适的路径将数据 包发送出去。而m p l s 则不然，数据包虽然也沿着i p 路由所选择的同一条路径进行传送， 但是它的数据包头在整条路径上从始至终都没有被检查。在每一个节点，m p l s 生成的树 是通过一级一级为下一跳分配标记，而且是通过与它们的对等层交换标记而生成的。交换 是通过l d p 的请求以及对应的消息完成的。 ( 2 ) 显式路由 m p l s 最主要的一个优点就是它可以利用流量设计引导数据包，比如避免拥塞或者满 足业务的q o s 等。m p l s 允许网络的运行人员在源节点就确定一条显式路由的 l s p ( e r l s p ) ，以规定数据包将选择的路径。不像h o pb yh o p 的l s p ，e r l s p 不会形成 i p 树。取而代之，e r l s p 从源端到目的端建立一条直接的端到端的路径。m p l s 将显式 路由嵌入到限制路由的l d p 的信息中，从而建立这条路径。 2 4 实现m p l s 的关键技术及特点 1 v c 合并( v cm e r g i n g ) 南京邮电大学硕士研究生学位论文 第二章 多协议标记交换技术 为了使得m p l s 达到至少是二_ 个典型的路由网络的规模，合并则是其本质的特征。 如果不具备合并能力，那么必须从每个入口点到每个出口点建立l s p 1 8 】。m p l s 通过对标 记不同粗细程度的分类和流合并两种方法将网络的连接数从d f ，2 2 ) 降到o ( n ) ，从而极大 地增加网络的可扩展性。当m p l s 运行在基于帧的媒质上时，流合并很简单，所要做的 仅仅是要求节点将多个上游标记对应到同一个下游标记，这也称为帧合并。但是在a t m 上就会产生问题。在a t m 中，m p l s 的标记对应于a t m 信元中的v p i 厂v c i 域，因此流 合并意味着v p i v c i 合并。但是标准的a t m 交换机不支持v c 合并。如果直接将不同的 v c 合并成同一个出口v c ，不同分组的信元就会交错在一起，而且接收方没有办法能分 辨出来。一种可行的方法是用v p 而不是v c 来进行流合并，通过对每个v p 分配不同的 v c 空间来解决信元交错问题；但这样将极大地降低v p i v c i 的利用率，而且需要机制来 进行v c 空间的分配。v c 合并要求a t m 交换机对不同入口v c 进来的分组先进行串行 化，这就要求a t m 交换机中有额外的缓存。对此m p l s 工作组在1 9 9 9 年9 月指定的标 准中提出了一种解决方案，并初步研究了在输出缓存采用f i f o ( f i r s ti nf i r s to u t ，先进 先出) 。研究结果表明，这种方案十分可行。 2 路由环( l o o p ) 的防止与检测 由于l s p 的建立基于路由信息，因此l s p 有可能也形成环路。在传统的i p 网络中， i p 通过1 v r l 域来减轻进入路由环的分组对整个网络的影响，但是a t m 和f r a m er e l a y 均 不支持1 v r l 。目前有两种方法来处理路由环：检测和防止。对于检测方式，可以通过在 m p l s 消息中加入路径矢量域来检测路由环。路径矢量域中包含了前传某个流的每个节点 的标识符。当某个节点收到这个域时，就检查自己的标识符是否已经在路径矢量域中：如 果已经有了，则表明产生了回路；如果没有，则将自己的标识符加到路径矢量域中并前传 m p l s 消息。对于防止方式，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 i n g ，基于路由的聚合 i p 交换) 提出了一种扩散( d i f f u s i o n ) 算法来防止路由环。对于某个流，当某个节点的下 一跳发生变化时，首先用d i f f u s i o n 算法来判断是否会产生路由环。在执行完毕之前，仍 沿用旧的路径来发送数据。m p l s 工作组也在考虑其它扩展性更好的机制。在1 9 9 9 年5 月提出的i n t e r n e t 草案中提出了一种线程机制( t h r e a d sm e c h a n i s m ) 。当一个节点( 比如 入口节点) 想建立l s p 或它的下一跳发生改变时，它向下游节点发送一个t h r e a d ，t h r e a d 由唯一的颜色( c o l o r ) 、跳数( h o pc o u n t ) 和1 v r