（信号与信息处理专业论文）基于网络层析的网络性能测量与推测方法研究.pdf

摘要摘要当今i n t e r n e t 是一个庞大的分布式网络，随着网络的不断扩大，网络的业务种类和复杂性也迅速增长。如何了解当前网络状态和性能，以便更合理、有效的管理网络，成为网络管理者和网络服务供应商都非常关注的问题。由于网络不断朝异构化、不协作特征发展，使得网络性能测量工作的研究极具挑战性。现有的许多测量工具都需要网络内部节点之间的协作，这会影响真实的网络业务量，并且会引发安全问题。因此，近年来人们提出了一种新的网络性能测量与推测技术，称为“网络断层分析”。该技术是通过网络端到端测量，对内部链路性能进行推测估计，对网络性能测量工作来说有重要研究意义。本文的主要工作以链路丢包率和时延的测量与推测为重点。首先介绍了近年来网络测量和推测技术的现状，然后详细阐述了网络层析技术中基于组播测量的链路丢包率推测算法一一直接推导法( d i r e e t - m l e ) 和期望最大化算法( e m m l e ) 通过o p n e t 和m a 廿a b 仿真建模，对比了主动测量中使用直接推导法和e m 算法推测链路丢包率的准确性、收敛性等特征，仿真证明e m m l e 算法优于d i r e c t - m l e算法。由于并非所有的网络都支持组播，且路由器处理组播数据包与单播数据包的方式也明显不同。为了避免组播的局限性，普遍采用背靠背单播数据包对进行丢包性能的测量推测。本文在基于单播测量的基础上提出了一种具有动态搜索间隔的基于t c p 监测的被动测量机制，被动测量机制具有不向网络注入探测包，不会影响实际网络流量的特性，可用于高负载的大规模网络性能测量。在被动测量仿真中，对比了固定搜索间隔和动态搜索间隔对估计值的影响，实验证明，采用动态的搜索时间间隔比固定搜索间隔得到的估计值更逼近真实链路丢包率。另外本文还研究了网络层析技术用于时延测量估计的方法，分别对基于累积生成函数和有限高斯混合密度函数的时延推测算法进行了分析。并通过m a t l a b 仿真证明了有限高斯混合模型中e m 算法的有效性。关键词：网络层析，丢包率，时延，网络测量，期望最大化算法a b s t f a c ta b s t i - a c tt o d a y si n t e r a c ti sam a s s i v e d i s t r i b u t e dn e t w o r kw h i c hc o n t i n u e st oe x p l o d ei ns i z ea sa l lk i n d so ft r a f f i ce x p a n d e dr a p i d l y h o wt og e tt h en e t w o r kp e r f o r m a n c e0 1 1t h ee x i s t i n gi n f i a s t m c t u r ea n dm a n a g en e t w o r km o r er e a s o n a b l eo rm o r ee f f e c t i v ei sac h a l l e n g et a s k e s p e c i a l l y i ti se s s e n t i a lf o rt h en e t w o r km a n a g e r sa n di s p t h eh e t e r o g e n e o u sa n dn o - c o r p o r a t i v es t r u c t u r eo ft h ei n t e r n e tr e n d e r st h et a s k ss u c ha sn e t w o r kb e h a v i o rm e a s u r e m e n te x t r e m e l yc h a l l e n g i n g m a n ym e a s u r e m e n tt o o l sr e q u i r et h ec o o p e r a t i o nw i t hn e t w o r kn o d e s ；t h e ym a ya f f e c tt h en e t w o r kr e a lt r a f f i c sa n dc a u s et h es e c u r i t yp r o m e m s f o rt h e s er e a s o n ，ap r o m i s i n gt e c h n i q u en a m e d “n e t w o r kt o m o g r a p h y ”i se m e r g i n gi nr e c e n ty e a r s i ti n f e r st h en e t w o r ki n t e r n a lp e r f o r m a n c eb ye n d t o e n dm e a s u r e m e n t s , a n dm a k e sag o o dp e r f o r m a n c ei nn e t w o r kf a u l td e t e c t i o n i nt h i sp a p e r , w ef i r s ti n t r o d u c et h er e c e n tr e s e a r c hi nn e t w o r kt o m o g r a p h y , a n dt h e nr e v i e wt h em e a s u r e m e n ta n di n f e r e n c ea l g o r i t h mw ec o u l du s ed i r e c t - m l ea n de m m l e b e c a u s em u l t i c a s tp r o t o c o l sa r cn o ts u p p o r t e db ys i g n i f i c a n tp o r t i o no fi n t e m e ta n dt h er o u t e r st r e a td i f f e r e n t l yb e t w e e nm u l t i c a s tp a c k e t sa n du n i c a s tp a c k e t s i ti sp o p u l a rt ou s eu n i c a s tb a c k - t o - b a c kp a i r sa st h ep r o b e st oa v o i dt h o s ep r o b l e m si nm u l t i c a s tn e t w o r k i nt h i sp a p e r , w ep r o p o s ean e wm e 鹤u r e m e n tb a s e do nt c pm o n i t o r i n gt og e tt h ep a c k e tp a i r s t h ep a s s i v em e a s u r e m e n td o e sn o ti n f l u e n c et h er e a ln e t w o r kf l o w s ，s oi ti su s e f u li nh e a v yl o a dn e t w o r km e a s u r e m e n t i nt h i sp a p e r , w eu s et h eo p n e ta n dm a n a bm o d e ls i m u l a t i o nt oa n a l y z et h ei n f e r e n c ea l g o r i t h m s w ec o m p a r et h ed i f f e r e n c eo na c c u r a c ya n dc o n v e r g e n c ec h a r a c t e r i s t i co fd i r e c ti n f e r e n c ea l g o r i t h ma n de ma l g o r i t h mi na c t i v em e a s u r e m e n t s s i m u l a t i o nr e s u l t ss h o wt h a te ma l g o r i t h mh a sb e t t e rc o n v e r g e n c ea n dc a ni n f e rt h ei n t e r n a lp e r f o r m a n c ee f f e c t i v e l y w ea l s oa n a l y z et h es e a r c h i n gs p a c eb e t w e e nt w op a c k e tp a i r sw h i c hi n f l u e n c e si n f e r e n c ea l g o r i t h m sa c c u r a c y t h ec o n c l u s i o ns h o w st h a td y n a m i cs e a r c h i n gs p a c ei sb e t t e rt h a nf i x e ds e a r c h i n gs p a c e a b s t r a c ta tl a s t ，w ei n t r o d u c et h ed e l a yi n f e r e n c ei nn e t w o r kt o m o g r a p h y w ed i s c u s st h ec g fm o d e la n dm f m mm e t h o d si nd e l a yi n f e r e n c er e s p e c t i v e l y w i t hm a t l a bs i m u l a t i o n ，i ts h o w st h a te ma l g o r i t h mi nm f m mm o d e li se f f e c t i v e l y ，k e y w o r d s ：n e 咐o r kt o m o g r a p h y ，p a c k e tl o s sr a t e ，d e l a y ，n e t w o r km e a s u r e m e n t ，e m玎i主要符号表主要符号表r 一，工)由v 个节点和l 条链路构成的逻辑组播树d ( j )节点j 的孩子节点集合，例如，d ( j ) 一 七y ：( j ，k ) e l f ( j )节点j 的双亲节点集合，例如，d ( j ) - k v ： ，j ) ，”( j ) 一f ( f ”1 ( j ) )如果对整数n o ，k 一，“( ，) 则j 是节点k 的子孙节点rc 矿叶节点的集合表示子孙节点u - y o 非根节点0 集合吼【0 ，1 】到ke v 节点为止的链路上探测包没有丢失的概率x 一瓴) 。探针的所经历的路由矩阵，其中每个五取值为 o ，1 )己假设链路概率为口一 。) 。，测量值( x k k ，的概率分布q 一 o ，妒所有测量数据的空间p ，a ) p o 僻一z )混合概率密度函数k k k 是k 的子孙节点，对k ，k 矿，k _ k r 0 ) t ) ，工 ) )以节点k 为根的子树尺) - r f l v ( k )以节点k 为根的予树的节点集合 一只i n 0 ) 】探针至少到达一个接收方的概率展- p t r ( k ) l x ，( i ) 一1 】探针到达父节点，o ) 的条件下，至少到达一个接收节点的概率v i独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。日期：y 田年月p 日关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后应遵守此规定)龆帛旆导师签名滗乏1日期：湖年朔订日第一章引言1 1 选题背景第一章引言近年来，i n t e m e t 发展极为迅速，随着网络规模和网络技术的迅猛发展，通信网络、计算机网络和有线电视网的逐渐融合，下一代网络是基于i p 技术的综合语音、数据、图像、视频的多媒体业务网络，能够为不同的业务类型提供优良的服务、保证不同级别的服务质量并提供宽带接入能力。网络已经从最初只为少数用户服务集中控制的小型网络发展成为一个庞大、复杂、开放的分布式网络，如何进行高效的网络管理，保障各种业务的顺利运行是每个运营商迫切需要解决的问题。由于i n t e m e t 最初不像是电信网那样是提供商业服务而有规则地组织起来的，其体系结构也由当初a p r a n e t 基于集中控制的方式演化成由i s p ( i n t e m e t s e r v i c ep r o v i d e r ) 分别运营管理的分散自治系统，网络的异构性和复杂性的不断提高。诸如动态路由、优化服务配置等网络行为变得难以控制，系统级网络的可控性和可管理性越来越困难，网络性能的可知性也变得越来越复杂。这就给i s p 对网络的管理、网络流量特征与协议的分析带来了一系列的困难；网络行为建模分析明显滞后于网络基础设施的建设和网络应用的发展，严重影响了对网络资源的有效利用与网络自身的发展。因此，对网络的拓扑结构和网络行为进行深入的了解和分析，发现网络瓶颈、优化网络配置和提高网络性能进行网络管理具有重要意义。网络测量技术是对网络进行认识与深入研究的重要手段，同时也是实施协议工程、进行网络管理与优化设计的重要前提条件。利用大规模网络测量可以对网络流量和网络拓扑的变化进行分析，对网络在异常环境下的可生存性做出分析和评估。因此，利用网络性能测量获得反映网络行为的第一手资料，是保证网络正常运行与关键业务完成的重要手段之一，是建立高效、稳定、安全、可靠、可控网络需要研究的重点。目前的网络性能测量工具主要分为三类：第一类是面向网络节点的，通过使用s n m p 或r m o n 来收集网络节点信息，进行分析和统计网络性能。这类工具首先都需要在每个网络节点上放置s n m p 或r m o n 代理，这使网络性能测量不仅代价昂贵而且不具有可扩展性；第二类是面向链路的，通过使用i c m p 探测包进行电子科技大学硕士学位论文链路检测，具有需要存储转发路由和无防火墙存在的假设前提，以及需要路由器之间的协作的特点，同时服务器和路由器对统计数据的收集和传递也会消耗大量带宽，增加网络负载。第三类是面向端到端路径的，由于具有不依赖路由器协作、开销少等特点，近年来成为研究人员关注的热点。1 2 国内外的研究现状1 2 1 网络测量的研究现状由于i n t e r a c t 的庞大和复杂，采用单一测量工具在少数工作点进行测量已经无法满足测量需求了，从9 0 年代开始，国外已经有研究机构开始着手测量基础设施方面的研究。i e t f 也成立了口性能指标工作组( i p p m w g ) 对i p 网络性能测量框架、指标定义与指标测量方法进行研究。迄今为止，主要的测量基础设施有：1 美国国家科学基金n s f 和d a r p a 资助的国家 n t e r n e t 测量基础框架n i m i ( n a t i o n a li n t e m e tm e a s u r e m e n ti n f r a s t r u c t u r e ) 项目【1 】。其目标是要建立一个全球化的、分布式、大规模的i n t e r n e t 测量体系，并已经设计出了轻负载、可升级、可动态配置、具有安全验证的测量探针测量各种性能参数；2 1 9 9 7 年，成立了依托于美国加卅i 大学圣地亚哥分校超级计算中一t ：, ( s a nd i e g os u p e r c o m p u t i n gc e n t e r ，s d s c ) 的互联网数据分析合作组织( c o o p e r a t i v ea s s o c i a t i o nf o ri n t e r n e td a t aa n a l y s i s ，c 肖d d a ) 【2 】，对网络测量的相关理论和方法展开系统研究。提出并实现了c o r a l 和s k i t t e r ，c o r a l 用来测量高速链路的工作流特性，s k i t t e r 通过几个源向其他的许多地址空间主动发送探测包来测得路径和性能；3 由斯坦福线性加速器中心( s t a n f o r dl i n e a ra c c e l e r a t o rc e n t e r ，s l a c ) 发起了端到端性能监控项目p i n g e r ( p i n ge n d t o - e n dr e p o r t i n g ) ，采用主动测量方式发送i c m p 数据包，用p i n g 指令来测量l 盯r 、丢包率等，进而推算出系统性能；4 由b e r k e l e y 大学和i b m 开放的s p a n d ( s h a r e dp a s s i v en e t w o r kd i s c o v e r y )项目【3 】，是一个被动共享的测量，通过发送u d p 、t c p 分组让客户机向服务器汇报网络性能，同时在网关处还加了一个性能捕获主机辅助测量；5 网络应用研究国家实验室( t h en a t i o n a ll a b o r a t o r yf o ra p p l i e dn e m o r kr e s e a r c h ，n i a n a ) 项目组开发的网络分析架构( n e t w o r ka n a l y s i si n f r a s t r u c t u r e )2第一章引言 4 】，目的是通过对原始数据的收集和公布，对网络测量进行可视化等研究和分析。n l a n r 主要包括两个子项目，一个是基于主动测量的a m p ，另一个是基于被动测量的p m a 。a m p 主要测量i m 、丢包率、拓扑和流量。p m a 主要进行基于包头追踪的分析。此外，还有基于控制信息监视的数据分析，主要来自于参与项目的服务器的s n m p 信息和基于b o p 数据的分析；6 s u r v e y o r 项目 5 】是用来建立一个用于长期测量广域范围内网络端到端单向时延、单向丢包率和路由信息的架构，它采用i p p m 已经定义好的标准测量方法，利用主动测量的方式得到拓扑和性能数据；7 r i p e r i s ( r e s e a r c hi pe u r o p e - r o u t i n gi n f o r m a t i o l ls e r v i c e ) 项目的主要测量内容是以控制信息监视的方式来收集拓扑和路由数据，提供i n t e r n c t 上实时的b g p 路由信息；国内在网络测量方面的研究正处于起步阶段，国防科技大学、西安交通大学、西南交通大学等单位在基于i c m p 协议的i p 拓扑测量方面的技术比较成熟 6 1 3 】。哈尔滨工业大学计算机科学与二强累计算机信息内容安全国家重点实验室实现了大规模网络拓扑测量的原型系统，能够针对大规模网络进行路由m 拓扑结构的自动发现，并进行可视化显示 1 2 】。1 2 2 网络推测的研究现状i n t e m e t 分布化、异构化、不协作的特性使传统网络测量方法由于需要网络内部的协作测量具有一定局限性。为了弥补这种传统网络测量方法的不足，研究人员将医学、地震学、地质勘探等领域成功应用的成熟理论和方法应用于网络通信领域，衍生出了网络断层分析成像( n e t w o r kt o m o g r a p h y ) 亚论 8 】，简称网络层析。网络层析技术一种基于网络端到端( e n d - t o e n d ，e 2 e ) 的性能测量统计，对无法直接观测的网络内部性能进行推测的方法。具有不依赖路由器协作、开销少的特点，保证了用户隐私和信息安全，减少了测量信息的传输 9 】 】o 】【1 l 】。目前网络层析的研究重点主要集中在时延和丢包率推测估计上，主要以a t & t和马萨诸塞州立大学的m i n c ( m u l t i c a s t - b a s e di n f e r e n c eo fn e t w o r k i n t e r n a lc h a r a c t e r i s t i c s ) 项目【1 4 】，以及莱斯大学研究的单播网络层析项目为主【2 0 】。m i n c 项目的c a c e r e s 首先提出了采用组播技术引入丢包相关性【1 6 ，在拓扑已知的情况下进行丢包率推测的算法，随后n g d u f f i e l d 、l op r e s f i 等人又提出了基于组播端到端测量的时延分布推测算法 2 6 】 2 7 】；同时还提出了在未知拓扑情况3电子科技大学硕士学位论文下的拓扑重构算法 1 7 】。莱斯大学的c o a t e s 、n o w a k 等人在组播的基础上，研究并实现了单播网络层析技术，提出了采用单播数据包对近似组播的思想进行丢包率推测 2 1 】。1 3 论文的研究内容和结构安排网络层析技术的主要测量推测对象包括丢包率、时延和带宽。本文主要研究基于网络层析技术的网络丢包率和时延的测量与推测方法，通过主动测量或被动监测端到端路径丢包率或时延等性能指标，对网络内部链路丢包率或时延进行推测。对链路丢包率和时延测量方法及推测算法进行比较分析，并提出了一种新的测量机制，通过o p n e t 和m a t l a b 进行仿真验证。本文的结构和内容安排如下：第一章概述了论文选题背景和当今网络测量与推测技术的现状，阐述了网络层析技术研究的意义。第二章主要介绍网络性能测量的基本概念，分别介绍了网络性能测量的特点和分类。接着阐述了网络性能推测技术的原理，以及网络层析技术的关键算法。第三章详细讨论了基于网络层析的网络丢包率测量和推测算法，即网络丢包层析技术。首先讨论了基于组播网络主动测量的丢包率推测方法；接着讨论了基于单播网络主动和被动测量的丢包率推测方法，并对基于被动测量的测量机制和算法提出了改进；然后讨论了丢包层析算法在多点测量中的应用，并提出了改进的伪似然估计法进行丢包推测；最后通过仿真分析，对丢包层析技术进行了验证。第四章主要介绍了基于网络层析的网络时延测量和推测所采用的基本算法，即网络时延层析技术。详细介绍了采用累积生成函数c g f 和有限高斯混合模型对链路时延分布进行推测的方法，通过仿真分析了算法的可行性。第五章是对全文的总结并指出了进一步研究的方向。4第二章网络性能测晕和推测技术第二章网络性能测量和推测技术网络测量是对网络进行认识与深入研究的重要手段，通过大规模网络测量了解网络运行状况，获取网络丢包率、排队时延和瓶颈带宽等性能参数，可以对网络流量和网络拓扑的变化进行分析，在网络拥塞检测和网络性能瓶颈定位中扮演重要的角色。对网络性能指标的长期测量与统计分析，能够对网络进行合理的资源配置和使用，是科学规划与建设网络、高效管理网络的基础。2 1 网络性能测量的基本概念网络测量就是指遵照一定的方法和技术，利用软件和硬件工具来测试或验证表征网络性能的指标的一系列活动的总和，它的目标是将i n t e m e t 网络拓扑、带宽等性能映射成随时间空间变化的函数。2 1 1 网络测量的基本要素测量对象：被测量的节点或链路，测量节点、链路或网络的具体特征，如链路的时延、带宽、丢包率；路由器的路由效率、时延、丢包率；w e b 服务器的应答延迟、吞吐率、系统容量、最大稳定链接数目等；测量环境：包括测量点的选取、测量时间的确定、测量设备、通信链路的类型等：测量方法：测量方法是指记录或估计某种特征的技术。针对菜一具体的网络行为指标，应选取合适的测量方法，测量方法至少应满足：稳健性一一被测网络的动态变化不会是测量方法失效可重复性一一同样的网络条件，多次测量结果应一致准确性一一测量经过应能反映网络的真实情况，应有一定的可信度2 1 2 网络测量的性能指标在进行网络测量的过程中，需要定义一系列定量的参数来描述网元、数据链路、端到端路径或整体网络的性能，使用户和运营商对网络所提供的服务能力或5电子科技大学硕士学位论文网络的整体性能有全面、准确的理解。这些经过严格定义的定量参数称为测量指标( m e t r i c s ) 。对应于特定的协议层次，满足某种具体需求的测量指标完备集合称为测量指标体系( m e a s u r e m e n tm e t r i c sa r c h i t e c t u r e ) 。网络性能指标主要用来描述运行中网络的特定性能，i p 网络测量指标框架最初由i e t f 的评测工作组( b e n c h m a r k i n gm e t h o d o l o g yw o r k i n gg r o u p ，b m w g ) 制定，并定义了局域网交换设备、防火墙、a t m 等多种网络互联设备的基准测试方法。指标的定义、测量方法等方面的研究主要由i e t f 的口性能测量工作组制定相关的建议和草案。在b m - w g 的基础上，i p p m ( i pp e r f o r m a n c em e 扛i cw o r k i n gg r o u p ) 定义了网络性能测量的基本框架，并规范了性能指标所必须遵循的标准。已经标准化的指标包括：1 连通性( c o n n e c t i v i t y ) ：连通性是指在某时刻t 或在时间间隔( r ，丁+ a t ) 内，源地址和目的地址间对某种类型数据包的可达性。连通性是描述网络可用性与可靠性最基本的指标，也是网络提供各种上层服务最基本的前提条件。2 单向时延( o n e _ w a yd e l a y ) ：由于路由的不对称性、应用的不对称性造成应用服务对不同方向上时延指标的要求不同，如f t p 或v o d 服务中，应用的数据主要来自于下行的数据流量，单向时延指标可以比较准确地反映出网络应用实际提供的服务水平。3 单向丢包( o n e - w a y p a c k e t l o s s ) ：网络发生拥塞使路由器缓存溢出或数据传输时延过大而导致数据包的丢失。丢包迸一步造成数据包重传，网络负载增大，性能恶化。因此，单向丢包率是描述网络当前负载状况与进行网络性能预测的重要指标。4 时延变化( pp a c k e t d e l a y v a r i a t i o n ，i p d v ) ：时延变化定义为给定网络流中，数据包之间的时延变化程度。i p d v 对v o l p 、网络视频会议、远程医疗等实时交互和流媒体应用具有重要意义。这类应用对服务的基本要求是数据包的定期到达，较大的i p d v 意昧着应用可能出现停顿或中止。此外，i p d v 也是网络负载特征的重要表征。5 往返时延( r o u n d t r i pd e l a y ) ：单向时延指标无疑可以反映网络的运行状况，但是进行单向时延测量时需要端到端系统间分别记录数据包发送和到达时刻、且端系统间必须进行时钟同步。进行往返时延的测量则因测量方法簏单、易部署与便于理解的优点，仍具有广泛应用。这些标准化的网络性能指标主要侧重于对网络中端到端性能的量化分析，这类指标直接反映了终端用户使用网络时可获得的性能。非标准化指标则主要是面6第二章网络性能测量和推测技术向网络的指标，主要有链路利用率( l i n ku t i l i z a t i o n ) 、网络吞吐量( t h r o u g h p u t ) 、流量的突发性f a u r s t i n e s s ) 、网络带宽等。本文中所研究讨论的是网络端到端性能指标。不同网络性能指标彼此之间不是孤立的，而是具有本质的或一定的内在联系。如果网络负载急剧增大，应用层性能则明显下降，同时链路负载的增加也会造成缓存溢出或数据包丢失重传，而数据包的重传则意味着应用层时延的增加。因此，通过对各性能指标问相互影响的因果关系，便于在网络性能分析评价中，发现问题本质，为网络性能的提升提供有价值的指导。2 2 网络测量的特点和分类2 2 1 网络测量的特点互联网规模的位置分散性和业务多样性给性能测量基础设施的建设带来一些难题。位置分散性：测量用户和目标系统可能分布在网络任意一个位置，用户和数据中心之间会跨越多个子网，包括多个采用不同技术的异构网络，即两者之间会有多个网络节点。业务多样性：现在互联网上业务类型成千上万，新应用层出不穷，应用的性能评价指标也呈现出多样性和动态变化，而网络性能测量工作都是围绕性能指标展开的。因此如何能有效对各种业务性能数据进行有效的分析，将决定整个测量系统的可用性以及可扩张性。2 2 2 网络测量的分类由于所关注的问题不同，测量系统的功能会各有侧重，测量的对象不同、方法不同、测量点的位置各异，所以网络测量的分类可以有多种方法2 2 2 1 按照测量的对象不同1 基于流的测量基于流的测量以业务流为基准对网络流量进行测量。测量信息通常包括源地址和目的i p 地址、端口号、协议类型、服务类型、时间戳、计数等。由于流是一个粒度很小的测量对象，一般不可能长时间对所有流进行测量，往往采取采样的方法进行测量。7电子科技大学硕士学位论文2 端到端的测量端到端的性能测量又称为路径级测量，路径可以定义为i p 分组从一个源端节点传送到目的节点的过程中所经过的一系列链路的集合。端到端的路径指标包括：瓶颈带宽、可用带宽、时延、时延抖动、分组丢包率等。3 基于节点链路的测量网络节点是指网络互连设备，包括各协议层的网络连接设备。内部节点可以是路由器、交换机、虚拟节点、代理等，主机视为边缘节点。例如采用s n m p 被动监听的方法，可以在路由器上收集原始数据的有关信息，并记录在m i b 中。这些信息包括发送接收分组的数量、字节量、丢弃分组数量等。网络链路是指连接两个相邻的同层网络节点的物理或逻辑链路。链路级的性能指标包括：链路带宽、带宽利用率、链路时延、丢包率等。2 2 2 2 按照测量方法的不同1 主动测量主动测量向网络主动发送探针，通过探针所携带的信息来推测网络的情况。探针是由源端发送的数据包序列，根据发送数据包的类型，探针可划分为组播探针和单播探针。根据探针结构的不同，又可以分为：单包探针、等长和非等长探针数据包对探针、以及数据包串探针等。主动测量的优点是对测量过程的可控性比较高、灵活、机动，易于进行端到端的性能测量。但是由于主动测量需要发送一定的探测包序列，若采用较长的探测包模拟真实的用户业务流，则会带来不可忽视的额外流量影响网络负载；若采用较短的探测包可忽略流量的影响，但该测量值并不等于用户业务流的实际性能；此外，i n t e m e t 的流量也存在一定的突发特性，并不服从统一分布。所以发送探针测量的方式无法准确反映实际网络的性能，存在一定的缺陷。要对一个网络进行主动测量，需要一个测量系统，这种主动测量系统一般包括以下四个部分：测量节点( 探针) 、中心服务器、中心数据库和分析服务器。有中心服务器对测量节点进行控制，由测量节点执行测量任务，测量数据由中心数据库保存，数据分析则由分析服务器完成。2 被动测量被动测量不向网络发送探针，在链路或设备( 如路由器，交换机等) 上利用测量设备对网络进行监测，而不需要产生多余流量的测量方法。被动测量的优点在于理论上它不产生多余流量，不会增加网络负担；其缺点在于被动测量基本上第二章网络性能测量和推测技术是基于对单个设备的监测，很难对网络端到端的性能进行分析，并且可能实时采集的数据量过大，另外还存在用户数据泄漏等安全性和隐私问题。2 2 2 3 按照测量点的分布不同1 基于路由器的测量基于路由器的测量方法是通过路由器中的管理软件直接获取统计数据，因而具有较高的测量精度。i s p 通常采用基于路由器的测量来监测其内部网络的拓扑、流量、时延、丢包率等。但是，由于i n t e m e t 不同i s p 之间不协作的特点，这些数据对外保密；另外，将大量路由器统计的性能数据传递给中心网管系统，本身就需要消耗大量带宽、增加网络负荷。所以这种方法在许多场合下不适合。2 路由器协作测量路由器协作的测量在网络边缘主机上执行测量，但需要路由器的配合，这方面近来提出了一些新协议。同基于路由器测量一样，由于i n t e m e t 不同i s p 之间不协作的特点，依赖于路由器配合的测量方法的能力将受限，因此，路由器协作的测量需要还获得标准化组织和工业界的支持。3 基于端到端的测量端到端测量的目标是在只有边缘主机参与下，无需路由器的配合，获取网络性能统计，并且尽可能减少对网络造成的负荷。基于端到端的测量系统不仅可以得到端到端的性能数据，而且可以采用网络层析技术( n e t w o r kt o m o g r a p h y ) 得到链路级的性能数据，这是近年来的一个研究热点。虽然端到端测量的精度低于基于路由器的测量，但是它只需要端系统的支持，因此具有很好的灵活性，对于某些跨越多个运营商的测量问题，端到端的测量技术可能是最佳的选择。2 3 网络性能推测技术为了获取网络内部链路级性能参数，可采用传统的测量工具如p i n g 、p a t h c h a r等，但是随着i n t e m e t 规模的扩大、异构化和分散性使得网络性能定量估计非常困难。任何人无法依靠个别的服务器和路由器自由的传输重要的网络统计量，如链路时延和丢包率等；服务器和内部路由器的网络统计量的收集也将增加通信、信息处理和硬件需求等方面的开支；而且各服务提供商i s p 把这些统计信息视为高度机密的，此外，传送这些统计信息给中央处理节点将消耗大量可用带宽，增加9电子科技大学硕士学位论文了网络负载和拥塞发生。大大降低了通过路由器等内部设备对链路级流量特征进行直接测量的可行性。图2 1 网络层析技术然而，在某些情况下，可以问接的获取有用的网络统计量，而不需要服务器和路由器之间特别协作，对网络负载几乎不产生影响。那些统计量能够显示出隐藏的网络结构，并可以帮助检测和隔离拥塞、路由故障等。由于这种端到端的测量具有不依赖路由器协作、开销少的特点。通过端到端( e 2 e ) 网络测量对内部网络行为推测的成为近来研究的热点，这类问题被统称为“网络层析( n e t w o r kt o m o g r a p h y ) ”，即对有限节点子集进行主动或被动测量，通过统计建模并求解线性模型，从而获得网络链路级性能的推测估计，如图2 - 1 所示。2 3 1 网络层析的基本原理从主动或被动的测量中提取隐藏信息的问题被视为统计学的反演问题，是信号和图象处理等研究人员长期关注的领域。网络层柝技术基于信号处理中透析图像重建原理，利用端到端测量技术推导网络内部性能或拓扑结构。文献【9 】总结了两种网络层析技术的形式：一、基于端到端路径级的流量测量对链路级性能参数进行推测估计：二、基于链路级的流量测量对路径级流量强度进行推测估计。这里我们仅讨论基于端到端测量对链路级性能推测的方法。网络层析问题可以粗略的近似为线性模型：y = 刺+ ( 2 1 )第二章网络性能测量和推测技术其中，】，是测量得到的向量，例如包数或端到端时延，需要从许多不同的测量站点取得。x 是需要推测的向量，比如各链路时延、丢包率对数等。彳是路由矩阵，一般是个0 1 矩阵，1 表示测量路径经过某链路，否则为0 。矩阵可能很大，需要用迭代算法；4 不一定是满秩的，需要用线性组合或统计平均的方法。s 可能是善引入的随即噪声，也可能是测量时的附加噪声。可以假设近似为独立高斯分布、泊松分布、二项式或多项式分布等。本文中忽略噪声的影响，则线性模型可写为：y 一4 x( 2 2 )节点2节点3彳一k 1 ；1c z s ，设岛，岛，岛为图中各链路的成功率的对数，b 为节点0 到节点珀测量路径p l o g 酬p 2 。1o 圄r e ,。，由于a 不是满秩的，所以无法对方程求解得出岛，岛，岛，可采用其他方法来补充矩阵a ，令p 出为在节点3 收到探测包的条件下，节点2 收到探测包的条件概率，则p 中一岛，类似地定义p a ：，则补充后的方程为：电子科技大学硕：| ：学位论文l o g p 2l o g p 3l o g 岛bl o g p 3 1 2l1o101oloo o1( 2 - 5 )这样就可以解出各链路的丢包率，由于方程是超定的，可采用最小均方误差来估计日，岛r 以。在网络层析推测中，首先要进行端到端测量，得到测量值矩阵y ，测量次数需要足够多，才能使统计推测更精确，测量路径要尽可能覆盖网络中的所有链路，或采用其他办法使得路由矩阵a 达到满秩，这样计算结果才有唯解。网络层析的端到端测量可以采用组播测量的方式，从源节点发送组播探测包到多个目标节点，探测包所经过的所有路径构成了逻辑组播树，出树状逻辑拓扑引入的链路相关性容易推测出逻辑链路的性能参数。组播网络层析技术具有发包少、流量小、测量范围广和测量精度高的优点，适合大规模网络测量。但是并不是所有网络都支持组播协议，而且路由器处理组播数据包与单播数据包的方式也明显不同。为了避免组搔的局限性，研究人员提出了b a c k - t o - b a c kp a c k e t p a i r ( 下面都简称为b 2 b p a i r ) 单播机制来模拟组播探测包【2 0 】，即源端连续发送两个紧邻的数据包。假设这对b 2 b 数据包分别发给不同的接收端，这两个数据包必然具有一段共享子路径，且共享路径越长则相关性越大。测量方法将在后面章节具体介绍。单播网络层析技术应用范围较广，不需要组播路由支持等条件。但是为了模拟组播特性会导致单播探测包数量增多，增加网络负载，也加大了推测算法的复杂度。网络层析利用组播测量或单播测量得到统计数据后，需要构造网络模型，利用优化过程将未知参数估计出来。该推测方法的主要问题在于隐变量的佶计，下面介绍常用的相关估计方法。2 3 2 最大似然估计和e m 算法参数估计最常用和最基本的方法有最大似然估计( m a x i m u ml i k e l i h o o de s t i m a t e m l e ) 。估计过程为一个具有目标函数的最优化问题，期望最大化( e s t i m a t e - m a x i m i z a t i o n , e m ) 算法是计算最大似然估计的常用方法。论文中的性能推测算法以e m 算法理论为基础，这里先简单介绍。1 2第二章网络性能测量和推测技术2 3 2 1 最大似然估计1 离散分布：设x 是离散型随机变量，其概率函数为p ( 墨p ) ，其中口是未知参数。设x 1 ，x 2 ，) 为取自x 的样本，x 1 ，x 2 ，) ( n 的联合概率函数为兀二e 。，( 置；d ，这里，0 是常量，x l ，x 2 ，x n 独立同分布。若我们已知样本取的值是x j ，x 2 ，x n ，则事件 五= 乇，五= 毛，l = 矗) 发生的概率为兀：p ( 墨；曰) 。这一概率随e 的值而变化。从直观上来看，既然样本值x i ，x 2 ，x 丑出现了，它们出现的概率相对来说应比较大，应使l - l ；，p ( 五；口) 取比较大的值。换句话说，护应使样本值x l ，x 2 ，x n 的出现具有最大的概率。将上式看作0 的函数，并用l ( o ) 表示，就有工( = ( 五，屯，；卯= 兀p ( 玉；口)( 2 6 )i - 1称l ( o ) 为似然函数，最大似然估计法就是在参数0 的可能取值范围0 内，选取使( 达到最大的参数值否，作为参数口的估计值，即取目，使下式成立：工( 印= 上( 五，恐，；占) 2 1 ：警三( 五，而，；印( 2 - 7 )因此，求参数0 的最大似然估计值的问题就是求似然函数工( 口) 的最大值问题。2 连续分布：设x 是连续型随机变量，其概率密度函数为p ；，若取得样本观察值为，t ，吒，则因为随机点( 墨，五，z ) 取值为( ，乇，) 时联合密度函数值为兀p ( 五；口) 。所以，按最大似然法，应选择0 的值使此概率达到最大。我们取似然卤数为上( 目) = 兀p ( 蜀；口) ，再按前述方法求参数0 的最大似然估计。扣，2 3 2 2e m 算法e m 算法( e s t i m a t e - m a x i m i z a t i o n ) d e m p s t e r ，l a i s d 和r u b i n 在1 9 7 7 年提出，用于解决不完全数据的最大似然估计问题【1 5 】。所谓不完全数据，对应于完全数据的概念，是指在实际情况中，由于某种原因，在所有要考察的变量中有一部分的数据并未观测到，这些数据中未观测到的变量就构成了缺失数据，而己观测到的变量的观测值构成了观测数据。e m 算法源于一个简单的想法：填充缺失的数据。考虑以下两个事实：1 如果缺失的数据得到了，就可以按完全数据的处理，得到未知参数的估计。2 如果模型的参数得到了，就可以按照模型参数填充缺失的数据。】3电子科技大学硕士学位论文反复在和步骤l 和2 中迭代，直到模型参数不再变化，这就是填充缺失数据的算法。e m 算法将缺失数据换成得到对应的完全数据的充分估计量。算法描述：x = ( x i ，x 2 ，x 。) 是密度函数p ( x l o ) 的一个样本，则该样本下的似然函数为：l ( oj x ) = p ( 协= 兀p ( 薯( 2 8 )t = 1对数似然函数为：，( 口i x ) = i o g l ( o x )0 的极大似然估计为：0 = a r g m a x l ( o i x ) = a r g m a x l ( 0 i x )样本z = ( ，砭，以) 与未知数据y 统称为完全数据，l ( t g l x , y ) = p y 协则完全对数似然函数为：( 2 - 9 )( 2 - 1