（电路与系统专业论文）基于mpls网络负载均衡动态路由算法研究.pdf

南京邮电大学硕士论文摘要 摘要 随着网络规模和网络流量的快速增长，网上传输的业务流中越来越多的是具有q o s 要 求的多媒体业务。但是目前的i p 网络技术不能充分利用现有的网络资源，经常导致有些链 路被过度使用，有些链路却空闲不用的负载不均衡局面，业务的服务质量也无法得到保证， 流量工程就是为此而提出的。流量工程实施的目标是实现网络操作的高效率和优化网络资 源的利用。多协议标签交换( m p l s ) 被公认为是目前实现流量工程的最有力工具。m p l s 负载均衡路由是这样一种技术：它是将业务流按照某种分割比例分配到源节点和目的节点 之间的多条路径上同时进行传输。这种负载均衡路由技术可以更好地平衡网络负载，更加 有效的利用网络资源，也可以增加业务连接请求的接入量。 本文首先阐述了m p l s 的主要概念、技术以及m p l s 流量工程的实现机制，分析了传 统的静态和动态路由算法及缺点，在此基础上介绍了约束路由。其次详细论述了多径路由 算法，其中本文所参考的算法为e b 和m p b f 算法。最后详细介绍了本文提出的一种新的 负载均衡路由算法，并通过m a t l a b 仿真软件对算法性能进行了模拟，同时将该算法与 m p b f 算法进行比较。比较结果显示，新的负载均衡路由算法提高了网络资源利用率，在 一定程度上降低了请求带宽拒绝率。 关键词：多协议标签交换，流量工程，负载均衡，链路带宽利用率 南京邮电大学硕士论文 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 dg r o w t ho ft h en e t w o r ks c a l ea n dt r a f f i c ，t h e r ea r em o r ea n dm o r em u l t i m e d i a a p p l i c a t i o n s q u a l i t yo fs e r v i c eg r a r a n t e e sa r er e q u i r e db yt h en e t w o r k b u tt h ep r e s e n ti pn e t w o r k c a r l tm a k ef u l lr e s o u r c eu t i l i z a t i o n ，w h i c ha l w a y sl e a dt ot h eu n b a l a n c e dt r a f f i cd i s t r i b u t i o n ， s o m el i n k sg e t t i n go v e r - u t i l i z e d ，w h i l eo t h e r sr e m a i n i n gu n d e r - u t i l i z e d t h i sl e a d st ot h eq u a l i t y o fs e r v i c e sn o tg u a r a n t e e d s ot r a f f i ce n g i n e e r i n gi sp r o p o s e d i t sp u r p o s e sa r et oi m p r o v et h e n e t w o r kp e r f o r m a n c et h r o u g ho p t i m i z i n gr e s o u r c eu t i l i z a t i o no ft h ee x i s t i n gn e t w o r k s m p l s h a sb e e nr e g a r d e da sap o w e r f u lt o o lt ot r a f f i ce n g i n e e r i n g m p l sl o a db a l a n c i n gr o u t i n gi ss u c h ak i n do fr o u t i n gt e c h n i q u et h a tc a nd i s t r i b u t et h et r a f f i cf l o wt om u l t i p l ep a t h sb e t w e e ns o u r c e n o d ea n dd e s t i n a t i o nn o d e ， a n dt r a n s f e rt r a f f i ct h r o u g ha l lt h e s ep a t h ss i m u l t a n e o u s l y t h i s r o u t i n gt e c h n i q u eo fl o a db a l a n c i n gn o to n l yc a nb a l a n c en e t w o r kl o a da n dm a k ef u l l u s eo f n e t w o r kr e s o u r c e s ，b u ta l s oi n c r e a s ea c c e p t a n c eq u a n t i t y t h i sp a p e rb e g i n sw i t hi n t r o d u c i n gm p l s sm a i nc o n c e p t s ，t e c h n i q u e sa n di m p l e m e n t i n g m e c h a n i s mo fm p l st e ，i n t r o d u c e st r a d i t i o n a ls t a t i ca n dd y n a m i cr o u t i n ga l g o r i t h m sa sw e l la s t h e i rd i s a d v a n t a g e s ，t h e np r e s e n t sc o n s t r a i n tr o u t i n g s e c o n d l y , l o a db a l a n c i n gr o u t i n gi s d i s c u s s e d ，p a r t i c u l a r l ye ba n dm p b fa l g o r i t h m sr e f e r e n c e di nt h ea l g o r i t h m s f i n a l l y ，w eb r i n g s f o r w a r dan e wd y n a m i cr o u t i n ga l g o r i t h mo fl o a db a l a n c i n ga n ds i m u l a t ei t sp e r f o r m a n c e t h r o u g hm a t l a b ，a tt h es a m et i m ec o m p a r e si tw i t hm p b fa l g o r i t h m s t h ec o m p a r er e s u l t s s h o wt h a tt h en e wd y n a m i cr o u t i n ga l g o r i t h mo fl o a db a l a n c i n gi m p r o v e su t i l i z a t i o no fn e t w o r k r e s o u r s e s ，i ta l s or e d u c e se n d t o e n dd e l a yt oac e r t a i ne x t e n t k e y w 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 g ，l o a db a l a n c i n g ， b a n d w i d t hu t i l i z a t i o no fl i n k 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名： 导师签名：上靼! k 日期：捌 南京邮电大学硕士论文 第一章绪论 1 1 课题的提出 第一章绪论 对网络的大量研究表明，造成目前网络拥塞的原因主要有两个，一个是网络资源不足， 不能满足客户流量的要求；另一个是传统网络路由算法导致的流量集中到部分链路上造成 拥塞。 对于第一种拥塞，通常采用以下两种途径解决：( 1 ) n 络扩容；( 2 ) 使用经典的拥塞控制 技术。网络扩容是指使用更加先进的交换机、路由器或采用更高带宽的传输介质，实现起 来非常简单。如果这些硬件设施价格低廉，或网络中的资源己接近饱和时，采用这种方案 比较合适。经典的拥塞控制技术是采用对业务请求加以控制的方法，保证业务量与可使用 的资源相匹配。经典的拥塞控制技术包括窗口控制、路由器队列管理等。 对于第二种拥塞，是由负载的分布不均衡引起的，单纯靠增加网络容量，显然不是根 本的解决方法，必须通过网络的调节和控制功能，使流量分布更加合理，才能有效的解决 这一问题。流量工程就是为此提出的。流量工程是一个控制业务流如何经过网络，以达到 优化网络资源利用、提高网络性能目的的过程。流量工程通过调节网络流量的分布来调节 网络资源的使用，以减轻拥塞，提高资源的使用效率。当拥塞最小化时，网络的各q o s 指 标将得到改善，分组丢失将减少，传输时延也将缩短，而吞吐量则将增大。这样，终端用 户所感受到的网络服务质量将得到显著的增强。 当前，i t u t 、i e t f 、m p l s 以及各大网络行业协会都非常关注流量工程问题，i e t f 为此专门成立了t e 工程组。随着近年来路由器性能的提高，i n t e r n e t 骨干网变为以高速 路由器为核心的网络。为了在无连接的i 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 负载均衡路由是这样一种路由技 术：它是将业务流按照某种分割策略分配到源节点和目的节点之间的多条路径上同时进行 传输。这种负载均衡路由技术可以更好地平衡网络负载，更加有效地利用网络资源，也可 以增加业务连接请求的接入量。 南京邮电大学硕：l 论文第一章绪论 1 2 国内外研究现状 目前国内外已经提出了多种多路径路由算法。最早提出的路由算法是等代价多路径路 由算法( e q u a l - c o s t m u l t i p a t h ( e c m p ) r o u t i n g ) 【2 】o 它是将业务流平均分配在多条具有相 等费用的路径上同时传输。这种路由算法可以利用o s p f 和i s i s 路由协议，另外一些路 由器拓展技术还可以使e c m p 支持路由信息协议( r i p ) 及其他的一些路由协议。文献 3 】 提出了一种应用于面向连接的动态多径路由算法，当网络处于低流量负载时使用最短路 径，而当最短路径发生拥塞时就转而使用多条路径。但是此文献只考虑了连接层或呼叫层 的路由和转发，而并未考虑流层的路由和转发。文献 4 提出了一种时间约束条件下的多路 径q o s 路由算法，但是这种方案由于在接收端对数据包的动态缓存而增加了网络开销。 对于多径之间的负载均衡问题目前也得到了广泛的研究并提出了一些成熟的算法。文献 5 】 中的m p l s - - o m p ( 最优多路径) 算法是根据由哈希计算得到分配到每条路径上的数字空 间的数量来确定多径之间的流量分割比例。w i d j a j a 和e l w a l i d 则提出了一种流量分割协议 “m a t e ”【6 1 ，即m p l sa d a p t i v et r a f f i ce n g i n e e r i n g 。m a t e 的主要目标就是通过均衡源 和目的路由器间的多条路径间的负载来避免网络中拥塞的发生。在m a t e 中，入口路由器 周期性地向出口路由器发送探测包，探测包到达出口路由器之后又由出口路由器反向发送 回入口路由器。根据返回的探测包中的信息，入口路由器就可以计算l s p 的特征并使路 径间的负载达到均衡。 1 3 课题的主要工作及安排 论文的主要内容分为五章。第二章阐述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 n t e m e t 网络路由体系结构的变化，i n t e m e t 可扩展性的要求以及新的路由功能的需求， 还有如q o s 等各种新型服务的要求，所有这些需求推动着包括m p l s 在内的各种技术的 诞生和发展。 2 1m p l s 产生的技术背景 在1 9 9 6 年，i p s i l o n 公司( 目前己被n o k i a 收购) 推出了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 m e r 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 ”为基础，并结合i b 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 ( 7 】是一种基于标签的转发技术，与a t m 交换类似，它引入了固定长度的短标签 ( l a b e l ) 作为在m p l s 网络中进行数据转发的依据。之所以称m p l s 为“多协议9 9 9 是因为 m p l s 可以支持网络层层面上的多协议( i p v 4 、i p v 6 、i p x 等) ，同时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 o l ，p p p ) 、以太网等，它可以 支持任何能够在网络层实体间传递网络层分组的第二层媒体，而并非针对任何一种链路层 技术。m p l s 将第二层交换能力和第三层路由技术完美地结合起来，在i p 路由和控制协议 的基础上提供面向连接的交换，保持了i p 技术的灵活性、可扩展性和a t m 的快速交换、 流量控制性能。 2 2m p l s 基本原理和工作过程 2 2 1 基本原理 m p l s 是一个可以在多种第二层媒质上进行标签交换的网络技术。这一技术结合了第 二层的交换和第三层路由的特点，将第二层的基础设施和第三层的路由有机地结合起来。 南京邮电大学硕士论文第二章m p l s 概述 第三层的路由在网络的边缘实施，而在m p l s 的网络核心采用第二层交换。 m p l s 是一种特殊的转发机制，它为进入网中的i p 数据包分配标签，并通过对标签的 交换来实现i p 数据包的转发。在m p l s 中，从i p 包到f e c 的映射只在l s r 入口处 进行操作，而且f e c 被转换成一个固定长度的标签。标签被粘贴到i p 分组上，入口路 由器不是将f e c 映射到下一节点的路由器，而是在分组上添加表示分组归属f e c 的一 个标签。在下一节点的路由器上，因为分组已经与f e c 关联，所以没有必要再检查分组 网络层的内容。 2 2 2 工作流程 m p l s 网络采用标准分组处理方式对第三层的分组进行转发，采用标签对第二层分组 进行交换。m p l s 是通过以下三个步骤来完成标签交换的： 1 在分组上添加表示分组归属的f e c 关联标签； 2 使用标签值转发分组； 3 检索一个包含出口和新标签的连接表并用新标签替换旧标签； 下面通过图2 1 所示的例子来进一步了解分组是怎样被转发的。 图2 1标签分组转发过程 在图2 1 中，一个流入的分组到达边缘l s r 时，它将读分组的目的地址的前缀， 1 9 2 1 6 8 ，下一步这个边缘l s r 查看交换表中的目的地址，加入对应的标签2 ，然后通过 端口l 发出。在中心的l s r 读到这个标签，然后在交换表中查找对应的标签，然后用标 签5 取代2 ，从端口1 转发。在出去的边缘l s r 查看标签5 ，在此除去分组的标签， 从端口2 出去。注意在网络的核心，i p 的转发信息只是用来建立标签交换表，并没有直 接参与转发。这个例子说明了数据怎样在一个路由的网络中转发。具体地来讲，m p l s 的 工作流程又可以分为几个方面：即网络的边缘行为、网络的中心行为以及如何建立标签交 南京邮电大学硕士论文第二章m p l s 概述 换路径( l s p ) 【引。 在网络边缘的节点就称做为标签边缘路由器( l e r ) ，而网络的核心节点就称为标签交 换路由器( l s r ) 。图2 2 为m p l s 网络的结构图。 图2 - 2 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 ，l e r 都 建立条独立的l s p 穿过网络，到达目的地。数据包分配了一个f e c 后，l e r 就可以 根据标签信息库( l i b ) 来为其生成一个标签。标签信息库将每个f e c 映射到l s p 下 - n g 的标签上。转发数据包时，l e r 检查标签信息库中的f e c ，然后将数据包用l s p 的 标签封装，从标签信息库所规定的下一个接口发送出去。 2 网络的核心行为 当一个带有标签的数据包到达l s r 时，l s r 提取入标签，同时以它作为索引在标签信 息库中查找。当l s r 找到它的相关信息后，取出出标签，并由出标签替代入标签，从标 签信息库中所描述的下一跳接口送出数据包。最后，数据包到达了m p l s 域的另一端，在 这一点上，l e r 除去封装的标签，仍然按照i p 包的路由方式将数据包继续传送到目的地。 南京邮电大学硕七论文第二章m p l s 概述 3 建立标签交换路径的方式 建立标签交换路径的方式主要有两种：一种是以h o p b y h o p 路由方式建立l s p ：另 外一种就是以显式路由方式建立l s p 。一个h o p b y h o p 的l s p 是所有从源节点到一个特 定目的节点的i p 树的一部分。另外，m p l s 允许网络的运行人员在源节点就确定一条显 式路由的l s p ( e r l s p ) 【9 1 ，以规定数据包将选择的路径。不像h o p 。b y h o p 的l s p ，e r l s p 不会形成i p 树。取而代之的，是e r l s p 从源端到目的端建立一条直接的端到端的路径。 2 3m p l s 体系结构 2 3 1 基本概念 1 标签( 1 a b e l ) ：标签是一个包含在分组中的短的、定长的、只有本地意义的标识符。 某一分组的标签代表了它所属的转发等价类，用来在一对l s r 之间进行分组交换。标签 可以封装到现有的数据链路层分组中，格式取决于分组封装所在的介质。图2 3 为通用标 签的格式1 0 i 。 其中m p l ss h i m 字段又分为： 标记标签值，2 0 比特： c o s 业务等级，3 比特； s 堆栈底标记，l 比特； 1 v r l 生存周期，8 比特； 图2 3m p l s 标签的格式 2 标签交换路由器( 1 a b e ls w i t c h i n gr o u t e r ，l s r ) l s r 是具有标签交换能力的路由器， 它是m p l s 网络的基本构成单元。在m p l s 网络中，无论是接入节点还是核心节点都是 l s r 。一个l s r 可以是一个传统的交换机( 如a t m ) 扩充i p 路由，或者是升级为支持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 ) ：f e c 是m p l s 中最重要的一个 概念，甚至可以说是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 应在共享状态发生改变的节点终止。 目前定义的f e c 要素有两类( 将来还可以再扩充) ： ( 1 ) i p 地址前缀，提供一个含有一个或多个i p 地址前缀的集合，符合其中一个或多 个i p 地址前缀的包被映射到相应的l s p 。 ( 2 ) 主机地址，以一个3 2 位的i p 地址作为单元。 4 标签空间( 1 a b e ls p a c e ) ：标签空间是指在l s r 进行标签分发过程中标签的取值范 围。标签具有局部性，因此，对于每个l s r 来说，确定标签的唯一性是非常重要的问题。 现有两类标签空间：每接口地址空间和每平台地址空间。 5 标签交换路径( 1 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 - 4 为l s p 建立过程示意图。 l i b ： ( 1 ) 标签请求 一一- 一一+ ，一 l s rl 一一jl s r 入口 出口 3 ( 2 ) 标签映射 入口 出口 35 图2 4 标签交换建立过程 l s r ) 入口出口 5 6 标签分发协议( 1 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 t l l 】) ：一个标签分发协议是由一系列 南京邮电大学硕士论文第二章m p l s 概述 的过程组成的，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 标签分发对等实体( l d pp e e r s ) ：两个l s r 通过l d p 协议进行l a b e l f e c 绑定信 息的交换，就它们所交换的绑定信息来讲，我们称这两个l s r 为标签分发对等实体。 8 标签交换( l a b e ls w a p ) ：标签交换指基本的m p l s 转发操作，它由一系列的过程组 成，包括查找l i b 决定用什么出标签替换入标签、标签封装、确定出端口和其它的数据处 理信息。 9 标签信息库( l i b ) ：它的作用类似于路由表，其中包括各个标签所对应的各种转发 信息。每个入口标签对应一个信息条目，每个条目包括出口标签、出口接口、出口链路层 信息等子条目。l i b 的内容如图2 5 所示： 入标签 入端口 i p 地址段 出端口出标签 4 11 9 2 1 6 8 o5 图2 5 标签信息厍 1 0 多协议( m u l t i p r o t o c a l ) ：多协议是指m p l s 位于传统的第二层与第三层协议之间， 其上层协议与下层协议可以是当前网络中存在的多种协议。 1 1 多协议标签交换域( m p l s 域) ：指一些邻接的l s r 组成的集合，它们之间进行 m p l s 路由和转发，而且这个集合处于一个路由或者管理域中。 1 2 上游( u p s t r e a m ) 和下游( d o w n s t r e a m ) ：上游和下游是根据s t r e a m 的流向而定的。 1 3 流( s t r e a m ) ：沿着同一路径、属于同一f e c 的一组分组被视为一个流。 1 4 流量( f l o w ) ：从一个应用流入到另外一个应用的数据称为流量。 2 3 2 节点结构 m p l s 网络中有三种节点，一是入口节点i n g r e s sn o d e ，负责为分组进行业务分类、分 发标签等工作，二是中间节点i n t e r m e d i a t en o d e ，完成标签交换等工作，三是出口节点e g r e s s n o d e ，将分组转发至目的地，解除标签。其节点结构如图2 - 6 所示。 南京邮电大学硕士论文第二章m p l s 概述 输出i p 数 据包 输出被标 记的数据 包 图2 6m p l s 节点结构 1 转发平面 m p l s 转发平面负责根据所附标记内的标记值来转发数据包。转发平面使用由m p l s 节点维护的标记转发信息库( l f i b ，l a b e lf o r w a r d i n gi n f o r m a t i o nb a s e ) 来转发带有标记的 数据包。标记交换转发组件使用的算法不仅利用了包含在l f i b 中的信息，还利用了包含 在标记值里的信息。每个m p l s 节点维护着两张表：标记信息库( l i b ，l a b e li n f o r m a t i o n b a s e ) 和l f i b 。l i b 包含了由本地m p l s 节点分配的所有的标记，以及这些标记与从邻 接m p l s 节点收到的标记之间的映射信息。l f i b 使用l i b 中所含标记的一个子集来进行 实际的数据包转发。 2 控制平面 m p l s 控制平面负责维护l f i b 表和向l f i b 表添加条目。所有的m p l s 节点必须运行 i p 路由选择协议来和网络中的所有其它m p l s 节点交换i p 路由选择信息。控制平面主要 包含信令和路由。 南京邮电大学硕士论文 第二章m p l s 概述 2 3 3 标签封装 标签是一个包含在分组中的固定长度的只有本地意义的标识符。一对l s r 必须在标签 的数值和意义上取得一致。为了在分组中携带标签或标签栈，需要对标签的编码加以规定。 目前标签栈有几种不同的编码技术，各种技术的使用取决于传输标签分组的设备类型。各 种技术对于标签的实现如图2 7 所示：， 第三层封装 i p 分组 m p l s 封装s h i m 标记 第二层封装 a t mf rp p pe t h e r n e t v c l ，v p id l c i 图2 7 标签封装格式 下面以设备类型为依据简单描述各种封装技术。 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 头对标签的封装主要有以下三种方式。 ( 1 ) s v c 封装 这种方式使用v p i 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 的入口 南京邮电大学硕士论文第二章m p l s 概述 节点。使用这种方式，可以利用传统a t m 的v p 交换功能来提供多点到点的v p 。来自于 不同入口节点的信元携带有不同的v c i 值。 m p l s 允许在l s p 的不同部分使用不同的标签栈封装技术，当l s r 收到标签分组时， 必须对标签栈的当前值进行解码，分析标签栈中有效的标签，决定新的下一跳标签并进行 编码，然后向下一跳转发标签数据包。例如，当收到的标签是a t ms v c 封装时，发送的 封装可以是m p l s 通用封装或其它a t m 封装。但是a t m 交换机通常不具有一种标签编码 方式向另外一种转换的功能，所以，当任意l s p 上有两台a t m l s r 相邻时，两台 a t m l s r 必须使用相同的标签封装技术。一般情况下，一个m p l s 网络中肯定会有这样 的情况：部分l s r 是a t m l s r ，而另一部分l s r 则使用m p l s 通用封装方式。因此必 然一些l s r 既有a t m 接口又有m p l s 通用接口( 使用s h i m 头) 。这样的l s r 可以将入 口上的a t m 编码方式去掉，在出口上以m p l s 的s h i m 形式重新编码标签栈。这样，在各 跳上就可以使用不同的标签编码方式。 2 3 4 标签交换机制 m p l s 采用标签交换机制来实现数据分组的转发。从典型的帧中继和a t m 的性能和容 量来看，实现标签交换是一个快速和简单的转发过程。没有必要像传统i 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 弹栈，就可以获得一个更好的优化方案，称 作倒数第二跳弹栈。然后分组到达出口l s r 设备并携带用于转发分组的已经在栈顶顶部的 标签。这样就节省了出口设备必须处理未必有用的标签表查询时间。 每个l s r 节点依据l i b 中的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 ) 来转发数据 分组，n h l f e 包含以下内容： ( 1 ) 数据分组的下一跳( n e x th o p ) ； ( 2 ) 转发数据分组时使用的d l l ( d a t al i n kl a y e r ) 封装： ( 3 ) 转发数据分组时所使用的标签栈的编码方式； ( 4 ) 对数据分组采取的标签栈操作( 压栈、替换、弹栈) ： 1 1 南京邮电大学硕十论文第二章m p l s 概述 数据分组在进入m p l s 时，首先被归类为不同的f e c ，然后这些f e c 同n h l f e 相映 射。f e c 同n h l f e 的映射关系有两种：入标签映射和f e c 到n h l f e 的映射。前者用来 在中间l s r 转发已经标签化的分组，后者用来在边缘l s r 转发为标签化的分组，但在转 发之前分组已经打上标签了。 2 3 5 标签分配协议 m p l s 使用了两种标签分发方式，即用控制消息携带和使用专用标签分发协议。虽然 使用专用标签分发协议会使路由的分发和标签的分发分离，但是因为使用控制消息存在诸 如无法协商标签的可用范围、无法处理无效的标签分配等问题。因此建议采用专用标签分 发协议( l d p ) 1 2 】。 l d p 用四类消息完成标签的分发过程，它包括发现消息、会话消息、公布消息、通 知消息。 标签分发协议的运行也可以分为三个阶段 1 发现阶段：在这个阶段里，l s r 可以自动发现它的l d p 对等，而无需进行人工配 置。l d p 将发现机制分为两种； ( 1 ) 基本发现机制，用来发现本地的l d p 对等； ( 2 ) 扩展的发现机制，用来发现远地的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 ”包的接收方会将这个对等关系标识为链路层可达。 扩展的发现机制则由l s r 周期性地发送特定i p 地址的“h e l l o 包。”h e l l o 按u d p 发送，目的协议地址为特定的i 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 协议版本、标签分发的方法、定时器值、标签的范围( 当底层使用a t m 网络 时是v p i v c i 范围，当底层使用帧中继网络时则是d l c i 范围) 等。 3 会话的维持和删除：l d p 通过监测会话传输连接上l d pp d u 的接收情况来判定会 话连接是否完整。一个l s r 为每个会话保持一个“保持存活 定时器，当从该会话上接收 到一个l d pp d u 时，“保持存活”定时器会刷新。如果“保持存活 定时器到时，则l s r 1 2 南京邮电大学硕士论文 第二章m p l s 概述 认为该传输连接中断，该对等失效，并由此关闭传输层连接，从而终止这个对等。 2 3 6 标签分配和发布 标签的分配和分发是两个独立而又紧密相关的操作。标签的分配是指l s r 分配一个标 签并与某个f e c 绑定的过程。标签的分发是指l s r 把标签与f e c 的绑定信息分发给上游 或下游l s r 的过程。 1 标签分配控制 i e t f 的m p l s 工作组粗略地确定了两类标签分配的驱动方式：控制流驱动和数据流驱 动。其中控制流的驱动又分为：基于控制流的拓扑驱动和基于控制流的请求驱动。 拓扑驱动与l s r 的路由表紧密相关。路由表的每一个条目指示去往某个目的地的下 _ 跳的地址，拓扑驱动即是据此为每一个条目分配一个标签。拓扑驱动的标签分配方式相 当于一种“预分配”的方式，与实际到达的分组无关，不需要在线地建立l s p ，相对来说 时延较小。请求驱动是在数据传输之前，由控制信令( 如扩展的r s v p ) 1 3 1 发出请求，l s r 接收到请求后动态地进行标签分配和标签交换路径的建立，它实际上也是“预分配的方 式。 数据流的驱动是在实际数据流分组到达时进行标签分配并在线地建立l s p 。这种方式 有效地利用标签空间，适用于l s r 的标签空间有限而网络数据流较多的情况。 2 标签分发机制 标签分发分为上游分发和下游分发两种策略。本文仅介绍下游分发机制，上游分发过 程是与下游分发相反的。 下游分发的策略是指标签的分发沿着数据流传输的逆行方向进行。下游l s r 为某个 f e c 分配一个标签，该l s r 用所分配的标签作为本地交换表的索引。这是单播通信最自然 的标签分发方式。 如在图2 - 8 中，对于某个新到达的数据流，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 ，以此类推。 南京邮电大学硕士论文 第二章m p l s 概述 2 3 7 路由选择 1 逐跳路由 图2 8 下游分发示例图 在逐跳路由中，每一个标签交换路由器l s r 都为每一个转发等价类f e c 独立地选择下 一跳。r f c 指出，这个选择可以继续使用原有i p 网中的路由协议，如o s p f l l 4 1 。“逐跳路 由l s p ”是指使用逐跳路由进行选路的标签交换路径l s p 。这种l s p 的建立是完全动态的， 当网络收敛后，每个节点都会建立自己的转发信息库( f i b ) ，运行h o p - b y h o pl d p 的入 口l s r 将会自动的以f i b 中的每一个表项( e n t r y ) 作为其f e c ，并将此f e c 通过r e q u e s t 请求消息建立一条l s p 。 虽然这种l s p 可以动态的建立，网络扩展性好，但是目前它还不支持q o s ，不能实 现流量工程，所以仅用于对服务质量没有要求的数据业务。 2 e r l s p ( 1 ) 紧密的e r l s p 紧密的显式标签交换路径( e r l s p ) 是一条通过源路由事先在入口处的l s r 就已经确 定了f e c 的m p l s 域中路径上每个节点的路径。这种显式路径的指定由操作员完成或者通 过源路由协议实现。通过e r l s p 可以很容易实现流量工程；由于路径事先指定，因此可 以根据网络资源分布选择合理的路径，保证资源充分利用并且避免经过拥塞节点。同时， e r - l s p 可以通过c r - l d p 信令( 或者r s v p t e 信令) 【1 5 1 在请求消息中携带l s p 所要求 的q o s 参数，以满足各种业务对于服务质量的要求。 ( 2 ) 松散的e r - l s p 在很多实际情况中，由于业务类型的不同，也不一定需要人为规定从源节点到目的地 经过的所有节点，而是只需要规定必须经过的几个节点即可。当然这种l s p 路径所必须 南京邮电大学硕士论文 第二章m p l s 概述 经过的节点是经过流量工程计算后决定的，这样可以确保网络业务的合理流向。般，这 种l s p 用于网络资源还相对充裕，流量对网络要求不是非常苛刻的情况。 2 4m p l s 的技术特点 m p l s 利用i