（通信与信息系统专业论文）ngn核心网负载均衡的优化设计.pdf

南京邮电大学硕十研究生学位论文 摘要 摘要 下一代网络( n g n ) 的核心网是一个m p l s 网络，主要采用的是多协议标记 交换技术。随着网络流量几何级数递增，不同类型的业务流要求不同等级的服务 质量( q o s ) 保证。基于传统路由算法的当前网络己不能很好的同时承载巨大的数 据流和实时流。这种情况下，对整个网络的流量进行均衡分配，调节全网资源的 利用，使资源利用达到最优的要求越来越强烈。流量工程能够实现网络操作的高 效率和优化网络资源利用，提高业务服务性能，而m p l s 被认为是实现流量工程 的最有力工具。 本文讨论了n g n 核心网中基于m p l s 的流量负载均衡问题。在多路径流量 分配算法- - t b ( t r a f f i cb i f u r c a t i o n ) 的基础上，提出了一种基于链路关键性的多路 径负载均衡算法l c t b ( l i n k c r i t i c a l i t yt r a f f i cb i f u r c a t i o n ) 。该算法根据链路在网 络业务承载中的关键性，为链路设定不同的传输成本，通过最小化网络传输成本， 找出网络负载均衡性更好的多路径。i l o g 系列软件是一款规划优化软件，能优 化关键业务资源的分配。i l o gc p l e x 强大灵活的高性能优化程序，能解决庞大 的，全球范围内的线性规划划，混合整数规划，二次方程规划( q p ) 问题。我们 利用c p l e x 优化软件进行计算，结果表明：文中提出的基于链路关键性的l c t b 算法，比传统算法具有更好的网络均衡负载性，进一步缓解了网络拥塞问题，提 高了服务质量。 关键词：多协议标记交换，流量工程，负载均衡，多径路由 南京邮电大学硕一l ：研究生学位论文a b s t r a c t a b s t r a c t t h ec o r en e t w o r ko fn g n ( n e x tg e n e r a t i o nn e t w o r k ) i sam p l sn e t w o r k ， w h i c hm a i n l yu s 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 gt e c h n o l o g y a sn e t w o r kt r a f f i c i n c r e a s e sg e o m e t r i c a l l y , d i f f e r e n tl e v e l so fq u a l i t yo fs e r v i c e ( q o s ) s h o u l db e g u a r a n t e e df o rd i f f e r e n tt y p e so fs e r v i c e b e c a u s eo ft r a d i t i o n a ln e t w o r kr o u t i n g a l g o r i t h m s ，c u r r e n tn e t w o r kl a c kt h ea b i l i t yt oa d a p th u g ed a t af l o w sa n dr e a l t i m e s t r e a m i n gv e r yw e l l i nt h i ss i t u a t i o n ，i ti sm o r ei m p o r t a n tt oa d j u s tt h ew h o l en e t w o r k r e s o u r c e su t i l i z a t i o na n dt h ef l o wl o a db a l a n c e i np r a c t i c e ，t h eu s u a lk e yo b j e c to f t r a f f i ce n g i n e e r i n g ( t e ) i st oo p t i m i z et h eu s eo fn e t w o r kr e s o u r c e s ，a n di m p r o v e s e r v i c ep e r f o r m a n c e m p l si sc o n s i d e r e da st h em o s tp o w e r f u lt e c h n o l o g yt oa c h i e v e t h i sp a p e rm a i n l ys t u d i e so nh o wt or e a l i z et h et r a f f i cl o a d b a l a n c i n gp r o b l e mi n n g nc o r en e t w o r kb a s e do nm p l s t e c h n o l o g y o nt h eb a s i so ft ba l g o r i t h m ( t r a f f i c b i f u r c a t i o n ) ，t h ea u t h o rd e s i g n sam u l t i p a t hl o a d b a l a n c i n ga l g o r i t h m - l c t b ( l i n k c r i t i c a l i t yt r a f f i cb i f u r c a t i o n ) ，c o n s i d e r i n gt h ed i f f e r e n tl i n kc r i t i c a l i t y i nl c t b ， e a c hl i n ki ss e tac o s ta c c o r d i n gt oi t sl i n kc r i t i c a l i t y b ym i n i m i z i n gt h en e t w o r k t r a n s m i s s i o nc o s t s ，t h ep a t h sw i t hb e t t e rl o a d b a l a n c i n gp e r f o r m a n c ec a l lb ef o u n d e d i l o gi sa no u t s t a n d i n gs o f t w a r et oo p t i m i z et h ea l l o c a t i o no fi m p o r t a n tr e s o u r c e s i l o gc p l e xc a ns o l v el a r g e ，g l o b a ls c a l el i n e a rp r o g r a m m i n g ，m i x e di n t e g e r p r o g r a m m i n g ，a sw e l la sq u a d r a t i cp r o g r a m m i n g ( q p ) i s s u e sb e c a u s eo fi t sp o w e r f u l a n df l e x i b l eh i g h p e r f o r m a n c eo p t i m i z a t i o np r o c e d u r e t h ea u t h o ru s e sc p l e xt o d e s i g na n dc o m p u t e ，t h er e s u l t ss h o wt h a t ：l c t ba l g o r i t h mb a s e do nl i n kc r i t i c a l i t yi s b e t t e rt h a nt h et r a d i t i o n a lm e t h o di nt h el o a d b a l a n c i n gp e r f o r m a n c e l c t bc a n f u r t h e re a s et h en e t w o r kc o n g e s t i o np r o b l e m s ，a n de n h a n c et h eq u a l i t yo fs e r v i c e k e yw o r d s ：m p l s ，t r a f f i ce n g i n e e r i n g ，l o a d b a l a n c i n g ，m u l t i p a t hr o u t i n g 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意 研究生签名：茎邀 日期：礁至： ：7 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：垂公喳垒导师签名： 日期：掣 南京邮电大学硕上研究生学位论文 第一章绪论 1 i 课题研究背景 第一章绪论 随着网络技术的发展和用户需求的多元化，下一代网络( n g n ，n e x t g e n e r a t i o nn e t w o r k ) 的研究已成为当前学术界和产业界关注的热点。 n g n 综合了固定电话网、移动电话网和i p 网络的优势，使得模拟用户、数 字用户、移动用户、a d s l 用户、i s d n 用户，i p 窄带网络用户、i p 宽带网络用 户甚至是通过卫星接入的用户都能作为下一代网络中的一员相互通信。n g n 包 含的内容非常广泛：从计算机网络看，n g n 是以高带宽和i p v 6 为基础的n g i ( 下一代互联网) 。从传输网络看，n g n 是以a s o n ( 自动交换光网络) 和g f p ( 通用帧协议) 为基础的。从移动通信网络看，n g n 是以w c d m a 和c d m a 2 0 0 0 为代表的3 g 。从电话网看，n g n 是指以分组交换和软交换为基础的电话网络。 n g n 采用了相对廉价的i p 等网络作为中间传输的载体。其核心网是一个 m p l s 网络，可以提供包括话音、数据和多媒体等各种业务综合开放的网络构架。 在n g n 网络中，业务的传递不仅仅需要可达性，更多的用户要求保证业务的服 务质量i ( q o s ，q u a l i t yo f s e r v i c e ) 。网络规模和业务量在迅猛增加，而带宽等资 源的增长速度远远跟不上前者的发展。因此，以i p 协议为主的n g n 核心网中如 不实行有效的路由算法，将不能很好的满足业务的服务要求。 传统的路由协议如o s p f 2 1 、i s ，i s 【3 】等，基于目的地址最短路径算法。选择 到目的地址度量( 如距离、跳数、代价等) 最短的一条路径。优点是实现简单，但 不考虑网络可用带宽以及流量的特征，短的路径容易阻塞，而较长的路径容易空 闲。这会导致某些网络节点过度拥塞，而有些链路被闲置。网络资源未合理的使 用，效率达不到最大化，网络性能也会降低，服务质量( q o s ) 也无法保证。 为了对最短路径造成的负载不均衡进行改善，后来在o s p f 基础上提出了等 价多路径( e c m p ，e q u a lc o s tm u l t i p a t h ) 【4 】方法。当存在多条代价相等的最短 路径时，将负载平均分摊到几条最短路径上。这在一定程度上均衡了网络的负载， 南京邮电大学硕：研究生学位论文第一章绪论 使得当存在多条最短路径时，业务流能在多少路径分摊，不会因业务流超出一条 最短路径的可用带宽而造成最短径上关键链路拥塞。但其调节作用比较有限，尤 其当只有一条最短路径存在时，其效果等价于s p f 算法。 1 2 课题提出 传统路由算法主要是考虑节省资源，而未考虑网络当前可用资源，链路负载 程度对选路的影响。因此，选路时通常采用静态度量值如距离、代价、跳数、链 路容量等最短的路径传输业务流。这种度量值的缺陷是不能反应当前网络的动态 负载情况。有可能来自不同源地址，而目的地址相同的业务流都通过同一条链路， 而造成此链路过度拥挤，其他链路却很闲置。拥挤链路的数据包的到达率超出节 点的处理能力，将导致数据包延迟，甚至丢弃，影响整个传输过程的时延、抖动、 丢包率，用户会明显感觉到服务质量的下降。 研究表明，目前造成网络堵塞的原因主要有两个：一是网络资源不足，不能 满足客户流量要求；二是由传统路由算法导致流量分布不均造成的局部拥塞。 第一种拥塞，可通过网络扩容和使用经典的拥塞控制技术【5 j 【6 j 加以改善。 第二种拥塞，单纯靠增加网络容量，既造成网络运营商成本增加，网络的综 合性又未得到增强，不能从根本上解决问题。网络运营商需要的是协调、控制和 有效利用现有资源来满足用户需求，实现资源利用最大化和利润最大化。因此， 希望在原有网络不扩容情况下，通过网络的调节和控制功能，使流量分布更合理。 解决这种由网络资源使用不均衡引起的拥塞、性能下降问题，需要引入流量 工程( t e ，t r a f f i ce n g i n e e r i n g ) 技术【7 】【8 1 。流量工程主要指合理安排业务流在网络 中的流向，以避免造成网络资源的不均衡使用，从而优化网络性能。 n g n 核心网络中，流量工程作为路由结构中一个重要的辅助部分，它能够在 沿网络中备选路径转发业务时提供辅助信息。流量工程在选择通路时往往并不简 单的选择两个设备之间的最短路径。通过这种方式，网络中负载较轻的网段和链 路能够得到充分利用，同时也减轻了繁忙网段及链路的负载。整个网络的流量可 以被均匀分摊到全网各结点。 n g n 核心网是一个m p l s 网络，而m p l s 网络主要利用标签交换路径实 施流量工程。网络运营者或网络管理应用软件可以通过建立显式路由一标签交换 2 南京邮电大学硕：i ：研究生学位论文第一章绪论 路径( e x p l i c i tr o u t i n g l s p ，e r l s p ) 来控制业务流的流向。m p l s 被认为是下 代i n t e m e t 骨干网络技术。基于m p l s 的流量均衡算法和技术的研究，是学者和 用户都比较关心的热点。 1 3 国内外研究状况 早期的流量工程只是通过简单的改变路由度量值来实现。即为每一条链路指 定一个度量，负载重的链路指定的度量大，空闲的链路指定的度量小，然后通过 最短路径算法计算出一条路径传输业务流。然而随着网络规模的不断扩大，由于 网络中路由的交互作用，部分链路度量的改变常常会影响到网络中其他的路径， 会导致全网范围内无法意料的流量抖动。算法只基于网络拓扑而不考虑业务负载 情况，无法真正达到全网的优化配置。 随着a t m 技术的成熟，a t m 交换机开始取代主干网上的路由器，在i n t e m e t 的骨干结构中，其边缘使用o c 3 速率a t m 接口的路由器，核心使用o c 1 2 速 率的a t m 交换机。基于a t m 核心的网络采用了一种i p o v e r - a t m 的覆盖模型【1 1 1 ， i p 运行在a t m 网络上，路由器在a t m 网络的边缘环绕，每个路由器通过一系 列经由a t m 物理拓扑配置的永久虚电路( p v c ) 与其他路由器通信。p v c 是一种 显式路由，i s p 可以通过控制p v c 的路由来控制网络中的流量，使流量分布均 衡，资源使用更有效。这种i p o v e r - a t m 方式的弱点是需要对两个不同的网络进 行管理：a t m 基础结构和逻辑的i p 覆盖。增加了网络的复杂性。随着核心路由 器技术的发展，a t m 骨干网逐渐被路由器所取代。 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 ，多协议标记交换) 技术是被普遍看好 的高速骨干网络技术，它将第二层交换和第三层路由结合起来的。将路由与转发 分离，将基于标签交换的数据转发机制与网络层的选路机制结合在一起，以适应 多种协议与不同规模的网络。m p l s 技术的出现，不仅解决了重叠模型实现复杂 和难以扩展的问题，并为解决流量工程问题开辟了新途径，被认为是目前流量工 程的最好解决方案，也是目前网络研究的热点。 对于采用m p l s 实现流量工程，目前i e t f ( i n t e m e te n g i n e e r i n gt a s kf o r c e ) m p l s 和t e 两个工作组都已经提出了一些相关的r f c 和大量的i n t e r n e t 草案， 如r f c 2 7 0 2 i 7 】描述了在m p l s 网络中实施流量工程的要求。r f c 3 2 7 2 t 9 1 对流量 3 南京邮电大学硕b 研究生学位论文第章绪论 工程及其基本原理进行了总结，r f c 3 3 4 6 t l o 】描述了m p l s 流量工程的适应性 i t u t 和m p l s 论坛也都分别把m p l s 流量工程作为研究工作之一。很多网络设 备厂商也致力于这方面的研究，希望在他们的产品中支持流量工程。然而虽然 m p l s t e 的标准已初步完善，但一些技术仍在发展中，如均衡负载。国内的研 究多停留在理论阶段，对于m p l s t e 的实现涉及较少，这些有待于进一步研究。 1 4 本文研究内容和成果 本文讨论了m p l s 流量工程，重点研究了m p l s t e 中的均衡负载技术。文 章首先简单介绍了m p l s 的体系结构和基本运作机制，着重讨论了与传统i p 网 络以及i p a t m 网络相比，m p l s 网络的优势，并具体介绍了m p l s t e 技术基 础和组成部件，指出了m p l s t e 运作机理和研究热点。 m p l s 作为一种先进的转发机制为t e 的实施提供了便利，负载均衡( l o a d b a l a n c i n g ，l b ) 1 1 2 】是其中的重要功能。 多路径路由算法( m l r ) 是流量工程中的一个能够最大限度进行流量均衡的 方法，能够达到最优的流量性能。相对于单径路由，多径路由策略的优势在于对 网络资源的充分利用和网络性能的优化。目前对于多径路由已展开广泛的研究。 优化路由可以有很多种目标函数，最小化最大带宽利用率是其中最常用的一种。 即对网络中负载最重的链路利用率( 即最大链路利用率) 的最小化，以确保流量 避开拥塞的热点以缓解该网络部分的压力，使网络容纳更多的业务流，并确保网 络流量分布的平衡性。 在多路径均衡算法中，基于最小化最大链路带宽利用率的流量分配算法 t b ( t r a f f i cb i f u r c a t i o n ) 0 3 1 能在链路容量、跳数限制等管理策略和约束条件下， 很好的均衡网络中的负载。然而算法的第二步中，是以最小化网络带宽资源的利 用为目标函数的。即在满足最小化最大带宽利用率的约束下，选择利用的资源最 小的一组路径传输。链路根据在网络中传输的业务流的流量的不同，其关键性是 不同的。在t b 算法未考虑链路的关键性的不同，仅考量利用网络资源的多少。 从均衡负载而言，这是个值得关注的问题。事实上在选路时，应考虑尽量避免 负载重、关键性大的链路，而优先选择负载轻的，处于空闲状念的链路。这样才 能缓解网络拥塞，提高q o s 性能，通过网络均衡，为更多的业务流服务。 4 南京邮电大学硬1 ：研究生学位论文 第一章绪论 因此，本文基于链路的关键性，为链路设定不同的成本，在t b 基础上提出 了基于链路关键性的l c t b 算法，目标函数为最小化网络传输成本。最后，运用 混合整数规划( m i x e di n t e g e rp r o g r a m m i n g ，m i p ) 方法建立数学模型，采用c p l e x 优化软件解决此混合整数规划问题，为业务流的建立求出趋近最优的路径。计算 表明，l c t b 较t b 算法和其他传统算法有一定的优越性，网络分布更趋平衡， 网络的吞吐量，q o s 性能都得到了改进。 1 5 论文的组织 本文共分六章，各章的主要内容如下： 第一章首先介绍了课题的研究背景，在传统路由算法存在局限性的基础上， 指出了n g n 网络实现流量工程研究的必要性。然后分析基于m p l s 的流量工程 路由技术，提出多径路由的优越性，并指出链路关键性思想和l c t b 算法通过改 变最优化目的函数实现负载均衡的优势。 第二章描述了基于m p l s 的流量工程，首先对m p l s 网络的体系结构，在 n g n 网络中的应用，进行了简单的介绍。然后研究了流量工程的概念以及m p l s 下的流量工程的多个方面的内容。在此基础上阐述了m p l s 流量工程的实现模 型和一些控制信令。 第三章研究了网络中的路由算法。分解介绍了目前使用的一些静态路由算 法，动态路由算法和基于约束的路由选择算法。 第四章是本论文的核心内容。这一章主要讨论了带有约束条件的多路径均衡 算法，重点研究了流量分配算法- - t b 。详细介绍了其算法实现，数学模型建立 和算法的优势。在此基础上，指出t b 算法不足之处。并提出了改进方法来更好 的均衡网络负载，提升网络性能。这部分内容也是本课题的主要工作体现。 第五章描述了数学规划的相关知识，并讲解了数学规划优化软件c p l e x 的 卓越功能、优势，以及使用方法。这一章通过具体的实验来验证上一章提出的改 进方法的有效性，并同现有的一些算法均衡算法做比较，从实验的角度对改进之 处进一步加以验证。 最后，对论文的研究工作进行总结，并提出可作进一步研究的一些问题。 5 南京邮电大学顶：t 研究生学位论文第二章m p l s 与流量t 程 2 1m p l s 概述 第二章m p l s 与流量工程 m p l s 最初是为了解决i p o v e r a t m 叠加模型的种种弊端。各个研究机构结 合a t m 的高效转发性能和i p 灵活的控制能力，提出了m p l s 的解决方案。 m p l s 技术【3 9 1 是在c i s c o 公司的标签交换( t a gs w i t c h i n g ) 技术【1 4 】、t o s h i b a 公 司的信元交换路由器( c e l ls w i t c h e dr o o t e r ，c s r ) 技术【1 5 】等技术的基础上发展起 来的。它利用嵌入在i p 数据包中的标签进行数据包的转发，是一种将第二层的交 换技术和第三层的路由技术结合起来的一种l 2 l 3 集成数据传输技术。m p l s 基 于标签转发技术i l6 1 ，与a t m 交换类似，它引入了固定长度的短标签( l a b e l ) 作为 在m p l s 网络中进行数据转发的依据。m p l s 可以支持多种网络层上的协议如 i p v 4 、i p v 6 、i p x 、a p p l e t a l k 、d e c n e t 、c l n p 等，还同时可以兼容第二层上的 多种数据链路层技术，如a t m 、帧中继、p p p 、以太网等。 2 1 1m p l s 的相关概念 l a b e l ：标签。用于标识转发分组一个简短的、固定长度的、仅具有本地意义 的标识符。图2 1 中给出了4 字节填充标签的格式。 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 ) ：转发等价类。具有相同处理方式的一组 i p 包。属于同一f e c 的分组在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 网络的核心交换机， 位于m p l s 网络中部，它提供标签交换、标签分发功能。 l e r ( l a b e le d g er o u t e r ) ：标记边缘路由器。m p l s 网络同其他网络的边缘设 备，提供流量分类和标签映射( 入口) 、标签移除( 出口) 功能。 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 标记以及他们之前的链路组成。 l i b ( l a b e li n f o r m a t i o nb a s e ) 标记信息库。作用类似于路由表 6 南京邮电大学硕士研究生学位论文第二章m p l s 弓流量- 下程 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 ) ：标记分发协议。相当于传统网络中的信令 协议，负责标记的分发与维护。l d p 是m p l s 专门定义的标记分发协议， m p l s 可用的协议还有c r - l d p ( c o n s t r a i n t b a s e dl a b e ld i s t r i b u t i o np r o t o c o l ， c r l d p ) ，r s v p ( r e s o u r c er e s e r v a t i o np r o t o c o l ，r s v p ) 的扩展等。 2 1 2m p l s 工作原理 标签：2 0 b i t s c o s - 4 k 务等级，3 b i t s s ：堆栈底标志i b i t s m ：生存坶j 。8 b i t s 图2 1m p l s 标签格式 而常规的i p 路由，基于最长地址匹配路由查找数据包逐跳转发。每个节点 都要独立分析i p 包头，并基于i p 地址做出路由决策。而m p l s 基于短标签交换 的数据转发，只是在分组进入网络的边缘节点处对i p 包头进行分析，后续节点 不再分析包头，路由决策的做出也不仅仅是根据i p 地址，它可以依据多种参数， 如q o s 参数、流量工程服务参数等。 在m p l s 中所有进入网络的分组都被指定到某个特定的f e c ，每一特定f e c 都被编码为一个短而定长的值( 即标记) 。标记加在分组前成为标记分组，再转 发到下一跳，在后续的每一跳上，利用标记作为指针，指向下一跳的输出端口和 一个新的标记，无需分析分组头。标记分组用新标记代替旧标记后，经指定的输 出端口转发。 m p l s 中的路由仍然使用第三层的路由协议，如o s p f 、b g p 等。l s r 与普 通的路由器一样也要不断的更新和维护路由表。l s r 还要根据这些路由信息在 m p l s 的控制信令下分配标记，建立并维护标记信息库l i b ，将第三层的路由信 息映射到第二层。l s r 的功能结构可以简单地由图2 - 2 所示。 7 南京邮电大学硕士研究生学位论文第二章m p l s 与流量t 程 图2 2l s r 功能模块图 m p l s 的工作过程为：在m p l s 设备之间运行路由协议，通过路由协议获取 网络拓扑信息，建立路由表。根据路由表使用标记分发协议( l d p 、r s v p 等) 在 节点间分发标记信息，建立l s p 。当一个数据流到达入口l e r 后，l e r 分析数 据包的i p 包头，把数据包映射到f e c 上，然后根据所属f e c 加上标记。在以后 的转发过程中，l s r 只根据数据流的标记进行查表、交换、转发，直至出口l e r 。 到达出口l e r 时，将标记移去，恢复原始数据流。图2 多是m p l s 网络中转发 数据过程的一个例子。 i 羞人ji。lj l 禺竹一 船璐冈i i 嗽1 l 7 1 5 r i7 i 唧l 艘曲终 i g p ：； ： !i - 一i t u | t 4 - 童，”j ； i ； ， 入数据出端口帛标霉入鳊口，入标签 出湍口出标签 l 入蔬口 入标签出数据 2 83 g1j l2 j 图2 一乡m p l s 转发数据的过程不意图 建立l s p 的方式主要有两种：“h o pb yh o p 逐跳路由和显式路由。 “h o p - b y - h o p ”逐跳路由 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 网络中，数据包头在整条路径上从始至终都没有被 检查。在每一个节点，m p l s 生成的树是通过一级一级为下一跳分配标记，而且 客 南京邮电大学硕士研究生学位论文第二素m p l s 与流量工程 是通过与它们的对等层交换标记而生成的。 显式路由 m p l s 最主要的一个优点是它可以利用流量设计“引导”数据包，比如避免 拥塞或者满足业务的q o s 等。m p l s 允许网络的运行人员在源节点就确定一条 显式路由的l s p ( e r l s p ) ，以规定数据包将选择的路径。 e r l s p 从源端到目的端建立一条直接的端到端的路径，m p l s 将显式路由 嵌入到限制路由的标记分配协议的信息中，从而建立这条路径。 2 1 3m 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 节点维护的标记转发信息库( l f i b ) 来转发带有标记的数据包。每个m p l s 节点维护着与m p l s 转发相关的两张表：标记信息库( l i b ) 和l f i b 。 控制平面 m p l s 控制平面负责维护l f i b 表和向l f i b 添加条目。m p l s 控制模块包括 使用传统的内部网关协议( i g p ) 建立f e c 表的单播路由选择模块：使用多播路由 选择协议来建立f e c 表的多播路由选择模块；使用m p l s 隧道定义和对i s i s 或o s p f 路由选择协议的扩展来建立f e c 表的流量工程模块。 这种控制与转发分离的结构使每个部分都可以独立的丌发和修改，便于实施 新业务。m p l s 控制与转发完全分离的特点为控制数据流在网络中的分布带来了 极大的灵活性，所以m p l s 被普遍看好是解决q o s 和流量工程的基本技术。 m p l s 非常完美地将i p 与a t m 结合在一起。m p l s 实现不仅能高速转发i p 包，同时可以保证用户对于不同服务质量的要求。 9 南京邮电大学硕二j j 研究生学位论文 第一二章m p l s 与流量丁程 2 2 流量工程概述 2 2 1 流量工程简介 流量工程 9 1 是一种能将业务流映射到实际物理通路上，同时又可以自动优化 网络资源以实现特定应用程序服务性能要求的，具有宏观调节和微观控制能力的 网络工程技术。有效、可靠地运行网络，同时优化网络资源的使用和提高业务的 服务性能，是实现流量工程的目标。由于网络商业化和竞争性的加剧以及网络资 源的局限性，流量工程己经成为许多大型自治系统不可缺少的功能。从网络流量 的观点来看，流量工程的功能可以看作是网络中业务流量分布的优化；从i s p 的 角度来看，流量工程的功能是使网络资源得到合理利用和网络性能得以优化：从 用户的角度看，流量工程的功能是保证用户的q o s 得到满足。 流量工程的性能指标分为两类： 一类是面向业务流对象的。面向业务流的性能目标主要与q o s 相关并试图 从端到端的分组延时、分组延时抖动和服务响应时间等方面来改善网络性能。其 主要性能目标有：分组丢失的最小化、延时最小化、吞吐量最大化。 另一类是面向资源对象的。面向资源的性能目标主要与网络资源有关，它试 图在网络资源利用率和网络吞吐量等方面来改善网络性能。有效的网络资源管理 是实现面向资源优化使用目标的手段。其主要策略思想就是通过有效的资源调 配，最小化最大拥塞的发生和最大化网络资源的使用。 总之，流量工程的应用旨在通过优化网络资源利用率来提高网络的性能。带 宽是当前网络上的一种非常重要的资源。因此，流量工程的一项中心任务就是对 带宽资源进行有效的管理。 2 2 2 流量工程实现模型研究 流量工程存在两种模型：面向无连接的t e 模型和面向连接的t e 模型 面向无连接的t e 模型 无连接的模型基于现有的i p 路由协议模型，是对现有的链路状态或距离矢 量路由协议的扩展。在这种模型中，每一个节点独立的决定下一跳的去向，他们 1 0 南京邮电大学硕：t ? 研究生学位论文 第二章m p l s 与流量工程 大多是通过改变路由参数或其他间接的方法实现的。一种方法是通过改变链路度 量值以控制流量在网络中的流向，链路的度量值改变后，将触发各个节点重新计 算到目的节点的最短路径，并更新路由表。另一种方法是采用多路径路由算法寻 找源到目的间的多条路径，将数据流在这多条路径间分摊，均衡网络负载。 面向连接的t e 模型 面向连接的t e 模型一般使用一定的信令协议建立路径，并在发送数据前先 进行资源预约，预约完成后开始传送数据。采用a t m ，、m p l s 等的实现模型都 是面向连接的形式。这种模型中，路径通常是由源节点或某些中心节点来决定， 然后使用信令协议在路径上的所有节点间分配路径的标识符，由一系列的标识符 决定数据包在网络中的流向，确定了数据的传输路径。 这种模型将控制和转发两种功能分开，控制基于全局标识( 如i p 地址) ，转 发基于本地标识( 如m p l s 的l a b e l ) ，信令协议将两者联系起来，并在他们之 间达成一致。这样，当引入新的t e 功能时只需要在控制平面上做修改就可以。 这种面向连接的t e 模型提高了网络的可靠性，确保了t e 功能的直接实现，。面 向连接的t e 模型通常采用显示路由方式，沿着明确的路径对数据分组进行转发， 便于对数据流的控制以及复杂t e 功能的实现，因此，无论是产业界还是学术界 都倾向于采用面向连接的t e 模型。 2 3m p l st e 实现模型 基于m p l s 的流量工程【1 7 】【1 8 l ，利用m p l s 技术在网络中可以配置显式路由 的优势实现流量工程。 m p l s 的流量工程包括以下四个组成部分，如图力午所示： 包转发单元。负责转发数据，使用的是m p l s 技术； 信息分发单元。负责更新网络状态信息，通过支持流量工程扩展的i g p 实现： 约束路径选择单元。负责根据收集的链路属性和拓扑信息采用受限路由计算 源到目的节点的路径； 信令单元。负责计算出路径后使用定的信令协议在各个节点间就标签达成 一致，建立起标签交换路径l s p 。 南京邮电大学硕一l ：研究生学位论文第二市m p l s 了流量丁程 图2 - 4m p l s 流量- - | ：样组成示意图 m p l s t e 的实现可按照如下步骤进行： 流量采集：对目前网络流量进行采集，获取网络中各设备和链路的流量状况； 流量分析：根据流量采集的数据进行分析，找出流量分布中存在的问题； 流量优化：重新优化流量的分布，不同的流量可按不同的路径传输； l s p 的发布：根据流量优化的结果，在网络中发布l s p ： 流量映射：将流量映射到相应的l s p 上。 2 4m p l st e 的信令控制协议 对于m p l st e ，通过信令协议在各个节点间就标记达成一致，建立起l s p 。 实现m p l st e 的信令协议主要有两种：c r l d p 1 9 1 和扩展的r s v p 2 0 】。 基于约束的标签分发协议( c r l d p ) l d p 是m p l s 工作组专门为m p l s 制定的一套信令协议，它支持h o p b y h o p 的l s p 建立。c r l d p 是对l d p 协议的功能扩展，与l d p 使用相同的消息集和 传输方式，不同的是c r l d p 使用受限路由进行选路，l d p 使用o s p f 、b g p 等传统的路由协议。 c r - l d p 对l d p 协议中的标签请求、标签映射、通知等消息进行了扩展： ( 1 ) 显式路由属性：用于携带显式路由信息； ( 2 ) 路径抢占属性：对每条路径标识建立优先级和保持优先级，分别用以判 断能否抢占己存在路径的资源和能否被新路径抢占自己的资源： ( 3 ) 路径锁定属性：对路径进行固定，即使有更好的路径，也不再理会； 1 2 南京邮电大学硕l ：研究生学位论文第一二章m p l s 与流量丁程 ( 4 ) 资源类别属性，网络管理员对网络资源进行的分类。 扩展的资源预留协议( 扩展的r s v p ) r s v p 最初提出的目的是在i p 网络中支持综合业务的信令协议。为了用于 在m p l s 网络中支持流量工程，对原有的p a t h 、r e s v 消息以及r s v p 原有对 象进行扩展： ( 1 ) 标签请求对象：向下游l s r 发出标签分配的请求，用于p a t h 消息中； ( 2 ) 标签对象：表示标签值，用于r e s v 消息中； ( 3 ) 显式路由对象：包含显式路由信息，用于p a t h 消息中； ( 4 ) 记录路由对象：记录实际建立的l s p 上的所有节点，p a t h 和r e s v 两 种消息中都使用； ( 5 ) 会话属性对象：指定l s p 的优先权、抢占权和快速重路由属性，用于p a t h 消息中。 c r ，l d p 和扩展的r s v p 实现的功能大致相似，但是它们的控制体系区别很 大，二者无法实现高效的互联互通。上述两种技术都拥有各自的优缺点，并且均 得到大企业的支持。 1 3 南京邮电大学硕：t 研究生学位论文第二三帝具有t e 功能的路由算i 去研究 第三章具有t e 功能的路由算法研究 业务在网络中的传输最终要映射到实际的物理拓扑上，要保证业务流的q o s 要求和网络整体性能的优化，最终也必须通过调整和控制业务流在网络中所走的 路径来实现。只有使用了良好的路由机制才能保证流量在网络中的合理分布，避 免拥塞的产生，最高效率的使用网络资源。所以路由问题是流量工程中的一个重 要问题，也是一个基本问题。 路由选择算法是路由器网络层软件的一部分，负责确定所收到的数据包应传 送的外出路线。可分为静态路由算法和动态路由算法等。 3 1 静态路由算法 静态路出算法在路由选择之前由网络管理员建立路由表的映射，所有的路由 信息事先脱线计算好，在网络启动时下载到路由器中。只有网络管理员更改时， 映射才会改变。静态路由的算法的设计比较简单，其优点是简单、高效、可靠， 对网络没有额外开销。但其不根据实测或估计的网络当前的通信量和拓扑结构来 作路由选择，不适合应用在在大型的多变的网络中。 典型的静态路由算法有最短路径算法、扩散法和基于流量的路由选择算法。 最短路径算法 算法的主要思想是建立一个网络图，图中的每个节点代表一个路由器，每条 弧表示一条通信链路，找出需要通信的一对路由器间的最短路径进行数据传输。 路径的度量值是一些静态的参数，如跳数，距离，代价等。在多数通用的情 况下，链路的代价标注可以用链路带宽、平均流量、队列平均长度、传输延迟等 因素的函数来计算出来。 典型的算法有d i j k s t r a 算法，用来计算一个节点到其他所有节点的最短路径。 以起始点为中心向外扩展，直到终点。d ! j k s t r a 算法能得出最短路径的最优解， 但由于它遍历计算的节点很多，效率很低。 扩散法 1 4 南京邮电大学硕l - 研究生学位论文第三章具有t e 功能的路由算法研究 扩散法是把收到的每个数据包从除了数据包到来的线路外的所有线路发出， 此过程会产生大量的重复数据包，有可能是无穷多个数据包。 扩散法的一个稍微实际的变种是选择性扩散法( s e l e c t i v ef l o o d i n g ) 。在这种 算法中，路由器并不将每个进来的数据包从每一条输出线路上发出，而是仅发送 到与正确方向接近的那些线路上。 基于流量的路由算法 这是一种既考虑拓扑结构又兼顾负载的静态路由算法，在一些网络中，每对 节点之间平均数据流量是相对稳定和可预测的，即预先知道i 到i 的平均通信流 量的情况下，有可能对流量进行数学分析，以优化路由选择。 3 2 动态路由选择算法 动态路由是路由器根据路由选择协议( r o u t i n gp r o t o c 0 1 ) 提供的功能，自动 ， 学习和记忆网络运行情况，在需要时自动计算分组传输的最佳路径，因此能实时 地适应网络的变化。路由器之间根据一定的规则相互发布路由更新信息，路由选 择软件就会根据更新信息重新计算，并发出新的路由更新信息。这些信息通过各 个网络，引起各路由器重新启动其路由算法，并更新各自的路由表以动态地反映 网