（电路与系统专业论文）网络性能测量和推测技术的研究.pdf

北京l l l l c 电火学博士学位论文 摘要 i n t e r n e t 是一个庞大的分布式网络，并且还在不断扩大，伴随着网络的规模 和复杂性的不断增加，新型的网络应用也不断涌现，但是目前的i n t e r n e t 存在 很多问题，作为网络管理的重要组成部分，网络性能测量所得到的数字指标具有 十分重要的意义。但是i n t e r n e t 的分布化、不协作、异质等特点以及流量特征 的复杂性，使得i n t e r n e t 测量研究是极具挑战性的工作。 大部分的测量工具功能单一，只能具有针对性地测量某个或某几个性能指 标。很多的测量系统需要网络节点的参与协作，或需要在网络中部署测量设备， 存储和分析包头信息，对网络用户而言，存在安全和隐私问题。测量信息的传输 为网络造成，附加流量，可能会影响到网络的运行。网络断层推测( n e t w o r k t o m o g r a p h y ) ，是一个新兴的领域，它利用端一端的性能测量结果，推测网络内部 链路节点的性能参数，如链路的时延、丢包率等。既能获得端一端的性能，又能 获得链路级性能参数。不需要网络节点的参与，也不需要在网络中部署溅量设备， 保证了用户隐私和信息安全，减少了测量信息的传输。 对于像i n t e r n e t 这样庞大的、子网管理相互不协作的网络，要测量它的q o s ， 网络推测技术就很重要。论文主要针对丢包率推测算法和时延推测算法进行研 究。总结了网络测量的方式、方法，以便进行端一端性能测量；总结了目前的丢 包率推测算法和时延推测算法：提出了多播依赖树模型，并用于推测网络内部链 路节点的丢包率和离散时延分布，该方法通过引入树的马氏性减少了估计的自 由参数，算法简单：对r n o w a k 等人提出的被动监测包对推测丢包率的算法进 行了简化，使之适合于在线计算；对基于有限混合模型推测链路的连续时延分布 的算法提出了改进，通过增加辅助测量信息，使推测算法更易于实现，推测结果 更准确。 在研究算法的基础上，论文提出了一个网络性能测量系统架构。目前国内外 的网络测量工具和系统还没有采用断层推测方法的，各种推测算法还只局限在仿 真实验中，算法的有效性如何需要在实际网络中验证，推测法在未来必将有它的 用武之地。该系统可以方便地部署测量，各种算法的加载卸载可以动态进行， 系统的扩展性很好。 关键词 网络测量，性能测量，网络断层推测，多播依赖树 第1 页 北京邮电大学博士学位论文 a b s t r a c t i n 础1 1 e ti st 1 1 eb i g 鼬s td i s 啊b u t i v en e 如，o r ki nt h ew o r l d w i t ht h er a p i d d e v e l o p m e n t s ，i n t e m c tb e c a m em o _ ec o m p l e x 廿l 卸e v e lni sac h a l l e n g r ct om 粕a g ea n e t w o l i i ( et h j s t h em o s tc h a l l e n g e a b kt h i n gm a yb et h em e a s u r e m e n to fi 疵m e t b e c a u o fi t sd i s t r i b u t i v e n oc o r p o r a t i v e 锄dh e t e r o g e l l e o u sc h a r a c t e r i s t i c ，a c c u m t e ， m e a s u r e m e n to f s u c han e 咖r ki sv e i vd i 仿c u l t ai o to ft 0 0 l sf o ri n t c m e tm e 髂u 佗m th a v eb e e nd e v e l o p e d ，s u c ha sp i n g ， t r a c e m u t e 柚de t c b u tm o s to ft l l 锄r c q u i r et i i ec o o p e r a t i o nw i t i in e h ，o l kn o d e s ，o r d e p l o y i n gt l l em e 笛u 咒n o d ei nm en e t w o f l 【t h em e a 轴m e n tm a y 疵c t 廿i en c t w o ( t r a m c ，a n dc a u s et h es e c u r h y 砌l e m ap m m i s i n gt e c h n i q u ei sn e 时o r kt o m o f a p h y ， w h i c hm f e r sn l ei n n e rm 蟑w o r kp a m m 鼬e r sb ye n d - t o e i l dm e a s u r e m e n t s t h e t e c h n o i o g yi ss i m i l a r 船t i l ec o m p m 盯t o m o g 糟p h y ( c d nn e i t l l e rn e e d st od e p l o ya m e a s u 姗e n tn o d ei n s i d e 山en e “v o r l ( n o rr e q u i r e sac o o p e r a t i v en o d e 1 nt i l i st h e s i s ，t l l en e 啪d ( t o m o 差野l p h ya l g o f i t i i m sa r ei n v e s “g a l e d t h el i n k s p a c k e t1 0 s sr a t i o 锄dd d a yd i s 晡b u t o na mi n f e 丌e du s i n 2t i l e s ea l g 硐t l l m sb y e n d - t o - e n dm e a s u r e m c i l t s t h e 、o f i 【o ft l l i st h e s i sc o n s i s t sa ft t l r e ep a r t s f i 哑1 y ， l i t e r a lr c v i e wa n dc 伽峰a r i s o no ft h e s ea i g o r i t h m sa f cd o n e s e c o n d l y ，s o m en e w a 1 2 r o r i t l l m sa r ep r o p o s e d an e wa l g o r 主t l l mb 瓣do nt h em u i l i c a s td e p e n d e n c e 打e e m o d e li sp m p o s e dt oi n f e rt h ei n s i d el i n k ，sp a c k e t1 0 s sr a t i oa n dd e i a v t h em a r c o v i a n c h a f a c t 廿o ft h e 心i sn a t u r a l l yi n c o r p o r a t e dt or e d u c et h ec o m p u t i n gc o m p l e x i t y s i m u l 硝sa l _ cd o n et os h o wt i i ee 行b c d v e n e s so fl l i ea l g 州岫a n o t h e ri m p m v e d a i g o m l l i l ib a s e d 佣l l i er n o w a k sw o f ki sp m p o s e dt om a | 【c tm o r es u i t 曲l ef o r o n l i n ec a l c u l a t i o n i no l d e rt oi n f 打t h ec 6 n u o u sp r o b 曲i l i 竹d i s 仃i b u t i o n ，a n i m p r o v e da i g o r i t l l m i sp 御o db yi n c o r p o m t i i l g 舳x j l i a qj l l 向哪a t i o nj nm i x e d f i n 沁m i ) 【t u r em o d e l t h ep m c i s i o f m ee 蛳m a t e dp a 阳m e t c r si si m p m v e d f i 1 l y an e 撕o r km e a s u r e m e m 觑哪e 、v o r ki sp r o p o s e di nt l l et i l e s i $ b yu s i n gn e t w o r k t o m o l 卵p h yt c c h n o l o g 再t h em a 伽他咖l so fn c t w o r i 【m e a s u 舳e 呲h a v e n ta d o p t e d t o m o 聊h yt c c h n o l o 科i nt l l ew o r l d as y s t c mb 舔c do nm em 咖e w o r kh a db e e n c o n s t n i c t e d i ti sc o n v 蛐i 锄tf b rd i 丘b 瑚l ta | l r o r i t h i i l st ou p l o a d d o w n l o a dd y n a m i c a l l y ! i ti sn e x i b i et oe x t c n dt h es y s t e m ， k e ”m r d s i n t e m e t m e a s u r e m e n 乞p e r f o 曲a n c em s u r c m 朋 n e t w o r kt o m o g r a p h y m u l t i c a s td e p e n d e n c et i e 第2 页 北京邮电大学博士学位论文 y 9 主6 1 8 0 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：动墨盏差 本人承担一切相关责任。 日期丝：! ! ! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期问论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论实注释。蕾学往论实属手保密萑：年解密后莲爵本授；胖。非保密论 文注释：本学位论文不属于保密范围，适用本授 本人签名；自! 盏翌 日期： 导师签名： 乏刍圣宠丛一 日期： 第l 页 权书。 卯6 r 佗 北京邮电大学博士学位论文 1 1 网络测量的意义 第一章绪论 i n t e r n e t 是从a r p a n e t 的基础上发展起来的，最初是一个主要服务于科研教 育部门的计算机网络，采用“尽力而为”的传输机制，无q o s 保证，无售后服务， 安全问题也由用户自行解决。但i n t e r n e t 的发展速度超出了人们的想象，到目 前为止，除了传统的浏览、聊天、网络新闻、电子邮件等业务外，新的业务类型 不断涌现，如远程教育、网上银行、在线交易、网络视频、i p 电话、网络游戏 等，到2 0 0 5 年年底，我国的网民数达到了1 1 1 0 0 万人，上网计算机达到4 9 5 0 万台，c n 下注册的域名数达到1 0 9 7 万个 1 ，增长速度非常之快。随着通信网 络、计算机网络与有线电视网络逐渐融合，i p 技术将获得更为普遍的应用。由 于i n t e r n e t 的初衷不象电信网那样是提供商业服务的，所以它一开始就不象电 话网那样是有规则地组织起来的，在发展过程中各个i s p 主要靠提升网络硬件设 施来保证服务质量，网络架构和技术都是按照经济规律来发展的，具有一定的盲 目性，所以目前的i n t e r n e t 存在很多问题：没有一个正常盈利的商业模型：网 络缺乏有效的管理和运营手段；面i 脑着安全、q 0 s 等问题；无法有效支持实时业 务；等等。新一代i p 网络技术的研究与发展需要了解网络的运行规律，验证新 的协议、算法、策略机制的性能，这就使得i p 网络测量这一基础课题成为必然 而迫切的需求。研究i p 网络性能测量就是了解网络行为、进行网络控制、实施 q o s 保证、提高网络性能的重要环节和基础，具有十分重要的意义。 从网络研究看，基于嘲络测量掌握i p 网络及其业务特征可以使新技术达到最 佳运用，网络的业务规律、性能行为模式需要通过测量掌握，采集、分析、解释 测量数据是网络流量、拓扑、行为建模分析的基础和验证手段，i n t e r n e t 流量的 自相似性、i n t e r n e t 拓扑的幂率分布等重要规律都是通过网络测量发现的。 从网络运营、维护和服务看，网络测量的结果是进行宏观网络控制和管理、 业务计费的重要依据。网络测量是网络开通后提供性能检验、考核指标的手段， 为网络工程提供验收依据，为网络运营提供实时或阶段性性能监控工具；通过测 量可进行网络诊断，如发现网络瓶颈节点或链路，有效配置资源，为网络规划、 第l 页 北京邮电大学博士学位论文 改造、及时解决性能问题提供参考和依据。 在服务质量研究领域，q o s 控制、管理、计费和测量是相互关联的。许多q 0 s 控制机制，如基于测量的接纳控制、q o s 路由、流量工程等，需通过测量获取网 络性能；q o s 管理需监测网络和用户的服务性能，进行动态资源管理、确认服务 等级合约( s l a ) 、执行入侵检测等；q o s 计费需要根据用户实际获得的服务质量 来收费。这些都需要q o s 测量的大力支持： 从应用性能优化看，多媒体应用需要通过测量了解当前网络的性能信息来优 化编码器解码器，内容分发网络中的请求路由协议、对等网络、网络缓存的位 置选择和维护策略、d n s 和w e b 性能检测等都需要网络测量的有力支持。 1 2 网络测量的研究现状 网络性能测量研究如何得到准确、可靠的测量数据以及如何在大量的测量数 据基础上，对网络的总体运行状态做个恰当的评估，但是，i n t e r n e t 分布化、 不协作( u n c o o p e r a t v e ) 、异质( h e t e r o g e n e o u s ) 的特点以及流量特征的复杂 性，使得i n t e r n e t 测量研究极具挑战性。目前对网络测量的研究主要集中在测 量工具和测量系统的开发上。 按照体系结构的不同，当前的网络性能测量系统可以分为测量工具和网络测 量基础设施两种类型。 单一功能的网络测量工具根据特定测量需求开发，主要针对一种网络参数或 者网络性能状况，目的性较强，功能相对单一。根据测量工具获取的参数的不同， 可以将其划分为路由探测、拓扑发现、流量监测、网络性能测量和网络应用性能 测量等几大类工具，般来讲，路由和拓扑探测是性能测量的前提。文献 2 总 结了1 9 9 6 年以来的主要的网络溯量工具。 ( 1 ) 、路由探测；路由可以看成是网络中两个主机之间的虚链路，由主机之 间的中间节点序列组成。最早的路由探测工具是t r a c e r o u t r ，可以采用i c 婶、 u d p 等协议，利用i p 数据包的t t l 域实现路由测量。从源端向目标端发送一系 列数据包，第一个数据包t t l 域设为l ，数据包到达第个中间节点后，该节点 将t t l 域值减l ，判断t t l 等于o ，则返回给源端一个i c 胛t i 殴- e x c e 朗e d 应答 包，这个数据包包含了这个中问节点的地址，于是第一个中问节点的地址被探测 第2 页 北京邮电大学博士学位论文 出来了；将第二个数据包t t l 域设为2 ，探测出第二个中间节点地址；用同样的 方法探测出其它所有中间节点的地址，直到源端收到来自目标端的响应数据包。 由于t r a c e r o u t e 会影响当前网络运行，即使数据包长度设为最短，也不应该频 繁发送。除此之外，还有多种通过被动方式获得自治域范围、路由拓扑、路由稳 定性、路由策略等与路由相关的信息的测量工具。基于t r a c e r o u t e 的工具有： p i n gp 1 0 t t e r 、n e o t r a c e 、v i s u a lr o u t e 等，可视化的路由探测工具显示更直 观，比如v i s u a lr o u t e 。 ( 2 ) 、拓扑测量工具通常具有分析并可视化网络拓扑的功能，而在分析和可 视化之前首先需要进行拓扑发现。所谓拓扑发现，一般是指发现完成最终用户服 务所涉及到的所有网络元素以及它们在网络中所起的作用和这些网络元素间互 相连接的方式。网络元素包括互连设备( 路由器、交换机、网关等) 、主机和子 网。网络拓扑对网络管理、网络规划非常有用。获得网络拓扑的最简单的方式是 由瞬缮管理员根据网络的实际状况手工绘出拓扑，但这种方式只能用于规模较 小、拓扑比较简单且较为固定的网络之中，对于大型网络来说是不可取的。网络 拓扑自动发现力图解决这一问题，依据拓扑发现的方式可将这类工具分为主动方 式、被动方式和读取网络管理控制信息三种方式。 主动方式：在管理中心向所有目标网络发送探测数据包，根据返回信息分析 拓扑结构。其发现方式是由内向外，逐渐扩散。发现过程有下面几个步骤：发现 本网所有主机；判断出所有中问节点；确定下一中间节点；分析本网拓扑结构； 分析下一个子网。 这种方案的优点在于能够比较快速地收集全局拓扑信息，最终形成拓扑结 构；收集的拓扑信息能比较好地反映网络的当前运行状况。缺点在于拓扑发现过 程需要发送大量的探测信息，产生大量的蹰络附加流量，对整个网络的运行影响 比较大。 被动方式：在各个目标网络部署管理代理，负责收集各个子网的拓扑信息， 收集的信息发回管理中心，经分析得到全局的拓扑结构。 这种方式的优点在于除了向管理中心发送子网拓扑信息外，不产生其它附加 流量，对网络正常运行的影响比较小。缺点在于由各个管理代理收集子网拓扑信 息，最终管理中心分析这些局部信息得到全局拓扑，所以耗费的时问比较长，而 第3 页 北京邮电大学博l 学位论文 且在网络规模比较大的情况下，在每个子网部署代理的代价比较高；需要对网络 信息采集有比较高的权限。 读取管理控制信息：通过s n m p 协议读取路由器等中间节点的网络控制信息， 最终分析得到网络拓扑结构。由于s n m p 是一种标准协议，网络中所有的中问节 点都支持它，所以这种方案具有普遍性。其缺点在于路由器中网络信息的更新有 一定周期，不能实时反映网络的当前状况。 ( 3 ) 、流量监测工具包括软硬件的包分析器，业务流监视分析工具，s n i p 网络管理工具几大类。 软硬件的数据包分析器主要提供网络或主机数据包的分析。其分析的目标数 据包可能是主动发送的数据包或被动收集的数据包。数据包分析通常具有数据包 过滤、数据包捕获、数据包协议类型解析、网络连通性和拓扑分析的功能。 网络流量具有方向性、端点性和时间性的特征。通过分析网络流量特征，建 立流量模型，可以为网络行为预测和网络规划提供依据。 对管理信息进行分析，采用s n i p 协议采集网络中间节点的性能数据，以评 价当前网络运行状况，通常具有流量监控、性能管理、计费管理、故障管理和安 全管理等功能。缺点是由网络管理员来完成，只能限定在一定的管理域范围。 常见的数据获取与分析工具有s n i f f e r 、n e t w o r kp r o b e 、c i s c o 公司的 n e t f l o w 、基于1 i b p c a p 软件包的t c p d u m p 等。 ( 4 ) 、网络的服务质量直接由网络性能决定，因此网络性能澜量是网络测量 领域中的一个非常重要的方面。 网络的性能监澳和分析，首先需要定义一种或多种性能指标来评价网络中某 条路径或链路的性能状况，常用的性能评价指标有瓶颈带宽、吞吐量、路由、路 径延迟、链路利用率、丢包率等，然后再通过主动或被动等测量方式获得网络性 能参数数据。如路径带宽测量工具t c p s p r a y 。 网络应用性能测量，与特定的应用类型相关，评价指标也因应用类型的不同 而不同。例如；评价一个w e b 系统可以选择连接延迟、吞吐量、连接数、速度等， s p e c 9 9 就是一个很好的w e b 服务性锯评测工具，这类工具还有：a p p m o n i t o r 、 h 3 2 3 b e a c o n 等。 由于当今i n t 啪e t 的庞大和复杂，采用单一测量工具在少数地点进行测量 第4 页 北京邮电大学培士学位论文 已经无法满足测量需求了，因此需要构建i n t e r n e t 测量基础设施，满足对 i n t e r n e t 测量曰益增长的需求。测量基础设旌，就是为进行i n t e r n e t 测量所创 建的底层架构，包括必要的测量平台和数据收集平台以及对两种平台的控制。从 9 0 年代开始，国外已经有研究机构开始着手测量基础设施方面的研究，迄今为 止，主要的测量基础设捕有； ( 1 ) 、美国国家科学基金n s f 和d a r p a 资助的国家i n t e r n e t 测量基础框架 ( n i m i ，n a t i o n a li n t e r n e t 雎e a s u r 鲫e n ti n f r a s t r u c t u r e ) 项目 3 ，其目标是 要建立一个全球化的、分布式的、大规模的i n t e r n e t 测量结构，已经设计出了 轻负载、可升级、可动态配置、具有安全验证的测量探针，测量各种性能参数。 n i 礁i 的体系结构包括以下5 个主要部分： n i m i d ( n i m id a e n ) 运行在网络中的一系列测量平台上，作为测量工具的 端点，负责与外部环境通信，并执行访问控制检查。 s c h e d u l e d ( s c h e d u l ed e a o n ) 做实际的测量安排、执行和结果打包。执行 测量的工具是相对独立的，作为第三方软件插入到m m i 中。 m e a s u r e m e n tc l i e n t 是终端用户实际操作的唯一n i m i 组件。它可以安装在 用户觉得方便的任何机器上，只要这个机器能够获得用户的信任。它直接与 n i m i d 联系。 c p 0 c ( c o n f i g u r a t i o np o i n to fc o n t a c t ) 配置和管理一组n i m i d 。c p o c 为 每个不同的n i m i d 提供了最初的授权策略，并随时间提供对这些策略的更新。在 将来的某个时刻，c p o c 将会作为n i m i 公钥和测量模块的仓库。安全是n i m i 结 构的一个基本部分，n i m i 的组件之问所有通讯的鉴别和授权都是利用公钥实现 的。每个n i m i d 都通过它相应的c p o c 进行配置。 d a c ( d a t aa c c e sc l i e n t ) 是存储测量结果的仓库和后处理器。m c 发送请求 给n i m i d ，同时请求指定d a c 的u r l ，指示测量结果的发送位置。为了立即收集 结果，d a c 可作为m c 的一部分运行，或作为后台程序，收集正在进行这的测量 结果。 与其它项目相比，n i m i 的主要特点是可以灵活地在底层架构之上添加自己所 需的澳0 最工具。 ( 2 ) 、i n t e r n e t 数据分析合作组织c a i d a 4 ( c o o p e r a t i v ea s s o c i a t i o nf o r 第5 页 北京邮电大学博士学位埝文 i n t e r n e td a t aa n a l y s i s ) 提出并实现了s k “t e r 和c o r a l 。c o r a l 用米测量高 速链路的工作流特征。s k i t t e r 通过几个源向许多其他的地址空间主动发送探测 包来探测路径和性能，测量内容主要包括： 搜集r t t 和路由数据( 用i c m p 包) ； 获得全球范围内的连接信息； 分析路由改变的频率； 将连通性以可视化方式表示出来，显示拓扑图； 用户通过访问w e b 服务器，在网页上选择各种参数，系统按要求进行测量把 处理结果传给用户。s k i t t e r 主要分析拓扑差异和r t t 性能差异，但比别的项目 测量范围大，覆盖面广。 ( 3 ) 、由斯坦福线性加速器中心( s l a c s t a n f o r dl i n e a ra c c e l e r a t o r c e n t e r ) 发起的端到端性能监控项目p i n g e r 5 ( p i n ge n d _ t o e n dr e p o r t i n g ) ， 采用主动测量方式发送i 数据包，用p i n g 来测量r h ，丢包率等，进而推算 系统的性能。在全世界布有监视点，部署在1 4 个国家的3 4 个监测点，可以监测 7 4 个国家的3 3 0 0 条链路的网络性能。 ( 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 k d is c o v e r y ) 项目 6 ，它是一个被动共享的测量，通过发送u d p 、t c p 分组让客 户机向服务器汇报网络性能，同时在网关处还加了一个性能捕获主机辅助测薰， ( 5 ) 、n l a n r ( 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 t w o r kr e s e a r c h ) 的项目组开发的网络分析架构n a i 7 ( n e t r ka i l a l y s i s 工n f r a s t r u c t u r e ) ， 日的是通过原始数据的收集和公布，网络测量的可视化等支持研究和分析。n l a n r 主要包括两个子项目，一个是基于主动测量的a 船，另一个是基于被动测量的 p 凇。a m p 主要钡5 _ 量r t t 、丢包率、拓扑和流量。p 姒主要进行基于包头追踪的分 析。另外还有基于控制信息监视的数据分析，主要是来自于参与项目的服务器的 s n l p 信息和基于b g p 数据的分析。 ( 6 ) 、s u r v e y o r 项日 8 是用来建立一个用于长期测量广域范围内网络端一 端单向时延、单向丢包率和路由信息的架构，它采用i p 删( i e t f 网络协议性能 指标) 已经定义好的标准测量方法，利用主动测量的方式得到拓扑和性能数据。 与其它项目相比，s u r v e y o r 的特色主要表现在：采用标准的测量方法，使结果 第6 页 北京邮电大学博士学位论文 更具有可比性：利用g p s 进行时钟同步，对单向测量的准确率较高。 ( 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 ns e r v i c e ) j 受 目 9 的主要测量内容是以控制信息监视的方式来收集拓扑和路由数据，提供 i n t e r n e t 上实时的b g p 路由信息，也可以让用户选择时间段。该项目收集的路 由数据更加丰富。 在国家自然科学基金和8 6 3 计划支持下，国内也开展了网络测量的研究，清 华大学提出了大规模互连网络性能监控模型l i 瑚( l a r g es c a l ei n t e r n e t p e r f o r i n a n c em o n i t o rm o d e l ) 【1 0 ，融汇了t 删在对象管理方面的方法；西安 交通大学提出了互连网应用性能测量系统n a 蹦( n e t w o r ka p p l i c a t i o n p e r f o r 日n c em e a s u r e m e n t ) 1 1 ，提出应用探针和区域探针的分布式体系结构。 研究取得了一定的成果，但还没有大规模地与运营商展开合作测量，研究规模的 广度和深度上需进一步加强。 1 3 论文的研究内容 大部分的测量工具功能单一，只能具有针对性地测量某个或某几个性能指 标。很多的测量系统需要网络节点的参与协作，或需要在网络中部署测量设备， 存储和分析包头信息，对网络用户而言，存在安全和隐私问题。测量信息的传输 为网络造成了附加流量，可能会影响到网络的运行。网络断层推测( n e t w o r k t0 l i l o g r 印h y ) 1 2 卜 2 1 ，是一个新* 的领域，它利用端一端的性能测量结果，推 测网络内部链路节点的性能参数，如链路的时廷、丢包率等。既能获得端一端的 性能，又能获得链路级性能参数。不需要网络节点的参与，也不需要在网络中部 署钡4 量设备，保证了用户隐私和信息安全，减少了测量信息的传输。 论文在讨论各种测量技术和推测技术的基础上，对时延和丢包率的推测算法 进行了深入研究提出了新的算法，并提出了一种网络性能测量系统架构，把推 测法应用孤测量系统，既便于目前的研究，又为今后的实用打下了基础。具体来 说，研究工作包括如下几方面： ( 1 ) 总结和讨论了网络测量技术的各方面。网络测量的目标可能是测量网 络应用的性能，或者是网络本身的性能，也可能关心端一端的性能，或者是网络 内部节点链路的性能，还可能是协议测试等各种不同的方面。标准化组织刘网 第7 贾 北京邮电大学博士学位论文 络的性能指标进行了定义，在实际应用和研究中，常关注的指标有时延、时延抖 动、丢包率、带宽等。在测量中，测量点的位置可能是：在网络节点中测量，或 者基于网络节点的协作进行测量，或者进行端一端测量不需要网络节点的参与。 测量方式有：主动测量、被动测量、基于管理信息的测量。在测量中所用的协议 有：i c 肝协议、t c p 协议、r t p r t c p 协议等。目前的测量工具和测量系统在测 量目标、测量方法、_ i 见4 量点的位置、所用的协议等各方面各不相同，各有优势。 ( 2 ) 对性能推测技术进行了深入研究。网络性能推测是基于端一端性能测量， 推测网络内部节点链路的性熊，又称为网络断层推测( n e t w o r kt o m o g r a p h y ) ， 是当前的研究热点，可以同时获得端一端性能和网络内部的性能数据；其基本原 理是：测出多条探测路径的端一端性能，一些探测路径有公共链路，在公共链路 上的链路性能参数就应该是相同的，采用参数估计方法，“分离”出各个链路的 性能参数。目前这方面的研究主要包括：端端单向时延测量和主机时钟同步、 性能相关的拓扑推测、丢包率测量和推测、时延性能的测量和推测、一般网络拓 扑下的性能推测等方面。丢包率推测方法有：基于主动方式的多播探测进行推测 和被动监测包对进行推测两大类。时延推测方法有：基于离散时延模型进行推测、 基于连续时延模型进行推游和动态网络时延推测三大类。 ( 3 ) 在对网络断层推测方法研究的基础上，着重讨论基于主动方式发送多 播探测包进行推测的情况，提出了多播依赖树模型，并提出利用多播依赖树推测 丢包率的算法和推测链路离散时延分布的算法，该方法通过引入树的马氏性减少 了估计的自由参数，算法简单。另外，对基于被动监测包对推测丢包率的算法进 行了简化，改进后算法计算比较简单，适合嵌入到网络推测软件中使用；对基于 有限混合模型推测链路连续时延分布的算法提出了改进，通过增加辅助测量信 息，使推测算法更易于实现，推测结果更准确。 ( 4 ) 提出了一个网络性能测量系统架构，把推测算法应用到测量系统中。 系统的目标是设计一个使用推测方法的实际网络的测量平台，一方面在可管理范 围内验证各种算法的有效性，另一方面，在将来可应用于网络测量。系统采用分 布式分层结构，论文详细讨论了如何部署测量，如何进行性能数据的存储和表示， 如何把各种推测算法动态加载到系统中，等等问题。 第8 页 北京邮电大学博士学位论文 1 4 论文结构和安排 本文的剩余部分内容安排如下： 第二章讨论了网络测量的原理、性能指标，就测量目标、测量点位置、测量 协议、测量方式等对网络测量技术进行了分类，对性能推测技术的原理、关键技 术等进行了分析。 第三章详细讨论了丢包率的测量和推测算法。基于多播方式的主动测量，提 出了采用多播依赖树模型推测丢包率的算法。对基于被动方式监测包对，进而推 测节点丢包率的算法提出了改进，使之适合于在网络性能推测系统中应用。 第四章讨论时延的测量和推测。提出用高斯混台模型为端一端时延建立密度 函数。对目前的时延推测算法进行了分析，对基于有限混合模型推测链路时延分 布的算法提出了改进算法，并提出了利用多播依赖树模型推测链路离散时延分布 的算法。对单向时延测量中的主机时钟同步问题进行了讨论。 第五章在分析比较现有的网络推测方法的基础上，设计了一个网络性能测量 系统架构，把网络推测技术应用到测量中。详细讨论了如何部署测量、如何进行 性能数据的存储和表示、如何把推测算法应用到测量系统中等问题。 第六章是结束语，对全文进行了总结，并指出了目前的研究进度和进一步的 研究方向。 本章参考文赫 1 中国互连网络信息中心( c n n i c ) ，第1 7 次中国互连网络发展状况统计报告， 2 0 0 6 年1 月1 7 日 【， 】n e 帆o r km i t o 】曲gl s ，鼬幽坠盟! 堑：墅垫鱼缒：鲤堂蚴噬型 n m l s n n l 【3 】v c 功p a x s o n ，j a m s h i dm a i l d a v i ， a n d m wa d a m a ，m a t l l l e wm a t l l i s ，a n a r c h i 妣t i l r ef o r l a 曙e s c a l e i i l t 咖e t m e 删r c m e n t ”， i e e e c o m m u n i c a t i o n s ， 1 9 9 8 0 8 5 4 【4 】h n p 卅w w w c a i d a o r 朋a l y s i s 如r f b 瑚a n m e a s i n 仔“ 【5 】，枷哪m a 劬c w s l e sc o n t c ”p i n g e rp 叫e c t ：a c t i v el m e m e tp e r f b m a n c e m o n i t o r m g f o rt l l e 圯n pc ( 蚰m 吼i t y ii e e ec o m m u n i c 鲥m a g 配i n e ，m a y 第9 页 北京邮电大学博士学位论文 2 0 0 0 1 3 0 - 1 3 6 【6 】 n o m a s s c h u p p e l ， i n t e m e t m e a s u r e m e n t s ”， h 鲤；地盟：地 一b c r l i n d 咖s t a i n 仍i l e m m 刖p a p e r h 蜘l 【7 】t o n ym c g 9 0 bh a n s _ w 锄c rb r a u n ，j e f fb r 洲，“n en l a n rn e 研o r k a n a l y s i si n f h s t m c t u r e ”，i e e ec o m m u n i c a t i o nm a g a z i n e ，m a y2 0 0 0 ，3 8 ( 5 ) 1 2 2 - l2 8 8 】 s u n 订 k a l i d j n d i s u r v e f y ： a ni n 抒a s 臼1 l c t u r ef o ri t l t e m e t p e r f o n l l a n c e m e a s u r c i n e n t 孓i n e t 9 9 【9 】h 牡p ：，w 、v w f r i p e n e t ， 【1o 】千继龙，吴建平。大规模计算机网络性能监控模型的设计与实现。计算机 研究与发展，3 7 ，4 ，2 0 0 0 p p 4 4 3 - 4 5 2 。 【1 l 】张文杰，钱德沛，张然，等。互连网应用性能测量系统的研究实现。计算 机研究与发展，v 0 1 4 0 n o 1 2 0 0 3 ，p p 6 0 - 6 7 。 【1 2 】m c o a t e s ，a o h e m ，r n o w a l ca n db y 吣叮n t e m e t1 o m o g r a p h y ”，娅j 髓鹭即口， m 睨镕砸 朋醣妇，m a y2 0 0 2 【1 3 】r c 矗c e r e s ，n d u 币e l d ，j h o r o w i 饶，a n dd 1 0 w s l e y ， 诅u l 廿c a s t - b a s e d i n f i e r e n c eo f n e 柳o r k - i n t e m a ll o 韶c h 锄c t e n s t i c s ，”艘e 乃切强坳r 舰m 叼v o j 4 5 ，p p 2 4 6 2 2 4 8 0 ，n o v 19 9 9 【1 qf l op r e s t i ，n g d u 艏e l d ，j h o m w i 嗨柚dd t c w s l e y ，“m u l t i c 啦- b a s e d i n f e r e n c eo fn e m o 睡j n t e m a ld e l a yd i s m b u t i o n s ”u n i v m a s s a c h u s e t t s ，a m h e r s t ， m a ，t e c h ，r e p 9 9 5 5 ，1 9 9 9 【1 5 】n g d i l 桶c l d ，j h o m w 峨f l o 脚s t ，卸dd t 0 w s l e y ，n e t w o r kd e j a y t o m o g r a p h yf m me n d - t o - e n d 珊i c a s tm e 咖册曲t s i nn 眦觚f 成，矗叩d 瞎打谢 c b m m 帆a ，o 枷f f o ，柳ym ，l 凼j h 铆t ，u 蛐a i t a i y ，s e p l2 0 0 1 【1 6 】m f s h i h 锄da o h e r o ，“u n i c a s ti n f e r e n c eo fn e t w o 一( i i n kd e i a yd i s 晡b u t i o n s f 确e d g cm e a s u r e m e n t s ，i nn 阢脚e 觚c o 矿一“虹，焉阳p 咖，舶d 瓯g m ， p m c 螂打够，s a l tl a k cc i t y ，u t ，m a y2 0 0 l ，p p 3 4 2 l _ 3 4 2 4 【1 7 】t b u ，n d u 塌e i d ，f l op r e 蚶柚dd t o w s i e y “ 【t o m 9 9 r a p h yo n g e n e m lt o p o l o g i e s ，”胁p p 螂彳c ，跏e 胁2 d ，m a r i n ad e lr e y c a ，j u n e 1 5 - l9 - 2 0 0 2 【18 】g l i a n g 柚db y u m 觚i m u mp s 叫d ol i k e l i h o o de 蚰n a t j o ni nn e m o r k 第l o 页 北京邮电大学博士学位论文 t o m o g r a p h y i ni e e et r a n s s i g n a lp m c e s s i n g ，v o i 5 】，n o 8 ，a u g u s t2 0 0 3 【1 9 lm c o a t e s 锄dr n o w 叱n e t 、v o r kt o m o g r a p h yf o ri n t e m a 】d e l a ye s t i m a t i o n ，” i n m c