（信号与信息处理专业论文）基于网络层析的丢包率推断算法研究.pdf

摘要 摘要 随着i n t e m e t 规模的扩大，网络结构日益复杂，服务优化、异常链路监测等 网络重大课题面临前所未有的挑战。但是各组织或部门之间不愿意分享其网络状 态，缺乏相互协作加剧了问题的复杂度。通常无法直接获取全部网络内部性能 参数或拓扑结构，这种因特网的分布化、不协作、异质等特点使得因特网测量研 究极具挑战性。 网络层析( n e t w o r kt o m o g r a p h y ) 是一个新兴的技术。它利用端对端测量技 术推断网络内部性能参数( 如：丢包率、延迟等) 和拓扑结构等。网络层析不需 要所有网络节点的参与，也不需要网络中部署测量设备，保证了用户的信息安全， 同时也减少测量信息的传输。网络层析技术已成为国内外网络测量的研究热点之 一。 本文主要针对丢包率推断算法进行研究。分析现有基于多播的链路级丢包率 推断算法，着重分析m l e 算法和p m l e 算法的特点。根据e m m l e 算法和p m l e 算法的缺点，研究了一种改进的e m p m l e 算法，该算法结合了m l e 算法和 p m l e 算法的优点，在保持较高推断精确度情况下，减少计算量。针对p m l e 算法的推断精度不高的缺点，提出了一种具有修正因子的“p m l e 算法，通过引 入修正因子，降低p m l e 算法推断丢包率时的误差，从而提高了算法的推断精 度。此外，对于多点多播测量技术，实现了利用单点多播丢包率推断算法的多点 多播丢包率推断的加权平均快速算法。对于不支持多播的网络，研究了一种可变 包对的单播丢包率推断算法。 在研究算法的基础上，本文还构建了基于n s 2 的丢包率层析的仿真实验平 台，利用该平台模拟了不同的网络仿真环境，对前述的网络丢包率推断算法进行 仿真，并通过对仿真结果的分析和比较，总结了这些算法的性能特点。 关键字：网络层析；丢包率；多播 a b s t r a c t a b s t r a c t a st h ei n t e r n e tg r o w si ns i z ea n dd i v e r s i t y , i t si n t e r n a lp e r f o r m a n c eb e c o m e se v e r m o r ed i f f i c u l tt om e a s u r e a n yo n eo r g a n i z a t i o nh a sa d m i n i s t r a t i v ea c c e s st oo n l ya s m a l lf r a c t i o no ft h en e t w o r k si n t e r n a ln o d e s ，w h e r e a sc o m m e r c i a lf a c t o r so f t e n p r e v e n to r g a n i z a t i o n sf r o ms h a r i n gi n t e r n a lp e r f o r m a n c ed a t a t h em o s tc h a l l e n g e a b l e t h i n gm a yb et h em e a s u r e m e n to fi n t e r a c t b e c a u s eo 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 a n dh e t e r o g e n e o u sc h a r a c t e r i s t i c ，a c c u r a t em e a s u r e m e n to fs u c han e t w o r ki sv e r y d i f f i c u l t o n ep r o m i s i n gt e c h n o l o g yn a m e dn e t w o r kt o m o g r a p h yh a sb e e np r o p o s e da sa l l e f f i c i e n ta p p r o a c ht oa n a l y z en e t w o r kp e r f o r m a n c e t h i sa p p r o a c hu s e se n d t o - e n d m e a s u r e m e n tt oi n f e rt h ei n n e rn e t w o r kp a r a m e t e r s i tn e i t h e rn e e d st od e p l o ya m e a s u r e m e mn o d ei n s i d et h en e t w o r kn o rr e q u i r e sc o o p e r a t i v en o d e n e t w o r k m m o g r a p h yc a l ln o ta f f e c tt h en e t w o r kt r a f f i c ，a n da l s oc a nn o tc a u s et h es e c u r i t y p r o b l e m i nt h i sp a p e r , w ec o n s i d e r et h ep r o b l e mo fc h a r a c t e r i z i n gl i n k - l e v e ll o s sb e h a v i o r t h r o u g he n d - t o e n dm e a s u r e m e n t s f i r s tw ee l a b o r a t ei nd e t a i lt h ed e r i v a t i v ep r o c e s s o fm u l t i c a s t - - b a s e de x p e c t a t i o nm a x i m u m - m a x i m u ml i k e l i h o o de s t i m a t ea l g o r i t h m ( e m - m l e ) a n d p s e u d om a x i m u ml i k e l i h o o de s t i m a t ea l g o r i t h m ( p m l e ) b a s eo n t h ee m m l ea n dp m l e ，w ep r e s e n t e da l la p p r o a c ht ol i n kl o s si n f e r e n c ef r o me n d t o e n dd a t a ；o u ra p p r o a c hh a st h ea d v a n t a g e so fh i 曲e f f i c i e n c y b a s eo np m l e ，an e w a l g o r i t h m ( p p m l e ) i sp r o p o s e dt oi n f e rt h ei n s i d el i n kl o s s ，t h r o u g ht h ei n t r o d u c t i o n o fc o r r e c t i o nf a c t o r , p p m l ea l g o r i t h mh a sh i g h e ra c c u r a c y i nt h i sp a p e r , w ea l s oi n t r o d u c et h em u l t i p l ep o i n t sm e a s u r e m e n t ，a n dd e s c r i b ea f a s tm i n i m u mv a r i a n c ew e i g h t e da v e r a g ea l g o r i t h m ( m v w a ) w er e s e a r c ht h eu n i c a s t b a s e dl o s si n f e r e n c ea l g o r i t h m ，i nt h i sp a p e r ；w eo f f e ra u n i c a s t b a s e df l e x i b l ee x p e c t a t i o nm a x i m u m a l g o r i t h i n a tl a s t ，w ed e s c r i b et h es i m u l a t e de n v i r o n m e n tb a s e do nn s 2 a c c o r d i n gn e t w o r k t r a f f i cm o d e l ，w ec o n s t r u c tt h eb a c k g r o u n da n dd e t e c t i o nt r a f f i c ，a n da n a l y z ee a c h 基于网络层析的丢包率推断算法研究 c h a r a c t e r i s t i c s i m u l t a n e o u s l yu s e dt h em a s s i v ee x p e r i m e n t a lr e s u l t ，w ed e t e r m i n e s a m ei m p o r t a n tp a r a m e t e r s w eu s e ds i m u l a t i o nt oa n a l y z ea l la l g o r i t h m si nt h i sp a p e r , s u m m e ru pt h ea d v a n t a g e sa n dd i s a d v a n t a g e so fv a r i o u sa l g o r i t h m s k e yw o r d s ：n e t w o r kt o m o g r a p h y ；l o s s ；m u l t i c a s t 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ：事聿象 年月日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“ 或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签名) ：哥4 钮 年月日 第一章绪论 1 1 研究背景 第一章绪论 随着i n t e r n e t 的飞速发展，今天的互联网已经成为现代社会发展和人们生活 不可或缺的部分，截止2 0 0 8 年底，中国网民规模达到2 9 8 亿人，普及率达到 2 2 6 ，超过全球的平均水平，网民规模将保持持续增长的趋势【1 。人们的生活 与互联网结合得越来越紧密，伴随着人们对于互联网依赖性的增加，对于网络服 务质量的要求也不断提高，互联网是一个庞大、复杂、开放的网络集合，如何更 好地获知互联网的性能越来越被网络使用者和网络开发者所关注。然而要深入了 解目前互联网的性能状况、优化互联网的性能、提高互联网的利用率等并不是很 容易的事情，特别是目前网络的规模日益增大，网络业务流量膨胀，使管理网络 变得越来越难。 要了解网络的运行状况，要管理好网络，就要对网络进行网络测量，通过测 量得到的数据可以具体的显示网络的性能及其变化，丢包率、延迟、流量、拓扑 结构是网络性能的重要指标，作为关键的网络测量信息，这些信息对于因特网服 务提供商在测试服务质量参数、评估链路性能以及进行网络异常检测等方面具有 重要的意义。同时可以通过监视各种网络性能参数的变换保证网络的可靠、高效、 稳定的运行。 传统的网络测量通常采取直接测量的方法来获取这些重要的网络性能参数。 但是随着网络大型化、异构化、分布化发展，使互联网结构日益复杂，直接测量 网络中的各种重要性能参数的难度变大，更迫切需要各个不同域内的网络节点合 作。但是安全因素越来越被重视，很多因特网服务提供商处于商业性的考虑，不 可能全力合作。因此，通过其他测量途径了解网络性能参数以及网络性能参数的 变换动态，具有极其重要的意义。网络层析是一种新兴的领域，通过端对端的测 量网络各种性能参数，克服了传统网络测量的缺点，具有非常重要的意义，网络 层析近年来成为科研人员关注的热点。 本文主要研究基于网络层析的丢包率推断算法，丢包率是网络测量中非常重 要的参数，所以研究丢包率推断算法具有重要的意义。目前已经提出了多种丢包 基于网络层析的丢包率推断算法研究 率层析推断算法，算法原理和性能各不相同。本文针对当前基于网络层析的主要 的丢包率推断算法进行对比研究，分析各个算法的优劣点，并提出相应的改进算 法，使丢包率算法在推断精度和计算复杂度上有一定的改善，更加适合大型网络 的丢包率推断。 1 2 研究现状 目前网络层析的研究重点主要集中在丢包率和时延推断上，主要以美国防部 高级研究计划局的m i n c ( m u l t i c a s t b a s e d i n f e r e n c eo fn e t w o r k - i n t e r n a l c h a r a c t e r i s t i c s ) 项目和r i c e 大学研究的单播网络层析项目为主。 1 ( 美) 国防部高级研究计划局( d a r p a ) 的多播层析项目( m i n c ) 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 ) 项目研究 推导网络内部链路性能特征测量的方法【2 】。m i n c 提出了多播网络层析方法的数 学模型，论证了多播层析算法的正确性和收敛性。该项目通过m t r a c e 工具发送 多播探测包测量网络端到端的性能特征，利用多播探测包间存在的相关性，使用 求解“逆问题”方法推导网络内部链路特征参数。m i n c 项目的目的是： ( 1 ) 基于己知拓扑结构的网络内部性能分布推断 在拓扑结构己知的情况下，针对网络链路性能特征，如丢包率、延迟、可用 带宽等，研究带参数的或不带参数的链路性能特征推断方法【3 】【4 。在网络模拟 环境和i n t e m e t 真实环境下，通过实验验证推断方法【5 【6 】【7 】【8 】。 ( 2 ) 基于未知拓扑结构的网络拓扑特征统计推断方法 在拓扑结构未知的情况下，利用己知的部分可用信息，研究推断多播分布树 完全拓扑结构的技术【9 。主要目标是利用接收器获得的端到端的丢包率和延迟 信息，开发一种有效的多播树分类识别技术。 ( 3 ) 基于多播的网络特征推理工具 使用上述技术，开发一种有效的、分布式的软件，用于估计网络链路级的性 能参数并判断链路瓶颈。该应用模块能够在类似n i m i ( t h en a t i o n a li n t e m e t m e a s u r e m e n ti n f r a s t r u c t u r e ) 的测量平台上使用。 ( 4 ) 支持多播推理技术的网络平台 开发支持多播网络推理的网络测量平台。该平台可以通过拓展n i m i 的多播 2 第一章绪论 测量功能得以实现。 2 r i c e 大学研究的单播网络层析项目 r i c e 大学的r o b e tn o w a k ，y o l a n d at s a n g 和m a r kc o a t e s 等人研究并实现 了单播网络层析技术【1 0 】【1 1 】，在目前大多数网络不支持多播路由的背景下有很 强的实际意义。r o b e t 等人的研究目标有以下几点： ( 1 ) 使用单播测量网络内部参数 研究表明由于路由传输队列的限制，单播组长度不能过长，一般包含两到三 个单播时，其探测能力最强。为了探测完整的网络特征参数，必须使用能覆盖全 部网路拓扑的单播组集合完成一次探测。 ( 2 ) 单播测量算法 该项目研究了基于单播的网络层析算法，i n t e m e t 链路丢包率符合b e r n o u l l i 模型，利用该模型建立似然函数方程，再利用极大似然估计算法推导网络内部特 征。 3 丢包率推断研究现状 网络丢包率是网络工程师优化网络设计，增强对网络控制的重要参数，对于 网络管理者来说也极其重要。因此网络链路级丢包推断作为网络层析成像的重要 研究部分，国外许多研究机构在这方面进行了大量研究。r c a c e r e s 等首先采用 最大似然估计方法来估计多播树的链路丢包率 5 】，这种方法能很好的对链路级 丢包进行估计，但i n t e m e t 中仍然有很大一部分并不支持网络级的多播。 m a r kc o a t e s 和r o b e r t n o w a k 等提出使用单播背靠背探测包对来测量路径 的丢包【1 0 】，然后通过求解最大似然方程来估计链路的丢包率。t i a nb u 等把该方 法扩展到非树状单播网络中进行链路丢包估计【1 2 】，文献【1 2 还介绍了多点多播 技术。由于单播包对在传输过程中不能完全保证同时被丢弃或是正确传输，即不 能完全达到多播传播的效果，文献【1 3 】中提出采用三包坌h ( t h r e e - p a c k e ts t r i p e ) 的方 法来解决这一问题。包组中的探测包在严格队尾丢包的情况下，将以极大的概 率同时被丢弃或是被正确传输，产生近似于多播的效果。 对于大型网络，利用最大似然估计方法推断链路丢包率时计算量比较大，文 献 1 4 1 5 1 6 1 q b 提出一种快速的至底向上的算法，只要通过简单的数值运算就可 以准确推断网络丢包率，但在网络丢包率较大的情况下，丢包率推断误差精度略 基于网络层析的丢包率推断算法研究 低于最大似然估计方法1 17 。 1 3 本文研究内容 本文主要研究网络层析中丢包率推断算法。重点研究基于多播的链路级丢包 率推断算法，在研究m l e 算法和p m l e 算法的基础上，对m l e 算法中的e m m l e 算法进行了改进，给出了一种计算量较小的e m p m l e 算法；针对p m l e 推断算法精度不高的缺陷，提出了一种具有修正因子的u p m l e 算法，该算法具 有较高的推断精度。最后通过仿真实验对四种多播丢包算法的性能进行多方面评 估；本文还研究了多点多播测量技术，介绍了一种快速的加权平均推测算法。 针对不支持多播的网络，研究了基于单播的丢包率推断算法，给出了一种可 变包对的丢包率算法。 本文还构建了基于n s 2 丢包率层析的仿真平台，确定网络流量模型和背景 流量，分析了影响网络丢包率层析测量精度的主要因素，并研究了不同测量策略 和路由器拥塞避免算法对丢包率推理算法准确率的影响。 1 4 本文主要章节介绍 本文共分5 章，剩余4 章内容安排如下： 第二章主要介绍网络测量和网络层析的基本思想，并介绍网络层析中丢包率 推断原理。 第三章详细讨论了丢包率推断算法。对于基于多播方式的主动测量，详细介 绍了e m m l e 算法和p m l e 算法，并分析两者的优缺点。对于基于单播方式的 主动测量，介绍了可变包对的e m 算法，并分析该算法的优点，进而提出并行的 思想，使之更适合于大型网络性能推测系统的应用。接着还研究多点多播技术， 介绍了一种快速的加权平均推测算法。在上述基础上，研究讨论了丢包率的改进 算法，提出一种e m p m l e 改进算法，使算法的计算复杂度下降；提出了一种具 有修正因子的“p m l e 快速算法，使p m l e 算法的精确度提高。 第四章主要基于n s 2 构建网络层析丢包率推断软件平台，并通过一系列的 试验确定该平台的各个重要参数。利用构建的仿真平台进行一系列的仿真实验， 分析和比较第三章所阐述的丢包率推断算法，总结这些算法的优缺点，并验证 4 第一章绪论 了改进算法的优点。 第五章是结论和建议，对全文进行了总结，并给出了进一步的研究方向。 基于网络层析的丢包率推断算法研究 第二章网络层析及丢包率推断原理 网络层析是- f - j 新兴的网络测量课题，它是基于医学层析概念的基础上提出 来的，利用信号处理问题中的层析图像重建原理进行网络拓扑和网络内部性能推 理。它旨在通过网络边缘节点进行端到端的测量，利用测量结果进行网络结构或 内部性能参数分析，比如：丢包率、延迟等。利用这些网络测量数据可以更有效 的设计、控制和管理网络，为链路拥塞、路由故障和网络异常流量的检测和控制 提供技术支持。本文主要研究网络层析领域中网络链路级参数丢包率推断算法。 本章首先介绍网络测量目的和意义，然后介绍网络层析的原理和网络层析丢包率 推断原理。 2 1 网络测量 2 1 1 网络测量的意义 随着i n t e m e t 规模的不断扩大，目前i n t e m e t 存在很多问题，网络缺乏有效 的管理和运营手段，面临安全、q o s ( q u a l i t yo f s e r v i c e ) 等问题，无法有效支持 实时业务等等。新一代i p 网络技术的研究与发展需要了解网络的运行规律，验 证新的协议、算法、策略机制的性能，这就使i p 网络测量( n e t w o r km e a s u r e m e n t ) 这一基础课题成为必然而迫切的需求，研究i p 网络性能测量是为了解网络行为、 进行网络控制、实施q o s 保证、提高网络性能的重要环节和基础，具有十分重 要的意义。 从网络研究看，基于网络测量掌握口网络及其业务特征可以使新技术达到 最佳运用。网络的业务规律、性能行为模式需要通过测量掌握，分析测量数据是 网络流量、拓扑、行为建模分析的基础和验证手段，i n t e m e t 流量的自相似性、 拓扑的分布等重要规律都是通过网络测量发现的。 从网络运营、维护和服务看，网络测量的结果是进行宏观网络控制和管理、 业务计费的重要依据。网络测量是网络开通后提供性能检验、考核指标的手段， 为网络工程提供验收的依据，为网络运营提供实时或阶段性性能监控工具；通过 6 第二章网络层析及丢包率推断原理 测量可进行网络诊断，如发现网络瓶颈节点或链路，有效配置资源，为网络规划、 改造、及时解决性能问题提供参考和依据。 2 1 2 网络测量的分类 网络测量有助于深入了解整体拓扑结构和网络行为，发现网络瓶颈，优化网 络配置，发现存在的潜在危险。网络测量有多种分类，基于测量方式：如主动测 量和被动测量，单点测量和多点测量；基于不同协议的测量：拓扑测量和性能测 量。下面对比较普遍的分类方式做详细的介绍【1 8 】。 1 主动测量和被动测量 主动测量：向网络中发送实际数据包，其测量的信息包括可达性、r t t 、经 过路由次数等。主动测量可控性强、灵活、测量范围大，但如此庞大的测量体系 有可能造成较大的网络负荷和改变网络行为。 被动测量：在网络中放置探针，捕获链路带宽、丢包率、延时等信息。它对 网络的行为没有影响，能够达到对观察点网络行为的详尽理解，但是它难以获得 对网络的整体理解，而且其前提是协作，否则无法工作。 2 单点测量和多点测量 单点测量：不需要协作就能较准确的探测网络性能，这是它得到广泛应用的 主要原因之一，但是它的测量能力有限，收集信息不够全面，有时候不能覆盖整 个待测网络。 多点测量：通过各个探测点相互协作，能够得到大规模的网络探测数据和比 单点更多的链路信息。其缺点是多个探测点之间的关系较为复杂不利于控制和管 理。 3 拓扑测量和性能测量 拓扑测量：推理网络的逻辑拓扑结构，构造网络拓扑结构图并进行可视化方 面的研究。同时它可以与实际地域位置相对应，得到具有地理信息的拓扑图。 性能测量：推理网络的吞吐量、延迟、丢包率等，通过它们研究网络的可靠 7 基于网络层析的丢包率推断算法研究 性、稳定性、可达性等。一方面是为了网络维护管理、保障服务质量；另一方面 是为了预报网络性能，每隔一定的时间间隔，周期性的监视、动态的预报( 各种 网络及计算资源1 网络性能。 2 1 3 网络测量的主要性能指标 为了定量地描述网络的性能，需要定义一系列描述网络性能的参数，在测量 时才可能有针对性。 目前i e t f 的i p p m ( i pp e r f o r m a n c em e t r i c s ) t _ 作组和i t u t ( 国际电信联盟) 都对网络性能参数进行了定义，并在不断修改中，两个标准组织指定的网络性能 参数均包括：时延、时延变换、丢包率等，这几个参数都是实际测量中经常关注 的重要参数。 ( 1 ) 时延 时延指i p 包从发送节点到目的节点所经历的时间，可分为单向时延和双向 时延。时延由固定时延和可变时延两部分组成。固定时延基本不变，由传播时延 和传输时延构成；可变时延由中间路由器等节点的处理时延和排队等待时延两部 分构成。因单向时延测量要求严格的时钟同步，在实际的测量中有一定难度，可 以借助g p s 等外部时钟源来实现测量主机间同步，精度高但费用昂贵，尤其是 r 在测量主机数量大时；有一些文献研究如何对测得的单向时延进行校准。在往返 时延的测量中可以避开时钟同步问题。 ( 2 ) 丢包率 丢包率指丢失的i p 包与发送的i p 包总数的比值。许多因素会导致数据包在 网络上传输时被丢弃，例如：当网络发生拥塞时，网络节点来不及转发同时到达 的过多分组，缓存将被耗尽时，后来的分组将被节点丢弃；当口分组出现比特 差错时，上层协议将简单地丢弃分组。 为了评估网络的丢包率，一般采用直接发送测量包来进行测量。对丢包率进 行准确的评估与预测则需要一定的数学模型。目前评估网络丢包率的模型主要有 贝努利模型、马尔可夫模型和隐马尔可夫模型等等。贝努利模型是基于独立同分 8 第二章网络层析及丢包率推断原理 布的，即假定每个数据包在网络上传输时被丢弃的概率是不相关的，因此它比较 简单，预测的准确度以及可靠性都不太理想。由于采用先进先出的排队方式，丢 包之间具有很强的相关性，即在传输过程中，包被丢失的概率受前一个包丢失的 影响相当大。 2 2 网络层析技术 2 2 1 网络层析的意义 i n t e m e t 的飞速发展迫切需要提高它的性能。同时，人们需要良好的q o s 和安全方面的保证，i s p ( i n t e m e ts e r v i c e sp r o v i d e r ) 也需要加强对i n t e m e t 的管理 这就使得网络测量成为越来越迫切的需求。然而现存的网络测量方法存在以下限 制及不利因素： ( 1 ) 目前广泛使用路由器测量方法，也就是常说的“内在 方法，在网络节 点或者网络节点之间直接进行主动或者被动测量，该方法有许多潜在的限制： 测量数据对一般用户来说是不可能得到的。可能不会覆盖到你所感兴趣的路径 上。在网络高负载的情况下，不可能进行测量。大尺度网络上，存在测量和 测量数据收集的问题。将每个测量点测量得到数据组成一个端到端的路径数据 信息是很困难的任务。 ( 2 ) 所谓的“外在”方法，即假定没有节点的配合，通过端到端的测量来诊 断问题。目前已有许多实际工具来测量端到端的性能。如广泛应用p i n g 和t r a c e r o u t e 等诊断工具来确定i p 网络连通性、r o u n d t r i p 测量丢失及延迟信息、p a t hc h a r 和t r a c er o u t e 用来估计链路级的可用带宽，延迟，丢包率等。这些方法也存有潜 在的缺陷： i c m p 包在路由器里处理的低优先级，使测量得到的延迟不能代表正 常流量的延迟。有些工具需要一些特殊的假设，如路由节点不能存在防火墙， 需要存储与转发路由器等。 i c m p 包不能被网络管理员认可，经常被i c m p 包 过滤器过滤掉，以至不能进行响应。需要路由器的协作。 为了弥补传统网络测量方法的不足，国际上多个研究机构都在寻找其它途径 来研究网络的整体性能及其相互影响。将医学、地震学、地质勘探等领域成功应 用的成熟理论和方法应用于通信网络领域，衍生出了网络层析成像( ( n e t w o r k 9 基于网络层析的丢包率推断算法研究 t o m o g r a p h y ) 。它基于端到端的技术( e n d t o e n d ，e 2 e ) 来获取网络中那些不能 直接观察到的信息，通过发送多种探测包给指定的接收器，观察并分析接收器所 获得的数据，最后通过统计和推断来获得各种网络信息，包括链路级的参数和拓 扑结构等。从反问题求解角度来看，网络层析成像进一步还可以包括网络 o d ( o r i g i n - d e s t i n a t i o n ) 流量强度估计，它实际是对网络链路级( l i n k l e v e l ) 参数推 理的反过程，其目的就是从各链路级的测量数据推断路径级参数。这两者求解都 反映了网络层析成像反问题求解的本质，因此同样可以归纳到网络层析成像这个 主题下。 网络层析成像技术在没有内部节点协作的条件下，通过主动发包或被动收集 网络内部的有用信息，运用统计学方法推理网络中链路q o s 参数，如丢包率和 延迟分布等，识别网络拓扑结构和进行o d 流的估计。特别是被动的方法因为不 发送探测包，很适合在高负载的网络中使用。 2 2 2 网络层析的基本思想 网络层析主要是利用端对端测量的数据推测网络内部性能参数，克服了传统 网络测量方法需要内部各个路由合作的缺点。端对端测量只需要部分边缘节点参 与。边缘节点指布置在网络周围与网络相连，测量人员拥有一定权限的计算机或 者网络设备，探测源点和接收器都属于边缘节点，它们之间的部分属于网络内部 节点( 或链路) 。探测源点主要用于发送探测包和接收探测反馈信息，接收器用于 捕获探测包、记录或者反馈探测信息，探测源点和接收器在测量拓扑图中对应根 节点和叶节点。网络层析的基本思想是从探测源点发送多播探测包或性质类似的 单播探测包，同时记录探测包到达接收器的情况，然后根据探测包之间的相关性， 推导网络内部性能参数。 如图2 1 所示，我们只要通过网络边缘的一些终端就可以进行网络内部性能 参数的测量，这是网络层析和传统网络测量的最大区别，并不需要内部路由器的 合作，网络层析的应用范围较传统网络测量更广阔。 1 0 第二章月络目折丑丢包车推* 原4 2 2 3 网络层析的基本原理 图2 - 1 网络层析示意图 网络层析首先是把待测量的现实网络抽象成逻辑树状结构，然后通过发送源 节点发送一系列的探测包，记录接收器收到的探测包信息，最后利用探测包具有 的相关性推翘悟个链路的性能参数。下面通过一个简单的例子说明网络层析的基 本原理： 图2 _ 2简单二叉树 如图2 - 2 所示的最简单对称二叉树，假设我们要通过端对端测量推断链路的 丢包率。节点0 是发送源，节点2 ，3 是接收器。节点0 开始向所有的接收器发 基于网络层析的丢包率推断算法研究 彳= 嘲01 _ 1 眩2 m l 1 ( 22 】) 设q ，包，岛为图中各链路的传输成功概率的对数，乃为链路1 、链路2 、链路 芝茎竺 ：) ： 墨 。2 2 2 ， 2 ，表示在链路3 接收到探测包的情况下，节点2 收到探测包的条件概率， 则：l o g p 2 4 30 2 ，类似的可以定义l o g 乃| 2 ，补充上面的方程可得如下： l o g p 2 l o g p 3 l o g p 2 1 3 l o g p 3 1 2 1 1o l01 olo 0o1 ( 2 2 3 ) 这样就可以求解各个链路的丢包率，由于方程是超定的，可以采用最小均方 误差来估计o l ，0 2 ，0 3 。 一般情况下，网络层析可以看成一个求“逆问题”的数学模型： 少= a 臼+ ( 2 2 4 ) 式中y 代表网络层析测量得到的数据的对数向量，比如，在不同测量点获得 的探测包的数量或端对端的延时，该向量的长度有接收器的个数来决定；a 代表 了路由矩阵；日表示网络性能特征参数的对数向量，例如：链路丢包率。链路延 迟等；s 是噪声向量，表示测量数据本身的偏差造成在9 平均值附件的随即摆动。 一般情况下假设测量数据不受到噪声的影响，即s = 0 ，本文采用链路级网络 层析技术均假设测量数据不受噪声影响。所以网络层析技术可表示成下列线性模 1 2 第二章网络层析及丢包率推断原理 型： y = a x ( 2 2 5 ) 其中，y 表示在不同接收器接收到的探测包信息，x 表示所要测量的链路丢 包率，a 是路由矩阵，钗) = 1 表示节点i 和节点j 之间的链路相连， 钗) = 0 表示节点i 和节点j 之间的链路不相连。这样，网络链路丢包率的估计 问题便成为已知a 和y ，逆求x 。 2 2 4 网络层析技术的分类 网络层析技术按照探测方式，主要可以分为基于多播网络层析和基于单播网 络层析【1 9 】【2 0 】。 ( 1 ) 多播网络层析技术 多播网络层析技术是本文的主要研究方向。它通过探测源点发送一系列多播 探测包，探测包通过路由器复制和转发到达接收器，接收器记录探测包的可达性 及其传输时间。获得网络端到端的测量数据后，使用多播层析算法推导内部特征 参数。 多播测量技术具有发包少、流量小、测量范围广和测量精度高等优点。探测 包具有的强相关性能满足层析算法的要求，少量的探测包就可以达到较高精度； 探测源点发送一个探测包就可以覆盖树型拓扑的所有链路，对网络负载的影响很 小，增加接收器数量可以提高测量范围。但是它需要多播路由技术支持，目前的 i n t e r n e t 网络环境较难满足，这是多播层析技术发展的主要障碍。但是我们相信 随着i p v 6 协议的广泛应用与发展，i n t e r n e t 将会对多播路由提供更好的支持，多 播测量技术将会得到更为广泛的应用。 ( 2 ) 单播网络层析技术 在不支持多播路由的网络中可以使用单播测量网络内部特征参数。单播层析 技术使用类似p i n g 的工具在源点发送背靠背单播组，单播组包含对多个目的i p 的不同的探测包，组内探测包的时间间隔很短可认为是链路上连续的数据包，单 播组在某种程度上与多播性质类似。接收器在目的i p 节点或者在源点监测背靠 基于网络层析的丢包率推断算法研究 背单播到达情况和传输时间。最后利用单播层析算法推导网络内部结构特征。单 播网络层析技术应用范围较广，不需要多播路由支持等条件，但是为了模拟多播 特征导致单播探测包的数量增多，增加网络负荷，也增加了层析算法的复杂度。 当今的链路级网络层析成像研究主要集中在时延分布、丢包率和带宽的参数 推断上【2 1 】 2 2 】。本文重点研究丢包率参数推断。而路径级网络层析成像的研究 主要集中在o d 流量估计 2 3 2 4 】。 2 3 网络层析的丢包率推断原理 通过对网络边缘节点的端对端测量可以推导出链路丢包率。网络丢包率的信 息使网络工程师能优化网络设计，增强对网络控制，对于互联网服务提供商决定 网络代价策略也非常重要。因此网络链路级丢包推断是网络层析成像的重要研究 部分。 2 3 1 丢包率模型 介绍丢包率推断算法之前必须先建立相应的丢包模型。假设丢包模型中的网 络逻辑拓扑结构是已知的且不是动态变化的，首先需要将大型现实网络抽象为树 形的逻辑拓扑图，如图2 3 所示，节点o 是探测包的发送源，这里假设是单点发 送探测包，边缘的节点作为逻辑树的叶结点，它们的主要功能是接收发送源发送 的探测包，中间的节点均为不可测量的节点。要注意的是我们这里的节点只是一 个概括性的定义，因为节点可以是计算机、网络设备甚至一个子网，树的边是各 个节点之间的逻辑连接。 网络拓扑结构转换为逻辑树结构，树的节点为边缘测量机( 源点、接收节点) 和探测包经过的分支节点，边是逻辑节点之间的连接。从图中可以看到逻辑图的 边是实际网络的一条路径，包含一条或者多条链路： 1 4 第= 章耐络层析a 丢包牢推断原4 图2 - 3 网络拓扑结构转换为逻辑树结构 网络层析丢包模型主要包括贝努利模型( b e r n o u l l i ) 和马尔科夫模型 ( m a t k o v ) 等，如图2 _ 4 所示，“a ”代表探测包成功到达目的地的状态，“b ” 代表发生探测包丢失的状态，“p ”代表从状态a 转换到状态b 的概率t “q ”则 代表从状态b 转换到状态a 的概率。 p 1 - p ， 1 - q q 图2 丢包率模型 若，2 l 一矿时，图2 - 4 丢包模型就是简单的贝努利模型，p 就代表链路丢包 率，q 代表链路通过率，即不发生丢包的概率。当，1 一矿时，圈2 4 丢包模型 为简单马尔科夫模型。 本文中假设丢包模型为贝努利模型，用，= ( 一句表示一个网络逻辑测量树， 该逻辑树中v 表示物理节点集合，l 表示节点间的链路集合。根节点用o 表示， o v ，叶节点用r 表示，r e v 。( 力表示节点，到节点的链接。f 表示中间 节点，v k v 、r u o ) 。每个节点，除了根节点外都有一个父节点一0 ，节点的 奈 兀一 ，壤等 菇，秘扩 若，一酽拳 弋 转 驴。一毋。 ：器。 。j i 1 、 基丁网络层析的丢包率推断算法研究 子结点用改，) 表示，对于对称二叉树，节点珀勺两个子节点破，) = 彳( ，) ，矿( ，) ) 。 啄表示模型中数据包通过句，句的概率，瓦= 1 一啄表示k 链路上数据 包的丢包率。每次测量中探测包在节点的分布由随机过程j = ( 彤) ，矿 表 示，如果探测包到达节点k ，则以= 1 否则以= 0 。以= ( z ) ，月为探测包 在接收器的分布。在链路丢包率为嚷的条件下，探测包分布概率可表示为 以五力= 乞【j = 明。 2 3 2 丢包率推断的基本原理 网络中包存储的发送机制并不能保证各个数据包百分百到达目的地，当一个 数据包达到网络某一个路由器节点的时候，如果节点的缓冲区已经满了，该数据 将被某种规律丢弃，这是造成网络丢包率的主要原因之一。通过测量丢包率可以 确定网络负载或瓶颈链路，对于网络规划、流量控制等起积极作用，所以研究网 络层析丢包率推断具有重要意义。 丢包率推断的基本原理就是利用多播探测包之间的相关性推断链路的丢包 率。如图2 3 所示，节点0 是发送源，它负责发送一系列的探测包，假设发送源 发送的是多播探测包，然后根据实际情况收集全部或部分接收器( 如节点6 ，7 ， 1 2 ，1 3 等) 接收的探测包信息，如果节点6 或者7 有接收到探测包，则可以推 断节点2 肯定接收到探测包，如果节点6 接收到探测包，节点7 没接收到探测包， 则可以推断链路( 2 ，7 ) 发生丢包。设以句表示节点k 接收的探测包数量，则链路 ( 2 ，7 ) 的丢包率估计值就可以用1 一以6 & 7 ) n ( 6 ) 表示。当探测包的数量增加时， 丢包率估计值就越逼近真实值，同理可估计其他链路的丢包率。当发送的是单播 探测包时，因为单播探测包不具有相关性，我们利用单播包对来模拟多播探测包， 使单播探测包也具有一定的相关性，从而可以推断网络链路的丢包率。 2 3 3 丢包率推断算法的分类 本文主要研究多播网络层析技术的丢包率推断算法，根据测量方式的不同， 1 6 第二章网络层析及丢包率推断原理 可以分成多播算法和单播算法；根据统计推理算法的不同，可以分为极大似然估 计算法和快速算法。根据极大似然估计算法的不同，可以分为d e 算法和e m 算 法。 ( 1 ) 多播算法和单播算法 网络通信有两种方式：多播和单播。在多播通信中，源节点发送的探测包在 每个分叉路由器上可以自动复制并传送到各个分支链路。单播通信中每个探测包 都只能有一个目的地。多播算法利用多播探测包，因为多播的探测包相关性好， 所以丢包率的算法简单、精度也高。现在多播算法已经相对成熟。在一些不支持 多播的网络中只能用单播算法，单播是利用包对( b a c k t o b a c k ，b 2 b ) 单播测量 数据，它的原理就是利用单播模拟多播，算法和多播算法相似，但是因为单播的 探测包的相关性比多播弱，所以算法的复杂度较高，准确度比多播低。 ( 2 ) 极大似然估计算法和快速算法 网络层析一般使用极大似然估计( m a x i m u ml i k e l i h o o de s t i m a t o r , m l e ) 技 术推导丢包率，主要包括d e ( d i r e c t e s t i m a t o r ) m l e 和e m ( e x p e c t a t i o n m a x i m u m ) - m l e 两种算法，其中e m m l e 算法是最常用的一