（计算机科学与技术专业论文）基于主动和被动测量的网络测量技术、模型和算法研究.pdf

垦堕型兰垫垄查兰翌茎竺堡主堡堡苎 摘要 随着i n t e m e t 应用的急剧增长，越来越多的网络应用程序需要了解网络延迟、 带宽、吞吐率等网络性能参数，以支持可区分的服务。这些及时的网络性能数据 对于许多网管业务，如主动式和被动式的资源管理、流量工程以及端到端的服务 质量保证，显得尤为重要。特别是现代的网络管理系统注重于服务级、应用级的 管理，网络测量的频率会越来越快，需求的网络性能数据也会越来越多。 近年来网络测量技术和网络测量模型已经成为研究的热点。网络测量方式可 以分为主动测量和被动测量两种。主动测量方式通过向目标链路或目标节点发送 探测包，来测量链路或端到端的延迟、带宽和丢包率等网络性能参数。被动测量 方式通过接入网络的测量探针，记录和统计网络链路或节点上业务流量的信息。 本文对基于主动测量和被动测量的网络测量技术、网络测量模型及其近似算法进 行了深入研究。本文工作的主要贡献和创新总结如下： f 1 ) 分布式主动测量模型中测量分配问题研究 主动测量的代价包括测量站部署代价和测量代价两个部分。测量站的数量和 位置确定下来以后，为了减少测量代价就需要优化测量分配方案，也就是确定链 路由哪一个测量站来负责测量。 本文提出了分布式主动带宽测量模型中的测量分配问题，给出了测量分配问 题的整数规划形式，并且指出测量分配的最优化问题是n p 难的。基于贪婪策略和 动态规划的思想，给出了近似比为2 的启发式算法，并且通过仿真实验证明了近 似算法的有效性。带宽测量分配问题及其解决思路和近似算法，同样可以用来解 决测量延迟、丢包率等其它网络性能参数，对分布式主动测量系统的设计和实现 具有很强的指导作用。 ( 2 ) 链路带宽被动监测模型优化问题研究及其近似算法 被动监测模型的研究重点在于如何部署尽量少的监控器去监控全网的性能， 这样一方面减少了安装和维护代价，另一方面也可以减少收集网管数据带来的额 外网络流量。利用路由器流守恒规律可以有效减少网管代理的安装数量，从而减 少安装代价和收集流量，实现低负载的链路带宽有效监控。 基于流守恒的网络链路带宽被动监测模型的最优化问题可以抽象为无向图中 的弱顶点覆盖问题。论文给出了一个从顶点覆盖问题到弱顶点覆盖问题的近似保 持归约。根据这个近似保持归约，要想找到弱顶点覆盖问题的一个常数近似比小 于2 的近似算法也是非常困难的。利用近似算法的原始对偶方法，可以得到一些 近似比为2 的近似算法。这些算法同样可以应用于解决带禁点的弱顶点覆盖问题。 ( 3 ) 链路约束的分布式网络收集框架优化问题研究及其近似算法 为了收集实时的网络性能数据，收集过程需要一个稳定可靠的低延迟路由。 链路延迟或者路由跳数的限制决定了收集节点负责查询和收集的监控节点的数量 是有限的。链路约束的分布式网络收集框架的优化目标是部署尽量少的收集节点 收集到所有监控节点的性能数据，其最优化问题是n p 难的。论文指出可以把链路 约束的分布式收集框架的最优化问题映射到集合覆盖问题，利用贪婪算法可得到 第1 页 里堕型兰茎查查兰堑壅生堕兰焦笙茎 i t i si m p o r t a n tt h a tt h en u m b e ro fp l a c e dm o n i t o r sb ek e p ta ss m a l la sp o s s i b l e ， s i n c ei tc o u l dn o to n l yr e d u c et h ed e p l o y m e n tc o s ta n dm a i n t e n a n c ec o s t ，b u ta l s o r e d u c et h ee x t r at r a f f i c sa n db a n d w i d t hc o n s u m p t i o nf o rp o l l i n gn e t w o r km a n a g e m e n t d a t a e x p l o i t i n gt h ef l o w - c o n s e r v a t i o nl a wc o u l dr e d u c ed e p l o y m e n tc o s ta n dp o l l i n g l o a dw i t hr e d u c i n gt h en u m b e ro fm o n i t o r s h e n c e ，w ec o u l dd e v e l o pal o w o v e r h e a d l i n k - b a n d w i d t hp a s s i v em o n i t o r i n gm o d e lb yu s i n gt h ef l o w - c o n s e r v a t i o nl a w t h ep r o b l e mo fe f f i c i e n t l ym o n i t o r i n gl i n k - b a n d w i d t hb a s e do nf l o w c o n s e r v a t i o n c o u l db er e d u c e dt ot h ew e a kv e r t e xc o v c r p r o b l e m ，w h i c hi sn p - h a r d i nt h i sp a p e r , w e d e m o n s t r a t ea na p p r o x i m a t i o np r e s e r v i n gr e d u c t i o nf r o mt h ev e r t e xc o v e rp r o b l e mt o t h ew e a kv e r t e xc o v e rp r o b l e m d u et ot h i sr e d u c t i o n ，i tf o l l o w st h a ti ti sv e r yd i f f i c u l t t og e ta l la p p r o x i m a t i o na l g o r i t h mw i t hc o n s t a n ta p p r o x i m a t i o nr a t i ol o w e rt h a n2f o r t h ew e a kv e r t e xc o v e rp r o b l e m t h e r ee x i s ts o m ea p p r o x i m a t i o na l g o r i t h mw i t h a p p r o x i m a t i o nr a t i o2b yu s i n gt h ep r i m a l - d u a lm e t h o d w ec o u l da l s ou s et h e s e a l g o r i t h m st os o l v et h ew e a kv e r t e xp r o b l e mw i t hb l a c k o u tv e r t i c e s ( 3 ) t h eo p t i m i z a t i o np r o b l e mo f d i s t r i b u t e dn e t w o r kp o l l i n gi n f r a s t r u c t u r ew i t hl i n k c o n s t r a i n ta n di t sa p p r o x i m a t i o na l g o r i t h m s f o ro b t a i n i n gu p - t o - d a t en e t w o r kp e r f o r m a n c ei n f o r m a t i o n ，t h e a g g r e g a t i n g p r o c e d u r er e q u i r e st h ee s t a b l i s h m e n to fr e l i a b l e ，l o wd e l a ya n dl o wc o s ta g g r e g a t i n g r o u t e s h e n c et h ea g g r e g a t i n gp r o c e d u r ei sc o n s t r a i n e db yt h el i n kd e l a ya n dt h er o u n d h o p s t h ep r o b l e mo fo p t i m i z i n gad i s t r i b u t e dp o l l i n gi n f r a s t r u c t u r ew i t hl i n kc o n s t r a i n t i sn ph a r d i tc o u l db em a p p e dt ot h ew e l l k n o w nw e i g h t e ds e tc o v e r p r o b l e m ag r e e d y a l g o r i t h mc o u l db eu s e dt os o l v et h i sp r o b l e mw i t ha na p p r o x i m a t i o nr a t i o1 + i n l 矿l ， w h e r evi st h en u m b e ro f m o n i t o r i n gn o d e s i ti si m p o r t a n tt oc h o o s ea na p p r o p r i a t el i n kc o n s t r a i n tv a l u es i n c et h en u m b e ro f m o n i t o r si sr e l a t e dt ot h el i n kc o n s t r a i n tv a l u e i ti sd i s c u s s e dh o wt oc h o o s ea n a p p r o p r i a t el i n kc o n s t r a i n tv a l u eb ys i m u l a t i o n ( 4 ) t h eo p t i m i z a t i o np r o b l e mo fd i s t r i b u t e dm o n i t o r i n gm o d e lw i t hl i n kc o n s 廿a i n t f o re v o l v i n gn e t w o r k sa n di t sa p p r o x i m a t i o na l g o r i t h m s w h e nt h en e t w o r kc h a n g e so ru p g r a d e s s o m en e t w o r kl i n k sa n dn o d e sm a yb e d e l e t e df r o mt h en e t w o r ka n dn e wl i n k sa n dn o d e sw o u l db ea d d e d c o n s e q u e n t l y , t h e m o n i t o r i n gs y s t e m sm a yn e e dt ob er e c o n f i g u r e df o ro b t a i n i n ga l ln e t w o r kp e r f o r m a n c e i n f o r m a t i o n t h em o n i t o r i n gi n f r a s t r u c t u r es h o u l db er e c o n f i g u r e da tm i n i m u mc o s tt o o b t a i nu p - t o - d a t es t a t u si n f o r m a t i o na st h en e t w o r ke v o l v e s t h en e t w o r ka d m i n i s t r a t o r s 时t om i n i m i z et h et o t a lc o s to fu p g r a d i n gt h em o n i t o r i n gi n f r a s t r u c t u r ei n c l u d i n g a d d i n gn e wp o l l e r sa n dr e c o n f i g u r i n gt h ee x i s t i n gp o l l e r s i nt h et h e s i s ，t h ep r o b l e mo fo p t i m a l l y u p g r a d i n g t h e e x i s t i n gm o n i t o r i n g i n f r a s t r u c t u r eh a sb e e na d d r e s s e d i ti ss h o w nt h a tt h i sp r o b l e mi sn p - h a r d s i n c et h e c o s to fa s s i g n i n gt h ep o l l e e ，p o l l e ra n dn e wn o d e sa r ed i f f e r e n t ，w ec o u l ds e tt h e s e n o d e sw i t hd i f f e r e n tw e i g h tv a l u e a n dw ep r o p o s eag r e e d ya l g o r i t h mw i t ht h e a p p r o x i m a t i o nr a t i ol + i n l 矿i ，w h e r e 【矿l i s t h en u m b e r o f m o n i t o r i n g n o d e s 第1 v 页 国防科学技术大学研究生院学位论文 ( 5 ) p 船s i v ec a l i b 洲o no f a c t i v em e a s l l r i n g1 a t e n c ym e t h o d i ng e n e m l ，m o n i t o r i n gs c h e m e st om e a s u r el a t e n c ya r ed i v i d e di n t o 铆ot y p e s ： a c t i v ea 1 1 dp a s s i v em e a s u r e m e n t u n f o i t u n a t e l y b 劬t y p e sh a v ed r a w b a c k s w bp r o p o s e 曲ep a s s j v ec a j j b 船t i o no fa c t i v em e a s 耐n gl a 自即c ym c d l o d 1 1 1 j s 如c t i v cm 劬o dh a s s o m e a d v a n t 嘈e ss u c ha sp r 蝴l - i n d 印e n d e l l t ，n e g l i 西b l ee x 廿at r a m c ，c o n v e | 1 i e n c ea n d b e i n ga b l et oe s t i m a t ci n d i v i d u a lu s c rp e r f b 珊a i l c e i nt h i sm e 山o d ，t 1 1 en 啪b e ro fu s e r d a t ap a c k e t sa 仃i v i n gb e t w e e np r o b ep a c l 【c t s 髓dt h el a t e n c ya 】t e r a t i o no fn e i g h b o r h o o d p m b ep a c k c t sh a v eb e e nc o n s i d e r e d ，粕dt 量l ea c t i l a ln e 柳o r ks t a t i l sc o u l db er e n e c t e d m o r ee x a c t l y ，e s p e c i a l l yi nt h ec a s eo fn e 帆o r kc o n g e s t i o n 锄dp a c k e t1 0 s s t h e e f r e c t i v e n e s so ft l l em e a s u r e m e mm e l o di sv a l i d a t e db ys i m u l a t i o n se v a l u a t i o no v e ra w i d e 啪g eo f n e t 、o r kt 叩o l o g i e s i n c o n c l u s i o n ， s o m e i n - d e p 廿l r e s e a r c hh a v eb e e n m a d e ， i i l c l u d i n g a c t i v e m e a s u r e m e mm o d e l ，p a s s i v em e a s u r e m e n tm o d e l ，d i s 删b u t e dp o l la l h i t e c t u r e ，e v o l v i n g n e m o r ka l l d 廿1 em e a s u r e m e n tm e t l l o dc o m b i n i n ga c t i v ea n dp a s s i v ea p p r o a c h e s t h e n e m o r km e a s u r e m e n tt e c l l l l o l o g i e s ，n e t w o r km e a s u r c m e mm o d e la n di t so p t i m i z a t i o n a l g o r i m m sp m p o s e d i n 廿l i st l l e s i sa r eh e l p f i l lt 0 d e s i 驴粕dd e v e l o pn 咖0 r k m e 髂u r e i n e n ts y s 把m s k e y w d r d s ：n e t w o r km 姐s m 蜘蚰t a c t i wm 髑册鹏m e t p a 鼹i wm 嘲u 坤m e t e v o l “n gn e 岍o r l ，p o m n ga r c h i t e 咖i 与m a 噶珈舳卸tm o d d ，m 【噶u 件m e t h 宅h o i o g y ，a p p i o x i m a t i o na l g o r i t h m 第v 页 曼堕型兰茎查查兰堡塑兰堕兰竺笙苎图索引图2 - 1 简单测量和灵活测量2 4 图3 1 网络拓扑实例3 3 图3 2 节点s 的路由树3 3图3 - 3 节点t 的路由树3 3 图3-4节点s测量路由树上的所有链路34 图3 - 5 节点r 测量剩下的链路3 3 图3 - 6 节点t 测量路由树上的所有链路3 4 图3 7 节点j 测量剩下的链路3 4 图3 - 8 节点5 测量路由树上的所有链路3 4 图3 - 9 节点r 测量剩下的链路3 4 图3 1 0 根节点，和节点m ，的路由树3 8 图3 - 11 三个测量分配算法得到测量代价4 3 图4 - 1 顶点覆盖和弱顶点覆盖实例4 7 图4 - 2 构造弱顶点覆盖的实例4 8 图4 - 3 考察项点k 、和v 。：的关系4 9 图4 4 在图中回避禁点5 4 图5 - 1 两层监测结构5 5 图5 - 2 三层监测结构5 6 图5 - 3 构造图g = ( 矿：e ，一5 9 图5 - 4 任意两点间最短距离的分布6 1 图5 - 5 任意两点间最短距离的概率分布6 l 图5 - 6 不同网络不同延迟约束值用贪婪算法得到的收集站数量6 2 图5 7 不同网络中最短距离的平均值6 3 图7 1 仿真单跳网络拓扑结构8 1 图7 - 2 通过探测包获得的排队延迟8 2 图7 - 3 排队延迟的概率分布p r ( x n ) 8 3 图7 4 排队延迟的概率分布p r ( x d ) ( 对数刻度) 一8 3 图7 - 5 仿真多跳网络拓扑结构8 4 图7 - 6 连接群6 的延迟分布函数8 5 图7 7 连接社l1 的延迟分布函数8 6 第i 页 里堕型兰垫查查兰堑茎生堕兰堡堡苎 表索引 表3 1 不同网络拓扑中测量分配算法得到的测量代价4 2 表4 1 利用三个算法得到的阿管代理数量比较错误i 未定义书签。 表7 1 单跳拓扑仿真数据源参数配置8 2 表7 2 各种测量方法得到的平均延迟8 4 表7 ；i 仿真数据源参数配置8 5 第i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢瓤 学位论文题目 学位论文作者 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阕；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：基王圭邈垄越邈型量曲圆鳌型：星筮盔! 搓型塑笠洼盟巍 学位论文作者签名 作者指导教师签名 日凝：瑚 年f 。a 8b 日期：o 耐卑f o 月肛 里堕型兰垫查查主堕茎竺堕主垡兰茎 第1 章绪论 随着i n t e m e t 应用的急剧增长，越来越多的网络应用程序需要了解网络延迟、 带宽、吞吐率等网络性能参数，以支持可区分的服务【1 n i d 。这些及时的网络性能 数据对于许多网管业务，如主动式和被动式的资源管理、流量工程以及端到端的 服务质量保证，显得尤为重要【4 j i 纠i o j 。现代的网络管理系统注重于服务级、应用级 的管理，网络测量的频率会越来越快，需求的网络性能数据也会越来越多。因此 许多研究者都在开展网络测量技术和网络测量模型的研究工作。 1 1 研究背景和意义 本课题的研究计划来源于国家自然科学基金项目6 0 3 7 3 0 2 3 ：“i p 网络q o s 参 数测量的模型、算法及其分析”。 1 1 1 网络发展面临的挑战 网络技术的迅猛发展，特别是基于t c p i p 协议的国际互联网( i n t e m e t ) 的广 泛应用，深刻地改交了人们工作、学习和生活的方式。网络从信息传输的基础设 施已逐步演变成为人类社会的基础设施。网络新应用不断涌现，网络的异构性与 复杂性不断提高，管理和控制大型网络变得越来越困难。尽管网络基础设施的建 设取得了长足的进步，但现有的网络服务和服务质量与用户的需求和期望仍然存 在着较大的差距【，j 。 根据第十六次中国互联网络发展状况统计所作的调查，截止到2 0 0 5 年6 月3 0 日，我国上网用户总人数达到了1 0 3 0 0 万人，上网人数仅次于美国，位居世 界第二。国际出口带宽的总量已经达到8 2 6 1 7 m b p s ，网络容量也成倍增加。网络 基础设施取得飞跃的同时，网络总体性能却没有得到大幅度提高，用户对网络使 用的总体满意程度仅为4 0 3 ，对网络速度的满意程度更是只有3 7 8 t 8 1 。 i n t e r n e t 对信息化的普及和发展起到了巨大的推动作用，但是因为i n t e m e t 缺 乏一个正常盈利的商业模式，网络缺乏有效的管理和运营手段，面i 临服务质量、 信息安全和网络管理等多方面的问题，尤其是无法有效支持实时业务已成为限制 其发展的最大障碍。i p 网络发展面临如下几个方面的挑战： ( 1 ) i p 网络的服务质量问题 随着网络设备技术上的快速发展、路由器性能的极大提高、以及密集波分多 路( d e n s ew 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 ) 技术的大量商用，信息的传输成本大 为降低。i n t e r n e t 上的业务发展相对较慢，使得网络处于相对轻载状态，因此可以 在i n t e m e t 上开展丰富的数据、语音、视频等增值业务和实时服务。然而如何调配 这些丰富的网络资源，以满足不同业务对网络资源的需求，从而达到不同业务各 第1 页 望堕型兰垫查查兰堑茎竺堕主篁丝苎 自的服务质量要求成为i p 网络发展的难题。 i m e m c t 缺省地为每个i p 数据包提供“尽力而为”的服务。在这种服务模型下， 所有的业务流公平地竞争网络资源，路由器对所有i p 数据包都采用先来先服务 ( f i r s tc o m ef i r s ts e r v i c e ) 的处理方式。虽然路由器等网络设备尽最大的努力将i p 数据包传送到目的地，但无法对数据包传递的可靠性和时效性提供足够的保障。 随着远程教学、视频会议、视频点播等大量服务质量( q u m i t yo f s e r v i c e q o s ) 敏 感应用的出现，“尽力而为”的服务方式已不能满足网络应用对网络有效带宽、延 迟、延迟抖动等q o s 指标的要求。由于i n t e r n e t 承载着越来越多的服务质量敏感的 业务和应用，i s p ( i n t e m e ts e r v i c ep r o v i d e r ) 也需要提供q o s 保证机制以开展新的 增值业务。如何在i n t e m e t 上提供q o s 保证已成为当前网络研究的重要内容。 ( 2 1i p 网络的安全问题 虽然同样基于统计复用的分组交换技术，但是相对x 2 5 、帧中继( f r a m er e l a y ) 和a t m 网络而言，i p 网络的安全性要差很多。这是因为i p 网络采用非面向连接 的工作方式，而x 2 5 、帧中继和a t m 均采用了面向连接的技术。 面向连接的工作方式在开展端到端应用前，必须通过信令建立端到端的连接， 然后进行通信；而非面向连接的工作方式在开展端到端应用前，无须通过信令来 建立连接，直接就进行通信。因此确保端到端通信的安全是确保数据交换安全的 关键。 i p 网络的开放性与终端的智能化使得i p 网络面临着前所未有的安全威胁，因 此i m e m e t 在承载重要的政治、军事和商业应用时存在很大的安全隐患。长期以来 i n t e m e t 的无序发展和缺乏有效管理，导致了i n t e m e t 网络管理机制和设计理念忽 略了i n t e m e t 的安全性和可信任性。i p 网络运营者必须采用一切技术措施来确保网 络的安全性和可信任性，必须对网络的管理和安全负责。 ( 3 ) i p 网络的可管理问题 传统的网络管理与性能监控主要是利用简单网络管理协议( s i m p l en e t w o r k m a n a g e m e mp r o t o c o l s n m p ) 来实现的l l 。其原理是通过读取网络设备中管理信 息库( m a n a g e m e n ti n f o r m a t i o nb a s e m i b ) 的信息，实现对网络性能指标的计算 或网络状态的推测。基于s n m p 的网络管理与监控所能提供的反映网络运行状况 的信息量有限，不能满足对不同粒度网络性能信息的需求。此外，基于s n m p 的 网络管理涉及到对m i b 中信息进行访问的权限管理问题，广泛的部署s n m p 管理 系统会对网络的安全性造成潜在的威胁；另一方面，周期轮询m i b 会降低网络设 备、特别是核心路由设备对数据包的处理速度，从而对网络的整体性能造成负面 影响。因此必须寻求新的网络管理与性能评价的手段，有效地解决用户的接入管 理、网络的资源管理、网络的安全管理、对网络节点及业务节点的监测、对业务 进程的监视、完备的运行维护体系等等这一系列关系网络运营和网络管理的技术 难题。 1 1 2 网络测量研究的意义 近年来，由于互联网的快速发展与新应用的不断出现，网络己从单纯的数据 第2 页 里堕型兰垫查查兰里墨竺堕兰垡笙苎 传输发展到同时支持多种信息类型的传输，网络流量与网络行为均发生了极大的 变化。流量模型从基于泊松分布转变为具有自相似的特性】【”】，动摇了互联网的 传统理论基础。对网络协议的分布、网络流量特征、用户与网络行为缺乏准确的 理解与精确的描述，严重影响了对网络资源的有效利用与网络自身的发展。网络 测量技术是对网络进行认识与深入研究的重要手段，同时也是实施协议工程、进 行网络管理与优化设计的重要前提条件【7 j 。 针对当前i p 网络发展面临的挑战，进行网络测量研究的意义主要体现在： ( 1 ) 网络测量可以为i m e m e t 流量工程和网络行为学的研究提供基础辅助依据 及验证平台，为开发高性能网络设备和设计网络协议提供理论基础。 大量新型的网络应用和增值业务不断涌现，使得网络流量特征日益复杂。不 同应用具有不同的流量特征与行为特征，仅仅利用数学仿真、经典排队论模型进 行建模和分析是远远不够的。基于测量的网络建模与分析是对理论模型进行验证 与修正的重要基准【7 。在互联网理论研究的初期，研究者均借鉴和采用p o i s s o n 模 型或m a r k o v 模型来进行流量特征分析。但大量的测量结果表明，实际的互联网流 量特征与p o i s s o n 模型有较大差距【1 2 】【1 8 1 1 ”1 。 1 9 9 3 年w i l l e l e l a n d 等研究者发现以太网流量具有自相似( s e l f - s i m i l a r ) 特 征1 1 “，这一重大发现不仅成功解释了以往在网络设备缓存大小设计中，采用排队 模型而经常出现缓存溢出的现象，也为分组交换方式下进行网络流量建模与分析 指明了新的方向p j 。继这以后，研究者陆续发现自相似特性是互联网中普遍存在的 现象l l 卅1 1 ，在w w w 流量和实验仿真的分析中也验证了网络流量自相似的特征。 因此，利用网络测量及其分析的结论，不仅可以更加准确的仿真模拟i n t e r n e t 环境，进行网络设备设计、优化，协议开发与评价，也为i n t e m e t 流量工程( t r 蛹c e n g i n e e r i n g ) 和网络行为学( n e t w o r kb e h a v i o r ) 的研究提供重要理论依据和准确 的验证平台m 。 ( 2 ) 网络测量是开展q o s 敏感应用，提供q o s 保证的前提条件。 随着i m e m e t 的发展，出现了远程教学、视频会议、视频点播等大量q o s 敏感 的网络应用。网络应用对网络传输服务提出了一组可度量的要求，主要包括带宽、 端到端延迟、丢包率、抖动等【9 j 。不同的网络应用对q o s 有着不同需求，如文件 传输服务要求低丢包率、高带宽和高吞吐量；实时多媒体业务则需要低延迟和尽 量小的抖动。 为了向用户提供有效的端到端( e n d t o e n d ) 服务质量保证，网络应用必须得 到实时的网络性能来评估当前网络对应用的支持程度。如在基于综合服务资源预 留协议( i n t s e r v r s v p ) 模型中，文献l l 副1 1 4 j 通过测量链路的利用率以及单个业务 流( p e r _ f l o wt r a f f i c ) 和聚集业务流( a g g r e g a t e - f l o wt r a f f i c ) 的流量模式，利用接 入许可控制算法比较当前链路的利用率与预定义的利用率阀值，以决定是否接纳 该业务。因此，利用网络测量技术，特别是精确的实时在线网络性能测量可以准 确地反映网络的运行状况，为实施自适应q o s 策略提供依据，保证应用的性能【刀。 ( 3 ) 网络测量是诊断网络运行状况、进行网络管理的重要技术手段。 通过网络测量，可以实时获取网络延迟、带宽、丢包率和抖动等网络性能参 数，从而及时了解网络运行状况，获取网络的性能视图，实旅有效的网络管理。 第3 页 国防科学技术大学研究生院学位论文 通过网络测量，可以检测网络拥塞状况、定位网络性能瓶颈，为网络资源优化提 供依据。 基于对网络性能参数的长期测量和统计分析，可以合理的分配网络资源和优 化网络结构能，提高资源的利用效率。如对网络拓扑结构与路由行为的测量，可 以发现并改正路由循环等病态路由状况，为网络选路制定相应的策略、确定网络 发生故障后的网络拓扑与资源的自组织方式i l “。 ( 4 ) 网络测量是保障网络安全，防范大规模网络攻击的重要方法。 面对日益严重的网络安全威胁，利用大规模网络测量可以对网络流量与网络 拓扑的变化进行分析，对网络在异常环境下的可生存性做出分析与评估，为防范 大规模网络攻击提供预警手段，使国家对网络管理更具宏观控制力f j 。 d a v i dm o o r e 在2 0 0 1 年7 月通过网络测量，记录了超过3 5 9 0 0 0 台计算机遭受 红色代码病毒时病毒传播及扩散的蔓延实况【l 6 】。s t e v e nb r a n i g a n 等则测量了在 1 9 9 9 年3 月至7 月科索沃战争期间，南斯拉夫的网络链路因战争影响不断消失与 逐渐恢复的情况。这些研究工作给网络安全、信息攻防等方面的研究带来了深 远的影响，科学的利用网络测量手段也成为保障网络安全、防范大规模网络攻击 的重要方法。 1 2 1 网络测量的对象 1 2 网络测量研究概述 网络测量的对象主要包括链路或端到端延迟、带宽、丢包率、吞吐量、突发 频率和网络拓扑，并开展网络可靠性、稳定性、可达性等方面的分析等1 1 5 1 1 2 0 1 。网 络测量的一类属性是网络固有的，如网络的拓扑、连接容量、延迟；另一类属性 反映网络的当前状态，如排队延迟、连接可用性、路由的动态性。 1 2 1 1 延迟( l a t e n c y ) 网络延迟由传播延迟( p r o p a g a t i o nd e l a y ) 、传输延迟( t r a n s m i s s i o nd e l a y ) 、排 队延迟( q u e u e i n gd e l a y ) 、介质访问延迟( m e d i aa c c e s sd e l a y ) 和服务器响应时间 ( s e r v e rr e s p o n s et i m e ) 等几个部分组成。传播延迟是电信号在物理链路上传播所 需要的时间，通常为每公里5 微秒。传输延迟是数据包从队列中到完全发送到输 出链路上所花费的时间，通常为微秒量级。传输延迟由数据包的大小和链路带宽 所决定，数据包越大，传输延迟越大，因为主干带宽一般比较大，所以传输延迟 的差异主要体现在低带宽链路上。 排队延迟是指数据包在路由器中排队所造成的延迟，通常为微秒到毫秒量级 之间。它与路由器本身的特性、链路拥塞状况等相关。服务响应时间( s e r v e r r e s p o n s e t i m e ) 指的是服务器接收到数据包并生成响应数据包所花费的时间。路由器处理一 个输入数据包的处理延迟( p r o c e s s i n gd e l a y ) 一般为几微秒到几十微秒，相对于端 到端延迟而言可以忽略不计，所以一般不考虑处理延迟。介质访问延迟与网络媒 第4 页 国防科学技术大学研究生院学位论文 体的特性和网络负载有关，轻负载时介质访问延迟可以忽略不计，对于点到点的 全双工链路而言，介质访问延迟为零。 传播延迟和传输延迟属于静态延迟，它们反映了端到端延迟的不变部分。介 质访问延迟和排队延迟属于动态延迟，它们反映了端到端延迟的可变部分。 1 2 1 2 带宽( b a n d w i d t h ) 网络带宽的测量包括链路带宽( 1 i n kb a n d w i d t h ) 、瓶颈带宽( b o t t l e n e c k b a n d w i d t h ) 和可用带宽( a v a i l a b l eb a n d w i d t h ) 。链路带宽是链路的最大吞吐量。瓶 颈带宽是指没有背景流量存在时，一条网络路径所能提供的最大吞吐量。可用带 宽是指存在背景流量的情况下，一条网络路径所能提供给某个业务的最大吞吐量。 链路带宽是静态的，对定的链路而言链路带宽是恒定的。瓶颈带宽取决于 网络路径中链路带宽最小的那条链路，可用带宽则受到背景流量的影响。 常用的带宽测量方法有基于变长包序列( v a r i a b l ep a c k e ts i z e ) 模型的带宽测 量方法、基于包分散( p a c k e td i s p e r s i o n ) 模型的带宽测量方法、基于s l o p s ( s e l f - l o a d i n gp e r i o d i cs t r e a m s ) 的测量方法、基于网络流量模型的测量方法等 1 3 6 1 1 3 7 。 基于变长包序列模型的测量方法常用来测量瓶颈带宽，主要的测量工具有 p a t h c h a r 【1 ” 、c l i n k 【2 0 】、p c h a r m l 等。基于变长包序列模型的带宽测量方法包括包 对( p a c k e t p a i r ) 测量方法和包列( p a i rt r a i n ) 测量方法：包对测量方法主要用来 测量瓶颈带宽，测量工具包括b p r o b e 1 2 6 1 、p a t h r a t e 1 3 8 l 、t o p p l l 蚓等：包列测量方 法主要用来测量可用带宽，测量工具有c p r o b e ”6 】等。基于s l o p s 的测量方法将延 迟与可用带宽紧密结合，通过速率调整来推断可用带宽，主要测量工具有 p a t h l o a d 1 3 9 等。d e l p h i 1 4 0 是一个基于网络流量模型的测量工具，它通过建立流量 模型来估算网络路径中的背景流量和可用带宽。 1 2 1 3 丢包率( p a c k e tl o s s ) 基于存储转发机制的i n t e m e t 在网络层为每个i p 数据包提供“尽力而为 ( b e s t - e f f o r t ) ”的服务。路由器尽力转发每一个数据包，但是可能会根据路由器 的当前状况丢弃一些数据包。“尽力而为”的转发报文是i p 协议的一个重要的设计 特征，因此需要可靠包传输的i n t e m e t 服务就必须检测报文丢失并且重新发送丢失 的报文包。t c p 协议在应用层提供这种重发数据报文的服务，如w e b 浏览器。 数据包丢失主要是因为路由器队列满了以后无法再处理新到达的数据报文， 而将数据包丢弃引起的。其它的一些网络出错可能会导致包丢失或者包损坏，但 并不是很普遍。 网络丢包率是在指定时间间隔内从客户端到服务器传输的数据包丢失的比 率。丢包率太高会导致一些网络应用无法使用。 第5 页 里堕型主垫查奎兰堡茎生堕兰堡堡苎 1 2 1 4 吞吐率( t h r o u g h p u t ) “吞吐率”是数据报文通过网络的速率，通常表示为每秒比特( b i t sp e r s e c o n d ) ，每秒字节( b y t e sp e rs e c o n d ) 或者每秒包( p a c k e t sp e rs e c o n d ) 。吞吐 率一般指的是数据流传输过程中总的传输速率，但是对于一些w e b 业务和i p 电话 等网络应用，也可以定义一个时间段的吞吐率。 计算在一个时间段内传