（通信与信息系统专业论文）高速互联网流量工程和性能测量技术的研究.pdf

摘要 下一代高速互联网实现电信级i p q o s ，必须是多种技术的综合，只有多层次( 应 用层、传输层、网络层、链路层、物理层) ，多平面( 数据平面、控制平面和管理 平面) 的q o s 技术的交互作用，才能系统的解决i p 网络的q o s 问题。其中控制 平面的流量工程技术和管理平面的q o s 性能测量技术是当前研究的热点和难点技 术。本论文正是在参与教育部博士学科点专项科研基金项目( i n t e r n e t 流量工程综 合实现的关键技术研究，项目编号：2 0 0 2 0 0 1 3 0 1 1 ) 的研究和些工程类项目 开发的过程中，对高速互联网的流量工程和网络性能测量理论和技术进行探讨和 研究的一些成果。 论文内容包括如下： 第一章、提出了下一代高速互联网实施电信级i pq o s 的体系框架，并且介绍 了流量工程技术的发展历程，和性能测量技术的分类和测量的指标体系，给出了 论文选题的背景和研究内容。 第二章、基于模拟退火的启发式搜索思想，提出了一种在i p m p l s 网络上的 高效静态流量工程路由算法；然后，针对动态流量工程问题，建立了一种集最小 干扰、最小拥塞和最小时延的多目标优化数学模型，并提出了种基于后悔函数 虽小的妥协法求解算法，并经过模拟仿真，验证了算法的可行性和有效性。 第三章、分析了支持d i t t s e r v 的i p m p l s 网络流量工程的新问题，结合基于 优先级的俄罗斯木偶( r d m ) 带宽管理模型，提出了一种多优先级流量工程动态 路由和路由抢占算法；并提出了该优先级抢占策略与m p l s 信令协议c r l d p 结 合的实现方案。 第四章、归纳总结了网络端到端q o s 性能的测量和分析的现状，着重讨论了 路径瓶颈带宽和可用带宽的测量原理和分析算法，针对现有测量算法的不足，提 出了一种自适应的可用带宽测量算法，使得测量更加迅速，精度更高，并且减少 了主动探测分组给网络的负荷。 第五章、提出了一种将端到端性能测量融入流量工程的体系架构，对下一代高 速互联网实现电信级i pq o s 的综合部署方案进行了探讨。 最后，总结了全文，并指出进一步研究的方向。 关键词：电信级i p 服务质量流量工程模拟退火算法多日标优化 区分服务基于优先级的抢占算法 自适应带宽测量 第1 页 a b s t r a c t t h en e x tg e n e r a t i o ni n t e r n e ta i m st oa c h i e v et h ec a r r i e r c l a s si pq o s ，w h i c hs h o u l d b ei n t e g r a t e dw i t hm u l t i f a r i o u s t e c h n o l o g i e s ，i n t e r a c t i o nw i t hm u l t i 1 a y e r s ( s u c ha s a p p l i c a t i o nl a y e r , t r a n s p o r tl a y e r , n e t w o r kl a y e r , l i n kl a y e ra n dp h y s i c a ll a y e r ) a n d m u l t i - p l a n e s ( s u c h a sd a t ap l a n e ，c o n t r o l p l a n e a n dm a n a g e m e n tp l a n e ) t r a f f i c e n g i n e e r i n gt e c h n o l o g y o fc o n t r o l p l a n e a n d q o sp e r f o r m a n c e m e a s u r e m e n t m e t h o d o l o g yo fm a n a g e m e n tp l a n e a r et w ok e yt e c h o n o l o g i e sa n dh o t s p o t s t h i s d i s s e r t a t i o ni sp a r to fr e s u l t so ft h ep r o j e c t s t u d yo ni n t e r g r a t e ds o l u t i o n sf o ri n t e r a c t t r a f f i ce n g i n e e r i n g s p o n s o r e db yr e s e a r c hf u n df o rt h ed o c t o rp r o g r a mo fm o e ， c h i n a ( g r a n tn o 2 0 0 2 0 0 1 3 0 1 1 ) a n ds e r v a le n g i n e e r i n gp r o j e c t s t h em a i ni s s u e so f t h i sp a p e ra r e ： c h a p t e r 1i n t r o d u c e st h ea r c h i t e c t u r eo ft h e c a r r i e r - c l a s si pq o smt h en e x t g e n e r a t i o ni n t e r e n t ，r e v i e w st h et h ee v o l u t i o no ft r a f f i ce n g i n e e r i n gt e c h n o l o g y , a n d d i s c u s s e st h ec l a s s f l c a t i o na n dm e t r i c ss y s t e mo f p e r f o r m a n c em e a n s u r e m e n t t h e nt h e m a i ni s s u e sa n dr e s u l t so f t h i sp a p e ra r e b r i e f l yi n t r o d u c e di nt h i sc h a p t e r c h a p t e r2m a i n l yd i s c u s s e st h e s t a t i ca n dd y n a m i cw a f 五c e n g i n e e r i n gr o u t i n g a l g o r i t h m s b a s e d 0 1 1t h e t h o u g h to ft h e s i m u l a t e d a n n e a l i n g s e a r c h a p p r o a c h ，a h e u r i s t i cs t a t i ct r a f f i ce n g i n e e r i n g r o u t i n ga l g o r i t h mi sp u tf o r w a r d a r e rm o d e l i n gt h e d y n a m i ct r a f f i ce n g i n e e r i n gu s i n gm u l t i o b j e c t i v eo p t i m i z a t i o n ( i n c l u d i n gm i m i m u m i n t e r f e r e n c e ，m i m i m u r nc o n g e s t i o na n dm i m i m u md e l a y ) ，an o v e ld y n a m i cr o u t r i n g a l g o r i t h mb a s e do nc o m p r o m i s ea p p r o a c hi sp r o p o s e d c o m p u t e rs i m u l a t i o n sv a l i d a t e t h ef e a s i b i l i t ya n d e f f i c i e n c yo f t h ea l g o r i t h m s c h a p t e r3a n a l y s e st h en e wi s s u e so fd i f f s e r v - a w a r e dm p l st r a f f i ce n g i n e e r i n g w i t ht h er d mb a n d w i d t hm a n a g e m e n tm o d e lo f m u l t i - p r i o r i t y , ar a f f l ee n g i n e e r i n g r o u t i n ga n dp r e e m p t i o np o l i c yi sp r o p o s e dw h i c hu s e df o rd y n a m i cm u l t i - p r i o r i t y r o u t i n g a n dd i c u s s e st h ei m p l e m e n ts c h e m eu s i n gm p l s s i g h t i n gp r o t o c o l - - c r - l d p c h a p t e r 4s u m m a r i z e st h e e x i s t i n ga p p r o a c h e s f o re n d - t o - e n d p e r f o r m a n c e m e a s u r e m e n ti nt h ei n t e m e ta n df o c u s e so nt h eb o a l e n e c kb a n d w i d t ha n da v a i l a b l e b a n d w i d t hm e a s u r e m e n t m e t h o d o l o g y a n o v e l a d a p t i v e a v a i l a b l eb a n d w i d t h m e a s u r e m e n t a p p r o a c hi sp u tf o r w a r d ，w h i c he n h a n c e st h ep r a c t i c a b i l i t yo fb a n d w i d t h m e a s u r e m e n t a p p l i c a t i o n s 第1 i 酉 c h a p t e r5m a i n l yd i s c u s s e st h ew a y st oi n t e g r a t ee n d t o - e n dm e a s u r e m e n ti n t o t r a f f i ce n g i n e e r i n g ，p u tf o r w a r daf r a m e w o r kf o ra e h i e v e m e n lt h ec a r r i e r - c l a s si pq o s u s i n g t r a f f i c e n g i n e e r i n g a n d p e r f o r m a n c e m e a s u r e m e n t t e c h n o l o g y i nt h en e x t g e n e r a t i o ni n t e m e t f i n a l l y ，s u m m a r i z e st h ed i s s e r t a t i o na n dp o i n t so u tt h ed i r e c t i o n sf o rf u r t h e rs t u d y k e y w o r d s ：c a r r i e r - c l a s si pq o s ，t r a f f i ce n g i n e e r i n g ，s i m u l a t e d a n n e a l i n ga p p r o a c h ， m u l t i o b j e c t i v eo p t i m i z a t i o n ，d i f f s e r v , p r i o r i t y - b a s e dp r e e m p t i o n p o l i c y , a d a p t i v e b a n d w i d t hm e a s u r e m e n t 弗i i i 页 北京邮电大学博士学位论文缩略语 缩略语 英文缩写英文全拼中文 a a b m a a d a p t i v ea v a i l a b l eb a n d w i d t hm e a s u r e m e n ta p p r o a c h a d r a f a m a o m a 1 - m b b b e c b r c d f c i d r c i r c m c r - l d p d j f r s e r v d s c p d s i e e f e l s p f c f s f d m f i f o f t p h 1 1 _ p l e t f i l m i n t s e r v i p i p f a s y m p t o t i cd i s p e r s i o nr a t e a s s u r e df o r w a r d m g a d m i s s i o nm a n a g e r a c t i v eq u e u em a n a g e m e n t a s y n c h r o n o u s t r a n s f e rm o d e b a n d w i d t l lb r o k e r b e s te f f o n c o n s t a n tb i tr a t e c u m u l a t i v ed i s t r i b u t i o nf u n c t i o n c l a s s l e s si n t e r - d o m a i nr o u t i n g c o n 3 l n i t t e di n f o r m a f i o nr a t e c o n n e c t i o nm a n a g e r c o n s t r a i n t - b 躺c dl d p d i f f e t n f i a t e ds e r v i c e s d i f f c r c n t i a t e ds e r v i c e sc o d ep o i n t d i f f s c r v - a w a r em p l s1 h 弼c e n g i n e e r i n g e x p e d i t e df o r w a r d i n g e x p - i n f e n e d - p s cl s p f i r s t - c o m ef i r s t - s e r v e d f r e q u e n c y d i v i s i o nm u l t i p l e x i n g f i r s t i nf i r s t o u t f i l et n m f e rp r o t o c o l h y p e f r e x t t r a n s f e rp r o t o c o l 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 i n c o m i n gl a b e lm 印 i n t e g r a t e ds e r v i c e s i n t e m e tp r o t o c o l i n t e g e rp r o g r a m m i n gf o r m u l a t i o n 第1 0 5 页 自适应的可用带宽测量方法 渐进分散速率 确保转发 接纳管理器 主动队列管理 异步转移模式 带宽代理 尽力而为 恒定比特率 累计分布函数 无类别的域间路由选择 承诺的信息速率 连接管理器 基于约柬的标签分发协议 区分服务 区分服务编码点 支持区分服务的m p l s 流量工程 加速转发 由e x p 导出p s c 的l s p 先到先服务 频分复用 先入先出 文件传输协议 超文本传输协议 互联网工程任务组 输入标签映射 综合服务 互联网协议 整数规划模型 北京邮电大学博士学位论文缩略语 i s p l a n l d p l s p l l s p m a m m a r m c r a m i r a m p l s m r f r a n a t n g i n t p 0 a 0 s p f p h b p m p n n l p p t d p q p s c q o s r d m r e d r f c r r r s v p r 竹 s l s s l a s l o p s i n t e m e ts e r v i c ep r o v i d e r l o c a la t e an e t w o r k l a b e ld i s t r i b u t i o np r o t o c o l l a b e ls w i t c h e dp a t h 亘联网业务提供商 局域网 标签分发协议 标签交换路径 l a b e l - o n l y - i n f e f r e d p s cl s p有标签导出p s c 的l s p m a x i m u ma l l o c a t i o nm o d e l 最大带宽分配模型 m a x i m u ma l l o c a t i o nw i t hr e s e r v a t i o n 带资源预留的m a m 模型 m i n i m u m c o n g e s t i o nr o u t i n ga l g o r i t h mf o rt r a f f i ce n g i n e e r i n g 最小拥塞t e 路由算法 m i n i m u mi n t e r f e r e n c er o u t i n ga l g o r i t h mf o rt r a f f i ce n g i n e e r i n g 最小干扰t e 路由算法 m u l t i - p t o t o c o ll a b e ls w i t c h i n g 多协议标签交换 m i n i m u m r e g r e tf u n c t i o nr o u t i n ga l g o r i t h m n e t w o r ka d d r e s st r a n s l a t i o n n e x tg e n e r a t i o ni n t e r a c t n e t w o r kt i m ep m t o e 0 1 o r d e r da g g r e g a t e o p e n s h o r t e s tp a t hf i r s t p e rh o pb e h a v i o r p e a ki n f o r m a t i o nr a t e p r i v 眦n e t w o r k - n e t w o r ki n t e r f a c , e p a c k e tp a i r ，t r a i n sd i s p e r s i o n p r i o r i t yq u e u i g p h b s c h e d u l i n gc l a s s q u a i l t yo f s e r v i c e r u s s i a ni ) o l l sm o d e l r a n d o m e a r l yd e t e c t i o n r e q u c 毗f o rc o m m e n t s r o u n dr o b i n p m o u r e * r e s e r v a t i o np r o t o c o l r o u n dt 唧t i r e s e r v i c el e v e ls p e c i f i c a t i o n s e r v i c el e v e la g r e e m e n t s e l f - l o a d i n gp e r i o d i cs u e a m 第1 0 6 页 后悔函数最小的t e 路由算法 网络地址转化 下一代互联网 网络时间协议 有序聚合 开放最短路径优先 每一跳行为 峰值信息速率 专用网络到网络接口 分组对，序列分散技术 优先级捧队 p h b 调度类 服务质量 俄罗斯术偶模型 随机早期探测 i e t f 建议 轮询 瓷源预留协议 往返时延 服务等级规范 服务等级协定 自加载的周期性探测流技术 些室墅皇奎兰堡主兰焦堡苎 塑坠至 s p f s r t c m t c p t d m t d m a t e 1 _ f r c t o p p t r t c m u d p v c l v o i p v o p v p l v p s w d m w f 2 q w f w f q w r e d w r r w w w s h o r t e s tp a t hf i r s t s i n g l er a t et r e ec o l o r m a r k e r t r a n s m i s $ i o nc o n t r o lp r o t o c o l t i m ed i v i s i o nm u l t i p l e x i n g t i m ed i v i s i o nm u j n p j ca c c e g t r a f f i ce n g i n e e r i n g t c p - f 一d l yr a t ec o n t ：r o ! t r a i n so f p a c k e tp a i r s t w or a t et r e ec0 1 0 rm a r k e r u s e rd a t a g r a mp r o t o c o l v i r m a lc h a n n e li d e n t i f i e r v u i c eo v e ri p v e c t o ro p t i m i z a t i o np r o b l e m v i r t u a lp a t hl d t n t i f i e r v a r i a b l ep a c k e ts i z e w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g w o r s t - c a s ef a i rw e i g h t e df a i rq u e u i n g w o t a t c 雒f a i r n e s si n d e x w e i g h t e df a i rq u e u i n g w e i g h t e d r 1 u l d o me a r l yd e t e c t i o n w e t g h t e dr o u n d r o b i n w o r l dw i d ew e b 第1 0 7 页 最瓴路径优先 单速率三色标记器 传输控制协议 时分复用 时分多路访问 流量工程 t c p 友好速辜控制 分组对序列技术 双速率三色标记器 用户数据报西议 虚通路标志 基于f p 的语音 向量最优化问题 虚遗道标忠 可变分组大小 波分复用 最坏情况公平的w f q 最坏公平指数 加权公平排队 加权随机早期探测 加权轮询 万维网 独创性( 或创新性) 声明 本人声明所呈变的论文是本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中i 包 含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：1 壑望盎日期：礁! 生f i 。蜘 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关韶门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：1 塾望垂日期 如。午f 2 ：4 导师签名： 生壹 = = | 期：丝! 生： 2 = ：22 北京邮电大学博士学位论文第一章绪论 第一章绪论 啉要】本章主要讲述论文研究的相关背景和选题的意义。首先分析了当 前互联网发展遇到的问题，提出下一代互联网实现电信级i pq o s 的整 体框架；然后回顾了流量工程技术的发展历程，指出了互联网上实施流 量工程的关键技术和本文研究的主要内容；接着阐述网络性能测量方法 的分类、研究现状和测量的主要指标，并讨论了本文的主要研究内容和 意义。最后，总结了论文的主要创新之处，给出论文的内容安排。 1 1 引言 近年来以t c p i p 为主要协议的互联网( i n t c m e t ) 技术飞速发展，网络的规模 不断扩大，网络上的流量爆炸式增长。i n t c m e t 已经渗透到社会的各个领域，成为 现代社会信息交流最重要的基础设施之一。i n t e m e t 从2 0 世纪8 0 年代初期的仅用 于科学研究的小型网络，现在已经逐渐进入大规模商用领域，已逐步由单一的数 据传输网向数据、语音、图像、视频等多媒体信息的综合传输网演化。但是由于 i p 协议固有的无连接特性和传统球网络“尽力而为”的服务模式，使得传统i n t e m e t 无法向用户提供有效的服务质量( q u a l i t yo f s e r v i c e ：q o s ) 保障，也不能实现网络 资源的有效监控和管理。这种状况严重阻碍了i n t e m e t 的进步发展。在思考当前 i n t e r a c t 网络的发展遇到了哪些问题时，大家普遍认为其中最主要问题集中在i p 地 址空间的耗尽和如何提供服务质量保证两个问题【1 1 1 2 。 i p 地址方式的特点是给每个终端分配一个网络地址，每个分组均携带这个地 址，作为网络节点转发分组的依据。目前普遍采用的i p v 4 的分组结构，采用了3 2 b i t 作为地址域，这大抵只相当于9 位十进制数( 4 , 2 9 4 ，9 6 7 , 2 9 6 ) ，现在我国大城市的 电话号码几乎都已经采用了8 位编号，在世界范围内采用3 2 b i t 的地址域标识终端 肯定是不够的。因此在9 0 年代初就意识到了这个地址危机问题，一方面，对现有 i p v 4 网络通过c i d r 的地址分割，通过代理服务器和n a t 协议的地址重用，以及 通过i s p 的动态地址分配等，使得i p v 4 尚能应付目前的实际需求；另一方面i e t f 等标准化组织开始i p v 6 的规范工作，i p v 6 采用了1 2 8 b i t 作为地址域，但其升级过 渡还面临很大挑战，现在世界上尤其亚洲国家的许多研究机构都在研究i p v 4 网络 向i p v 6 网络的平滑过渡问题。 另一个面临的主要问题就是如何提供口网络的服务质量保证。传统的i n t e m e t 网络采用基于逐跳转发机制的无连接的i p 协议，与其他网络技术相比，i p 具有许 第5 页 北京邮电大学博士学位论文第一章绪论 多特点，其中最重要的一个特点就是i p 网络在设计时最大限度地降低了应用对网 络的依赖性。这一点主要通过无连接、每包路由和尽力而为( b e s te f f o r t ) 服务这 几个方面来体现。也就是说，i p 网络的架构是建立在对网络不信任的基础上的， i p 的应用主要依靠终端的智能来实现( 其他网络，包括t d m 和a t m 网都建立在 一个复杂的、精细控制的网络层上) 。i p 网络的这种设计有许多优点1 3 ： ( 1 ) i p 具有网络兼容性，它对网络没有太多的要求，因此各种网络传输技术 都能够被包容到i p 上； ( 2 ) i p 网络具有灵活性，i p 网络在总体上呈现分布式管理和松散控制的特点， 因此局部网络的变化通常不会给整个网络带来太大的影响，这使得网络在设计、 规划和扩充方面都很灵活； ( 3 ) 具有丰富和强大的应用扩展能力，这一点在i n t e m e t 上体现得非常明显， 除了早期的f t p 、t e l n e t 等应用外，w w w 浏览、电子商务、多媒体、p 2 p 等新应 用不断涌现，层出不穷。 从技术上来看，i p 为各种应用的设计和开发提供了最好的条件，因为i p 对网 络的依赖性很小，在实现上，网络只要提供可达性即可，所有的复杂性和功能都 可以在终端系统上实现。但是，i p 网络的这种设计原则在提供q o s 保证时遇到了 极大的困难，q o s 问题成为目前i p 网络面临的最重要、最复杂的问题之一。 如何在i n t e r n e t 上提供q o s 保证是学术界和产业界共同关心的热点问题。网络 的存在就是为了信息交换与资源共享。因此不论是电话网还是i m e m e t ，网络的存 在意味着共享，共享就有拥塞概率和网络“瓶颈”的存在，会有q o s 保证问题口l 。 只不过，电话网有非常成熟的话务量模型和e r l a n g 公式，在设计时就很好地解决 了此类问题，从而很好的保证了话音业务的q o s 要求。而i n t e r a c t 的业务量模型非 常复杂，如：数据业务流量的不对称性、统计自相似性、高突发性等特点，到目 前还没有一个完善的数学模型去表述它，更谈不上在设计时就很好地解决此类问 题。 现在人们对于i n t e m e t 的业务流量模型、网络行为、性能指标等都缺乏理解和 精确的描述，对业务流量在网络中的精确控制和网络性能测量等技术的研究明显 滞后于网络本身及其上的应用快速发展。流量工程技术就是在这种背景下提出的 一种用来预测网络状况，控制网络流量，管理网络资源，提高网络性能，满足业 务q o s 要求的网络技术。网络性能测量则是探讨网络行为和运行规律，进行q o s 验证和控制的基础技术和重要手段。因此，高速互联网的流量工程技术和网络性 能测量和分析方法的研究课题，对于下一代互联网提供全面的o o s 解决方案具有 十分重要的意义。 本章下面的内容安排为：1 2 节首先提出下一代高速互联网实现电信级i pq o s 的整体框架；然后在1 3 节给出了流量工程问题的定义、目标、发展历程和关键技 第6 页 北京邮电大学博士学位论文 第一章绪论 术，讨论了本文对流量工程研究的内容和意义；1 4 节分析了网络性能测量的分类、 研究现状、主要指标和本文的研究内容：最后，在1 5 节和1 6 节分别阐述了本文 的主要贡献和内容安排。 1 2 下一代高速互联网实现q o s 的整体框架 下一代i n t e m e t 网络( n g i ) 的体系结构和发展趋势是目前国内外关注的热点。 基于i p 技术构建多业务综合网络成为i n t e r a c t 发展的一个重要趋势，n g i 的主要 特点将是开放和高效，能够提供对各种业务的综合支持，尤其应该提供对各种应 用的不同q o s 保证。当前，建设下一代i n t e r a c t ，也被许多专家称为电信级的i p 网络l j j ，已经得到了业界的普遍共识。 对于电信级i p 网络，通常包含以下几层含义p 】： 一是该网络必须以i p 为核心技术构建，以满足i p 的基本特征； 二是该网络能够支撑传统的电信业务，特别是话音业务和视频业务； 三是该网络能够满足电信运营的要求，即具有可管理性和可运营性。 电信级i p 网络的核心问题是服务质量问题，即电信级i pq o s 问题。实施电信 级i pq o s 保障，需要一个系统的综合体系框架，要具有技术的可实旌性。这就需 要综合考虑数据平面的一系列q o s 转发机制、控制平面的对业务流路径的动态路 由和资源分配等技术，管理平面的q o s 业务预定( s l as u b s c r i p t i o n ) ，计费和q o s 性能测量等技术1 4 1 5 】【6 。 图1 1 下一代高速互联网实现q o s 的整体框架 第7 页 北京邮电大学博士学位论文 第一章绪论 图11 给出了下一一代高速互联网实现0 0 s 的整体框架。实现电信级i p 网络，必 须是多种技术的综台。多层次( 应用层、传输层、网络层、链路层、物理层) ，多 平面( 数据平面、控制平面和管理平面) 的q o s 技术的交互作用，才能系统解决 i p 网络的o o s 问题。 过去i po o s 的研究主要集中在数据平面，人们在流量分类，标记，调节，队 列管理和队列调度方面已经提出了许多很好的算法和机制。其中许多简单高效的 算法，如单速率三色标记算法s r t c m ，双速率三色标记算法t r t c m ，基于令牌的 单漏桶算法，基于令牌的双漏桶算法，随机早期丢包算法r e d ，加权的随机早期 丢包算法w i l e d ，加权公平排队算法w f q 、最坏情况公平的加权公平排队算法 w f 2 q ，加权轮循w r r ，等等都已经在路由器交换机上实现，并部署在网络节点 中。但是，在控制平面的实用化研究还非常少，目前i p 网络上还几乎没有一种资 源和路径的动态管理机制，无法实现真正的接纳控制和q o s 路由。现在的i n t e r a c t 路由协议( o s p f 、1 s i s 、r i p 、b g p 等) 都采用单个度量( 如跳数、代价) 来计 算最短路由，没有考虑q o s 参数和网络资源分配等的度量。另外，q o s 管理平面 的流量预测、s l a 管理、计费和性能测量技术的研究才刚刚起步，离真正的i pq o s 业务全面开展还有相当的距离。 本文的研究课题就是在上述背景下提出来的，将重点研究控制平面的流量工程 技术和管理平丽的q o s 性能测量技术。下谣分别对两部分内容的研究情况进行阐 述。 1 3i n t e r n e t 流量工程技术 1 3 1 流量工程的定义 i n t e r a c t 流量工程( t r a 硒ce n g i n e e n n g 简称r e ) 广义的定义为口】：一种将数 据流量映射到相应的物理路径，同时通过自动控制和优化网络资源以实现特定流 量q o s 要求的，具有资源宏观调节和微观控制能力的网络工程技术。微观控制是 在数据流层面上的控制功能，主要包括b u f f e r 管理。捆塞避免，流量整形，队列 调度等；宏观调节则是网络级的控制，用来解决全网范围的资源分配和路由选择。 i e t f 的流置工程工作组( t e w g ) 的对流量工程的定义为“i n t e r a c tt r a f f i c e n g i n e e r i n gi sd e f m e d a st h a ta s p e c to fl n l e r n e tn e t w o r ke n g i n e e r i n gd e a l i n gw i t ht h e i s s u eo fp e r f o r m a n c ee v a l u a t i o na n d p e r f o r m a n c eo p t i m i z a t i o n o f o p e r a t i o n a l i p n e t w o r k s ”瞵j 。其中包括两个方面的内容：网络性能评估和性能优化。本文中的流 量 二程定义主要是指狭义上的流量工程技术，即通过综合动态资源管理和路径管 理来实现运行的j p 网络的性能优化，而通过对网络性能的测量和分析来实现运行 笔8 面 北京邮电大学博士学位论文第一章绪论 的i p 网络的性能评估。 流量工程的主要目标可以分为两种： 1 面向应用的性能目标 面向应用的性能对象是与特定应用业务流的流量特性相关的，具体表现为增强 对业务流的q o s 保证，如分组丢失率最小化，时延最小化，吞吐量最大化等业务 性能。 2 面向资源的性能目标 面向资源的性能对象是与网络资源密切相关的，实现有效地管理网络资源，优 化地利用网络资源( 对网络运营商来说，这一点是非常重要的) ，如负载均衡，合 理分布网络流量，避免拥塞。通常我们都希望能够确保在其他可选路径上还有可 用资源时，一条路径上的网络资源不会被过度的使用。 下面首先来回顾一下流量工程技术的发展历程【8 】【9 】，然后讨论i n t e r a c t 流量工程 研究的关键技术点。 1 3 2 流量工程技术的发展历程 1 3 2 1 传统电话网中的流量工程 其实，早在电话网的规划设计中就已经体现了流量工程的思想。早期的电话网 络依靠静态分级路由，这种分级结构的目的是解决过载流最，通过备用路由提高 网络的可靠性。但是，数字交换和程控技术的出现使得电话网络中的分级路由变 得过于严格和固定。 因此，人们引入了动态路由技术，使得网络可以更加灵活有效的选择路由。电 话网络中使用了三种主要类型的动态路由技术：i ) 时间相关路由，针对流量负载 按照时间有规律的变化来预先设定路由表：2 ) 状态相关路由，路由表根据网络的 当前状态进行更新( 例如，流量要求、利用率等等) ：3 ) 事件相关路由，路由表 根据事件( 例如，建立呼叫时遇到拥塞或者阻塞链路) 进行更新。 1 3 2 2 传统路由技术下的流量工程 数据网络的性能优化最早开始于a r p a n e t 的出现。从流量管理的观点看，直 到现在，i n t e r a c t 都是一个尽力服务的网络口网络提供了非鬻有限的流量管理功 能：从路由控制的观点看，尽管i n t e m e t 为域内路由开发了分布式协议，而且这些 协议具备可扩展性，但是它们基于简单的路径选择算法，只能非常有限地对路径 选择过程进行控制。 ( 1 ) a r p a n e t 中的自适应路由 早期的最小延时路由是通过条路径将每个数据包传送到其目的地，在这条路 径上的总的估计传输时间最短。每个节点将维护一张网络延时表，指示了数据包 第9 面 北京邮电大学博士学位论文第一章绪论 通过给定路径到达其目的地所要经过的估计延时。最小延时表由节点周期性地传 输到其邻居节点。最短路径，也就是跳数，也作为连接信息被传送。这种方法的 一个缺点就是动态链路度量可能会产生“个“流量磁场”，使得网络拥塞从一个节 点转移到另一个节点，从而导致网络的振荡和不稳定。 ( 2 ) i n t e r a c t 中的路由算法 i m e r n e t 是从a p a r n e t 网络发展而来的，采用了分布式控制的动态路由算法， 用来确定数据包通往其目的地的路径。路由算法都是最短路径算法的改进，最短 路径算法的费用主要基于链路度量值。这些路由算法在进行路由选择时没有考虑 流量特性和容量约束。即使链路度量值根据流量值来指定，网络中的负载不平衡 现象仍然会出现。 传统i n t e r a c t 内部网关路由系统的不足之处也就是促使大家热衷于研究面向连 接技术的原因，这类技术可以具有显式路由和基于约束的路由的能力，比如后来 出现的m p l s 技术。 ( 3 ) t o s 路由 服务类型( l o s ) 路由可以根据i p 数据包的 l o s 字段独立地选择去往相同目 的地的不同路由。t o s 的类型可以分成低延时和高吞吐量。每条链路都有相应的多 个链路费用，映射到不同的 l o s 上。最短路径算法必须计算每个 l o s 的结果，经 典的基于t o s 的路由现在已经过时了，其i p 包头的字段被d i f f s e r v 字段所取代。 流量工程很难在经典的基于t o s 的路由中应用，因为每个分类都独立地根据最短 路径算法计算，从而导致网络中的流量集中到本地。 ( 4 ) 平等费用多径选择 平等费用多径选择( e c m p ) 是内部网关路由系统中用来解决最短路径优先 ( s p f ) 算法不足之处的另一个技术。在经典的s p f 算法中，如果到某个目的地存 在两条或多条最短路径，则算法将选择其中的任意一条。e c m p 算法对此进行了 简单的修改，如果两个节点之间存在两条或多条具有同等费用的最短路径，则将 节点之间的流量平均分配到多条平等费用路径上，实现了负载的较合理分配。 ( 5 ) n i m r o d 路由协议， n i m r o d 是一个路由系统，用来在i n t e r n e t 中向不同种类的服务提供特定路由， 同时考虑了多种约束条件。尽管n i m r o d 协议并没有在i n t e r a c t