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

南京邮电大学硕士研究生学位论文摘要 摘要 流量工程对于今天的i n t e m e t 来讲是非常重要的，它包括了网络性能的很多方面，比 如服务质量的保证、通过将流量均匀分发到网络中来提高网络资源的利用率和提供在节 点或链路失效时快速恢复的能力。但是现有的i p 由于其路由的局限性而不能够对流量工 程提供更好的支持。而m p l s 凭借其显式路由的能力提供了很好的解决方案，同时m p l s 具有提供自动化流量工程功能的可能。m p l s 多径路由是这样一种路由技术：它是将业务 流按照某种分割策略分配到源节点和目的节点之间的多条路径上同时进行传输。这种多 径路由技术可以更好地平衡网络负载，更加有效地利用网络资源，也可以增加业务连接 请求的接入量。 本文首先阐述了m p l s 的主要概念、技术及m p l s 流量工程的实现机制。在流量工程 路由算法一章中分析了传统的静态动态路由算法及其缺点，在此基础之上介绍了约束路 由，包括t e 路由和q o s 路由，最后详细论述了多径路由算法，其中包括本文所参考的算法： e b 和m p b f 算法。在第五章中详细介绍了本文提出的一种新的多径路由算法，并通过n s 仿真软件对算法性能进行了验证，同时将本文新的算法与e b 和m p b f 算法进行比较。比 较结果显示，新的多径路由算法提高了网络资源的利用率，在一定程度上降低了传输时延。 关键词：多协议标签交换，流量工程，多径路由，利用率 南京邮电大学硕士研究生学位论文abstract a b s t r a c t n o w d a y s ，t r a f f i c ee n g i n e e r i n g ( t e ) i sv e r yi m p o r t a n tf o rt h ei n t e r n e t t ec o n s i s t so fm a n y f e a t u r e sa b o u tn e t w o r k s ，s u c ha s ，q u a l i t yo fs e r v i c e ，i m p r o v et h eu t i l i z a t i o no fn e t w o r kr e s o u r c e s v i ae q u a b l yd i s t r i b u t i n gt r a f f i ct on e t w o r k ，a b i l i t yo ff a s tr e c o v e r yw h i l es o m en o d e so rl i n k s f a i l w h e r e a s ，t h ee x i s t i n gi pn e t w o r kc a l l ts u p p o r tt ew e l l ，d u et oi t sl o c a l i z a t i o no n r o u t i n g m p l sp r o v i d e sab e t t e rr e s o l v e n tw i t hi t se x p l i c i tr o u t i n ga b i l i t y m e a n w h i l e ，i tc a n s u p p o r ta u t ot e m p l sm u l t i p a t hr o u t i n gi ss u c hak i n do fr o u t i n gt e c h n i q u e ：a c c o r d i n gt oc e r t a i n p a r t i t i o np o l i c y , i tc a l lp a r t t i o nt 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 en o d ea n d d e s t i n a t i o nn o d e ，a n dt r a n s f e rv i aa 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 sm u t i p a t ht e c h n i q u en o to n l y c a nb a l a n c en e t w o r kl o a d ，m a k eu s eo fn e t w o r kr e s o u r c e sm o r ee f f e c t i v e l y , b u ta l s oi n c r e a s e a 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 sa n dt e c h n i q u e s ，a sw e l la s i m p l e m e n t i n gm e c h a n i s mo fm p l st e i nt h ec h a p t e ro ft er o u t i n ga l g o r i t h m s ，i tf i r s ti n t r o d u c e s t 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 st 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 s c o n s t r a i n t r o u t i n g ，i n c l u d e s t e r o u t i n g a n dq o s r o u t i n g ；f i n a l l y d i s c u s s e s m u l t i p a t h r o u t i n g ，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 en e wa g o r i t h m c h a p t e r5b r i n g s f o r w a r dan e wm u l t i p a t hr o u t i n ga l g o r i t h ma n dv a l i d a t e si t sp e r f o r m a n c et h r o u g hn s ( n e t w o r k s i m u l a t i o n ) ，a tt h es a m et i m ec o m p a r e si tw i t he ba n dm 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 wm u l t i p a t ha l g o r i t h mi m p r o v e su t i l i z a t i o no fn e t w o r kr e s o u r c e s ，i ta l s or e d u c e s e 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 yw o r d s ：m u l t i - p r o t o c a 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 ，m u l t i p a t hr o u t i n g ，u t i l i z a t i o n 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：蔓重坌日期：二盟r 汐 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：b 穗会 导师签名： 南京邮电大学硕士研究生学位论文第一章绪论 1 1 课题的提出 第一章绪论 i n t e m e t 的初期设计主要是针对数据通信的，i p 网络的网络结构、支持的协议及对服 务质量的要求也都是按照数据通信的要求来设计的。数据通信对时延和抖动的要求是比较 宽松的。随着i n t e m e t 的迅猛发展，i n t e m e t 的业务种类也与日俱增，除了传统的数据传输， 语音、图象等的应用也越来越多。目前，i n t e m e t 上已经开通了i p 电话、视频会议、可视 电话等实时业务，这些多媒体业务对网络的时延、带宽和抖动都有严格的要求。因此，业 务的传递不再是只需要具有可达性，而更多的用户要求保证业务的服务质量。传统路由器 的转发能力在这些日益庞大的数据量面前也越来越显得力不从心，不仅转发实现的难度增 大，成本也在不断地增加。在q o s 方面，由于i p 协议是面向无连接的，i n t e r n e t 网络中没 有严格的服务质量的概念和技术，不能保证有足够的吞吐量和符合要求的传输时延，只是 尽最大努力来满足用户的要求。所以，如果不采取新的方法改善目前的网络环境，就无法 大规模发展新的业务。在这种形式下，提出了流量工程( t r a f f i ce n g i n e e r i n g ，t e ) 的问题i lj 。 流量工程是一个控制业务流如何经过网络，以达到优化网络资源利用、提高网络性能 目的的过程。通过它可以平衡网络中不同链路、路由器和交换机之间的负荷，使所有这些 设备既不会被过度使用，也不会未被充分使用。这样就可以有效利用整个网络的资源，以 减轻拥塞。当拥塞最小化时，网络的各项q o s 指标将得到改善，分组丢失将减少，传输时 延也将缩短，而吞吐量则将增大。 可见，流量工程也是一种间接实现q o s 的技术。对于服务提供商( i n t e m e ts e r v i c e p r o v i d e ，i s p ) 来说，经常增加网络基础设施的投资是不现实的。通过流量工程，i s p 可 以在已有网络基础设施投资的基础上，最大限度的利用网络资源，提供尽可能好的服务， 满足用户的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 流量工程【5 l 的主要原理是基于m p l s 支持“显式路 南京邮电大学硕士研究生学位论文第一章绪论 由 ，在支持m p l s 网络域边缘建立满足业务流需求和网络约束条件的最短路径，达到优 化网络资源和满足业务流要求的流量工程的目标。m p l s 多径路由是这样一种路由技术： 它是将业务流按照某种分割策略分配到源节点和目的节点之间的多条路径上同时进行传 输。这种多径路由技术可以更好地平衡网络负载，更加有效地利用网络资源，也可以增 加业务连接请求的接入量。 1 2 课题的国内外研究现状 目前国内外已经提出了多种多径路由算法。最早提出的多径路由算法是等代价多径路 由算法( e q u a l c o s tm u l t i p a t h ( e c m p ) r o u t i n g ) 【6 1 。它是将业务流平均分配在多条具有相 等费用的路径上同时传输。这种路由算法可以利用o s p f 和i s i s 路由协议，另外一些路 由器拓展技术还可以使e c m p 可以支持路由信息协议( 砌p ) 及其他的一些路由协议。文 献 7 提出了一种应用于面向连接的动态多径路由算法，当网络处于低流量负载时使用最短 路径，而当最短路径发生拥塞时就转而使用多条路径。但是此文献只考虑了连接层或呼叫 层的路由和转发，而并未考虑流层的路由和转发。文献 8 】提出了一种时间约束条件下的多 径q o s 路由算法，但是这种方案由于在接收端对数据包的动态缓存而增加了网络开销。 对于多径之间的负载均衡问题目前也得到了广泛的研究并提出了一些成熟的算法。文 献 9 1 q b 的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 u o ，即m p l sa d a p t i v e 删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 被认为是下一代i n t e r n e t 的骨干网络技术。目前，m p l s 最重要的应用就是流量 工程。m p l s 流量工程多径路由技术可以通过将业务流分割到多条路径上来更好地平衡网 络中的负载，在很大程度上可以更有效地避免拥塞的发生。 南京邮电大学硕士研究生学位论文 第一章绪论 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 概述 i n t e m e t 网络路由体系结构的变化，i n t e m e t 可扩展性的要求以及新的路由功能的需求， 还有如q o s 等各种新型服务的要求，所有这些需求推动着包括m p l s 在内的各种技术的诞 生和发展。针对以上问题，1 e t f 提出了m p l s 网络。 2 1m p l s 产生的技术背景 到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 月份在m i t 举办了一个关于标签交换的b o f 会议。之后，i e t f 成立了一 个从事综合选路和交换问题研究的工作组，并将标签交换以m p l s 来命名【l 】。这个名称是 基于这样一个事实，即简单标签交换是作为底层转发机制。名称中的多协议( m u l t i p r o t o c 0 1 ) 意味着除了m 之外还支持多种网络层的协议。在体系结构上这是对的，但实际上网络层协 议将只限于p v 4 和i p v 6 。按照国际标准化组织的o s i 七层网络协议模型，我们可以将m p l s 定位在2 5 层。图2 1 是一个基于m p l s 的软件框架，其中l d p 模块和m p l s f m 模块与 其他模块相配合共同完成m p l s 的任务。我们可以看到实现时m p l s 所处的层次和它与其 他各层次之间的交互。 特别地，m p l s 将合并网络层选路和标签交换而形成一个单一的解决方案。为了吸引 更多的客户并产生更大的利润，网络供应商需要发布新业务和改善的业务。考虑到i p 交换 和a t m 的密切关系，以及m p l s 在引进和实施新业务时的灵活性，m p l s 是非常有希望 的一种解决方案。 南京邮电大学硕士研究生学位论文 第二章m p l s 概述 图2 1m p l s 软件框架 2 2m p l s 基本原理和工作过程 2 2 1 基本原理 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 2m p l s 工作流程 m p l s 网络采用标准分组处理方式对第三层的分组进行转发，采用标签对第二层分组 进行交换。m p l s 是通过以下三个步骤来完成标签交换的： 在分组上添加表示分组归属的f e c 关联标签； 使用标签值转发分组； 检索一个包含出口和新标签的连接表并用新标签替换旧标签。 - 5 - 南京邮电大学硕士研究生学位论文第二章m p l s 概述 下面通过图2 2 所示的例子来进一步了解分组是怎样被转发的。 图2 2 标签分组转发过程 在图2 - 2 中，一个流入的分组到达边缘l s r 时，它将读分组的目的地址的前缀，1 9 2 1 6 8 ， 下一步这个边缘l s r 查看交换表中的目的地址，加入对应的标签2 ，然后通过端口l 发出。 在中心的l s r 读到这个标签，然后在交换表中查找对应的标签，然后用标签5 取代2 ，从 端口1 转发。在出去的边缘l s r 查看标签5 ，在此除去分组的标签，从端1 2 12 出去。注意 在网络的核心，口的转发信息只是用来建立标签交换表，并没有直接参与转发。这个例子 说明了数据怎样在一个路由的网络中转发。 具体地来讲，m p l s 的工作流程又可以分为几个方面：即网络的边缘行为、网络的中 心行为以及如何建立标签交换路径( l s p ) 。 在网络边缘的节点就称做为标签边缘路由器( l e r ) ，而网络的核心节点就称为标签交 换路由器( l s r ) 。图2 3 为m p l s 网络的结构图。 ( 1 ) 网络的边缘行为： 图2 3m p l s 网络结构 矗 南京邮电大学硕士研究生学位论文第二章m p l s 概述 当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 下一跳的标 签上。转发数据包时，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 包的路由方式将数据包继续传送到目的地。 ( 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 ) ，以规定数据包将选择的路径。不像h o p - b y h o p 的l s p ，e r l s p 不会形成i p 树。取而代之的，是e r o l s p 从源端到目的端建立一条直接的端到端的路径。 2 3m p l s 体系结构 2 3 1 基本概念和主要数据结构 2 3 1 1 基本概念 ( 1 ) 标签( 1 a b e l ) ：标签是一个包含在分组中的短的、定长的、只有本地意义的标识 符。某一分组的标签代表了它所属的转发等价类，用来在一对l s r 之间进行分组交换。标 签可以封装到现有的数据链路层分组中，格式取决于分组封装所在的介质。图2 4 为通用 标签的格式f 2 5 】。 南京邮电大学硕士研究生学位论文 第二章m p l s 概述 l 用户数据i p 头 m p l ss h i m 第二层帧头 标记 c o sst t l 标记：2 0 b i ts ：堆找厩标岙1 6 b i t c o s ：业务等级，3 b i t1 r l ：生存周期，8 b i t 图2 - 4m 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 可以是一个传统的交换机( o na 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 网络中将获得完全相同的处理。 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 要素有两类( 将来还可以再扩充) ： i p 地址前缀，提供一个含有一个或多个i p 地址前缀的集合，符合其中一个或多个 i p 地址前缀的包被映射到相应的l s p 。 主机地址，以一个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 5 为l s p 建立过程示意图。 8 南京邮电大学硕士研究生学位论文第二章m p l s 概述 l i b ： ( i ) 标签请求 i 三兰 三兰 ( 2 ) 标签映射 舀圈圉 ( 3 ) l s p 建立 图2 - 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 ) ：一个标签分发协议是由一系列 的过程组成的，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 - 6 所示。 南京邮电大学硕士研究生学位论文 第二章m p l s 概述 入标签入端口i p 地址段出端口出标签 41 1 9 2 1 6 8 o 5 图2 击标签信息厍 ( 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 1 2 主要数据结构 1 n h l f e 转发标签分组时将使用下一跳标签转发条目( n h l f e ) ，它将包含下列信息： ( 1 ) 分组的下一跳； ( 2 ) 在分组的标签栈上完成的下列操作之一： 用特定的新标签替代标签栈顶的标签； 标签栈执行出栈操作； 用特定的新标签替代标签栈顶的标签，然后将一个或多个特定的新标签压入标签 栈。 ( 3 ) 传送分组使用的数据链路封装； ( 4 ) 传输分组时标签栈的编码方式； ( 5 ) 对分组进行适当的处理所需的其他信息。 如果分组的下一跳为某个l s r 自身，则该l s r 将栈顶标签弹出并将由此得到的分组 “转发”给自己。此后，如果标签弹出后标签栈不空，则l s r 根据标签栈中仍保留的信息 作出另一个转发决定；如果标签栈为空，则l s r 根据i p 分组头转发该分组。 2 输入标签映射( i l m ) 输入标签映射( i l m ) 将每个输入标签映射到一组n h l f e 。对将收到的标签分组进行 转发时将使用i l m 。当i l m 将某一个特定标签映射到包含多个元素的一组n h l f e 时，转 发该分组之前必须从该组中明确地选出一个元素。 1 0 南京邮电大学硕士研究生学位论文 第二章m p l s 概述 3 f e c 至n h l f e 映射( f t n ) f e c 至n h l f e 映射( f t n ) 即将每个f e c 映射到一组n h l f e 。对于收到的未打标 签的、但要在转发之前打上标签的分组，将其转发时需要使用f t n 。 当f t n 将某一特定标签映射到包含多个元素的一组n h l f e 上时，在该分组进行转发 之前必须从该组明确地选出一个元素。图2 7 说明了这两种数据之间的关系。 图2 7 中有两个平台：控制平台和转发平台。已经打上标签1 4 5 0 的分组从a 端口进 入，又被转换为标签1 0 0 6 从b 出去。这个功能是在标签为c r o s s 的n h l f e 表的参与下 完成的。n h l f e 表并不是一个独立的数据库，它在控制平台中连接了另外的两个数据 库：f e c 表和f t n 表。f e c 表通常包括目的地i p 地址，但是它还可以包含流量特征和分组 处理要求。在f e c 表中的数据必须与标签相关；将f e c 与一个标签联系在一起的过程被 称为绑定。 圆圆圆 2 3 2 标签封装 转发平台a b 1 4 5 0 囤1 0 0 6 n h l f e 图2 7f e e 和n h l f e 之间的关系 标签是一个包含在分组中的固定长度的只有本地意义的标识符。一对l s r 必须在标 签的数值和意义上取得一致。为了在分组中携带标签或标签栈，需要对标签的编码加以规 定。目前标签栈有几种不同的编码技术，各种技术的使用取决于传输标签分组的设备类型。 各种技术对于标签的实现如图2 - 8 所示。 第三层封装l p 分组 m p l s 封装s h i m 标记 第二层封装 a t m f rp p pe t h e m e t v c l p id l c i 图2 8 标签封装格式 下面以设备类型为依据简单描述各种封装技术。 ( 1 ) m p l s 专用硬件软件 南京邮电大学硕士研究生学位论文第二章m p l s 概述 当传输设备为m p l s 专用的硬件软件时，将使用m p l s 专用的封装技术，即在数据链 路层与网络层头标之间使用一种“s h i m 封装，该封装将置于网络层分组头标之前，链路 层封装之后，独立于网络层协议和链路层协议。这种封装又称为m p l s 通用封装，这种封 装的编码方式如图2 - 9 所示。 图2 - 9通用m p l s 标签封装 其中，标签的长度为2 0 比特。e x p 字段的作用是实现d i f f - s e r v 等高级应用，3 比特。 s 字段用于栈底标志，1 比特；当s 字段为1 时，则表明该标签已经是栈底标签，如果到 达了网络边缘节点，则需要对其进行出栈操作并进行网络层封装的处理。t t l 字段：生存 期，8 比特，它的涵义是与传统i p 网中的t t l 字段完全相同的。 ( 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 头对标签的封装主要有以下三种方式。 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 将不能对标签栈实施入栈和出栈操作。 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 的信令协议。 如果网络中包含一条通过非m p l s 网络的a t mv p 的话，则不能使用这种技术。 在这种方式中，v p 出口上的a t m l s r 将对标签栈实施出栈操作。 s v p 多点封装 这种方式将使用v p 字段来构成栈项标签的封装，同时使用v c i 字段的一部分来构成 标签栈中下一层标签的封装( 如果有的话) ，使用v c i 字段的剩余部分来标志l s p 的入口 节点。使用这种方式，可以利用传统a t m 的v p 交换功能来提供多点到点的v p 。来自于 不同入口节点的信元携带有不同的v c i 值。 m p l s 允许在l s p 的不同部分使用不同的标签栈封装技术，当l s r 收到标签分组时， 必须对标签栈的当前值进行解码，分析标签栈中有效的标签，决定新的下一跳标签并进行 1 2 。 南京邮电大学硕士研究生学位论文第二章m p l s 概述 编码，然后向下一跳转发标签数据包。例如，当收到的标签是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 3 标签交换机制 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 弹栈，就可以获得一个更好的优化方案，称作倒数第二 跳弹栈。然后分组到达出c i 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 ) 对数据分组采取的标签栈操作( 压栈、替换、弹栈) 数据分组在进入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 多j n h l f e 的映射。前者用来在中间l s r 转发已经标签化的分组，后者用来在边缘l s r 转发为标签化的分组，但在转发之前分组已 南京邮电大学硕士研究生学位论文 第二章m p l s 概述 经打上标签了。 2 3 4 标签分发协议 2 3 4 1l d p 消息 1 l d p 协议分组格式 l d p 的消息交互是通过在l d p 会话t c p 连接上发送l d pp d u 实现的，也就是说，各 种消息都将被包含在t c p 包的p d u 中。每个l d pp d u 可以带有一个或多个l d p 消息， 在l d pp d u 中带有的多个消息是彼此独立的。例如，一个p d u 可以带有对于某一f e c 的标签映射消息，同时还可以带有对其它f e c 的标签请求消息，以及针对其他一些事情的 通知消息等。 l d pp d u 由l d p 头和一个或多个l d p 消息组成。l d p 头的格式如图2 - 1 0 所示。 图2 1 0 l d p 头格式 l d p 消息格式如图2 1 1 所示 0 11 5 1 6 3 1 u 消息类型 消息长度 消息标识符 必选参数 可选参数 图2 - 1 1l d p 消息格式 2 类型一长度一值( t l v ) 编码 l d p 使用类型长度一值编码体系表示l d p 消息中的大部分信息，如图2 - 1 2 所示。 图2 1 2t l v 编码 t l v 编码体系是一种通用的形式。原则上l d pp d u 中出现的任何信息都可以用t l v 南京邮电大学硕士研究生学位论文 第二章m p l s 概述 的方式编码。但是在l d p 协议中，并未在所有可能的情况下都使用t l v 体系，因为有时 使用t l v 是没有必要的，并且浪费了空间资源。 3 l d p 消息类型 在l d p 协议中主要有4 种l d p 消息： 发现( d e s c o v e r y ) 消息，用于通告和维护网络中l s r 的存在。 会话( s e s s i o n ) 消息，用于建立、维护和终止l d p 对等实体之间的会话连接。 通告( a d v e r t i s e m e n t ) 消息，用于创建、改变和删除f e c 标签的绑定。 通知( n o t i f i c a t i o n ) 消息，用于提供建议性的消息和差错通知。 在l d p 的发现过程中，l s r 之间可以通过周期性地发送h e l l o 消息来表明它们在网 络中的存在。最常用的h e l l o 消息有： 初始化( i n i t i a l i z a t i o n ) 初始化消息在一个l d p 会话之初就被发送，这使得两个 l s r 对关于这个会话的各种参数和选项达成一致。初始化消息包括标签分配模式、计时器 的值以及在这两个l s r 之间的链路上使用的标签的范围。 会话保持( k e e p a l i v e ) - 会话保持消息被周期性地发送，如果在适当的时间间隔内 没有会话保持消息或者某个其他的l d p 消息，那么一个l s r 就断定它到对等实体的连接 已经拆掉了，并且终止这个会话。 标签映射( l a b e lm a p p i n g ) - 是标签分布的核心。它们是被用于通告关于一个f e c 和一个标签之间的绑定的消息。 标签回收( l a b e lw i t h d r a w a l ) ：与标签映射消息过程相反，它被用于撤回一个先前 通告的绑定。回收绑定的原因包括，由于路由的变化而从发送通告的l s r 上的路由表中将 一个地址前缀除掉，或者是在此l s r 中的配置发生变化导致它在此f e c 上停止标签信息 交换。 标签释放( l a b e lr e l e a s e ) ：个标签释放消息由一个先前接收了一个标签映射，而 后来再也不需要这个映射的l s r 所使用。 标签请求( l a b e lr e q u e s t ) 标签请求中断( l a b e lr e q u e s ta b o r t ) ：l s r 可能以主动提供的下游标签分配模式或 者是以按需提供的下游标签分配模式操作。在后面的一种模式下，l s r 使用标签请求消息 从它们下游的邻机请求标签映射。如果一个标签请求消息在它被满足之前需要被取消，则 发出请求的l s r 用标签请求消息中断这个请求。 2 3 4 2l