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

南京邮电大学硕士研究生学位论文摘要 摘要 随着i n t e m e t 的快速发展，流量工程己经成为i e t f 和网络服务提供商( i s p ) 所讨论 的一个热门课题。流量工程旨在对运营网络的业务流量进行合理控制，其目标是使网络资 源利用和网络性能达到最优化。而多协议标签交换技术则运用显示路由使i n t e m e t 上的流 量工程的实施变得简单而高效。m p l s 流量工程中的动态路由算法则是这一技术得以实施 的关键因素。 本文在研究多种m p l s 流量工程动态路由算法的基础上，深入剖析了最小干扰路由算 法的关键思想，指出了该算法的不足，提出了一种改进的最小干扰路由算法( e m i i u ) 。 e m i r a 的基本思想是在考虑不包括当前节点对的其它入口出口节点对的关键链路和准关 键链路( 指需要关注的非关键链路) 的同时，综合考虑了当前节点对的关键链路，使网 络中相应链路的重要程度以链路权值的方式表现出来。通过仿真工具m a t l a b ，对e m i r a 与m i r a 算法进行了比较，仿真结果表明e m i r a 在满足l s p 请求的同时，提高了整个网 络总的最大流，增加了l s p 请求接入的个数，进一步降低了l s p 请求的拒绝率；同时，本 文还把e m i r a 的仿真数据和其它的m i a r 改进算法( 如wsc 、d 。m i r a 和i m i r a ) 进行了l s p 请求被拒绝个数的比较，结果显示e m i r a 进入网络重负荷状态前能接入更多 的l s p 请求，能更均衡有效地利用网络资源，具有良好的现实应用意义。 关键词：多协议标签交换流量工程最大网络流最小干扰路由算法关键链路 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t a l o n gw i t ht h ef a s td e v e l o p m e n to fi n t e r a c t ，t r a f f i ce n g i n e e r i n gn o w a d a y sh a sb e c o m e a h o tt o p i co fi n t e m e ts e r v i c e sp r o v i d e r s ( i s p ) b yc o n t r o l l i n gt h et r a f f i ci ni s pr o u t i n gd o m a i n ， t r a f f i ce n g i n e e r i n ga i m sa te n h a n c e m e n tu t i l i z a t i o no fr e s o u r c ea n di m p r o v e m e n to fn e t w o r k s e r v i c e 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 ) e n a b l e st h ed e p l o y m e n to fi n t e r n e tt r a f f i c e 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 yu s i n ge x p l i c i tr o u t i n g a n dd y n a m i cr o u t i n gi 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 , a f t e rt h ek e yi d e ao fm i r ai sa n a l y z e d ，t h el i m i t a t i o n so ft h i sa l g o r i t h ma r e r e v i e w e da n dam o d i f i e da l g o r i t h m ：e m i r ai sp r e s e n t e d e mi r an o to n l yt a k e si n t oa c c o u n t t h ec r i t i c a ll i n k sa n dn e a r - c r i t i c a ll i n k sf o rt h o s ei n g r e s s - e g r e s sp a i r se x c e p tt h ec u r r e n tp a i r w h i c hm u t i n ga nl s pr e q u e s t ，b u ta l s oa c r i t i c a ll i n k sf o rt h i sc u r r e n tp a i ri t s e l f t h e nt h e a p p r o a c hi st od e t e r m i n ea p p r o p r i a t ew e i g h t sf o rt h e s el i n k si nt h en e t w o r k t h r o u g hm a t l a b s i m u l a t o r , t h ep a p e rc o m p a r e de - m i r aw i t hm i r a s i m u l a t i o nr e s u l t ss h o wt h a tu n d e rt h es a m e s u i t a b l ee n v i r o n m e n t s ，t h et o t a la v a i l a b l eb a n d w i d t hf o re m i r ai sh i g h e rt h a nt h a to fm i r a a n dt o t a ln u m b e ro fl s ps e t u pr e q u e s t sw h i c ha c c e s st ot h en e t w o r ki si n c r e a s e da n dt h en u m b e r o fr e j e c t si sf e w e r m o r e o v e rs i m u l a t i o nr e s u l t sr e c o g n i z et h a te m i r ap e r f o r m sb e t t e rb y r e j e c t i n gf e w e rl s ps e t u pr e q u e s t st h a no t h e ra l g o r i t h m ss u c ha sw sc ，d - m i r aa n di - m i r a s oe - m i r al e a d st oi m p r o v e dp e r f o r m a n c ea n dp r o v i d e sb e t t e ro v e r a l ln e t w o r kr e s o u r c e u t i l i z a t i o n k e yw o r d 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 t r a f f i ce n g i n e e r i n gm a x i m u mn e t w o r kf 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 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：煞盘驽 日期：尘丑生! 羔 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：醒塞垫导师签名：z 壅型童日期：盘立：垒：墨 南京邮电大学硕士研究生学位论文 第一章概述 1 1 引言 第一章概述 近年来，随着i n t e m e t 的飞速发展以及新应用的层出不穷，包括话音、数据和视频在内 的各种业务均需在i p 网上进行传输，i p 业务也即将成为通信业务的主流。但由于i p 协议是 面向无连接的，只是尽力而为( b e s t - e f f o r t ) 来满足用户的需要，而无法保证有足够的吞 吐量和符合要求的传输时延，所以出现了服务质量( q o s ：q u a l i t yo f s e r v i c e ) 难以保证等 问题。 a t m 技术是由电信界提出的，为实现宽带综合数据业务网b i s d n 而发展起来的网络 技术，该网络能够传输包括话音、数据和视频在内的多种业务。其主要优势是能保证端到 端的q o s 、具有流量控制和拥塞控制功能、支持多业务等。但由于协议较为复杂，缺少良 好的a p i 接口以及设备价格昂贵，从而限制了a t m 技术的进一步推广。 于是，如何将a t m 技术与i p 技术的各自优势结合起来，解决目前i n t e m e t 网络中存在的 问题，就成为了研究的热点。目前，i p 与a t m 的结合技术主要分为两大类：重叠模型和集 成模型。采用重叠模型时，i p 层叠加在a t m 层之上，a t m 端点使用a t m 地址选择协议将i p 地址映射到a t m 地址，并通过a t m 路由协议为i p 分组选择路由。但由于i p 技术是面向无连 接的，a t m 技术是面向连接的，两种技术的这种结合会造成大量的协议转换以及工作方式 转换，进而引起许多问题。而集成模型是使用第二层信令与路由协议，直接通过一定的机 制使用i 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 ) 【i 】技术就是一种典型的集成模型技术，它 是综合了网络核心的交换技术和网络边缘的路由技术的优点而产生的，可以解决目前 i n t e m e t 网络存在的q o s 、流量工程等一系列问题，因此被认为是下一代的骨干网络技术【z j 。 1 2 课题的提出 针对用户和i s p 对i n t e m e t 的需求，目前i n t e m e t 网络迫切需要解决的问题是如何保证 q o s ，如何有效管理和利用网络资源。流量工程技术3 1 就是来解决这些问题的，通过它可 以平衡网络中不同的链路、路由器和交换机之间业务负荷，使这些设备既不会过度使用， 也不会未被充分使用。这样就可以有效利用整个网络的资源，平衡网络的负载，从而间接 南京邮电大学硕士研究生学位论文第一章概述 地达到了提供q o s 保证的目的。而m p l s 在实施流量工程方面有先天的优势，通过为数据流 建立合适的标记交换路径l s p ，就可以对网络的流量进行合理地控制，优化网络资源的利 用，达到实施流量工程的目的。而本文的目标正是研究如何在m p l s 网络上运用改进的流 量工程路由算法来合理优化网络资源，充分提高网络性能。 1 3 课题的研究现状 1 9 9 7 年，i n t e r n e t 工程任务组i e t f 专门成立了m p l s i 作组，负责开发和制定有关m p l s 的标准，目前形成的标准草案主要是关于m p l s 技术的基本实现，包括标记的定义和编码、 标记分发协议规范、m p l s 体系机构、m p l s 基本应用等【4 l 。目前m p l s 工作组的工作重点 己经从原理技术的基本实现，转移到m p l s 技术的应用中来，主要是面向m p l s 如何更有效 的提供增值服务、m p l s 在局域网中的应用、m p l s 与光传输网的融合、m p l s 流量工程的 具体应用等。 在流量工程应用方面，i e t f 已制定了关于m p l s 流量工程要求的标准草案，包括网络 流量中继属性和资源属性的分析，以及约束路由的讨论，但仅限于局部的理论分析，并没 有给出关于m p l s 流量工程的系统化解决方案。另外，当前支持流量工程应用的信令协议 主要有两种；扩展c r - l d p 协议和r s v p 协议，对于这两种协议的选择以及约束参数的定义， 仍存在一些争论。m p l s 技术正在以前所未有的速度往前发展，但当前m p l s 技术的应用仍 处在初级阶段。为了发挥m p l s 技术在实施流量工程的优势，提出一个成熟的m p l s 流量工 程模型成为国外许多公司和研究机构的研究目标。 1 4 课题的研究内容 本文主要研究m p l s 流量工程的体系结构和相关的实现技术，侧重于对m p l s 流量工 程路由选择机制的研究，主要内容包括： 1 研究m p l s 技术的原理、关键技术、工作过程等，着重研究m p l s 体系结构： 2 研究流量工程的概念，原理和相关标准，以及利用m p l s 技术实施流量工程的技 术和方法等； 3 研究m p l s 流量工程的路由算法，特别是针对最小干扰路由算法( m i r a ) 的不足， 提出一种改进的最小干扰路由算法e m i r a ，通过对特定网络模型进行了仿真并 与m i r a 的相关性能指标进行了比较。 2 南京邮电大学硕士研究生学位论文 第一章概述 1 5 课题的研究意义 m p l s 对流量工程有十分重要的意义，其提供了流量工程动态实现的可能。m p l s 为 流量工程技术在i n t e r n e t 中的实施带来了以下便利： 1 精确的标签交换路径l s p ，不受基于目的地址的包转发的限制并且可以很容易 地通过手工配置来创建，或由下层协议自动完成； 2 l s p 可以有效地维护； 3 + 流量中继可以被创建并映射到l s p ； 4 可以建立一个和流量中继有关并调节它们行为特性的属性集； 5 可以建立一个和资源相关的属性集，用来约束l s p 的布置和上面通过的流量中继； 6 m p l s 允许流量合并和分解，而传统的基于目的地址的i p 转发仅允许合并； 7 将约束路由框架和m p l s 集成相对容易； 8 一个好的m p l s 流量工程实现能提供比其它竞争方案低得多的维护费用。 1 6 论文结构安排 论文的主要内容分为六章。第二章多协议标签交换技术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 流量工程的最小干扰路由的改进算法e m i r a 并在仿真 网络上对该模型进行了相关性能指标比较和分析。晟后第六章对全文作了总结，并对需要 深入研究的问题作了展望。 南京邮电大学硕士研究生学位论文 第= 章多协议标签交换技术 第二章多协议标记交换技术 2 1m p l s 产生及其标准化5 1 截至1 9 9 6 年秋季出现了很多不同的i p 交换方案，分别由i p s i l o n 和计算机业界公司( 如 c i s c o 、i b m ) 提出。其中一些是流驱动方案。主要采用基于硬件的a t m 交换技术为端到 端的主机和应用业务流提供了改善的性能和更多的带宽；其他则是拓扑驱动方案，主要基 于路由器和选路协议来提高业务流的吞吐量。总的来说，这些不同的方案都采用一个简单 的标记交换方式。所有这些方案都意识到将选路和交换综合起来具有极大的优点。选路当 然是i n t e m e t 的要求所在，而交换则提供便宜的、高容量的分组信元转发硬件。1 9 9 6 年1 2 月份举办了一个关于标记交换的会议。之后，i e t f 成立了一个从事综合选路和交换问题研 究的工作组。并将标记交换以多协议标记交换m p l s 来命名。 1 9 9 7 年i e t f 提出m p l s 以后，有关m p l s 技术的协议标准草案和规范已经有1 4 0 多个， 并且在1 9 9 9 年就有厂商推出m p l s 设备。这种进展速度是毗前任何一种技术所没有的。 在2 0 0 0 年以前，m p l s 的标准化制定工作仅由i e t fm p l s t 作组完成。m p l s - i - 作组成 立于1 9 9 7 年3 月，当时的主要任务和工作重点是研究制定m p i s 技术的实现规范，使得这种 新的网络技术能够达到： 灵活的网络层路由选择； 高效的分组交换转发( q o s 保障) ； 有效的网络管理； 强大的网络扩展能力； 有效的增值服务提供能力； 兼容性好。 这些目标现在看来由m p l s 技术实现基本没有问题。目前，m p l s i 作组的工作重点已 从原来技术的基本实现转移到m p l s 技术的应用上来，主要是m p l s 直i 何更有效地提供增值 服务、m p l s 在局域网中的应用、m p l s 与光纤传输网( o t n ) 的融合、m p l s 网络流量工 程的具体应用等。 i p 技术到现在已经在i n t e m e t 上占了绝对的领导地位，m p l s 技术的提出又使得i p 可以 为用户提供如语音传输、视频会议、多媒体等实时业务，并且其q o s 保障可以达到电信级。 因此，i t u t 各研究组在1 9 9 9 年底的总结会上进行了未来研究工作的战略转移，全面开展 4 南京邮电大学硕士研究生学位论文第二章多协议标签交换技术 有关i p 标准化方面的研究工作，其中作为全球信息基础设施( o i ) 和b i s d n 的主导研究组 p t u ts g l 3 d 组将m p l s 歹j 为2 0 0 0 - - - 2 0 0 3 年的重点研究课题，并一致同意将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 ) c r l d p ( c o n s t r a i n e dr o u t e - l d p ) 作为公网传输标准信令。 为了更好地研究发展m p l s 技术，协调各厂商之间的利益和统一思想，2 0 0 0 年3 月以 l u c e n t 公司为首的有关机构联合成立了m p l s 论坛。论坛的基本成员为计算机网络及电信通 信软件、设备制造商和i s p 及研究开发机构。 2 2m p l s 基本原理 2 2 1m p l s 中常用术语 首先，我们简单介绍一些在m p l s 网络中经常使用到的概念和术语。 1 l a b e l ：标记，也称为标签，是一个简短的、固定长度大小的、具有本地意义的标 识符： 2 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 网络中获得的处理方式是完全相同的； 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 网络中部，如图2 一l 中所示，它提供标记交换、标记分发功能； 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 络同其它网络的 边缘设备，如图2 1 中所示，它提供流量分类和标记的映射( 作为入口) 、标记的 移除( 作为出口) 功能。 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 的标记以及它们之间的链路组成； 6 l i b ( l a b e li n f o r m a t i o nb a s e ) ：标记信息库，作用类似于路由表，其中包含各个 标记所对应的各种转发信息，每个入口标记对应一个条目，包括出口标记、出口 接口等信息。 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 0 1 ) ：标记分发协议，相当于传统网络中的信令协 议，负责标记的分发与维护。m p l s 定义了一种专门的标记分发协议一l d p 【6 l ，但 是i e t f 并没有规定m p l s 只局限于这一种协议，另外还有几种协议也处于标准化进 程之中，血1 c r l d p 7 1 、r s v p 的扩展 8 】等。 8 流( s t r e a m ) ：沿着同一路径、属于同一f e c 的一组包被视为一个流。 南京邮电大学硕士研究生学位论文 第二章多协议标签交换技术 9 上游( u p s t r e a m ) 和下游( d o w n s t r e a m ) ：上游和下游是根据s t r e a m n 流向而定的。 在一个r 1 r 2 r 3 的网络拓扑中，无法孤立地说谁是谁的上游节点，必须针对某一 个s t r e a m 。当s t r e a l - l 从r 1 经过r 2 再流向r 3 时，r 1 是r 2 的a z 游节点，i 毪是r 3 的上 游节点。但对于从r 3 流向r 1 的s t r e a r n _ 2 而言，r 3 则是r l 的上游节点。 2 2 2 网络结构 m p l s 网络的典型结构如图2 1 所示。m p l s 的基本组成单元是m p l s 标记交换路由 器( l s r ) ，由m p l sl s r 构成的网络区域称为m p l s 域，位于m p l s 域边缘与其它网络 或用户相连的l s r 称为边缘l s r ( l e r ) ，而位于m p l s 域内部的l s r 则称为核心l s r 。 l s r 既可以是专用的m p l sl s r ，也可以是由a t m 交换机升级而成的a t ml s r 。m p l s 网络与传统i p 网络的不同主要在于m p l s 域中使用了标记交换路由器，域内部l s r 之间 使用m p l s 协议进行通信，在m p l s 域的边缘由l e r 进行与传统i p 技术的适配。 m p l s 边缘路由嚣 ( l e r ) 标记交换路由器 ( l s r ) 图2 1m p l s 网络结构 6 点 南京邮电大学硕士研究生学位论文第二章多协议标签交换技术 2 2 3 工作过程 m p l s 使用标记来转发数据包。当传统i p 数据包进入m p l s 网络时，入口边缘l s r 仅仅一次性地把这个数据包分配给一个特定的等价转发类( f e c ) ，而且f e c 被编码成一 个固定长度的值，这个值就被叫做标记。标记分发协议( l d p ) 预先会将相应f e c 的标记 分配到网络的相应节点上，并存放在其标记信息库( l i b ) 中。在数据包通过m p l s 中间 节点时，数据包的网络层包头将不再被作进一步的分析，只需要检索l i b 中出口节点信息， 并用新标记替换旧标记，数据包就被转发到下一个节点。 m p l s 的工作过程如下所述： 1 标记分发协议( l d p ) 和传统路由协议( o s p f 等) 一起，在各个l s r 中为有业务 需求的等价转发类( f e c ) 建立路由表和标记映射表： 2 入口边缘l s r 接收数据包，判定其所属的f e c 。基于路由和策略的需求，边缘l s r 有选择地放入一个标记到数据包头中，形成m p l s 标记分组，然后转发； 3 核心l s r 对标记分组不再进行任何第三层处理，只是根据数据包的标记以及标记 转发表，通过交换新旧标记对其转发； 4 在出口边缘l s r 上，数据包中的标记将被去掉，边缘l s r 执行第三层查找，并转 发数据包至外部的下一跳路由器。 下面给出一个数据包在m p l s 网络中转发的具体过程，如图2 2 所示。 入端口 入标记i p 地址段出端口出标记 o 1 9 9 5 5 13 o1 4 5 6 5 15 入端口入标记i p 地址段出端口 出标记 l 7 1 9 9 5 5 o l91 4 5 6 5 o 图2 2m p l s 转发数据包过程 在图2 2 中，一个流入m p l s 网络的数据包到达边缘l s r l 时，它将分析包的目的地址前辍 7 南京邮电大学硕士研究生学位论文第二章多协议标签交换技术 ( 1 9 9 5 5 ) ，然后查看交换表中的i p 地址段，加入对应的标记3 ，然后通过端口1 转发出去。 当l s r 2 接收到该数据包，读取这个标记，然后在交换表中查找对应的标记，用标记7 取代3 ， 从端口1 转发。在出口处，l s r 3 查看标记7 。将标记弹出，执行第三层查找，从端i ：1 0 转发 数据包。注意在网络的核心，i p 的转发信息只是用来建立标记交换表，并没有直接参与转 发。这个例子说明了数据包怎样在一个口路由网络中转发，在a t m 网络中，工作原理是一 样的，但数据将会在进出的结点上被分段和重组。在一个基于m p l s 的a t m 网络上，m p l s 标记取代a t m 信元v p i v c i 头，信元转发的决定与上例所讲的机制相同。 2 3m p l s 体系结构 2 3 1 标记与标记栈 1 标记 标记是m p l s 的核心技术之一，标记的使用类似于a t m 交换中对于v p i n c i 的使用，用 来提高数据分组的转发速度和性能。由于m p l s 是为了在任何第二层协议上工作而设计的， m p l s 未强制规定一个具体的标记格式。实际上，标记编码严格遵循两个相邻l s r 之间的相 互约定，并且仅具有本地意义。 标记的格式取决于分组封装所在的介质。一个数据包通常有两种方式被打上标记：一 是利用数据链路层( 如a t m 、帧中继) 包头中的现有字段，例如，a t m 封装的分组( 信元) 采用信元头的虚拟路径标识符，虚拟信道标识符( v p w c i ) 字段作为标记，如图2 3 ：帧 中继p d u 采用帧头的数据链路连接标识符( d l c i ) 字段作为标记。另一种是对于那些没有 内在标记结构的介质( 如以太网、p p p ) 封装，则可以在数据链路层与i p 层之间插入一个 特殊的填充( m p l ss h i m ) 格式。图2 4 给出7 4 b y t e s 填充标记的格式。 l a b e l i g f cv p iv c ip 1 1c l p既c d a t a l 图2 - 3a t m 的标签格式 8 南京邮电大学硕士研究生学位论文第二章多协议标签变抉技术 图2 4m p l s 填充标签( m p l ss h i m ) 格式 填充标记中的各字段定义及作用如下： l a b e l ：标记值，2 0 比特。 e x p ：e x p e r i m e n t a l ，以前称为c o s ( c l a s so fs e r v i c e ，服务等级) ，类似i p 中的t o s ( t y p e o fs e r v i c e ，服务类型) 字段，3 比特。 b s ：b o t t o mo f s t a c k ，栈底标识符，1 比特。 t t l ：t i m et ol i v e ，生存周期，8 比特。 m p l s 技术最显著的优点之一就在于能够分配标记，这具有非常特殊的意义，不同的 标记可以区分路由信息、应用类型和业务级别。而且标记只受本地局限，所以用尽标记的 可能性几乎没有，这种特性是实施i p 增值服务的基础，! t f l q o s ，v p n 平d t e 。 2 ，标记栈 帧中继只有一级标记，即数据链路连接标识符( d l c i ) ；a t m 有两级标记，即虚通路 标识符( v p i ) 和虚信道标识符( v c i ) 。而m p l s 支持按先进后出( f i l o ) 组织的标记堆 栈，称为标记栈。每个标记中的栈底标志字段用于表示该标记是否在栈底。标记栈顶部的 标记值为有效标记，l s r 根据栈顶标记来转发包。l s r 只根据数据分组中的栈顶标记来转发 数据分组，不用考虑栈顶下是否还有标记，或者曾经是否有标记在栈顶标记之上。m p l s 对数据分组标记栈的操作有三种： 压栈( p u s h ) ：包在进入某个m p l s 域时，向标记栈中压入一个标记，占据栈顶位置， 这时栈深度加l 。 替换( s w a p ) ：在同一个m p l s 域内的l s r 只查看和替换栈顶的标记，对于栈中其它的 标记项则忽略。 弹栈( p o p ) ：包离开同一个m p l s 域时，则执行出栈操作，弹出栈顶的标记，标记栈 恢复原来进入m p l s 域之前的情况。 这样，m p l s 就可以容易地实现网络分层，标记栈的深度表示网络的层次：包通过t u n n e l 或某个低一层m p l s 网络的时候，标记栈的深度将增加；反之，包回到上层网络时，深度 9 南京邮电大学硕士研究生学位论文第二章多协议标签交换技术 减小。各层之间不需要协商，从而使业务的组合简单而且实用。标记栈的另一个作用体现 在业务快速恢复上，采用标记栈和隧道概念，我们可以用一条旁路隧道来承载业务量均衡 隧道，从而提供备用路径。 2 3 2 节点结构 m p l s 网络中的节点主要由标记交换路由器组成，m p l s 节点有两个结构平面：m p l s 转发平面和m p l s 控制平面。除了可以交换带有标记的数据包外，m p l s 节点还可以执行第 三层路由选择或者第二层交换。图2 5 显示了一个m p l s 节点的基本结构 9 1 。 控制平面 图2 5m p l s 节点结构 路由选择 信息交换 标记绑定 信息变换 输出i p 数 据包 辅出被标记 的数据包 m p l s 转发平面负责根据由m p l s 节点维护的标记信息库( l i b ) 来转发带有标记的数 据包，标记信息库和标记转发算法是转发平面的两个重要组件。标记转发算法不仅利用了 包含在l i b 中的信息，还利用了包含在标记值里的信息。 m p l s 控制平面负责生成和维护标记信息库。所有的m p l s 节点必须运行i p 路由选择协 议来和网络中其它m p l s 节点交换i p 路由选择信息，链路状态路由选择协议( 如o s p f 和 i s i s ) 是m p l s 网络中i p 路由协议的一种合适选择，因为它们可以为每个节点提供整个网 络的拓扑视图。标记绑定信息的发布使用标记分发协议( l d p ) ，因为传统的链路状态路由 选择协议是在一组路由器( 并不要求必须是邻接的) 之间扩散路由选择信息，而标记绑定 信息仅仅在邻接的路由器之间发布，所以链路状态路由选择协议不适合发布标记绑定信 息。m p l s 控制平面除了包含上述的路由协议和标记分发协议外，根据m p l s 节点支持的功 能还可能包括下列模块：单播路由选择模块；多播路由选择模块；流量工程模块： 虚拟专用网络( v p n ) 模块；q o s 模块。 1 0 南京邮电大学硕士研究生学位论文 第二章多协议标签交换技术 2 3 3 标记交换机制 m p l s 用的转发机制，即标记交换。从典型的帧中继和a t m 的性能和容量来看，实现 标记交换是一个快速而简单的转发过程。没有必要像传统i p 选路那样分析分组头中的变长 部分。标记作为一个整体( 也可能是标记中的附加字段，如t 1 1 l 和e x p ) 由交换机组件处 理。即使一个分组包含一个多级的标记栈，m p l s 设备也只负责处理栈中的栈顶标记。 沿着一个l s p 转发分组的过程是：在l s p 入口处，给分组帖上一个标记，产生一个深度 为m 的标记堆栈。在l s p 上的中间m p l s 节点接收和处理这个分组，只有堆栈的顶部标记被 处理，并与对应于下一节点l s r 的新标记进行交换。l s p 出口的l s r 根据堆栈中的下一个标 记的内容做出转发的决定。这意味着l s r 出口只需要弹栈就可以得到栈中的下一个标记。 如果出口节点告诉仅次于最后一个l s r 弹栈，就可以获得一个更好的优化方案，称作倒数 第二跳弹栈。然后分组到达出i 二i l s r 设备并携带用于转发分组的己经在堆栈中项部的标记。 这样就节省了出口设各必须处理未必有用的标记表查询时间。 每个l s r 节点依据n h l f e ( n e x th o pl a b e lf o r w a r d i n ge n t r y ) 来转发数据分组，包含 以下内容： 1 ) 数据分组的下一跳( n e x th o p ) ； 2 ) 转发数据分组时所使用的d l l ( d a t al i n kl a y e r ) 封装； 3 1 转发数据分组时所使用的标记栈的编码方式； 4 】对数据分组采取的标记栈操作( 压栈、替换、弹栈) 。 数据分组在进入m p l s 时，首先被归类为不同的f e c ，然后把这些f e c 同n h l f e 相映 射。f e c 同n h l f e 的映射关系有两种：入标记映射( i l m i n c o m i n gl a b e lm a p ) 和f e c 到 n h f l e 映射( f t n ) ，前者用来在核。b l s r 转发已经标记化的分组，后者用来在边缘l s r 转 发未标记化的分组，但在转发之前分组已经打上标记了。 2 3 4 路由选择机制 路由选择( r o u t es e l e c t i o n ) 机制是指为特定f e c 选择l s p 的方法。m p l s 支持两种路 由选择方式建_ 立l s p ：逐跳路由( h o p b y h o pr o u t i n g ) 和显式路由( e r ：e x p l i c i tr o u t i n g ) 。 逐跳路由是目前i p 网中的传统路由选择机制，每个l s r 独立地为给定的f e c 选择下一 跳路由。m p l s 之所以保留了这种传统的路由选择机制，是考虑到以下几个方面的原因： 还存在一些传统的网络需要这种路由选择机制； 妻塞塑皇查堂堡主竺塞圭堂垡堡奎苎三童墨堡鲨堡竺奎垫垫查 安全过滤设备( 如防火墙) 需要第三层路由； m p l s 需要和非m p l s 的网络保持兼容。 运用显式路由时每个l s r 不能独立地选择下一跳，而是由一个l s r ( 通常是l s p 的入节 点) 决定l s p 。如果确定出整条l s p 贝j i 称为精确的( s t d c t ) 显式选路，若只确定l s p 中的部 分l s r ，则称为松散的( 1 0 0 s e ) 显式选路。而l s p 中的转接节点只需进行标记交换，无须 考虑路由。这样可以大大提高网络的转发效率，而且由于路由只由少数节点完成，运营商 可以方便地制定统一的路由策略和进行整体的业务量规划。 显式路由技术与i p 协议中定义的源路由( s o u r c er o m i n g ) 技术相似，但又存在着区别： 源路由技术要求在网络中传输的每一个i p 报文头部要携带用于明确标识整条路径的i p 地 址，其传输开销太大，使得网络负载难以承受，因而难以得到实际应用。而m p l s 仅在建 立特定l s p 时，才要求在标记分发信令中携带明确的标记交换路径信息，而非具体针对每 个i p 传输报文，因此m p l s 中的显式路由技术得到了广泛的实际应用。 2 3 5 标记分发协议 标记分发协议1 6 】( l d p ) 是一个单独的控制协议，l s r 应用它交换和协调f e c 与标记间 的绑定信息，使得对等l s r 就一个特定标记值达成一致，这个标记指示出数据包所属的某 个特定f e c 。 2 3 5 1l d p 消息类型 l d p 协议主要使用四类l d p 消息：发现消息( d i s c o v e r ym e s s a g e ) 、会话消息( s e s s i o n m e s s a g e ) 、公告消息( a d v e r t i s e m e n tm e s s a g e ) 、通知消息( n o t i f i c a t i o nm e s s a g e ) 。 i 发现消息：在l d p 的发现过程中，l s r 之间可以通过周期性地发送h e l l o 消息来 表明它们在网络中的存在。h e l l o 消息使用子网组播地址，以u d p 包的形式发往其它l s r 。 当其它l s r 收到消息后，会回应一个h e l l o 信息，该信息内容除了信息识别码外，还有双 方协定的多久时间传送或接收次h e l l o 消息，以表明彼此在网络中的存在。 2 会话消息：主要用于两个l s r 之间建立、维持和拆除连接关系。当两个l s r 建立t c p 连接后，将通过初始化信息来协商、交换彼此的会话参数，包括l d p 协议版本、标记分发 的方法、定时器值、标记的范围( 使用a t m 网络时是v p i v c i 范围，使用帧中继网络时是 d l c i 范围) 等。l d p 建立会话正常连接后，仍需要在协商期限内传送保持存活信息。以确 保各l s r 能正常工作。 3 公告消息：用于建立、交换和删除f e c 与标记间的对应关系。在标记交换路径建立 1 2 南京邮电大学碉士研冤生学位论文 第二章多协议标签交换技术 过程中会用到标记请求消息和标记映射消息，对f e c 与标记间绑定的删除可以通过标记撤 销消息( l a b e lw i t h d r a wm e s s a g e ) 和标记释放消息( l a b e lr e l e a s em e s s a g e ) 。 4 通知消息：用于提供网络状态、诊断和差错等信息。例如在保持存活信息计时器 满或l s p 出现故障不通时，l s r 便会发送相应的错误信息，通知l d p 对等实体。 上述四种l d p 消息的传送方式，除了发现消息是通过u d p 数据包组播传送外其余三种 l d p 消息都是以t c p 数据包传送，阻增加信息传送的可靠性。 2 3 ，5 2 标签分发和管理 m p l s 中有两种标签分发方式：下游l s r 明确提出标签请求的l s r 分配“f e c 标签”绑 定，这种方式称为下游按需( d o w n s t r e a md e m a n d ) 标签分发；下游l s r 没提出标签分 配的l s r 主动分配f e c 标签绑定，这种方式称为下游自主( d o w n s t r e a mu n s o l i c i t e d ) 标签 分发。 m p l s 在标签管理中也有两种方式： i 标签控制方式 标签控制方式也分为两种：独立和有序。 使用独立的l s p 控制时，每个l s r 可以在任何时候向和它相连的l s r 通告标签映射。如 工作在独立下游按需标签分发控制方式下，l s r 可以立刻对上游的标签请求消息发出响应， 而不需要等待来自下一跳l s r 的标签映射消息。当工作在独立下游自主标签分发控制方式 下，只要l s r 准备好对于特定f e c 进行标签转发，l s r 就可以向和它相连的l s r 通告特定 f e c 标签映射消息。使用独立标签控制允许l s r 在收到下游的标签映射消息之前，就可以 向上游通告标签映射消息。 当使用有序的l s p 控制时，只有当l s r 收到特定f e c 下一跳的特定f e c 标签映射消息或 者l s r 是l s p 的出口节点时，l s r 才可以向上游发送标签映射消息。如果l s r 既不是特定 f e c 的出口节点也不存在对于特定f e c 的标签绑定，那么l s r 在对特定f e c 进行f e c 标签 绑定并向上游l s r 返回特定f e c 标签绑定消息之前，必须等待收到下游l s r 的特定f e c 标 签响应消息。 2 标签保持方式 标签保持方式指l s r 对收到的但目前暂无用的“标签f e c 绑定”的处理方式。主要有两 种：保守标签保持方式丢弃所有无用的“标签f e c 绑定”：自由标签保持方式将无 用的“标签f e c 绑定”保存起来以供后用。 保守标签保持方式 在下游自主标签分发方式中，从任何相邻l s r 都可以收到对于所有路由的标签映射消 南京邮电大学硕士研究生学位论文 第二章多协议标签交换技术 息。当使用保守标签保持方式时，只有用于数据转发的“标签- f e c 绑定”才会被保留，即接 收到的“标签f e c 绑