（通信与信息系统专业论文）基于流优化的qos路由算法研究.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 下一代网络是基于i p 分组技术的网络。传统的i p 路由协议采用基于目的地址的最短 路径优先算法，当最短路径上无可利用资源时，即使在其它路径上有足够的资源，连接请 求也将被拒绝，导致网络负载不平衡。多协议标签交换( m p l s ) 将数据包的路由和转发相 分离，利用约束路由建立显示路径，进而建立标签交换路径。因此，m p l s 网络非常适合 实施流量工程，其显示路由为流量工程的应用提供了便利。 本文首先介绍了两种数学规划模型：i r ( i d e a lr o u t i n g ) 模型和m i n c u t 模型。两种模型 以最小化连接请求拒绝率为目标，为动态在线路由算法的性能提供了一个理论边界，可以 作为动态路由算法性能评价的绝对标准。r 模型通过假定连接请求的到达时间和持续时 间，得到一个严格的理论边界。m i n c u t 模型把最小化多商品流删减理论和m u l t i c l a s s e r l a n g 公式相结合，提供一个松散的理论界线。其计算简单，易适用于大型网络。 最后，详细阐述了一种改进的基于流优化的多路径q o s 路由算法- - t e b ( t r a d e o f f b e t w e e ne f f i c i e n ta n db a l a n c e ) 算法。该算法以多商品流理论为基础，选择恰当目标函数，通 过设置最大链路利用率，很好地实现网络资源利用率与负载均衡的折中。文中在介绍相关 概念和定理的基础上，描述了t e b 算法的数学规划模型公式，最后运用c p l e x 优化软 件详细分析了该算法的性能。该算法的主要优点是：给出了一种新颖的商品流定义方法， 减少了算法公式中的变量，节省了计算时间；与最短路径算法和t b ( t r a f f i cb i f u r c a t i o n ) 算 法相比较，t e b 算法在网络资源效率和负载均衡方面显示了良好的性能；便于网络管理 员对网络不同部分进行流量控制。 a b s t r a c t t h en g n ( n e x tg e n e r a ln e t w o r k ) i san e t w o r kb a s e do ni pp a c k e ts w i t c h i n g t h e c o n v e n t i o n a li pn e t w o r kr o u t i n gp r o t o c o l s ，u s i n gas i n g l es h o r t e s tp a t hf i r s ta l g o r i t h m ( s p f ) ， r e s u l ti nu n b a l a n c e d1 0 a d i no t h e rw o r d s ，w h e nt h er e s o u r c e sa r en o ta v a i l a b l eo nt h es h o r t e s t p a t h ，t h ec o n n e c t i o nr e q u e s t i sr e j e c t e de v e ni fs u f f i c i e n tr e s o u r c e se x i to na l t e r n a t i v ep a t h s t h e m p l ss e p a r a t e st h er o u t i n ga n df o r w a r d s ，e x p l o i t st h ec o n s t r a i n tr o u t i n g ，s e t su pe x p l i c i tp a t h s a n dl a b e ls w i t c h i n gp a t h s ( l s p ) s ot h em p l si sf i tf o rt h ei m p l e m e n to ft r a f f i ce n g i n e e r ( t e ) ， s i n c ei t se x p l i c i tr o u t i n gp r o v i d ec o n v e n i e n c ef o rt h et e i nt h i sp a p e r , w ef i r s tp r o p o s et w om a t h e m a t i c a lp r o g r a m m i n gm o d e l s ，i r ( i d e a lr o u t i n g ) m o d e la n dm i n - c u tm o d e l ，w h i c hm i n i m i z e st h en u m b e r so fr e je c t e dc o n n e c t i o n sa n dc a n p r o v i d e t h e o r e t i c a lb o u n d st ot h ep e r f o r m a n c ea c h i e v a b l eb yo n - l i n er o u t i n ga l g o r i t h m sa n ds e t a l la b s o l u t ee v a l u a t i o no ft h ep e r f o r m a n c eq u a l i t y 1 1 1 ei rm o d e l ，a s s u m i n gt h ec o n n e c t i o n a r r i v a lt i m e sa n dt h e i rd u r a t i o n s ，p r o v i d e sa no p t i m a lr o u t i n gb o u n d s t h em i n - c u tm o d e l ， i n t e g r a t i n gt h em u l t i - c l a s se r l a n gf o r m u l aw i t ht h em i n i m u mm u l t i c o m m o d i t yc u tp r o b l e m ，i s a na p p r o x i m a t eo n ea n dp r o v i d e sal o o s e rl o w e rb o u n dt ot h ec o n n e c t i o nr e j e c t i o np r o b a b i l i t y i tc a nb ea p p l i e dt ol a r g e ra n dm o r ec o m p l e xn e t w o r k t o p o l o g i e s f i n a l l y ，w ep r o p o s ea ni m p r o v e dm u l t i p a t hq o sr o u t i n ga l g o r i t h mb a s e do n f l o w o p t i m i z a t i o n - t e b ( t r a d e - o f fb e t w e e ne f f i c i e n ta n db a l a n c e ) a l g o r i t h m ，w h i c hi s o f f - l i n e b a s e do nm u l t i - c o m m o d i t yf l o wt h e o r y ，i t so b j e c t i v ef u n c t i o na l l o w sp r e c i s et u n i n go ft h e t r a d e o f fb e t w e e nl o a db a l a n c i n ga n dt o t a ln e t w o r ke f f i c i e n c yt h r o u g ht h es e t t i n go fm a x i m u m l i n ku t i l i z a t i o nr a t e i nt h et e x tw ei n t r o d u c et h er e l a t i v en o t i o n sa n dt h e o r e m s ，a n dt h e nw eg i v e t h em a t h e m a t i cf o r m u l a t i o no fm o d e la n da n a l y s i st h ep e r f o r m a n c ei nd e t a i l s 、i t l lc p l e x t h e t e ba l g o r i t h m sa t t r i b u t i o n sa r e ：f i r s t ，g i v i n gan o v e ld e f i n i t i o no fc o m m o d i t yf l o w ，r e d u c et h e n u m b e ro fv a r i a b l ea n ds a v et h ec o m p u t i n gt i m e ；s e c o n d ，d i s p l a yg o o dp e r f o r m a n c eo nt h e t r a d e o f fb e t w e e ne f f i c i e n ta n db a l a n c ec o m p a r i n gw i t ht h es p fa l g o r i t h ma n dt ba l g o r i t h m t h i r t y i t se a s yf o rt h ea d m i n i s t r a t o rt oc o n t r o lt h et r a f f i co fd i f f e r e n ts u b n e t w o r k i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：维日期：2 弛 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 ， 么 研究生签名：_ 二璐导师签名：尹_ 夕审7 产 南京邮电大学 硕士学位论文摘要。 学科、专业：工学通信与信息系统 研究方向：网络与应用技术 作者：2 0 0 4 级研究生王磊指导教师庭室垦 题目：基于流优化的q o s 路由算法研究 英文题目：t h eq o sr o u t i n ga l g o r i t h mb a s e do nf l o wo p t i m i z a t i o n 主题词： q o s 路由多协议标签转发流量工程 多径路由 k e y w o r d s ：q o sr o u t i n g m p l st r a f f i ce n g i n e e n n g m u l t i p a t hr o u t i n g 南京邮电大学硕士研究生学位论文第一章绪论 第一章绪论 1 1 引言 下一代网络( n g n ) 是基于分组技术的网络；能够提供包括电信业务在内的多种业务； 在业务相关功能与下层传送相关功能分离的基础上，能够利用多种带宽、有q o s 支持能 力的传送技术；能够为用户提供无限制接入到多个运营商；能够支持普遍的移动性，确保 用户一致的、普遍的业务提供能力。 下一代网络是以i p 分组的数字通信技术为核心的通信网。因此，服务质量( q o s ) l h - j 题 是必须重点解决的关键，要能够保证提供电信级的服务质量。q o s 路由所涉及的路由机 制要完成两个目标：选择满足q o s 需求的路由；如果存在多条可行的通路，则选择出一 条或者多条有效的通路，从而能提供高的网络吞吐量。q o s 路由主要包括管理理由信息( 例 如，链路状态或距离向量) 和路由算法。 传统的路由协议采用基于目的地址的最短路径优先( s h o r t e s tp a t hf i r s t ，s p f ) 算法，由 于无法平衡网络负载，常常会导致网络中某些链路负荷过重，而另一些链路资源没有充分 利用，从而使原本能满足流量需求的网路发生拥塞。对于这个问题，人们希望通过流量工 程来解决。流量工程是指为了平衡网络的流量负载，根据数据流量来选择路径的过程。流 量工程的主要目标是采用可靠有效的网络操作来优化网络资源使用和通信性能。 多协议标签交换( 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 ) 是下一代i n t e r n e t 宽带网络技 术，它将数据包的路由和转发相分离，利用约束路由建立显示路径，进而建立标签交换路 径( l a b e ls w i t c h e dp a t h ，l s p ) 。因此，m p l s 网络很适合实施流量工程，它的显示路由为 流量工程的应用提供了便利。在实施流量工程的过程中，优秀的约束路由算法是工程的关 键，路由算法既要满足流量的q o s 要求，又要达到优化资源利用率的目的。 当前，在流量工程中进行路由的一个重要算法工具是基于约束的路由选择，基于约束 的路由选择算法可以充分考虑网络资源以及流量主干的流量工程约束属性。根据路径计算 的触发机制来分，可以把约束路由算法分为离线方式和在线方式。基于约束路由机制在进 行路径选择时的优化目标主要有两个：一个是节省网络资源，即路径所需的预留资源尽可 能少，或者说路径的跳数尽可能少；另一个是业务流在网络中尽可能均匀分布，以减少拥 塞发生的概率。 1 2 主要研究方向和工具 许多基于标签转发机制的动态路由算法被提出 7 1 3 】，而相关文献中对算法性能的评 南京邮电大学硕士研究生学位论文 第一苹绪论 估和比较缺乏统一标准。本文建议了两种数学规划模型，i r 模型和m i n c u t 模型，两种模 型可以提供动态在线q o s 路由算法的理论边界，可以为动态路由算法的性能分析提供一 个统一的参考。 接着，文中重点介绍一种离线的基于约束的多路径路由算法一一t e b 算法，该算法 以折中网络资源效率和负载均衡为目标，基于多商品流优化理论，建立数学规划模型求解， 便于网络管理员更加便捷的控制网络资源效率与网络负载的均匀分布。 c p l e x 是l i n e a r p r o g r a m m i n g 的运算核心软件，其软件控制平台基于w e b 或w i n d o w s 。 其内部函数库所拥有之演算法，均具备解决最佳化问题的能力，是一款高性能的临界任务 资源分配中解决线性、混合整数以及二次方程的应用建模优化软件。文中的线性数学规划 模型均采用a m p l 建模语言，运用c p l e x l 0 来进行编程和求解。 1 3 论文框架 第一章，绪论，简单阐述了下一代网络中的q o s 路由算法必要性，介绍了本文的主 要研究方向和使用工具。 第二章，简要介绍了m p l s 技术，m p l s 的概念，基本原理以及在下一代网路中的应 用等。 第三章，介绍了流量工程的概念和m p l s 中的流量工程。包括m p l s 的管理机制和 实现机制等。 第四章，回顾了几种常见的动态在线q o s 路由算法，在此基础上建议了两种数学规 划模型，瓜模型和m i n c u t 模型。i r 模型能够为在线路由算法提供一个严格的性能界限， 但计算复杂，适用于小型网络。m i n c u t 提供一个松散的边界，计算简单，适用于复杂的 网络。 第五章，重点讨论了一种离线的基于约束的多路径路由算法一- - t e b 算法。该算法 基于多商品流优化理论，以折中网络资源效率与负载均衡为目标。阐述了相关的概念和定 理，描述了算法的数学模型公式，并从多个方面对算法的性能进行了分析。 第六章，对文中的数学规划模型和算法作进一步总结。 南京邮电大学硕士研究生学位论文 第二章m p l s 技术概述及其在下一代网络中的应用 第二章m p l s 技术概述及其在下一代网络中的应用 2 1m p l s 技术概述 2 1 1m p l s 的基本概念 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 ) 目 j 多协议标记交换属于第三代网络架构，是新一 代的i p 高速骨干网络交换标准，由i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ，因特网工程任务 组1 所提出。 m p l s 是集成式的i po v e ra t m 技术，即在f r a m er e l a y 及a t ms w i t c h 上结合路由 功能，数据包通过虚拟电路来传送，只须在o s i 第二层( 数据链路层) 执行硬件式交换，以 取代第三层( 网络层) 软件式路由，它整合了i p 选径与第二层标记交换为单一的系统，因 此可以解决i n t e m e t 路由的问题，使数据包传送的延迟时间减短，增加网络传输的速度， 更适合多媒体讯息的传送。因此，m p l s 最大技术特色为可以指定数据包传送的先后顺序。 m p l s 使用标记交换( l a b e ls w i t c h i n g ) ，网络路由器只需要判别标记后即可进行转送处理。 m p l s 是一种特殊的转发机制，它为进入网络中的i p 数据包分配标记，并通过对标 记的交换来实现i p 数据包的转发。标记作为i p 包头在网络中的替代品而存在，在网络内 部m p l s 在数据包所经过的路径沿途通过交换标记，而不是看i p 包头来实现转发；当数 据包要退出m p l s 网络时，数据包被解开封装，继续按照i p 包的路由方式到达目的地。 m p l s 将i p 技术与下层技术结合在一起，兼具了高速交换、q o s 性能、流量控制以 及i p 技术的灵活和可扩展等特性。它不仅能够解决当前网络中存在的问题，而且能够支 持许多新的功能，是一种较为理想的骨干i p 网络技术。它吸收了a t m 的v p i v c i 交换 些思想，无缝地集成了i p 路由技术的灵活性和二层交换的简捷性，m p l s 基于i p 路由 和控制协议，提供面向连接的基于标记的分组交换，在面向无连接的i p 网络中增加了 m p l s 这种面向连接的属性。通过采用m p l s 建立“虚连接”的方法，为i p 网增加了一些 管理和运营的手段。m p l s 提供一套核心的机制，以多种方式提供丰富的功能。m p l s 核 心技术可以在多个网络层协议得到扩展，而且并不局限于任何一种特定的链路层技术。此 外，m p l s 也为支持更加先进的路由服务提供了基础，因为它解决了下面一系列复杂的问 题：使用m p l s 可以使网络具有很好的可伸缩性能；降低了网络操作的复杂性；促进新 的路由技术的发展，提高了i p 选路技术：并且日益成为扩大i p 网络规模的重要标准，促 进不同业务提供商之间的合作。在i p 网中，m p l s 流量工程技术成为一种主要的管理网 络流量、减少拥塞、一定程度上保证i p 网络的q o s 的重要工具。在解决企业互连，提供 壹室塑皇奎兰堡主堕窒生兰垡笙奎至三雯竺! 兰! 垫查塑堕墨基垄! 二垡塑竺! 堕壁旦 各种新业务方面，成为在i p 网络运营商提供增值业务的重要手段。 2 1 2m p l s 技术中常用术语 ( 1 ) 标记( l a b e l ) ：标签是一个包含在每个包中的短的具有固定长度的数值，用于通过 网络转发包。 ( 2 ) 标记边缘路由器( l a b l ee d g er o u t e r ，l e r ) ：l e r 是m p l s 网络同其他网络相连的 边缘设备，它提供流量分类和标签的映射( 作为i n g r e s s ) 、标签的移除功能。 ( 3 ) 标记交换路由器( l a b l es w i t c h i n gr o u t e r ，l s r ) ：l s r 是m p l s 网络的核心设备， 提供标签交换、标签分发功能，具有第三层转发分组和第二层交换分组的能力。 ( 4 ) 等价转发类( 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 是在转发过程中以等效的 方式处理的一组数据包，例如目的地址前缀相同的数据包。f e c 归类的方法可以各不相 同，粒度也可有差别。 ( 5 ) 标记交换路径( l a b l es w i t c h i n gp a t h ，l s p ) ：m p l s 实际上是一个面向连接的系统， 标签的分配实际上就是一个建立连接的过程，也即建立了一条l s p 。l s p 可以是动态的， 也可以是静态的，动态l s p 是通过路由信息自动生成，静态l s p 是被明确提供的。 ( 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 ) ：l d p 提供一套标准的信令机制用 于有效地实现标签的分配与转发功能。l d p 基于原有的网络层路由协议o s p f 、i s i s 、 r i p 、e i g r p 或b g p 等构建标签信息库，并根据网络拓扑结构，在m p l s 域边缘节点( 即 入节点与出节点) 之间建立l s p 。 ( 7 ) c r - l d p ( c o n s t r a i n tr o u t el a b e ld i s t r i b u t i o np r o t o c 0 1 ) ：限制路由的标记分配协。 2 1 3m p l s 技术的工作原理 m p l s 的工作流程可以分为几个方面，即网络的边缘行为、网络的中心行为以及如何 建立标记交换路径，如图2 1 所示。 南京邮电大学硕士研究生学位论文第二章m p l s 技术概述及其在下一代网络中的应用 图2 1m 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 ) 来为其生成一个标记。标记 信息库将每一个f e c 都映射到l s p 下一跳的标记上。如果下一跳的链路是a t m ，则m p l s 将使用a t mv c c 里的v c i 作为标记。转发数据包时，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 ) 如何建立标记交换路径： 建立l s p 的方式主要有两种，及“h o pb yh o p ”路由和显式路由。 “h o pb yh o p ”路由 5 堕塞唑皇奎堂堡主婴窒竺兰垡笙奎 兰三主竺! 兰! 垫查塑堕垒! ! 塑j ! 二堡塑丝! 塑! ：! 旦 一个h o p b y h 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 的请求以及对应的消息完成的。 显式路由 m p l s 最主要的一个优点就是它可以利用流量设计“引导”数据包，比如避免拥塞或者 满足业务的q o s 等。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 l s p 从源端到目 的端建立一条直接的端到端的路径，m p l s 将显式路由嵌入到限制路由的标记分配协议的 信息中，从而建立这条路径。 2 2 肝l s 技术在下一代网络( n g n ) 中的应用 下一代网络( n g n ，n e x tg e n e r a t i o nn e t w o r k ) 概念是在上个世纪9 0 年代提出的，当时 电信运营行业已经出现了两个明显趋向，一个是电信业务种类不断增加和电信业务量不断 增长的巨大变化趋向，突出表现是互联网业务量呈现爆炸式增长趋势；另一个是电信市场 竞争环境出现不断加剧的巨大变化趋向。在世界范围内，电信运营企业都在试图用最新的 技术成果来适应这种变化趋向，于是关于n g n 的网络概念、架构、关键技术、运营等标 准和发展趋势的研究课题得到了超常规的发展。尽管对下一代网络定义不尽相同，但是通 信界对下一代网络的基本特征有着共同的认识，即融合与开放。融合与开放并不是抽象的 概念，具体到电信网络中，融合与开放有其具体的含义。 尽管目前对于n g n 还没有统一看法，但是在以下一些方面基本达到了共识： ( 1 ) 下一代网络应支持业务的多样化，包括话音、数据和多媒体业务，支持实时非实时的业 务，同时应支持业务的个性化、业务的移动性、开放性和灵活性。 ( 2 ) 下一代网应是以i p 为基础的分组交换的网络；业务承载网和业务网相分离，网络结构 是分层的结构，各层之间具有开放的标准接口；传送网为高带宽的光传送网；该网络支持 广泛的移动性( 终端的移动性和用户的移动性) 等。 南京邮电大学硕士研究生学位论文第二章m p l s 技术概述及其在下一代网络中的应用 ( 3 ) 网络具有服务质量保证和安全保证；网络是可维护、可运营并且是可赢利的多业务网 络。 ( 4 ) 下一代网路必须要能与传统网的配合，因为无论网路如何演进现有的传统的网路还要 继续发挥作用，还要充分利用现有的网路资源因此下一代网路必须解决与传统的现有的各 种网路的配合和互通。 n g n 涉及范围宽泛，包括了固定网、移动网、业务网、承载网等，但目前存在问题 最多、解决难度最大的是承载网。电信网面临转型，正从目前的t d m 技术为主的网络转 向分组网络，下一代网络是以多媒体业务为主，因此要是以固定为主的信道承载将会出现 很多问题。 下一代承载网是一个能满足未来业务发展需求的、新型的分组数据网，因此它必须满 足几点要求。第一，它应该能融合目前已经存在的大量专用承载网，如p s t n 、a t m 、f r 、 i pv p n 等；第二，能够在面向连接和不面向连接两种方式下工作；第三，能承载面向连 接和不面向连接两种业务；第四，具有高可靠性、高强壮性、高扩展性；第五，承载网能 为以后承载的业务网的控制平面和管理平面提供资源独立、信息隔离的逻辑信道，以确保 业务的控制平面和管理平面的安全。除了对安全方面的保障之外，与此同时，电信承载网 也要满足一定的质量要求，另外，它还应该能够支持紧急通信。 在上世纪8 0 年代到9 0 年代，面向连接的a t m 网络具有流量工程、q o s 保证、业务 合约等优点。而面向无连接的i p 网络技术具有简单、灵活的优点。a t m 技术和i p 技术 都希望成为下一代网络的胜出者，m p l s 就是在两者的互相竞争的过程中，吸取了a t m 和i p 网络的各自优点逐步融合产生的。 m p l s 非常完美地将i p 与a t m 结合在一起，对于i p 业务，m p l s 实现不仅能高速 转发i p 包，同时由于m p l s 继承了a t m 的q o s 机制，因此可以保证用户对于不同服务 质量的要求。m p l s 对于q o s 的支持是通过p e ( p r o v i d e re d g ed e v i c e ) 、和l s r 的合作来 实现的。在p e 上进行i p 包的分类，将i p 包的业务类型映射到a t m 的服务等级上，在l s r 上进行a t m 的业务量控制，保证每种业务的服务质量得到满足。 有材料指出，解决传统电信运营中业务发展与网络承载矛盾的出路在于采用i p ( t c p i p ) 三层网络技术承载各种业务，采用m p l s 实现三层i p 网络层和二层链路层多种网络( 比如 现电信业已存在的a t m f r 、p p p 、以太网、s d h 、光波网络) 的无缝融合。显然，m p l s 是向n g n 核心网络演进的核心技术。 南京邮电大学硕士研究生学位论文 第三章m p l s 流量工程 第三章m p l s 流量工程 3 1 流量工程系统 传统的路由协议用d i j s k t r a 算法计算出路由表，当一个数据报到达一个路由器时，通 过查找路由表来完成投递转发。这一个方式的主要缺点是负载不均。由于采用最短路径的 方式，则不管最短路径是否拥塞，i p 包都会沿着这条路径传送，不在最短路径上的链路 即使一直空闲也不会被使用，这样就造成整个网络在某处资源过度利用，而另外一些地方 网络资源闲置不用，使整个网络资源不能得到充分合理的利用。因此，提出了流量工程的 概念。流量工程从资源的可用性、当前的和期望的流量这一管理角度出发，来进行数据的 路由。 优化网络性能的过程被称为流量工程( t r a f f i ce n g i n e e r i n g ，t e ) ，它使用先进的路由算 法规定网络内部的业务流干线和规划业务流，将业务流映射到物理拓扑网络中，从而充分 提高网络的整体效率。流量工程可以平衡网络中不同的链路、路由器和交换机之间的业务 负载，有效地利用网络所提供的带宽资源。 ( 1 ) 流量工程系统组成 流量工程系统包括六个主要部分：拓扑与状态发现，路由计算，流量需求估计，图形 用户界面( g t n ) ，网络接1 2 1 ，以及数据知识库。 数据知识库存储所用共享数据对象的永久信息，如网络拓扑、链路状态、流量需求、 路由、策略等，系统中其它模块可以通过数据库存储、访问和交换信息。 流量工程系统需要确切地知道用户的流量需求，在v p n 服务中，流量需求可以在服 务提供商和客户之间的s l a 中说明。在另一些情况下，需求估计基于流量测试。 流量工程系统根据流量需求建立最佳路由之后，通过w 曲接口或者s n m p 配置网络 单元完成这些需求。 ( 2 ) 网络拓扑和链路状态发现 流量工程必须时刻关注网络拓扑和链路状态的变化，在配置网路时可以获得一些静态 信息，使用网络管理系统( 如s n m p 陷阱和轮询系统) 可以收集动态信息，如剩余带宽、链 路利用率等。 扩展路由协议( 如o s p f ) 可以周期性地广播链路状态信息，o s p f 应用范围很广，并且 已经为分配链路状态信息和构造拓扑数据库提供了必要的机制。所以，o s p f 也被扩展到 流量工程中用于拓扑和状态发现。 南京邮电大学硕士研究生学位论文 第三章m p l s 流量工程 o s p f 方法要求所有节点尽力同邻居建立并维持对等关系，个节点的邻居( 即对等体) 是跟它直接交换控制信息的节点，每个节点都记录着本地链路状态以及此状态与其它节点 或者网络管理站之间的通信信息，流量工程系统可以根据o s p f 链路状态信息建立拓扑数 据库。 ( 3 ) 路由计算 路由计算引擎是流量工程系统的“大脑 。 从流量工程角度出发，路由选择必须超越简单的最短路径算法，即需要根据流量需求、 拓扑结构和链路状态信息计算出最佳路由，解决资源优化、恢复以及抢占优先等问题，称 之为约束路i 扫( c o n s t r a i n t - b a s e dr o u t i n g ) 。 约束路由有两种实现方式：在线和离线。 离线方式根据当前信息对所有路由进行周期性计算，在维护期间完成路由更新。在离 线方式中，所有路由在改变之后都要进行重新优化。所以，网络路由结果更佳。但是，对 网络进行频繁、大规模的重新路由会导致数据流激增，从运营商的角度来看并不理想。此 外，由于路由计算时周期性地进行的，所以当网络增加新的流量需求时，容易产生额外时 延。 在线方式的路由计算以增量方式进行，即收到一条新请求后，路由计算模块只为新需 求计算最佳路由，当前需求下的路由并不会被调整。在线方式的资源利用率没有离线方式 高，但现有业务流的重新路由率却被降到最低。 在线和离线方式可以结合使用。例如，在网络繁忙时，新的路由需求可以采用增量方 式建立；当网络不太繁忙时，再用离线方式对所有需求做全面的最优化。 约束路由有两个基本要素：路由优化和路由设置。路由优化在给定一组约束条件的情况下， 根据流量需求选择路由；确定路由之后，再在整个网络实现路由设置，以便于业务流沿着 这些路由传输。 路由约束解决方案很多，有一些基于高等数学的方法，可对网络资源的总体效率进行 优化，还有一些是在i p 路由框架中使用启发式的方法。另外，一个特定的网络选择合适 的流量工程技术时要考虑很多因素，如网络配置、业务流特征以及需求分布等。 3 2 胛l s 流量工程的提出 在传统的i p 网络中实现流量工程是一个具有挑战性的问题。i n t e m e t 网络在短时期内 的快速增长，通信网络中各种业务的出现，尤其是实时的多媒体业务、交互式服务等，造 成网络流量的高速增长，流量瓶颈也日益明显，如果只靠单纯的扩容方式增加网络的带宽， 南京邮电大学硕士研究生学位论文第三章m p l s 流量工程 不仅网络建设成本高，周期长，而且会增加网络系统的复杂性。在网络中提供具有流量工 程的能力正是上述问题的一个最好的解决方案。 由于a t m 技术是宽带网络的核心技术，a t m 网络可以支并综合服务，并在网络工程设 计方面具有高度的灵活性，提供流量管理能力和o o s ，支持v p n 和多种业务类型。但由于 a t m 信令过于复杂，给广泛应用带来了不利。而i p 技术的简单、高效使其得以广泛应用 并迅速成为网络的主导技术。其灵活的路由体系结构，非面向连接的尽力而为的分组传送 方式，尤其适合非实时数据信息的传输。但i p 技术对网络流量的管理能力很弱无法提供 q o s 服务( 时延、带宽等) 保证，无法满足语音、视频图象等实时信息的传输要求。因此， 在实现流量工程的初期，主要是利用a t m 的流量管理能力，在i n t e r n e t 网络中使用基于 a t m 技术的重叠方式i po v e ra t m 实现流量工程。随着重叠模式的各种局限性以及m p l s 技术的出现，在网络中使用m p l s 实现流量工程在网络的扩展性、网络的管理等多个方面 更加具有良好的可操作性。使用m p l s 实现流量工程成为最具前景的解决方案。 3 3 即l s 在流量工程中的优势 m p l s 是近几年发展起来的新型网络交换技术。它主要是在传统的i p 网络中增加了面 向连接的特性，从而使得在传统i p 网络中实施流量工程成为可能。由于m p l s 采用集成 模型，将三层技术与链路层技术结合在一起，较之其它技术，m p l s 在实现流量工程方面 具有许多优势，主要体现在以下几个方面： ( 1 ) m p l s 集成了二层的标记交换和三层的路由技术。在m p l s 域内使用定长的短标签 对分组进行转发，不仅克服了a t m 交换机控制信令的复杂性，而且提高了使用传统路由 协议的路由器的转发效率。 ( 2 ) m p l s 流量工程是基于业务流的需求以及网络的状态约束为业务流选择路径的。 m p l s 流量工程采用约束的“显式路由”方式，使用此方式可选择满足业务流需求的路径， 从而克服了传统路由协议的逐跳选路方式的局限性。 ( 3 ) m p l s 流量工程可以使用多种策略属性，在不中断业务的情况下，恢复网元节点和 链路的故障。 ( 4 ) 通过手工的网管配置或是下层协议的自动配置，可以很容易的建立起不受传统逐跳 路由协议限制的显式l s p ，l s p 可以被高效的维护。 ( 5 ) 流量主干可以被使用并被映射到l s p 上，可以给流量主干规定一套属性来调整流量 主干的行为，可以给各种网络资源规定属性，对建立的l s p 通过的流量主干加以限制。 南京邮电大学硕士研究生学位论文 第三章m p l s 流量工程 ( 6 ) 既可以对业务进行组合，也可以对业务进行分割，而基于传统的路由协议的i p 转 发只支持对业务的组合，可以较容易的实现“约束路由”。 ( 7 ) m p l s 流量工程是一种软资源，网络管理人员可以随时根据需要启动并利用它，具 有调整周期短、见效快、开销低的特性。 m p l s 流量工程的主要原理是基于m p l s 支持“显式路由”功能，支持m p l s 网络域边缘 建立满足业务流需求和网络约束条件的最优路径，达到优化网络资源和满足业务流需求的 流量工程的目标。 3 4 肝l s 流量工程中的管理机制 m p l s 的流量管理机制主要包括路径选择、负载均衡、路径备份、故障恢复、路径优 先级及碰撞等。 l 路径的选择 m p l s 采用显示路由的方式为i p 包选一条从源到目的地的路径，网络中的不同节点 不需要再为i p 包选择路由，仅需根据c r l d p 信令中携带的路由信息将信令信息转发到 下一个节点。这种显示路由的选择是m p l s 入口节点l e r 上完成的，具体实现可以由操 作员配置或通过源路由协议实现。这种显示路由的优点就是：网络管理者可以根据网络资 源合理地引导业务的流向，可以避免网络业务流向已经拥塞的节点。 2 负载均衡 m p l s 可以使用两条或者多条l s p 来承载同一个用户的i p 业务流，合理地将用户业 务流分摊在这些l s p 之间。 3路径备份 可以配置两条l s p ，一条处于激活状态，另一条处于备份状态，一旦主l s p 出现故 障，业务立刻导向备份的l s p ，直到主l s p 从故障中恢复，业务再从备份的l s p 切回到 主l s p 。 4 故障恢复 当一条已经建立的l s p 在某一点出现故障时，故障点的m p l s 会向上游发送 n o t i f i c a t i o n 消息，通知上游l e r 重新建立一条l s p 来替代这条出现故障的l s p 。上游 l s r 就会重新发出r e q u e s t 消息建立另外一条l s p 来保证用户业务的连续性。 5 路径的优先级及碰撞 在网络资源匮乏的时候，应保证优先级高的业务优先使用网络资源。m p l s 通过设置l s p 的建立优先级和保持优先级来实现的。每条l s p 有n 个建立优先级和m 个保持优先级。 南京邮电大学硕士研究生学位论文第三章m p l s 流量工程 优先级高的l s p 先建立，并且如果某条l s p 建立时，网络资源匮乏，而它的优先级又高 于另外一条已经建立的l s p 的保持优先级，那么它可以将已经建立的那条l s p 断开，让 出网络资源供它使用。 3 5 实现御l s t e 的功能模型和运作原理 基于m p l s 流量工程集成模式的方式采用m p l s 技术，在网络中可以配置显式路由实现 流量工程。使用m p l s 技术实现流量工程集成模式的实现机制包括以下四个功能组成构件， 如图3 1 所示： ( 1 ) 报文转发组件； ( 2 ) 信息发布组件； ( 3 ) 约束路径选择组件； ( 4 ) 信令组件： l 5 ! 立 i g p 路由选择e r l s p 路由选择 晤碉丫 链路状态数 流量工程数 l 、 l ，r 据库 据库 l 布 信 一一n ， 、 1 3 。1 3 ，u 3 r r 口亩出1 ，1 ，x 生入 、r、，包输 l l 7 i 报转及早兀 j 图3 1m p l s 的功能组成构件 每一个功能构件都是一个单独的模块，报文转发部分负责转发数据，使用的是m p l s 技术。信息发布部分负责更新网络状态信息，通过支持流量工程扩展的i g p 实现。约束路 径选择部分负责根据收集的链路属性和拓扑信息采用约束路由计算源到目的节点的路径。 信令部分负责计算出路径后使用一定的信令协