（通信与信息系统专业论文）internet+qos及流量工程关键技术的研究.pdf

北京邮电大学博士学位论文摘要 摘要 市场的巨大驱动力使m t e m e t 面临着新的机遇与挑战。提供满意的应用服务质量， 已经成为i n t e m e t 当前和未来持续性发展的重要方向。流量工程是一种网络优化和控制 技术，其目标是实现网络性能的优化以及网络资源的合理利用。因而流量工程的实施 对于i n t e m e tq o s 保证有着不可或缺和不可替代的意义。 本文的研究课题正是基于这背景提出的，研究的核心是满足q o s 和流量工程目 标的网络路由优化控制的研究，同时探索了遗传算法，混沌优化以及局部搜索等优化 方法，在网络流量工程方面的应用。主要研究工作包括：满足流量工程目标的m p l s 显式路由优化；多q o s 约束下的负载均衡：流量工程动态路由算法；区分业务环境下 的流量工程：以及基于传统路由协议实施流量工程。 总结起来，本文的主要工作包括如下几个方面： 1 对基于m p l s 技术实现流量工程进行了分析探讨。提出一种群双搜索优化算法， 实现以拥塞最小化为目标的显式路由全局优化；阐述了算法思想和特点，利用计算 机仿真对算法性能进行分析，并与其它优化算法进行了比较。仿真结果证明本文算 法是种行之有效的优化算法。 2 深入研究了多约束下的流量工程问题。建立了多q o s 约束下的网络流量分布优化 数学模型，提出一种两阶段求解方法，将原问题分解为两个子问题：计算满足多 q o s 约束的备选路由集合；基于备选路由集合，进行路由全局优化，均衡网络负载。 针对第一个问题，提出三种启发式算法，详细阐述了算法理论基础对算法性能进 行了分析，并与相关的研究工作进行了比较：针对第二个问题，提出一种基于启发 式自适应遗传算法的优化算法，仿真结果证明该算法显著改善了传统s p f 路由算 法易于导致的网络流量分布不均衡的状况。 3 通过详细分析当前基于动态路由方式实施m p l s 流量工程的研究工作，提出一种 基于晟小干扰思想的改进动态路由算法，以提高网络吞吐量作为流量工程目标。算 法综合考虑了网络拓扑和流量分布状况，提出分等级的链路关键度定义。在同样的 仿真条件下，通过对几个典型的性能指标进行仿真的结果显示，本文算法优于其它 几种典型的路由算法。 4 对区分业务环境下的流量工程进行了有益的探讨，指出目前区分业务流量工程研究 中的不足之处；分析了区分业务环境下流量工程的主要目标并转化为路径代价的 定义；在分析不同业务类型特点的基础上，提出一种新的集成的区分业务动态路由 策略，具有如下主要特点：反映了不同q o s 业务类型之间的差别；综合考虑了流 量工程与q o s 要求；通过路径代价的定义，将q o s 类型业务的路由与b e 类型业 务的路由联系起来。 5 ，提出一种基于传统路由协议实施流量工程的多目标路由优化模型，综合考虑了拥塞 代价和时延代价，并提出一种基于混沌群搜索的优化算法。仿真结果显示经过优化 之后，网络业务流的分布得到了良好的平衡，因而提高了网络的服务能力。 关键词：q o s ；流量工程；m p l s ；区分业务；约束路由；遗传算法：局部搜索；混沌 北京一电大学博士学位论文摘要 a b s t r a c t n o w a d a y si n t e m e tf a c e sn e w c h a n c e sa n dc h a l l e n g e st h a n k st ot h et r e m e n d o u sd r i v i n g f o r c ef r o mm a r k e t c u r r e n ti n t e r a c tm u s te v o l v et op r o v i d eg u a r a n t e e dq u a l i t yo fs e r v i c en o m a t t e ri nt h es h o r to rl o n gr u nt e r m t i a 硒ce n g i n e e r i n g ( r e ) i sc o n c e r n e dw i t hp e r f o r m a n c e o p t i m i z a t i o na n dc e n t r e io fo p e r a t i o n a ln e t w o r k s 1 1 l em a j o rg o a lo ft ei s t oo p t i m i z e n e t w o r k 自限蕊cp e r f o r m a n c ew h i l es i m u l t a n e o u s l ya c h i e v i n ge c o n o m i cr e s o u r c eu t i l i z a t i o n s ot eh a sb e c o m ea ni n d i s p o n s a b l ea n di n s u b s t i t u t a b l ee l e m e n tt oi m p l e m e n ti n t e r n e tq o s t h es u b j e c t so ft h i sd i s s e r t a t i o na r c j u s tb r o u g h ta b o u ti ns u c hb a c k g r o u n d s o u rs t u d i e s p a ya t t e n t i o nt or o u t i n go p t i m i z i n g c o n t r o lw i t hr e q u i r e m e n t so fq o sa n dt e a sw e l la st h e a p p l i c a t i o n so f s o m eo p t i m i z a t i o na l g o r i t h m st ot ep r o b l e m s ，s u c ha sg e n e t i ca l g o r i t h m ， c h a o so p t i m i z a t i o n ，a n dl o e a ls e a r c h i nm o r ed e t a i l ，o u rr e s e a r c hw o r kf o e l l so nt h e f o l l o w i n gi s s u e s ：劓口l se x p l i c i tr o u t i n go p t i m i z a t i o nw i m t h eo b j e c t i v e so ft e ；n e t w o r k l o a db a l a n c ew i t hm u l t i p l eq o sc o n s t r a i n t s ；t ew i t hd y n a m i cr o u t i n g ；d i f f - s e r v a w a r e m p l st e ；t ew i t ht r a d i t i o n a li pr o u t i n gp r o t o c o l s t h em a i na c h i e v e m e n t si nt h i sd i s s e r t a t i o na r es u m m a r i z e da sf o l l o w s ： 1 t e c h n o l o g i e s o fm p l st ea r e s u r v e y e d a no p t i m i z a t i o na l g o r i t h m ，b a s e d o n i n t e g r a t i o n o fc h a o sa n dg r o u pd o u b l et r a c k l o c a ls e a r c h ，i sp r e s e n t e d ，w h i c hi s a p p l i c a b l e t o g l o b a l l yo p t i m i z i n ge x p l i c i tr o u t i n g s w i mo b j e c t i v eo fm i n i m i z a t i o n n e t w o r k c o n g e s t i o np r o b a b i l i t y t h ea l g o r i t h m i ci d e a sa n dc h a r a c t e r sa r ee x p a t i a t e d ，a s w e l la si t sp e r f o r m a n c ei sa s s e s s e dt h r o u g hc o m p u t e rs i m u l a t i o n ，a l s oc o m p a r e dw i t l l o t h e ro p t i m i z a t i o na l g o r i t h m s t h er e s u l t sm a n i f e s tt h a t0 1 2 4 a p p r o a c hi se f f e c t i v e 2 t e p r o b l e m sw i t hm u l t i p l eq o sc o n s t r a i n t sa r et h o r o u g h l yi n v e s t i g a t e d m a t h e m a t i c a l m o d e lo fn e t w o r kt r a f f i cd i s t r i b u t i o no p t i m i z a t i o nw i t hm u l t i p l eq o sc o n s t r a i n t si s p r e s e n t e d f u r t h e r m o r eat w os t e ps o l u t i o ni sp r o p o s e d ，w h i c hs u b d i v i d e st h eo r i g i n a l p r o b l e mi n t ot w os u b p r o b l e m s ：c o m p u t i n gc a n d i d a t e s e t sc o m p o s e do ff e a s i b l er o u t i n g s a c c o r d a n tw i t h m u l t i p i eq o s c o n s t r a i n t s ；a n d i m p l e m e n t i n gg l o b a l l yr o u t i n g o p t i m i z a t i o nw i t ho b j e c t i v eo f l o a db a l a n c i n g f o rt h ef i r s ts u b p r o b l e m ，t h r e eh e u r i s t i c a l g o r i t h m sa r ep r o p o s e d ，w i t h t h e o r e t i c a lf o u n d a t i o ne x p o u n d e d ，a sw e l la sa l g o r i t h m i c p e r f o r m a n c ea n a l y z e da n dc o m p a r e dw i t ho t h e rc o r r e l a t i v es t u d yw o r k f o rt h es e c o n d s u b p r o b l e m ，a no p t i m i z a t i o na p p r o a c hb a s e do nh e u r i s t i ca d a p t i v eg e n e t i ca l g o r i t h mi s p r e s e n t e d ，a n dt h es i m u l a t i o nr e s u l t s s h o wt h a ti ti se f f e c t i v e ，i nw h i c hi t e v i d e n t l y i m p r o v e st 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 nc o n d i t i o nb r o u g h t a b o u tb yt r a d i t i o n a ls p f m u t i n gp o l i c y 3 t h r o u g h c a r e f u la n a l y s i so f c u r r e n ts t u d yw o r ko nd y n a m i cr o u t i n gp o l i c yf o rm p l st e ， i i 北京邮电丈学博士学位论文 摘螫 a l li m p r o v e d a p p r o a c hb a s e d0 nm i n i m u m i n t e r f e r e n c ei d e a si sp r e s e n t e d t eo b j e c t i v e c o n s i d e r e dh e r ei st oi n c r e a s en e t w o r kt h r o u g h p u t t h i sa p p r o a c ht a k e s n t oa c c o m r b o t hn e t w o r kt o p o l o g ya n dt r a f f i cd i s t r i b u t i o ns t a t e ，a l s o b r i n g s f o r t hg r a d e dl i n k c r i t i c a l i t y s i m u l a t i o ne x p e r i m e n t s a r ec a r r i e do u tw i t hs e v e r a lt y p i c a lr o u t i n g a l g o r i t h m s u n d e ri d e n t i c a lc o n d i t i o n s ，a n dt h ep e r f o r m a n c eo fr o u t i n ga l g o r i t h mi sa s s e s s e db y t h r e e r e p r e s e n t a t i v ep e r f o r m a n c e c r i t e r i a t h es i m u l a t i o nr e s u l t s t e s t i f y t h a to u r a p p r o a c ho u t p e r f o r m s t h eo t h e r s 4 i s s u e sa b o u td i f f s e r v - a w a r et ea r ed i s c u s s e d l i m i t s nc u r r e n tr e s e a r c ha l ep o i n t e do u t f u r t h e r m o r e ，m a j o rt eo b j e c t i v e si nd i f f s e r vn e t w o r k a r eg i v e n , a n dt r a n s l a t e dt op a t h c o s t ，t h r o u g 虫c a r e f u li n v e s t i g a t i o no nc h a r a c t e r i s t i c so f d i f f e r e n t i a t e ds e r v i c e s ，ah o v e i i n t e g r a t e dr o u t i n gp o l i c y i s p r o p o s e d ，w h i c h i sc h a r a c t e r i z e d b y t h e f o l l o w i n g p a r t i c u l a r i t i e s ：r e f l e c t i n gd i f f e r e n c e sa m o n g d i f f e r e n t i a t e dq o ss e r v i c et y p e s ；t a k i n gi n t o a c c o u n tb o t ht ea n dq o s r e q u i r e m e n t s ；c o u p l i n gq o s s e r v i c er o u t i n g sw i t hb es e r v i c e r o u t i n g s 5 a m u k i p l eo b j e c t i v e so p t i m i z a t i o nm o d e lo fr o u t i n gw i t ht r a d i t i o n a lm u t i n gp r o t o c o li s p r e s e n t e d ，w h i c hp a y sa t t e n t i o nt ob o t hn e t w o r kc o n g e s t i o nc o s ta n dd e l a yc o s t a n da c h a o t i cg r o u ps e a r c ha l g o r i t h mi sp r o p o s e d s i m u l a t i o n sm a n i f e s ti t sv i r t u a lv a l u ei n b a l a n c i n g t r a f f i cl o a d ，a n di m p r o v i n gn e t w o r kp e r f o r m a n c e k e yw o r d s ：q o s ；t r a f f i ce n g i n e e r i n g ；m p l s ；d i f f s e r v ；c o n s t r a i n e dr o u t i n g ；g e n e t i c a l g o r i t h m l o c a ls e a r c h ；c h a o s | l l 第1 章绪论 【摘要】首先对i n t e m e t q o s 体系作了一个概括，分析阐述了流量工程对于实施 i n t e m e t 服务质量保证有着不可或缺和不可替代的意义；进而对流量工程的关键 技术进行系统讨论；阐述了课题意义，给出论文的主要工作和内容安排，为论文 后续工作的展开作了一个铺垫。 1 1 引言 i n t e m e t 自8 0 年代以来出现蓬勃发展，近年来更以惊人的速度增长，有统计 称联网主机量每年翻一番，w e b 站点每半年翻番，这个速度已经突破了摩尔定 律。伴随着多媒体技术的飞速发展，网上多媒体应用层出不穷，多媒体信息的数 量与日俱增，这些新业务对网络提出了新的服务质量要求，不仅要求可靠的数据 传输，还要求传输过程的实时性和可预见性。市场的驱动使i p 网络面临着新的 机遇与挑战。i n t e m e t 己逐步由单一的数据传输网向数据、语音、图像等多媒体 信息的综合传输网演化，现有的仅提供尽力传送业务的传输模式已经无法适应业 务发展的需求，它必须演进为能够提供对各种业务的综合支持，并且对不同的应 用提供不同的服务质量( q o s ) 保证。同时电子商务的应用前景也使得i s p 需要 提供更好的服务质量吸引用户，并通过一些增值业务来获得更大的利润。虽然光 纤和其他硬件技术的发展使得网络的服务能力越来越强，但是资源和需求是一对 永远存在的矛盾，事实上流量的增长要比带宽增长的速度快，而且最大限度利用 带宽是数据传输的本性。因此i p 网络仍然需要有效的q o s 机制能够为用户提供 可靠的服务质量保证，以顺应现在和未来发展的需求。 正如上面所述，迅猛发展的网络应用所产生的大量数据给网络带来了极大的 压力。这要求网络运营商必须有效地提高现有网络资源的利用率以满足同益增长 的业务量需求，并实现利益的最大化。流量工程就是在这种背景下提出的一种用 来预测网络状况，控制网络资源，提高网络性能，满足业务要求的网络技术。从 定义上它涵盖了用于对网络进行测量、分类、建模和控制的科学原则和工程应用， 以及用于实现特定性能目标的原理和技术川。流量工程的实质是对网络进行性能 分析和实施优化的技术。从网络服务提供商的角度看，实施流量工程可以保证网 络资源的合理利用和网络性能的优化；从用户的角度看，实施流量工程可以更好 地保证用户要求的服务质量。因此，在骨干网的设计和运行中，实施流量工程十 分必要。 提供满意的网络应用服务质量( q o s ) ，已经成为i n t e m e t 发展的重要方向f l ”。 而流量工程对于实施i n t e m e t 服务质量保证有着不可或缺和不可替代的意义。本 文的研究课题正是在这背景下提出的。下面首先对i n t e m e t q o s 业务控制模型 及综合体系作一个概括，然后重点对流量工程及其关键技术进行系统分析：基于 目前的研究现状，阐述课题提出的意义，并给出论文的主要工作和内容安排。 1 2i n t e r n e tq o s 业务控制模型 q o s 是指网络在传输数据流时要满足的应用服务请求，具体可以量化为传输 时延、时延抖动、分组丢失率、吞吐量等指标。说到对q o s 的保证，不能不提 到a t m 网络技术。a t m 当时是作为一种能够适配各种业务而提出来的一种集传 输、复用、交换、交叉连接于一体的技术，其实质是快速分组交换p j 。当初a t m 的优势在于具有比i p 路由器更快的交换速度，并能够针对业务特点提供不同的 q o s 保证。但由于高速路由器的发展使得a t m 在交换速度方面的优势已经不存 在了，另外a t m 自身由于s a r 过程难以高速实现( 目前很难实现高于2 5 g 的 速度) ，信元头开销太大，信令控制过程复杂等原因，使得其进一步的发展和应 用受到了局限。但是a t m 的一些思想，尤其是对业务进行分类以提供不同的q o s 保证，流量控制和拥塞控制策略等方面，对于目前i p 网络的发展仍然具有重要 的借鉴意义。 近年来i n t e m e t 国际标准化组织i e t f 在i n t e r n e tq o s 方面做了很多工作，同 时吸取了a t m 技术的一些优点，起草了很多有关保证q o s 的建议，其中最有影 响力的q o s 模型包括：集成业务模型，通常也称为i n t s e r v ( i n t e g r a t e d s e r v i c e ) f 4 1 ；区分业务模型，即d i f f s e r v ( d i f f e r e n t i a t e ds e r v i c e ) 饽】；以及多协议标签交换 - - m p l s ( m u l t i p r o t o c o l l a b e ls w i t c h i n g ) f 引。 1 2 1i m s e r v i n t s e r v 是基于流的，状态相关的体系结构，使用资源预留协议r s v p 作为 信令机制。用户通过r s v p 向网络请求满足特定服务质量要求的缓存和带宽；中 间节点利用r s v p 信令在数据传输通路上建立起资源预留并维护该通路，以实现 相应的服务质量【w 。i n t s e r v 模型需要所有路由器在控制路径上处理每个流的信令 信息并维护每个流的路径状态和资源预约状态；在数据路径上执行流的分类、调 度和缓冲区管理。具体而言，i n t s e r v 依靠r s v p 逐节点( h o p b y h o p ) 地建立或 拆除每个流的资源预留软状态；依靠接纳控制决定链路或网络节点是否有足够的 资源满足q o s 请求；依靠传输控制将i p 分组分类成传输流，并根据每个流的状 态对分组的传输实施q o s 路由，传输调度等控制。i n t s e r v 模型定义了3 种业务 类型：保证型业务、负载受控型业务，以及尽力传送型业务。 i n t s e r v 模型的主要优点在于： 夺对业务能够提供有保证的q o s 。因为，所有的节点都运行r s v p ，对业 务流提供资源预留。 夺使用了r s v p 的软状态( 周期性的资源预留更新) 特性，这样它可以支 持网络拓扑的变化与多播成员的动态加入与退出。 夺使用r s p v 资源预留模式，在实际应用中，可以实现多播业务中网络资 源的有效分配。 然而，要实现i n t s e r vq o s 是比较困难的，它需要基于流的、复杂的资源预 留、接纳控制、q o s 路由和调度机制。i n t s e r v 的局限性主要表现如下： 夺扩展性是i n t s e r v 最严重的问题。由于使用了软状态的工作方式，r s v p 北京邮电太举博士学位论文第1 章绪论 邋行资添舔嚣嚣瑟瓣大羹豹状态僚惑进行稍耨及储存。京网络摄大辩，蒿葵占强 根大的带宽资源，端到端的q o s 很难实现。 夺砖网终要求较衰。要求溺络中鲍路由爨均支持r s v p 。 夺信令协议复杂，用户认证、优先权管理及计费需要复杂的上层协议，目 自h 尚处于发展阶段，无法付诸应用。 霞蔼，擎缝懿i n t s e r v 模墼实际上无法禳、监赛接受，不可莪露大静律为，现 在酱遍认为1 n t s e r v 以其现在的形式将不会在i n t e m e t 中料到广泛应用。 1 2 2d i f l s e r v 隧蓑l p 整务琴孛粪懿逐潦增多，l p 喇上数据渡塞不蘩嬲大，数i n t s e r v 方式对 每一个i p 数据包以绝对端对端的q o s 保证是不现实的：另外，越来越多的i s p 希望能够与客户之阅建立起以缀务质量为衡量标准的她务等级约定( s l a ： s e r v i c el e v e l a g r e e m e n t ) ，明确所支持的服务级别以及在每个服务级剐所允许的 业务量，i s p 依搬提供的服务级别收取不同的费用。在这种情况下，区分业务， 鞭d i f l s e r v 应运鬻生了。 d i f f s e r v 在网络层实现，它寰行粗粒度控制，目标在于简单有效，毗满足实 黻应用对霹扩震性的要求。为了攥证业务的q o s ，i s p 首先要与蜜户就睽缝获撂 的服务避行协商，如果成功，他们之间将达成一个业务等级约定，即s l a 。网 络边缘节点( e r ：e g r e s sr o u t e r ) 根据s l a 对逃入网络的业务流分类、整形、 聚合为不闷的瀛聚集，这种聚集信息存储在每个p 毽头的d s 标记竣中，称为 粥c p ( d i f f e r e n t i a t e ds e r v i c e sc o d ep o i n t ) ；中间节点( i r ：i n t e r i o rr o u t e r ) 在调 震转发i p 包露投攥包头熬d s c p 选择提供特定貘量的谖发转发黢务，其矮特性 称为逐跳行为( p h b ：p e r - h o p b e h a v i o r ) 。网络边界对单流做分类聚合与网络核 心对漉聚集提供特定质摄的调度转发服务，这两个过程是通过i p 包头内的d s c p 协同起来的强l 。溅西定义了3 种类墅的p h b ：e fp h b ，邵胡遥转发鼙p h b ； a fp h b ，即确保转发型p h b ：b ep h b ，即尽力转发型p h b 。 d i f f s e 与i n t s e r v 缀率豹嚣裂在予它不是镑辩每一缝务滚在每一节点上都 进行网络资源的分配及q o s 参数的配鬣，而是将具有相似服务质量要求的一组 业务浚聚合成为流聚集，然后对流聚集遗行相应的传输调度。因此具有良好的可 扩展憔，鼹体表现在：( 】) 网络按心节点僳存的状态信息蹩决定予流聚集的数目， 而不是与应用流的数目成比例的；( 2 ) 复杂的分类，监镑，标记和成形只在网络 鹣边缘送行；( 3 ) 核心节点援需蘩根撵分组翡d s c p 霹分组逶孬l 嫠类，重l l i 嚣敬列 管理和调度镶略。 d i f f s e r v 由予其实现豹德单性以及嶷好静可扩展性，毅试必是实现i n t e r n e t q o s 的商发展前景的一项技术。但是单靠d i f f s e r r ，并不能提供端到端i pq o s 的全面锵决方寒，需要不同层面上的0 0 s 机制相互补充与协作。 1 2 3m p l s m p l s 是一秘褥露终层翡转发与链鼹罄静交换籀结合熬侠逮分组转发技术， 北京耜电大学博士学位论文第1 章绻论 i 黼i 田i i l l i i 皇高 它瓣核心慰想是萼譬分组转发与控巷l 翱分褒，基于撂签对分鳃送行转发翻。 在m p l s 域的边缘节点( l e r ：l a b e le d g er o u t e r ) 按一定的规则将数据流 进行分类，形成转凝等价类( f e c ：f o r w a r de q u a lc l a s s ) ，然后在边缘节点之闻 经由中间节点( l s r ：l a b e ls w i t c hr o u t e r ) 建立鼹由，荠糟其有弱韶意义盼标 签来标识备段链路，这一系列的标签就表，谯了一条源和目的端之间的通路，称为 蠡诧交换路径( l s p ：l a b e ls w i t c h i n gp a 氇) 。当数据包烈达辩，入日边缘萤点 ( i n g r e s sl e r ) 根据它的包头决寇它所属的f e c ，然后加入定长标签，转发到 下节点p j 。中间节点只辫根据入翻标签以及预先建立的转发表，交换标煞后从 指定的端四发送捌下一跳帮可，不需要进行传统的鼯由，程出口边缘节点( e g r e s s l e r ) 只需要移去标签，发往指定的网络或主机即可。与传统i p 技术中的最长 l p 遮薤莲黧稿篷，m p l s 爨纯了孩，豁鼹壶舔内豹爸处理杌潮，捷曩镶单瓣毒器签索 引搜索代替最长前缀匹配搜索，从而可以提高分组转发的效率。谯m p l s 域中， 复杂的漉掇控割与警理功越主要由l e r 实现，位予网络核心的l s r 是高性能的 网络交换单元，不需要执行流分类操作，只需执行简单的流控功能。 m p l s 技术提出的最初目的是加快数搌报的转发速度，改善网络中的分组转 轰性能。丽当蓠受令久惑兴趣静燕它对滚爨工程霸q o sf l 奄支撩。流量工程戆嚣 的是实现嘲络的有效和可靠运行，同时优化利用网络资源。在传统i p 网络中路 由戆选择楚根据链鼹狻态域者楚单麴链路发量( m e m c ) 霹定，这撰就会逡成整 个网络在巢个地方资源过度利用，而另外一些地方网络资源闲置不用。m p l s 支 持两种确定路由的方法：一种是控制驱动l s p ( 也称为逐跳l s p ) ，另一种是显 式路由l s p ( e r ，l 。s p ：e x 鹾i c i tr o u t el s p ) 。建立逐蔬路交l 辩，每个l s p 穰据其 路由转发蒗，确定下一跳，并向下跳发邀标签请求信息，这种方式与传统的i p 路囱楣弱。建立e r l s p 辩，l 鼹懿路交是在黪绞建立瀵怠中掺霆豹，e r 。l s p 上的所有节点根据指定选择下一跳，并向它发送标签请求信息，因此可为业务流 分配不同于传统玲包转发的路径。显式路出类似予传统网络中的源路由，但不 需要i p 数据包携带显式静糟墙簸。显式路由爵戳潮分为严格显式路由或松教显 式路由。严格显式路由必须顺序包括l s p 经过的所有l s r ，而松散显式路由只 攒定l s p 上豹部分l s r 。鑫式路瞧龛海终鑫选强模浃，褒霹裁熬媾酲下给予路 裰选择最大的自由度，又可以在需要的情况下给予约束。 m p l s 的最大优势在于：幂唾用箍式路由技术易于实现满足约束的路啦，并且 这个过程可以自动完成，这使得强m p l s 系统中实施流量工程十分便利。 1 。3 综合的i n t e r n e tq o s 体系 舀1 1 给密了耱综合瓣q o s 俸系功雏模登。该模鼙毽括了镑瑾嚣，控制瑟 和数据面的功髓【1 9 1 。 霹中示意了燃户与遂务疆供麓( 鼹终篌j 之蕊戆基本交互，热渡务注鼹，业 务请求和数据传输。 4 北京邮电大学博士学位论文第1 章结论 管理面 控制面 数据面 用户侧网络侧 图1 1 i n t e r n e tq o s 体系功能模型 1 策略管理 策略管理从逻辑上可以分为三层：业务级策略，网络级策略和节点级策略。 如图1 2 所示。 l业务级策略 + i网络级策略 图1 2 逻辑分层的策略模型 策略实际上是一系列的规则，协议，信息模型和参数的定义，可以灵活地动 态配景和修改【1 4 】【1 5 l 。业务级的策略描述了业务的特征，包括业务的q o s 参数( 时 延，时延抖动，丢失率，以及其它的流量参数等) ，业务注册流程，业务规范的 定义，业务接入控制参数，业务流预测控制，以及计费策略等等。 网络级策略定义了与网络相关的控制规则与参数，如网络拓扑，拓扑更新报 告频率，流量工程的性能目标定义，网络优化进程的运行时间区间与路径或链 路有关的属性( 如链路代价函数，链路容量分配策略等) ，以及路由策略等相关 参数。 节点级策略定义了与节点相关的控制参数，如与队列管理和调度策略相关的 参数，如队列长度，w f q 中不同服务类别的权值，r e d 中的丢包闽值等。节点 北京邮电大学博士学位论文第1 章绪论 级策略最终翻译成设备级的指令，以达到策略执行的目的。 2 业务管理 业务管理是用户和网络之间的接口，通过在业务层面上网络与用户之间的协 商，建立起以服务质量为衡量标准的业务等级约定( s l a ：s e r v i c el e v e l a g r e e m e n t ) ，并以此形成业务级规范( s l s ：s e r v i c el e v e ls p e c i f i c a t i o n ) ，定义 了业务质量方面总体的特征与性能，流量调节规范( t c s ：t r a m cc o n d i t i o n i n g s p e c i f i c a t i o n ) 是s l s 的一个重要子集，t c s 为每个业务级别指明了具体的参数， 这些参数包括： 一业务标记。 一具体的业务性能参数，如峰值传输速率平均传输速率，丢失率，时延 等。 业务范围。 一业务特征描述。 一当提交的业务超出规定的特征描述时的处理措施。 s l s 是划分不同类别业务，实施区分业务的基础；另外结合业务监测统计功 能，进行业务量预测。可以为流量工程模块提供网络业务量需求描述，便于其优 化业务流到物理链路的映射。 业务管理包括业务注册和业务请求，前者是长期的行为，可以离线进行，而 后者是在线动态发生的。相应地，有静态s l a 和动态s l a 1 7 】。目前d i f f s e r v 体 系中集成了业务层功能【1 9 】。 3 流量工程 流量工程是一种网络优化和控制技术。具体来讲，它是一种以获取的网络状 态信息为基础，进行网络资源分配、业务流量调整，实现优化网络资源利用、满 足业务服务性能要求的网络工程技术【l 。 实际上网络拥塞是导致网络性能下降，因而服务质量得不到保证的最重要原 因。拥塞的出现有两种原斟l 】：一是网络资源不足以满足业务流的需求，这种情 况下一个解决方案是对网络进行扩容，从基础建设上提高网络的服务能力：另外， 可以实施流控技未，如接入控制，源速率限制，节点队列调度机制和分组丢弃策 略等。区分业务模型中通过对业务流进行分类，监管，标记，成形，并实施w f q 等队列调度算法和r e d r i o 等分组丢弃算法，在出现拥塞的时候，优先保证高 优先级业务的服务质量，通常需要相对牺牲低优先级业务的服务质量。 另一种是业务流分布不均衡造成的网络拥塞。目前的内部网关协议i g p s 是 基于最短路径优先方式进行选路的，不考虑当前链路负载状态，因而很容易导致 网络局部节点出现了拥塞，而其余部分节点的资源却处于空闲状态，网络的资源 利用率很低，性能下降，自然就无法提供满意的服务质量。这就需要通过实施流 量工程( t e ：t r a f f i ce n g i n e e r i n g ) 来解决。 流量工程可以通过长期的离线方式实施，也可以动态的在线实施。实现的关 键技术包括m p l s ，约束路由以及增强的内部网关协议( i g p ：i n t e r i o rg a t e w a y p r o t o c 0 1 ) 1 1 3 】。在论文的后续部分还将对流量工程进行系统深入地研究。 流量工程与业务管理之间的接口是业务量需求描述。流量工程模块是面向网 6 北京邮电大学博士学位论文第1 章绪论 络资源的，它不需要了解用户信息，由业务管理模块根据s l s s ，以及对用户行 为的监测，进行业务量预测，生成业务量需求描述，输入到流量工程模块，作为 网络资源分配和优化的基础。流量工程对数据面实施控制调节功能，保证网络运 行在一个良好的状态上。 4 数据面 实现数据转发功能，根据t c s ，提供分类的业务质量保证。边缘节点对单流 做分类聚合，标记流量调节和调度转发，核心节点对不同业务类型的流聚集， 提供基于业务类型的调度转发服务。 为了给不同的业务类型提供不同的服务质量保证，通常在网络节点把业务放 到不同的队列里，再利用不同的调度规则( 比如：先入先出、优先级调度、轮询 调度、处理器共享、随机调度等) 对业务队列进行调度，这就是队列调度技术所 要完成的工作。有效的队列调度算法应达到的性能指标主要有：公平性、链路 带宽的利用率、时延特性、对恶意业务流的隔离能力、复杂性等，前4 个指标与 q o s 密切相关。基于循环调度的算法轮流地对每个队列进行服务，其实现简单， 但不能对业务提供时延保证，目前主要有w e i g h t e d r r 、d e f i c i tr r 等。基于 g p s 的调度算法目前主要有：加权公平排队( w f q ) 、自时钟公平排队( s c f q ) 、 虚拟时钟( v c ) 等，它们( 尤其是w f q ) 能提供较好的公平性、时延特性以及 对恶意业务流的隔离能力，但当队列数较多时，其实现复杂度较大。在网络发生 拥塞时，路由器必须丢弃一些分组，实施有效的队列管理机制，即缓冲区管理策 略来保证不同业务对于丢失率的要求。目前应用的主要队列管理机制有：r e d 、 f r e d 、r i o 、p p d 、e p d 等【2 。队列调度和队列管理都是数据面上要研究的关 键技术。 综上所述，提供i n t e m e tq o s ，需要不同层面上的q o s 机制协同作用。本文 将重点对其中的流量工程技术进行深入地分析研究。 1 4 i n t e r n e t 流量工程 1 4 1 流量工程的意义 从1 3 小节中，可以看到流量工程与i n t e m e tq o s 是紧密相关不可分割的。 下面我们对流量工程的意义做进一步的阐述。 实际上在网络轻载的时候，即使是尽力而为业务也能够得到满意的服务 质量。因此如果能够通过有效的手段控制网络流量分布，使网络尽可能处于一种 负载平衡的状态，避免拥塞，那么网络的性能就能够得到保证，而这正是流量工 程提出的初衷，也是最终目的。 夺通过“过剩配置”( o v e r p r o v i s i o n ) 来提供q o s 保证，会导致网络资源利 用率低下。而流量工程的主要目标是在满足业务流性能需求的同时经济有效地利 用网络资源。这对于网络服务提供商来说意味着更大的投资回报，因而是非常有 吸引力的。 北京邮电大学博士学位论文第1 章绪论 就目前的高速路由器成交换机而言，正常情况下( 没有发生拥塞) 的排 队时延小于l m s 。这慧味着采用复杂的机卷4 减少队列辩延，相对来说不那么蘩要 了，除非网络发生了稍塞使褥酞列时延交褥非常长，黼透过恰当魏控涮流量藏身于 来避免拥塞则更有意义。 龚供q o s 爨诞实霞土壤是兔不目豹数务提供不鞫懿瓣务质量。帮使寂蹋 了区分业务，如果网络业务流分配不含理，大量高优先级业务在网络的同一个节 点处发生摆塞，那么区分业务对于要嬲对保谣赝毒赢优先级效务的服务质量也是 无能为力的。 令流量工程的蹦络流量监测功能可以为确定路由器队列调度和篱理算法中 静酞籁长度等参数鼹供参考。 综上所述，流量工程对于保障i n t e m e tq o s 起着不可或缺和不可替代的作用。 1 4 。2 流量工程韵性能嗣标 滚量工疆懿主簧嚣拣莛逶过建终资源熬谯铯列鼹，筑琵渡务量镁娆，绦渡网 络高效可靠运行，为用户提供业务质照保证。具体可以分为耐向业务流的性能目 标和蕊向资源的性能强标 1 l 。 夺面向渡务流瀚性髓秘标 面向业务流的性能对象照与特定应用业务流的流量特性相关的，具体表现为 灌强瓣选务滚靛q o s 绦谖，懿分鬣轰失率戢夺袋，延瓣最小谴，蚕睦量最大纯 等网络性能。 夺嚣自滚滚的髅能晷橼 溺向资源的性能对象是与网络资源密切相关豹，实现有效地管联网络资源， 优化地利用网络资源( 对运萤商来说，这一点是非常重要的)