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

南京邮电大学硕士研究生学位论文 摘要 摘要 随着网络和多媒体业务的迅速增长，网上传输的业务流中，越来越多的是具有服务质 量要求的多媒体业务。但是传统m 网络主要采用最短路径算法选择路径，忽略了网络可用 链路容量和业务本身的要求，导致整个网络的利用率没有达到最佳，流量工程就是为此而 提出的。多协议标签交换( m p l s ) 认为是实现流量工程最有效的工具。基于m p l s 的流 量工程可以对网络中的业务流进行精确控制，在满足服务质量的前提下，使网络资源尽可 能的得到合理利用。 文章首先介绍m p l s 的基本概念、技术原理和体系结构，并分析m p l s 流量工程的性 能目标、结构模块和具体实现。其次，重点对m p l s 流量工程中的约束路由算法进行研究。 分析、总结经典约束路由算法的优缺点。在此基础上提出了一种性能优越的、满足流量工 程要求的约束路由算法b p r a 。 b p r a 算法根据自身的约束条件对到达的业务请求进行选路，分为两个阶段：第一阶 段，在一定源、目的节点对下，根据链路被选中的概率计算链路潜在关键度( p c v ) 约束； 第二阶段，根据链路带宽和利用率计算链路带宽约束。链路的权值由两部分约束值按比例 相加得到。在选路时，选取链路权值和小的路径作为业务请求的传输路径。通过计算得知， b p r a 算法的复杂度要小于经典约束路由算法m i r a 。 最后仿真结果表明：与m i r a 算法相比，b p r a 算法在拒绝率、最大链路利用率方面 体现出较优的性能，它使网络容纳更多的业务请求，拥塞发生的概率大大减少，从而达到 了网络负载均衡和性能优化的目标。在网络故障方面，b p r a 算法相比m i r a 算法需重路 由的业务请求少、重路由成功率高，说明b p r a 算法在网络故障时算法的健壮性和稳定性 更好，对业务传输的影响更小。 关键词：多协议标签交换，流量工程，负载均衡，链路带宽利用率，服务质量 南京邮电大学硕士研究生学位论文 a b s t r a c t w i t ht h er a p i dg r o w t ho fn e t w o r k sa n dm u l t i m e d i ab u s i n e s s ，q u a l i t yo fs e 而g r a r a n t e e s a r or e q u i r e db ym u l t i m e d i ab u s i n e s s b u tt h et r a d i t i o n a li pn e t w o r ku s e st h es h o r t e s tp a t h a l g o r i t h mt oc h o o s ep a t h s ，t h i sm e t h o do v e r l o o k st h ea v a i l a b l el i n kc a p a c i t i e sa n dt h eb u s i n e s s s r e q u e s t s , s ot r a f f i c g i n e e r i n gi sp r o p o s e d m p l si sr e g a r d e d 鹤ap o w e r f u lt o o lt or e a l i z e t r a f f i ce n g i n e e r i n g t h et r a f f i ce n g i n e e r i n gb a s e do nm p l sc a np r e c i s e l yc o n t r o lt h eb u s i n e s s f l o wi nt h en e t w o r k , s a t i s f i e st h eq u a l i t yo f s 贸v i ，a n dl 玛豁t h en e t w o r kr o s o u r c or a t i o n a l l y t h i sp a p e rf i r s t l yi n t r o d u c e st h eb a s i cc o n c e p t s ，t e c h n o l o g yt h e o r i e sa n da r c h i t e c t u r e so f m p l s i ta n a l y s e st h eo b j e c t i v e s ，m o d u l a rs t r u c t u r e so ft r a f f i ce n g i n e e d n g 口a n dh o wt or e a l i z e t r a f f i ce n g i n e e r i n gb a s e do nm p l s s e c o n d l y , t h ep a p e rf o c u s e so nt h ec o n s t r a i n t - b a s e dm u t i n g a l g o r i t h m so fm p l s - t e ( t r a m ce n g i n e e r i n gb a s e do nm p l s ) ，s u m m a r i z e st h ec l a s s i c c o n s t r a i n t - b a s e dm u t i n ga l g o r i t h m s m e r i t sa n dd r a w b a c k s o nt h i sb a s i s ，t h ep a p e rp u t so u ta v a l i dc o n s t r a i n t - b a s e dr o u t i n ga l g o r i t h m - b p r 气w h i c hm t st h er e q u e s t so ft r a f f i ce n g n e e r i n g b p r a a l g o r i t h ms e l e c t sp a t h sa c c o r d i n g t oc o n s t r a i n t s b p r aa l g o r i t h mi sd i v i d e di n t ot w o s t a g e s ：s t a g eo n e , o nc e r t a i np a i r so fi n - o u tn o d e s ，c o m p u t et h ep c v ( p o t e n t i a lc r i t i c a lv a m e ) c o n s t r a i n t sa c c o r d i n gt ot h el i n k s s e l e c tp r o b a b i l i t i e s s t a g et w o , c o m p m et h eb a n d w i d t h c o n s t r a i n t sa c c o r d i n gt ot h el i n k s b a n d w i d t ha n du t i l i z a t i o n t h ew e i g h to ft h el i n ki sa d d e du p b yt h et w op a r t sa c c o r d i n g t ot h e i rp r o p o r t i o n s w h e nm u t i n g , c h o o s et h ep a t ht h a th a sas m a l l e r v a l u eo fl i n kw e i g h t s s u m m a t i o na n dt r a n s m i tt h eb u s i n e s sr o q u e s to nt h i sp a t h t h et i m e c o m p l e x i t yo fb p r a i ss m a l l e rt h a nt h ec l a s s i cc o n s t r a i n t - b a s e dm u t i n ga l g o r i t h m - m i r a t h es i m u l a t i o nr e s u l ts h o w st h a tb p r ai sb e t t e ri nr e j e c tr a t ea n dl i n ku t i l i z a t i o nt h a nt h e a l g o r i t h mm i r a b p r aa l g o r i t h me n a b l e st h en e t w o r kt oa c c e p tm o r eb u s i n e s sr e q u e s t s , r e d u c e st h ep r o b a b i l i t yo fo c c u n e n c oo fc o n g e s t i o n s ，a c h i o v e st h eg o a lo fl o a d i n gb a l a n c ea n d p e r f o r m a n c i n go p t i m i z a t i o n w h e nt h en e t w o r kg e t si n t of a i l u r e , b p r aa l g o r i t h ma l s oh a sl e s s b u s i n e s sr e q u e s t sw h i c hn e e dt ob er e r o u t e d , a n dh i g h e rs u c c e s s f u lr e r o u t er a t e i th a sab e t t e r s t a b i l i t ya n dl e s si m p a c to nt h et r a n s m i s s i o no f t r a 伍cf l o w k e yw o r d s ：m u f f - p r o t o c o ll a b e ls w i t c h i n g , t r a f f i ce n g i n e e r i n g , l o a db a l a n c i n g , b a n d w i d t h u t i l i z a t i o no fl i n k , q u a l i t yo fs e r v i c e i i 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学 或其他教育机构的学位或证书而使用过的材料。与我一起工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：j 签址日期：刍嘞路 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所 送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保 存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保 密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部 分内容。论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：脚师签名： 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 课题的提出 第一章绪论 近年来随着i n t e r n e t 的迅猛发展，i n t e m e t 网络业务种类也与日俱增，这种高速的增长 对网络的传输线路和带宽提出了迫切的要求。宽带的需求成为了互联网发展的必然方向。 从1 9 9 9 年起，中国电信、网通、长城、铁通等宽带运营商在骨干网、接入网领等域相继 开始运作，极大地推动了中国宽带网络的发展，形成了中国宽带网络建设和发展的热潮。 在宽带骨干网方面，各大运营商主要采用的技术包括i p - o v e r - a t m 、i p - o v e r - s d h 和 m 一o v e r - d w d m 【1 1 以及m p l s 2 i ( m u f f p r o t o c o ll a b e ls w i t c h i n g ) 。由于网络承载的流量中越 来越多是具有服务质量【3 1 ( q u a l i t yo f s e r v i c e ，q o s ) 要求的多媒体业务，传统p 网络已经 无法满足业务需求，因此采用m p l s 技术就显得非常必要。 m p l s 技术是i e t f 正在积极研究并大力推广的一种新的数据转发机制。它处在数据链 路层和网络层之间，在克服口对于流量工程的局限性方面具有显著的优势。m p l s 技术 引入标签交换概念，每个节点收到数据包后，通过预先建立的标签交换表进行选路和标签 交换。在标签交换表形成之前，m p l s 先通过约束选路算法，在边缘路由器确定每条业务 流通过网络的标签交换路径l s p 4 ( l a b e ls w i t c h i n gp a t h ) ，即业务流经过网络的节点和次 序列表嘲。这些显式l s p 的建立，不仅可以对m 实时性业务提供服务质量支持，而且能 够通过对l s p 的合理部署，优化网络资源、提高网络的性能【钥。m p l s 被认为是下一代 i n t e r n e t 骨干网络技术，已经得到业内人士的普遍认可。 将m p l s 用于实施流量工程嘲，是m p l s 最主要的应用。流量工程是通过将大量的用 户业务转移到预先设定的路径来实现的。基于m p l s 流量工程的约束路由算法是实现 m p l s 流量工程的重要组成部分，也是实现q o s 业务的关键。传统路由协议中所采用的路 径选择算法通常是只考虑单一的度量参数，如跳数或时延等，如现有的i n t e m e t 路由是基 于目的口地址的最小跳数寻路，没有考虑网络资源有关参数，如带宽、利用率等。随着网 络规模的不断扩大，使得网络资源使用情况变得紧张【9 】，链路误码率高、传输速率小，并 将会在很大程度上影响业务传输的可靠性，因此研究并提出具有约束条件的路由算法【1 0 1 已经显得十分重要。 基于约束的路由选择算法可以根据一个或多个满足q o s 的约束条件，来计算出所有的 南京邮电大学硕士研究生学位论文第一章绪论 可行路径，并根据一定的法则从中选出一条最佳的路径。与传统的最短路径优先路由算法 相比，基于约束的路由选择算法不仅可以为业务流找出满足其q o s 要求的可行路径，而且 还可以根据其它的度量方式使业务流均匀合理地分布，从而可以在很大程度上克服最短路 径的瓶颈效应、减少拥塞的发生概率、提高网络资源的利用效率、达到网络性能优化的目 标。所以研究并提出有效的基于m p l s 流量工程的约束路由算法，通过实施合理的选路控 制，实现数据的服务质量，最大限度得优化网络的运行性能，成为流量工程研究的热点问 题。 1 2 国内外研究现状 基于m p l s 流量工程的约束路由算法的研究，在国际上已经有了长足的发展，并已经 形成了许多规范、r f c 或者草案。在m p l s 流量工程方面，d a w d u c e 等人于1 9 9 9 年9 月 发表了第一篇研究流量工程的r f c “r e q u i r e m e n t sf o rt r a f f i ce n g i n e e r i n go v e rm p l s 。同 年1 1 月，流量工程工作组( 1 r i w g ) 在华盛顿成立，随后出现一系列的r f c 和草案，分 别阐述了实现流量工程的必要条件、流量工程通用方法、对象和数据集以及可用于实现流 量工程的技术和方法学，如约束路由。1 9 9 6 年m r r 的w c l e e 在i e e en e t w o r km a g z i n e 上发表针对虚电路网络中路由选择综述文章，和伦敦大学的c w a n g 在j s a c 上发表的关 于约束路由算法研究的文章，标志着约束路由算法成为研究的热点。随之涌现了许多满足 满足q o s 的约束路由算法，比如满足带宽和跳数约束的最短路径算法；满足带宽和时延约 束的最短路径算法；或者是满足其它约束条件组合的最短路径算法。并且依照约束路由算 法的约束条件产生了许多具有一定代表性的经典约束路由算法。 约束路由算法在进行路由选择时不仅要考虑网络拓扑，并要满足一系列约束条件( 包 括带宽、跳数、时延或资源类别属性等管理策略) ，在寻求最小代价路径的同时优化整个 网络的性能。当前国内外对约束路由算法的研究集中在三方面： 1 解决多约束n p 问题【1 1 , 1 2 ，提出高效且适用的约束路由算法； 2 扩展现有的路由协议实现约束路由算法； 3 约束路由算法与流量工程、m p l s 等网络技术相结合，从各个层面实现优化网络资 源利用和性能这一最终目标。 当同时对两个以上相互独立的参数提出要求时，这个问题就是一个多约束的n p 问题， 实时应用往往会对带宽、拒绝率、延时、业务代价等多个参数同时提出性能要求。例如， 实时多媒体业务会对延时和延时抖动同时提出要求，这些参数相互独立时，选择满足多个 2 南京邮电大学硕士研究生学位论文第一章绪论 参数约束的路由就成为n p 问题( 多参数约束问题) ，n p 问题直接关系到约束路由算法的 可实现性，目前这方面仍有大量工作需要进一步研究。 1 3 课题研究意义 m p l s 流量工程是一种实现q o s 要求的网络优化和控制技术，通过优化网络资源的分 配和使用提高网络性能，满足用户服务质量的要求，它的实际应用对我国通信网络的建设 和发展具有重要的意义。基于m p l s 的流量工程的直接用户将是大型运营商( i s p ) 。为了 在现有网络上提供尽量好的服务和获得最大利润，最大程度利用现有网络资源，优化网络 的运行性能，运营商必然借助于m p l s 流量工程，因此m p l s 流量工程本身的实用前景十 分广泛。 从世界范围来看，m p l s 实施流量工程处在研究和实际应用阶段。j u n i p e r 等各大网 络公司已经推出了各自的m p l s 产品。因此建立有效实施m p l s 流量工程的系统模型是很 有必要的因为m p l s 流量工程的问题最终可以归结为业务数据流传输的路径确定问题， 即显式路径的确立问题，所以说针对m p l s 网络，研究流量工程约束路由算法的约束条件 和目标函数，进而建立算法的数学模型和算法的具体规则，对动态实现基于m p l s 的流量 工程、均衡网络负载、避免拥塞的发生和优化网络利用率都具有特别重要的意义。 1 4 本文主要工作和组织结构 本文在对基于m p l s 的流量工程进行了深入的研究的基础上，主要完成了以下工作： ( 1 ) 对m p l s 技术进行详细的介绍，包括m p l s 概念原理、体系结构、工作流程等。 在此基础上对m p l s 流量工程进行了深入的研究，包括实施流量工程的必要性，m p l s 流 量工程的总体结构、功能模块、信令协议等，以及m p l s 流量工程的实现和具有的优势。 ( 2 ) 文章重点对m p l s 流量工程中的约束路由算法进行研究，对目前的经典约束路 由算法进行研究分析，并总结其优缺点，在此基础上提出一种基于链路潜在关键度和带宽 约束的路由算法b p r a ，b p r a 算法根据自身的约束条件对到达的业务请求进行选路，希 望在消耗较少网络资源的同时，使负载尽量分布在有宽裕空闲资源的链路上，以达到实现 网络性能优化的目标。文章对算法的思想，算法流程进行了深入的研究，并且详细计算、 对比算法的复杂度，总结算法的优缺点。 ( 3 ) 算法仿真时，使用了一种专门针对流量工程的t o t e m 仿真工具箱，简单介绍了 t o t e m 的功能、结构和使用。重点通过t o t e m 进行仿真实验，对b p r a 算法与m i r a 3 南京邮电大学硕士研究生学位论文 第一章绪论 算法的性能进行比较。结果显示在拒绝率、最大链路利用率、利用率分布、网络故障重路 由等方面，b p r a 算法体现出了更好的性能，达到了网络负载均衡和网络性能优化的目标。 文章最后指出了算法研究中存在的不足，和下一步的研究方向。 论文的结构安排如下： 第一章主要介绍基于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 流量工程中的经典约束路由算法进行研究，研究目前经典约束路由 算法，并总结其优缺点。在此基础上提出一种新的约束路由算法b p r a ，对b p r a 的算法 思想、算法实施流程进行详细介绍，并计算、比较了算法复杂度。 第五章首先介绍t o t e m 流量工程仿真工具箱。用t o t e m 进行仿真实验，从拒绝率， 最大链路利用率，利用率分布，网络故障重路由四方面对本文提出的b p r a 算法和m i r a 算法进行仿真实验，最后得出仿真结果，并对两种算法的性能进行比较、分析。 第六章对全文的工作进行总结，分析并指出算法存在的不足和进一步研究的方向。 南京邮电大学硕士研究生学位论文第二章m p l s 概述 第二章m p l s 概述 随着网络通信业务向视频、多媒体等宽带业务的发展，现有的网络己不能满足这些高 宽带业务的发展要求。m p l s 技术是i e t f 正在积极研究并大力推广的一种新的数据转发机 制，它兼有a t m 交换技术和口技术的优良性能，被认为是下一代网络的核心技术。m p l s 能够通过对l s p 的合理部署，使流量均衡地分布在现有的网络中，同时实现业务的服务质 量，最大限度的优化网络性能。 2 1m p l s 产生的技术背景 网络业务的迅速增长，给网络运营商带来了巨大的商业机遇，同时也对其网络提出了 更高的要求。人们希望m 网络不仅能够提供e m a i l 、上网等服务，而且能够提供宽带、实 时性的多媒体业务。a t m 曾经是被普遍看好的、能够提供多种类型业务的交换技术，但是 由于实际的网络中已经普遍采用口技术，现有a t m 也一般都是用来承载口，因此人们就 希望口也能象a t m 一样提供多种类型的服务。 1 9 9 6 年，i p s i l o n 公司推出了i ps w i t c h i n g 协议，该协议的推出在数据通讯界引起了巨 大的震动，并由此引发了路由器技术的革命。各个公司开始纷纷提出自己的方案：c i s c o 公司提出了t a gs w i t c h i n g s 方案；i b m 提出了a r i s ( a g g e g a t er o u t e - b a s e di ps w i t c h ) 方 案；t o s h i b a 提出c s r ( 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 为基础，并结合m 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 工作组正式成立。 m p l s 就是在这种背景下产生的一种网络技术，它是一种基于标签的转发技术。m p l s 与a t m 交换类似，引入了固定长度的短标签( l a b e l ) 作为在m p l s 网络中进行数据转发 的依据。之所以称m p l s 为“多协议一，是因为m p l s 可以支持网络层面上的多协议如： i p v 4 、p v 6 等；同时m p l s 也可以支持第二层上的多协议，如a t m 、帧中继、p p p ( p o i n t - t o p o i n tp r o t o c 0 1 ) 、以太网等。m p l s 将第二层交换能力和第三层路由技术完美地 结合起来，在m 路由和控制协议的基础上提供面向连接的交换。m p l s 保持了口技术的 灵活性、可扩展性和a t m 的快速交换、流量控制等性能，正在成为网络运营商提供增值 业务的主要手段。 5 南京邮电大学硕士研究生学位论文第二章m p l s 概述 2 2m p l s 基本概念和技术原理 2 2 1 基本概念 1 标签( l a b e l ) 标签是一个包含在分组中短的、定长的、只有本地意义的标识符。某一分组的标签代 表了它所属的转发等价类，用来在一对l s r 之间进行分组交换，标签可以封装到现有的 数据链路层分组中，格式取决于分组封装所在的介质。图2 1 为通用标签的格式。 其中m p l ss h i m 字段又分为： 标记 标签值，2 0 比特； c o s 业务等级，3 比特； s o s 堆栈底标记，l 比特； t t l 生存周期，8 比特； 图2 - 1m p l s 标签的格式 2 标签交换路由器( l a b ds w i t c h i n gr o u t e r ，l s r ) 0 3 1 l s r 是具有标签交换能力的路由器，它是m p l s 网络的基本构成单元。在m p l s 网络 中，无论是接入节点还是核心节点都是l s r 。一个l s r 可以是一个传统的交换机，或者是 升级为支持m p l s 的一个传统路由器。当一个分组由一个路由器发往另一个路由器时， 对应于该分组，发送方的路由器称为“上游路由器 ，接收方的路由器就称为“下游路由 器 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 ) 【1 4 】 f e c 是m p l s 中最重要的一个概念，甚至可以说是m p l s 技术的基础。m p l s 实际 上是一种分类转发的技术，它将具有相同转发方式( 目的地相同、转发路径相同、具有相 同服务等级) 的分组归为一类，这种类别称为转发等价类，每个转发等价类被指定为一个 或多个转发等价类单元。属于相同转发等价类单元的分组在m p l s 网络中将获得完全相 同的处理。 f e c 将具有一定特性的数据包映射到指定的l s p 路径上，并在本地链路上使用惟一 的标签值。每个f e c 由一个或多个f e c 要素来描述，每个f e c 要素描述一组特定l s p 的 数据包。当某条l s p 由多个f e c 要素共享时，l s p 应在共享状态发生改变的节点终止。 6 南京邮电大学硕士研究生学位论文第二章m p l s 概述 目前定义的f e e 要素有两类： ( 1 ) i p 地址前缀，提供含有一个或多个p 地址前缀的集合，符合其中一个或多个口 地址前缀的包被映射到相应的l s p 路径。 ( 2 ) 主机地址，以一个3 2 位的p 地址作为单元。 4 标签空间( l a b e ls p a c e ) 标签空间是指在l s r 进行标签分发过程中标签的取值范围。标签具有局部性，因此对 于每个l s r 来说，确定标签的唯一性是非常重要的。标签空间分为两类：接口地址空间和 平台地址空间。 5 标签交换路径( l a b e ls w i t c h i n gp a t h ，l s p ) l s p 指属于特定f e c 分组所经过的处于同一层次的、多个l s r 所形成的路径。简单 的说，l s p 就是源l s r 与目的l s r 之间的一系列的l s r ，以及它们之间的链路构成的一 条路径。图2 - 2 为l s p 建立过程示意图。 ( 1 ) 标签请求 入口出口 2 ( 2 ) 标签映射 入口出口 26 入口 出口 6 图2 2 标签交换建立过程 6 标签分发协议( l a b e ld i s t r i b u t i o np r o t o c o l ，l d p ) 【1 5 】 一个标签分发协议是由一系列的过程组成的，l s r 通过这些过程通知其它的l s r 它 自己作出的标签绑定消息，此协议也包括两个标签分发对等实体之间的任何协商，它们用 这些协商来了解彼此之间的m p l s 参数设置。该协议是m p l s 控制协议，也是m p l s 技术 的核心。它相当于传统网络中的路由协议，负责f e c 的分类、标签的分配、分配结果的传 输及l s p 的建立和维护等一系列的操作。 7 标签分发对等实体( u ) pp e e r s ) 两个l s r 通过l d p 协议进行l a b d f f e c 绑定信息的交换，就它们所交换的绑定信息 7 南京邮电大学硕士研究生学位论文第二章m p l s 概述 来讲，称这两个l s r 为标签分发对等实体。 8 标签交换( l a b e ls w i t c h ) 标签交换指基本的m p l s 转发操作，它由一系列的过程组成，包括查找l i b 决定用什 么出标签替换入标签、标签封装、确定出端口和其它的数据处理信息。 9 标签信息库( l m ) 标签信息库的作用类似于路由表，其中包括各个标签所对应的各种转发信息。每个入 口标签对应一个信息条目，每个条目包括出口标签、出口接口、出口链路层信息等子条目。 l i b 的内容如表2 1 所示： 表2 1 标签信息库 入标签入端口 口地址段出端口出标签 4 l1 9 2 1 6 8 o5 l o 多协议( m u l t i p r o t o c a l ) 多协议是指m p l s 位于传统的第二层与第三层协议之间，其上层协议与下层协议可以 是当前网络中存在的多种协议。 2 2 2 技术原理 m p l s 是一种集成式的i p o v e r - a t m 技术。m p l s 使用标签交换，网络路由器只需要 判别标签后即可进行转发处理，它可以使数据包传送的延迟时间减短，增加网络传输的速 度，更适合多媒体讯息的传送。在m p l s 网络中，数据包转发是基于4 字节的短标签，它 不同于常规p 路由基于最长地址匹配查找的h o p - b y - h o p 的数据包转发方式。在常规的p 路由中，每个节点都要独立分析口包头，并基于目的地址做出路由决策。而在m p l s 中， 只是在分组进入网络的边缘节点处对口包头进行分析，为数据包分配标签，并由此决定数 据包的路径以及优先级。每个数据包被沿着预先建立的标签交换路径转发，后续节点不再 分析i p 包头，只根据标签内容做出如何转发数据包的决定。在每一跳上，标签交换路由器 去掉数据包中己有的标签，并为之绑定一个新的标签，这个新的标签指明数据包被转发的 下一跳。在m p l s 网络出口边界路由器上，数据包中的标签被去掉，并被按一般的方式转 发到它的目的地。 8 南京邮电大学硕士研究生学位论文 第二章m p l s 概述 2 3m p l s 标签的操作 2 3 1 标签映射 标签映射分为两种：一种是入口路由器处的标签映射：另一种是m p l s 域内的标签映 射。入口路由器处的标签映射为“i n g r e s sl s r ，其依据一定的原则对输入分组进行划分， 得到多个f e c ，接着将有关标签与这些f e c 进行映射，并记录在相应的数据库( l a b d i n f o r m a t i o nb a s e ，l m ) 中。简单地说，就是将一个标签指派给f e c ，就称为“标签映射 。 m p l s 域内的标签映射又称为输入标签映射( i n c o m i n gl a b e lm a p ，i l m ) ，即将每个输入 标签映射到下一跳标签的转发入口( n e x th o pl a b e lf o r w a r d i n ge n t r y ，n h l f e ) 上，然后 根据映射结果，将分组沿各通路进行转发。 2 3 2 标签封装 标签是一个包含在分组中的、固定长度的、只有本地意义的标识符。任一对l s r 必须 在标签的数值和意义上取得一致。为了在分组中携带标签或标签栈，需要对标签的编码加 以规定。目前标签栈有几种不同的编码技术，使用哪种技术取决于传输标签分组的设备类 型。各种技术对于标签的实现如图2 3 所示。 第三层封装口分组 m p l s 封装s h i m 标记 第二层封装 a n 垤风p p pe t h o r n o t v c i ，v p id l c i 图2 - 3 标签封装格式 下面以设备类型为依据，简单描述各种标签封装技术。 1 m p l s 专用硬件软件 当传输设备为m p l s 专用的硬件软件时，将使用m p l s 专用的封装技术，即在数据 链路层与网络层头标之间使用一种“s h i m 封装，该封装将置于网络层分组头标之前，链 路层封装之后，独立于网络层协议和链路层协议。因此这种封装又称为m p l s 通用封装。 2 使用a t m l s r 技术 a t m 技术十分适用于构成标签交换路由器。将a t m 硬件进行软件升级就构成了 a t m l s r ，它使用v c 或v p 构成标签。 a t m 对标签的封装主要有以下三种方式： 9 南京邮电大学硕士研究生学位论文 第二章m l s 概述 ( 1 ) s v c 封装 这种方式使用v p f v c i 字段来构成栈顶标签的封装。这种技术可以使用于任何网络 之中。使用这种技术，l s p 由a t ms v c 来实现，l d p 成为a t m 的信令协议。在这种方 式中，a t m - l s r 不能对标签栈实施入栈和出栈操作。 ( 2 ) s v p 封装 这种方式使用v p i 字段来构成栈顶标签的封装，同时使用v c i 字段来构成标签栈中下 一层标签的封装。使用这种技术可以实现a t m 的v p 交换。此时，l s p 由a t ms v p 来 实现，l d p 将成为a t m 的信令协议。 ( 3 ) s v p 多点封装 这种方式使用v p 字段来构成栈顶标签的封装，同时使用v c i 字段的一部分来构成标 签栈中下一层标签的封装，使用v c i 字段的剩余部分来标志l s p 的入口节点。使用这种方 式，可以利用传统a t m 的v p 交换功能来提供多点到点的v p 。来自于不同入口节点的信 元携带有不同的v c i 值。 2 3 3 标签的分配和分发 标签的分配和分发是两个独立而又紧密相关的操作。标签的分配是指l s r 分配一个标 签并与某个f e c 绑定的过程。标签的分发是指l s r 把标签与f e c 的绑定信息分发给上游 或下游l s r 的过程。 1 标签分配控制 m t f 的m p l s 工作组粗略地确定了两类标签分配的驱动方式：控制流驱动和数据流驱 动。其中控制流驱动又分为：基于控制流的拓扑驱动和基于控制流的请求驱动。 拓扑驱动与l s r 的路由表紧密相关。路由表的每一个条目指示去往某个目的地的下 一跳地址，拓扑驱动即是据此为每一个条目分配一个标签。拓扑驱动的标签分配方式相当 于一种“预分配 的方式，与实际到达的分组无关，不需要在线建立l s p ，相对来说时延 较小。请求驱动是在数据传输之前，由控制信令发出请求，l s r 接收到请求后动态地进行 标签分配和标签交换路径的建立，它实际上也是预分配方式。 数据流驱动是在实际数据流分组到达时进行标签分配并在线建立l s p 。这种方式有效 地利用标签空间，适用于l s r 的标签空间有限而网络数据流较多的情况。 2 标签分发机制 标签分发分为上游分发和下游分发两种策略。这里仅介绍下游分发机制，上游分发过 程是与下游分发相反的。 1 0 南京邮电大学硕士研究生学位论文第二章m p l s 概述 下游分发的策略是指标签的分发沿着数据流传输的逆行方向进行，下游l s r 为某个 f e c 分配一个标签，该l s r 用所分配的标签作为本地交换表的索引。这是单播通信最常用 的标签分发方式。 如在图2 _ 4 中，对于某个新到达的数据流，l s r l 、l s r 2 、l s r 3 均需要分配一个标签 与之绑定，但该绑定信息的传递是由l s r 3 发起的，具体过程如下：首先l s r 3 分配一个 标签与该f e c 绑定，然后它把绑定信息沿着分组转发的逆向路径分发给l s r 2 ：l s r 2 接 收到l s r 3 的绑定信息后，同样根据本地策略分配一个标签与该f e c 绑定，并把该信息传 输给上游的l s r l ，以此类推。 图2 4 下游分发示例图 2 3 4 标签的分配协议 m p l s 使用了两种标签分发方式，即用控制消息携带和使用专用标签分发协议( l d p ) 。 虽然使用专用标签分发协议会使路由的分发和标签的分发相分离，但是因为使用控制消息 存在诸如无法协商标签的可用范围、无法处理无效的标签分配等问题。因此建议采用专用 标签分发协议。l d p 用四类消息完成标签的分发过程，它包括发现消息、会话消息、公布 消息、通知消息。 标签分发协议的运行可以分为三个阶段： 1 发现阶段 在这个阶段里，l s r 可以自动发现它的l d p 对等，而无需进行人工配置。l d p 将发 现机制分为两种：基本发现机制，用来发现本地的l d p 对等；扩展的发现机制，用来发现 远地的l d p 对等。基本发现机制通过在l d p 链路上周期性地发送“h e l l o 一包来通知相邻 节点本地对等关系。这个“h e l l o 按u d p 发送，目的协议地址为所有路由器的地址，u d p 端口号为公认的l d p 发现端口号。“h e l l o 一包的接收方会将这个对等关系标识为链路层 南京邮电大学硕士研究生学位论文 第二章m i l s 概述 可达。扩展的发现机制则由l s r 周期性地发送特定m 地址的“h e l l o 刀包。“h e l l o 一按 u d p 发送，目的协议地址为特定的地址，u d p 端口号为公认的l d p 发现端口号。搿h e l l o 一 包的接收方会将这个对等关系标识为网络可达。 2 会话建立阶段 在两个l s r 交互发现“h e l l o 包后，就会启动l d p 会话建立阶段。会话建立阶段又 划分为两个子阶段：建立传输层连接和初始会话。建立传输层连接就是在两个l s r 之间建 立t c p 连接，而初始会话就是通过交互l d p 初始化消息来协商会话的参数，包括l d p 协 议版本、标签分发的方法、定时器值、标签的范围等。 3 会话的维持和删除 l d p 通过监测l d pu d p 的接收情况来判定会话连接是否完整。一个l s r 为每个会话 保持一个“保持存活 定时器，当从该会话上接收到一个l d pu d p 时，“保持存活定 时器会刷新。如果“保持存活一定时器到时，则l s r 认为该传输连接中断，该对等失效， 并由此关闭传输层连接，从而终止这个对等。 2 4m p l s 网络体系结构 1 m p l s 网络结构 图2 - 5 m p l s 网络结构图 m p l s 网络【1 6 】结构如图2 - 5 所示，它由网络节点和链路组成，m p l s 网络的组成节点【1 7 1 1 2 南京邮电大学硕士研究生学位论文第二章m p l s 概述 是标签交换路由器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 控制协议和第三层路由 协议，并负责与其它l s r 交换路由信息来建立路由表。l s r 负责f e c 和口分组头的映射、 建立f e c 和标签之间的绑定、分发标签绑定信息、建立和维护标签转发表等工作。位于网 络边缘的l s r 称为边缘l s r ( l a b e l e de d g er o u t e r ，l e r ) ，主要完成连接m p l s 网络和非 m p l s 网络的功能，并实现对业务的分类、分发标签、剥去标签等。其中入口l e r 叫i n g r e s s ， 出口l e r 叫e g r e s s 。位于网络内部的l s r 则称为核心l s r ，核心l s r 是支持m p l s 的路 由器，它提供标签分发、交换功能。带标签的分组沿着由一系列l s r 构成的标签交换路径 ( l s p ) 传送。 2 m p l s 网络节点结构 m p l s 网络节点包括两个结构平面【1 3 】：m p l s 控制平面和m p l s 转发平面。除了可以 交换带有标签的数据包外，m p l s 节点还可以执行第三层路由选择。图2 - 6 显示了一个 m p l s 节点的基本结构。 控制平面 图2 - 6 m p l s 节点结构 ( 1 ) 转发平面 m p l s 转发平面使用由m p l s 节点维护的标签转发信息库( l a b e lf o r w a r d i n g i n f o r m a t i o nb a s e ，l f i b ) ，来转发带有标签的数据包。标签交换转发组件使用的算法，利 用了包含在l f m 中的信息和包含在标签值里的信息。每个m p l s 节点维护着两张表：标 签信息库( l i b ) 和l f m 。l i b 包含了由本地m p l s 节点分配的所有的标签，以及这些 1 3 南京邮电大学硕士研究生学位论