（计算机应用技术专业论文）面向互联网流量工程的网络测量及路由调整算法研究.pdf

北京邮电大学博士论文 摘要 摘要 近年来，随着互联网的一迄速发展，网络性能面临严峻挑战，流量工程成为互联网进一步 发展的关键性问题。由于网络传输速度日益加快，新业务不断出现，目前的流量工程技术已 经不能满足高速网络性能优化的要求，更无法满足未来网络发展的需要。本文重点研究了 t c p 往返时延测量、高速网络中的大流检测、高速网络中的路由调整，为解决流量工程中 的一系列问题提供基础，从而改善网络的性能和服务质量。本文主要研究工作及内容如下： ( 1 ) 被动测量t c p 连接往返时延( r t t ) 对网络设计、流量工程、p 2 p 网络性能优化 等方面都有重要作用。本文针对现有被动测量方法的不足之处，提出一种在t c p 连接的非 发送端被动测量i 册的c r o s s 算法。c r o s s 算法通过互相关函数判断数据分组与a c k 分 组之间的对应关系，继而获得t c p 连接的r t t 值。通过p l a n e t l a b 网络上的实验数据验证， c r o s s 算法不但能够在t c p 连接建立后的任意阶段计算该连接的r t t ，并且可以在网络性 能较差导致i m 变化较大时准确测量。 ( 2 ) 互联网中大流数目少但流量大，因此在网络拥塞发生时快速准确地找出网络中的 大流并对其路由做出调整，就能够有效地提高网络性能，同时避免了处理大量小流导致的系 统开销。传统上基于采样或f i l t e r 结构的大流检测算法存在准确率不够高的问题。不能满足 互联网应用的需要。本文提出一种基于两级l r u 结构的大流检测算法l r u 2 ，其中第一级 l r u 用于小流过滤，第二级l r u 用于对大流的准确计数。文章推导了最坏情况下l r u 2 算 法对大流统计的误差上限。并且通过分析证明算法具有1 0 g b p s 的线速处理能力。基于实际 互联网数据的实验表明：与现有算法相比，l r u 2 算法具有更高的准确性和实用性。 ( 3 ) 互联网流量分布的不均衡会导致拥塞的发生，此时对某些造成拥塞的关键大流进 行路由调整能够有效地改善网络的性能。本文提出一种针对单条流的路由调整算法，一方面 降低了网络最大带宽利用率，另一方面把被调整流的路径长度限制在可接受的范围之内，从 而保证了该流的服务质量。基于真实网络拓扑和流量的实验表明：新算法能够有效缓解骨干 网拥塞，最多可降低最大带宽利用率近5 0 。仿真实验显示：与现有算法相比，新算法能 够同时满足关键流路径长度和降低最大链路带宽利用率两方面的要求。此外，算法复杂度为 d f ，2 妇夕，好于现有的大部分路由调整算法。 北京邮电大学博士论文 摘要 ( 4 ) 互联网中发生多链路拥塞的概率虽然较小，但也会时常出现，并且难予处理，给 网络性能优化带来了困难。针对这一问题，本文提出了一种基于概率选择下一跳的关键流路 由调整算法。当网络中出现多链路拥塞时，算法通过同时调整多条关键流路由的方式改善网 络性能，使流量分布更加均衡。仿真实验表明，新算法有效地提高了网络吞吐量，很好地实 现负载均衡，同时通过控制路径长度保证了服务质量。 【关键词】互联网，流量工程，网络测量，大流检测，路由调整 l i 北京邮电大学博士论文a b s t r a c t a b s t r a c t w i t ht h er a p i dg r o w t ho fi n t e m e t ，n e t w o r kp e m r m a n c ei sf a c i n gs e v e r ec h a l l e n g er e c e n t l y t h u st r a 衔ce n g i n e e r i n gh a sb e c o m eac r i t i c a li s s u eo f 如r t h e rd e v e l o p m e n to fi n t e m e t b e c a u s e n e m o r kt r a n s m i s s i o nr a t ei n c r e a s e sc o n s t a n t l ya n dn e w 印p l i c a t i o n se m e 唱e 舶q u e n t l y ，p r e s e n t t e c h n i q u eo ft r a f f i ce n g i n e e r i n gc a n n o tm e e tt h ed e m a n do fo p t i m i z a t i o no fh i g h s p e e dn e t w o r k ， l e ta l o n et h er e q u i r e m e n t0 ff u r t h e rd e v e l o p m e n to fi n t e m e t t h i sd i s s e n a t i o ns e t st h es t a g ef o r s o l v i n gas e r i e so fp r o b l e mi nt r a 筒ce n g i n e e r i n gt oe n h a n c en e t w o r kp e r f o n n a n c ea n dq u a n i i t yo f s e r v i c e i tf o c u s e so ns e v e r a la s p e c t sw h i c hi n c l u d e sm e a s u r e m e n to fr o u n dt r i pt i m eo ft c p c o n n e c t i o n ，i a 唱ef l o wi d e n t i f i c a t i o ni nh i g h - s p e e dn e t w o r k ，a n dr o u t i n ga d j u s t m e n ti nb a c k b o n e n e t w o r k t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s 1 ) p a s s i v e l ym e a s u r i n gi 之t to ft c pc o n n e c t i o ni so fg r e a ti m p o n a n c ef o rn e t w o r kd e s i g n ， t r a 丘i ce n g i n e e r i n g ，o p t i m i z a t i o n0 fp 2 pn e t w o r k ，a n de t c t bd e a lw i t ht h es h o r t c o m i n g so fp r e s e n t m e t h o d s ，t h i sp a p e rp r o p o s e sa na l g o r i t h mn 锄e dc r o s st oe s t i m a t er t to ft c pc o n n e c t i o n f 而mn o n - s e n d e rs i d e c r o s sa c q u i r e st h ec o n e s p o n d e n c eb e t w e e nd a t a p a c k e t sa n da c k p a c k e t sw i t hc r o s sc o n e l a t i o n 如n c t i o n ，a n dt h e ni tg e t sr t to ft h i st c pc o 彻e c t i o n t h e e x p e r i m e n tu p o np l a n e t l a bs h o w st h a tt h i sa l g o r i t h mn o to n l yp r e c i s e l ym e a l s u r e si 订ti na n y p h a s eo ft c pc o 彻e c t i o n ，b u ta l s ow o r k sw e l lw h e nr t 丁f l u c t u a t e sg r e a t l yd u et ot h ed e t e r i o m t j o n o fn e t 、 ，o r kc o n d i t i o n 2 ) i h en u m b e ro fl a f g ef l o w si ni n t e m e ti ss m a l l 。b u tag r e a td e a jo fl r a 伍ci sc o m p o s e do f t h e m t h e r e f o r ei tc a ne 仃e c t i v e l ye n h a l l c et h ep e 而m a n c eo fc o n g e s t e dn e t 、v o r kt h a ti a 唱ef l o w s a r er a p i d l ya n da c c u f a t e j yf o u n do u ta n dt h er o u e sa r ea d j u s t e d b yt h i sm e a n sa h e a v yc o s to f m a n a g i n gt h el a 唱en u m b e ro fs m a l in o w si sa v o i d e d t r a d i t i o n a l l a 唱ef l o wi d e n t i f i c a t i o n a l g o r i t sb a s e do ns a m p h n g 鲰：h n i q u eo ra l t e rs _ 觚c t u r eh a v ed e f i c i e n c yo fi o wa c c u a y h e n c e t h e yc a n n o ts a t i s yt h en e e do fi m e m e ta p p l i c a t i o 璐t l i sp a p e rp r e s e n t sad u a l l r ub a s e d a l g o r i t h mc a l l e dl r u 2t oi d e n 虹母a n dm e a s u r el a 喀en o w s i nt h e 柳ol e v e l so fl r u ，l e v e lo n ei s f - o rf i l t e r i n gs m a l lf l o w s ，a n dl e v e lt 、 ，oi sf o ra c c u r a t e l yc o u n t i n gl a 喀en o w s w ed e d u c et h eu p p e r i i i 北京邮电大学博士论文a b s t r a c t b o u n do fs t a t i s t i c a le r r o rf o rl a 唱ef l o w sa tt h ew o r s tc a s e ，a n dp r o v eb ya n a l y z i n gt h a tt h e a l g o r i t h mh a sp r o c e s s i n gc a p a c i t yo f1o g b p sl i n es p e e d t h ee x p e r i m e n tb a s e do nr e a ld a t a s e to f i n t e m e ts h o w st h a tt h en e wa i g o r i t h mh 豁h i g h e ra c c u r a c ya n dp r a c t i c a b i l i t yt h a no l do n e s 3 ) u n b a l a n c e dd i s t r - b u t i o no fi n t e m e tt r a 伍cm a yl e a dc o n g e s t i o n a tm i st i m e ，c h a n g i n g r o u t e sf o rc e r t a i nt r a 塌cw i t hg r e a ti m p a c to nc o n g e s t i o nw i l li m p r o v et h ep e m r m a n c eo fn e t w o r k t h i sp a p e rp r e s e n t sar o u t i n ga d j u s t m e n ta l g o r i t h mf o rs i n g l el a 唱en o w i td e c r e a s e st h el a 唱e s t b a n d w i d t hu t i l i z a t i o nr a t eo no n eh a n d ，a n do nt ：? eo t h e rh a n di tg u a r a n t e e sq o so ft h en o wb y c o n f i n i n gr o u t el e n g t ho ft h ef l o wa d j u s t e dw i t h i ns o m ea c c e p t a b l eb o u n d t h ee x p e r i m e n tb a s e d o nr e a in e t w o r kt o p o l o g ya n dt r a f f i cs h o w st h a tt h en e wa l g o r i t h me f f b c t i v e l yr e l i v e v e sc o n g e s t i o n w i t ht h em a x i m a id e c r e a s eo fl a r g e s tb a n d w i d t hu t i l i z a t i o nr a t ea p p r o a c h i n g5 0 s i m u l a t i o n p r o v e st h a tt h en e wa l g o r i t h mo v e r n l a t c h e se x i s t i n ga l g o r i t h m sf o ri tn o to n l ym e e t st h ed e m a n do f t h ep a t hi e n g t h0 fk e yf l o wb u ta i s od e c r e a l s e st h el a 唱e s tb a n d w i d t hu t i l i z a t i o nr a t eo fn e t w o r k i n a d d i t i o n ，t h ec o m p u t a t i o n a ic o m p l e x i t yi sc k 2l o g ) ，w h i c hi sl o w e rt h a nm a j o r i t yo fp r e s e n t r o u t i n ga d j u s t m e n ta l g o r i t h m s 4 ) a l t h o u 曲t h ep r o b a b i i i 妙o fm u l t i l i n kc o n g e s t i o ni ss m a l ii ni n t e r n e t ，i td o e se m e r g e s o m e t i m e s t h i sk i n do fs i t u a t i o ni sn o te a s yt od e a lw i t h ，a n dw i l lm a k ed i 确c u l t i e st on e t w o r k o p t i m i z a t i o n t bs o l v et h i sp r o b l e m ，t l l i sp a p e rp r o p o s e sak e yf l o wr o u t i n ga d j u s t m e n ta l g o r i t h r n w h i c hs e l e c t sn e x th o pw i t hp r o b a b i l i 够w h e nm o r et h a no n ei i n ki sc o n g e s t e d ，m i sa l g o r i t h m a d j u s t sr o u t e sf o rs e v e r a lk e yf l o w ss i m u l t a n e o u s l y w i t ht h i sm e t h o d ，t r a 历cd i s t r i b u t e sm u c h m o r ee v e n l yt h a nb e f o r ea n dn e t 、o r kp e 哟n n a n c ei m p r 0 v e st h e r e b y s i m u l a t i o ni n d i c a t e st h a tt h e n e wa l g o r i t h mg r e a t l ye n h a n c e st l l et h r o u g h p u to f n e t w o r ka n dm a k e sb e t t e rd i s t r i b u t i o n0 ft r a f f i c b e s i d e s ，i tg u a r a n t e e sq o sb yc o n f i n i n gr o u t el e n 甜h 雏w e l l k e yw o r d s ： i n t e m e t t r a 塌ce n g i n e e r i n g ， n e t 、v o r k m e a s u r e m e n t ，l a 唱ef l o w i d e n t i f i c a t i o n ，r o u t i n ga d j u s t h l e n t i v 北京邮电大学博士论文缩略语 缩略语 英文缩写英文全拼中文 a q m a c t i v eq u e u em a n a g e m e m主动队列管理 a sa u t o n o m o u ss y s t e m自治域 c a i d a c 0 0 p e r a t i v ea s s o c i a t i o nf o ri n t e m e td a t aa n a l y s i s 互联网数据分析合作协会 c a mc o n t e n ta d d r c s s a b l em e m o 珂 内容寻址存储器 c n n i cc h i n aj n t e m e tn e t w o r ki n f o m l a t i o nc e n 亡c r 中国互联网络信息中心 d r a m d y n a m i cr a n d o ma c c e s sm e m o 叫 动态随机访问存储器 i di d e n t i t v 标识 i e t fi n t e t n e te n g i n e e i i n gt a s kf o r c e 互联网工程任务组 l pi n t e t n e tp r o t o c o l 互联网协议 i s i s i n t e r m i d j a t es y s l e m i n t e r m j d j a t es y s t e m中间系统到中间系统 i s pi n t e n l e ts e r v i c ep r o v i d e r 互联网服务提供商 l e rl a b e le d g er o u t e f标签边缘路由器 l l bl a b e il n f o 咖a 蛀o nb a s e 标签信息库 l r ul e a s tr e c e n t l yu s e d 最近最久未使用 l s rl a b e ls w i t c h i n gr o u t e r 标签交换路由器 m i r am 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 m m 最小干扰路由算法 m p l s m u l t i p r o t o c o ll a b e ls w i l c h i n g 多协议标签交换 n pn o n d e t e r m i n i s t i cp o l y n o m f a i 非确定性多项式 o s p f 0 p e ns h o r l e s tp a t hf i r s l 开放式最短路径优先 p 2 p p r t op e e r 对等( 网络) q o sq u a l j t yo fs e i c e 服务质量 r l br a n d o m i z e dl o a db a l a n c i n g随机负载均衡 r s r 0 u t i n gs e r v e r 路由服务器 r ，玎r o u n dt r i p 啊m e 往返时延 北京邮电大学博士论文 缩略语 s n m p s i m p i en e t w o r km a n a g e m e n tp m t o c o l 简单网络管理协议 s i 认ms t a t i cr a n d o ma c c e s sm e m o w静态随机访问存储器 t c pt r a n s m i s s i o nc o n t r o lp r o t o c o l传输控制协议 t e1 m 伍ce n g i n e e r i n g流量工程 u d pu s e rd a t a g r 哪p r o t o c o l用户数据报协议 v o i pv b i c e o v e r l pi p 电话 9 5 北京邮电大学博士论文图目录 图目录 图1 1 论文结构示意图5 图2 1t c p 首部1 7 图2 2 发送端r 1 v r 测量1 7 图2 3 非发送端r t t 测量18 图2 4a c k 分组序列与数据分组序列的相似性1 9 图2 5 离散s i n e 函数2 0 图2 6 离散c o s i n e 函数2l 图2 7s i n e 与c o s i n e 的互相关函数2 l 图2 8 自相关函数( 网络不拥塞) 2 3 图2 9 自相关函数( 网络拥塞) 2 3 图2 1 0 互相关函数( 网络不拥塞) 2 4 图2 1 1 互相关函数( 网络拥塞) 2 4 图2 1 2p l a n e t l a b 节点分布图2 6 图2 13t r a c el 发送端i m 2 7 图2 1 4t r a c e l 接收端r 1 广r ( p i n g ) 2 7 图2 一1 5t r a c e l 接收端i 汀t ( c r o s s 算法) 2 8 图2 1 6t r a c e l 接收端i m ( 文【1 0 】中的方法) 一2 8 图2 17t r a c e 2 发送端r t t 。2 9 图2 1 8t r a c e 2 接收端i 汀t ( p i n g ) 2 9 图2 1 9t r a c e 2 接收端r 盯( c r o s s 算法) 3 0 图2 2 0t r a c e 2 接收端i 玎t ( 文【l o 】的方法) 3 0 图2 - 2lt r a c e 3 发送端砌盯3l 图2 - 2 2t r a c e 3 接收端l 汀t ( p i n g ) 3l 图2 - 2 3t r a c e 3 接收端i 汀t ( c r o s s 算法) 3 2 图2 2 4t r a c e 3 接收端r 盯( 文【l o 】的方法) 3 2 图3 1l r u 2vl 算法系统结构3 8 图3 2l r u l 最大长度与误差关系i 4 2 图3 3l r u l 最大长度与误差关系i i 4 3 v i i i 北京邮电大学博士论文 图目录 图3 4l r u l 通过门限与误羞关系i 4 4 图3 5l r u l 通过门限与误差关系i i 4 4 图3 6 大流到达时刻与误差关系i 4 5 图3 7 大流到达时刻与误差关系l l 4 7 图3 8l r u 2v 2 算法系统结构4 7 图3 9l r u 2v 3 算法系统结构5 0 图3 1 0l r u 2v 2 与l r u 2v 3 的比较5 2 图4 1a b i l e n e 2 拓扑6 3 图4 2m i r a n e t 拓扑6 4 图4 3a b i l e n e 2 实验结果i 6 5 图4 4a b i i e n e 2 实验结果1 i 6 5 图4 5a b i l e n e 2 实验结果i i i 6 6 图4 6a b i l e n e 2 实验结果1 v 6 6 图4 7a b i l e n e 2 实验结果v 6 7 图4 8 加权平均流长曲线6 8 图4 9 最大流长曲线6 9 图4 1o 流个数曲线6 9 图5 1 代价函数曲线8 0 图5 2 关键流选路8l 图5 3m i r a n e t 网络拓扑8 2 图5 45 0 个节点拓扑上的最优差( i ) 8 5 图5 58 0 个节点拓扑上的最优差( 1 ) 8 6 图5 65 0 个节点拓扑上的最优差( i i ) 8 6 图5 78 0 个节点拓扑上的最优差( i i ) 8 7 图5 85 0 个节点拓扑上的平均路径长度8 8 图5 98 0 个节点拓扑上的平均路径长度8 8 i x 北京邮电大学博士论文 表目录 表目录 表2 1 实验数据描述2 6 表3 - l 数据集描述4 l 表3 - 2 比较实验结果4 9 表4 la b i l e n e 2 数据描述6 4 表5 1 符号表7 8 x 声明 独创性声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮 电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 埃裔圭叫 日期：_ 9 叫 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定， 即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学 校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论 文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用 影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密 后遵守此规定) 本学位论文不属于保密范围，适用本授权书。 本人签名垫塑兰 嗍 导师签名：乏垒丝 日期： 枷j ( 1 j 北京邮电大学博士论文第l 章绪论 第1 章绪论 本章首先对本论文选题的背景和依据进行总结和归纳，然后引出论文主要研究内 容并介绍本论文的主要贡献。最后介绍全文结构安排。 1 1 引言 近年来，随着科学技术的进步，国际互联网以前所未有的速度发展，已经由最初仅用于 军事和科研目的的网络，演变为重要的基础通讯设施。在当今的信息时代，互联网已经渗透 入社会生活的各个领域，经济、军事、文化、教育、体育等各个方面的发展都离不开互联网 的支持。 互联网高速发展的同时，互联网骨干网底层的基础设施面临海量数据的冲击。一方面， 随着宽带的普及以及各种新型接入终端的涌现，互联网用户数量迅速增加，直接导致网络内 部流量的增长。中国互联网络信息中心( c n n i c ) 在2 0 0 5 年7 月的调查数字显示，截止 2 0 0 5 年6 月，中国互联网网民达到1 0 3 亿。而易观国际发布的中国互联网年度综合报告 2 0 0 7 2 0 0 8 ”截止2 0 0 7 年底，中国互联网网民数量已达2 1 亿，并且这一数字将在2 0 1 1 年达到6 亿。另一方面，一些新业务的出现加大了对网络带宽的需求。早期互联网上的应用 主要是w 曲业务，单个用户业务的流量不大。近年来，多媒体应用使得人们通过互联网打 电话、看电影、开电视会议成为可能。虽然编码技术不断发展，这类业务产生的流量仍然远 远高于传统互联网业务。网络流量增长的另一个原因是用户对网络使用方式的改变，特别是 p 2 p 技术的出现，给网络带来了极大冲击。在传统的互联网中，不管是下载文件还是收看视 频，用户都是与服务器直接建立连接，从服务器获取需要的信息。在这种情况下，网络内部 的流量与用户数量呈正比。p 2 p 技术出现后，用户不但与服务器，还与其他用户建立连接， 从其他用户处获取信息。此时，骨干网内部流量与终端用户数量不再是线性关系，而是指数 关系。 面对流量增长的压力，互联网运营商必须采取行之有效的措施维护网络的正常运行。虽 然光纤技术发展很快，骨干网链路带宽不断增加，但是单独依赖带宽的增长仍然不能抵消流 量增长对网络的冲击。在这种情况下，针对提高网络性能的研究非常必要。一方面，要充分 1 北京邮电大学博士论文 第l 章绪论 利用现有资源，提高网络的处理能力和可靠性；另一方面，要保证网络用户能够获得高质量 的服务。流量工程的研究在这样的背景下显得意义重大，引起了产业界和学术界普遍的重视。 i e t f 【3 】对流量工程的定义【4 1 是：流量工程是对i p 网络实施性能评估和优化的行为。流量 工程是对网络规划的一种补充和完善，目的是使实际网络业务量以一种最优的方式存在于物 理网络之中。流量工程的优化目标可以从两种角度考虑：面向流量和面向资源。面向流量的 优化目标主要从吞吐量和时延等流量统计特性的角度表征网络服务性能的提高；而面向资源 的优化目标主要是从合理分配资源的角度对网络优化。虽然这两者的角度不同，最终都是要 避免拥塞发生，提高网络资源利用率。 通过对流量工程定义的分析可以看出，流量工程是一个自适应的反馈系统，过程分为三 个步骤：即网络测量，网络建模及流量控制。首先，通过测量手段获得网络的状态信息。网 络状态信息分为两类：一类是网络自身属性，如网络拓扑5 】【6 】【7 】【8 1 、链路带宽哪! o 】【l l 】、路由 器缓存大小【1 2 1 【1 3 1 【1 4 1 等：另一类是针对业务的特性，如端到端业务路径上的时延、带宽和丢 包率【1 5 】。然后，通过对数据分析建模找出各种流量分布的统计特性和分布规律，建立网络 的输入输出模型。例如，通过对实际网络流量的研究，人们发现了互联网流量的自相似性 f 1 6 】f 17 1 、互联网拓扑的幂率分布【l s 】【1 9 】、互联网流大小的重尾分布f 2 0 】f 2 1 j f 2 2 1 等重要规律。最后， 计算流量对现有网络的最优化使用方式，并将结果运用到实际网络中去。因为控制引起了网 络状态的改变，因此需要重复上面的过程，才能一直保持流量工程的准确性。网络测量是流 量工程的基础，用于获取评价网络性能的所有数据，发现对网络性能产生负面影响的异常事 件。流量控制是实现流量工程目标的最终手段直接决定了网络性能。因此，在流量工程研 究中，网络测量和流量控制具有重要意义。 网络测量从方法上分为两大类，即主动测量【2 3 l 【2 4 】【2 5 】f 2 6 1 和被动测量【2 7 】【2 3 】【2 9 j 【3 0 】【3 i j 。主动测 量需要向网络中发送测量探针，通过分析测量探针携带的信息获取网络的状态。此时，测量 系统一般部署在网络的边缘，而获得的结果则是测量系统端到端路径的参数，如带宽、时延、 抖动等。相反，被动测量不向网络添加任何流量，由位于网络内部的路由器或专用测量设备 通过采集并分析流经网络的分组得到网络的状态。主动测量和被动测量方法不同，面临的困 难不一样。获取的信息也不尽相同，因此应该针对流量工程具体任务的需要，选择适当的测 量方法，为后续的流量控制打好基础。 当骨干网链路上的流量超过该链路的处理能力时，通常有两种方法用于避免拥塞的发 生。第一种方法是丢弃，即路由器通过主动丢弃分组的方式降低负载，满足链路的处理能力 要求p 2 】1 3 3 】【3 4 】。如果被丢弃的分组是t c p 分组，这种方法还能使该分组对应的t c p 连接的终 2 北京邮电大学博士论文 第l 章绪论 端主动降低发送速率。丢弃分组虽然能够解决流量与系统处理能力之间的矛盾，但也会严重 降低t c p 的吞吐量。并且，互联网流量分布并不均匀f 3 5 j ，简单地丢弃分组还会使网络中 出现大量空闲链路，降低网络利用率。降低链路负载的另一种方法是路由调整，即结合网络 带宽的占用情况，改变某些流量的原始传输路径，使其绕开拥塞链路。正是因为互联网流量 在空间分布上的不均衡性，网络中的某些链路拥塞时，另外一些链路仍然处于空闲状态得不 到充分利用，这使得通过调整路由避免拥塞成为可能。 在传统l p 网中，使用以最短路径算法为基础的路由协议( 如o s p f ( 3 刀、i s i s 渊) ，这给 流量工程中对流量的控制和调整带来了困难。此时，路由器只按照目的节点和路由表转发分 组，任何针对流量的路由调整都需要对整个网络内所有链路权值的重新计算。在改变了导致 拥塞的流量的路由的同时，也影响了其它流量。因此，这种方法不够灵活，针对性不强。并 且，每次调整过程都会改变整个网络结构，系统的开销较大。另一方面，最优链路权值的计 算复杂度高，当网络规模较大时难以实现。 近年来，m p l s 【3 9 1 的出现为流量工程的实施提供了有力的技术保障。m p l s 网络的转发 设备由标记边缘路由器l e r 和标记交换路由器l s r 构成。数据分组进入网络时，l e r 根据 标记策略为该分组添加标记，中间路由器l s r 按照标记值通过查询标签信息库l i b 确定交 换路径l s p ，从而实现对分组的转发。m p l s 协议的出现在提高了核心网转发速率的同时， 也弥补了传统i p 网在流量工程能力上的不足，推动了流量工程技术的发展。在m p l s 网络 中，可以很方便地建立显式路由，也就是说，可以通过建立l s p 为分组指定要经过的节点。 这一特点使得网络中以流为单位的流量控制成为可能，解决了传统域内网关协议在面对拥塞 时开销大以及不够灵活的缺陷。 流量工程有两大基本目标：一是路径选择要满足用户对服务质量的需求；二是路径选择 要实现对网络性能的优化。满足以上两个目标的路由技术称为约束路由，也是流量工程的核 心技术。约束路由问题对应到m p l s 流量工程中，就是要为业务流建立l s p ，满足业务流 的时延及带宽等q o s 要求，并且提高网络的吞吐量和传输效率，降低拥塞发生的概率。有 关约束路由的研究已经取得了一些进展，如：最小跳( m i n h o p ) 为基础的路由算法【4 0 】【4 l 】f 4 2 1 、 基于最小跳算法的改进算法【4 3 1 【4 4 1 、最小干扰路由算法【4 5 】等。但是，互联网规模的扩大以及 流量的不可预测性决定了约束路由技术仍然存在不足之处，有待进一步的研究。 互联网流量工程是一个大规模的系统工程问题，目前仍然存在亟待解决的问题与挑战。 首先，网络管理者需要切实有效的方法及时发现网络性能问题，例如网络中的某处发生拥塞。 网络传输性能下降是流量工程实施的前提，及时发现问题能够使流量工程做到有的放矢。当 3 北京邮电大学博士论文第l 章绪论 前网络管理员主要通过s n m p 协议f 4 6 l 监测网络性能。但s n m p 协议只能提供粗粒度的信息， 如一段时间内流经路由器某接口的字节数，并不能够提供对流量工程来说更有意义的流信 息。并且，s n m p 协议对一般的统计信息采用定时发送的方式，这不利于管理员及时发现网 络中的拥塞。当前流量工程面临的另一个问题是路由优化问题，也就是说，当网络拥塞时如 何通过调整路由实现网络性能优化。由于互联网规模大、发展速度快、业务组成复杂，如何 在节点和链路不断增加的网络中优化路由才能提高网络性能并且满足不同的业务需求，是当 前流量工程面临的另一个严峻的挑战。 上述互联网流量当前面临的两大类问题所包含的具体目标和任务极其广泛，因此本文只 选取其中几个有代表性的问题，提出切实可行的方法。本文研究以下三个方面的问题： 1 ) t c p 连接r t t 的被动测量：r 1 r r 是反映网络性能的一个重要参数指标，管理员能够 根据r 1 陌的变化及时发现网络中的拥塞【4 7 】【4 8 】f 4 9 j 。因此，r 阿测量可以作为流量工程中发现 网络性能问题的一种手段，弥补s n m p 协议的不足。传统方法通过主动测量获得t c p 连接 的r 1 t 。但是，主动测量方法由于需要向网络注入流量，会对网络性能产生负面影响。并且， 主动测量需要在测量路径的两个端点部署测量系统，当要测量的路径较多时开销较大。与主 动测量相比，被动测量不会向网络注入额外的流量，并且只需要在网络内部的部分节点部署 测量系统，就可以测量到所有通过网络的t c p 连接的r r r 。因此，在r t t 的测量中，尤其 是用于流量工程目的时，被动测量比主动测量更有优势。但是同时也应该看到，被动测量只 是在网络中被动的观察，信息的不对称性导致某些计算i m 的必要参数不能直接获得，如 t c p 的发送窗口，这给被动测量r t t 带来了困难。 2 ) 高速网络中的大流检测：流量测量是网络监测、控制和管理的重要手段，可用于网 络计费、网络安全及流量工程等多种应用。传统的路由协议容易造成流量分布不均衡，导致 网络中“热点”区域的产生，某些链路带宽被过度使用的同时，另外一些链路利用率低，甚 至长期处于空闲状态。当网络拥塞时，应该有的放矢地找到拥塞所处的位置，并对相应的流 量做出路由调整。其中，调整的对象分为以分组为单位和以流为单位。以分组为单位的调整 容易导致同一t c p 连接内的分组因不同路径存在差异而发生乱序，严重降低t c p 的吞吐量 1 5 0 】【5 l 】【5 2 1 。因此，在流量工程中，更多的是以流为单位做调整。所谓流，指的是在一段时间 内，源地址和目的地址具有相同特征的分组的集合【5 3 】。对于互联网中的流