（通信与信息系统专业论文）网络突发性丢包的时域特征参数估计.pdf

摘要 摘要 网络层析成像可以在无需中间节点协作的情况下，估计得到包括网络拓扑 结构在内的多种网络状态特征参数。近年来许多学者提出可以使用网络层析成 像的方法估计得到网络链路的时域特征参数，即获得反映网络链路在连续传输 多个数据包时链路性能特征的参数，它能够反映出网络流量的突发性。然而现 有的时域特征参数的估计方法全部是基于多播测量的，无法反映出在单播包在 网络中的运行特征。 文章针对当前链路丢包的时域特征参数估计方法的不足，提出了一种基于 单播的突发性丢包时域特征参数估计方法。主要工作包括：在分析比较当前 多种单播丢包率估计方法的基础上，提出采用探测包群作为探测包的发送方 法，来模拟多播条件下探测包发送的过程。深入研究了当前多播时域特征参 数估计的方法，发现借助探测包群内探测包之间良好的相关性，在基于探测包 群测量方法的基础上，可以成功的将基于多播的丢包时域特征参数估计方法应 用到单播条件下。将探测包群与时域特征参数估计方法结合到一起，提出了 基于探测包群的单播突发性丢包时域特征参数估计方法，并对连续传输概率、 平均丢包长度等丢包时域特征参数进行了估计通过n s 2 仿真实验，验证 了文中提出的估计方法的可行性与估计结果的准确性。仿真实验结果表明，基 于探测包群的单播的突发性丢包时域特征参数估计方法具有较高的准确性。 在单播网络突发性丢包时域特征参数的估计方法研究的基础上，文章还进 一步研究了基于单播的网络链路延迟时域特征参数估计方法。提出了基于探测 包群的单播链路延迟时域特征估计方法。主要思路是：通过发送探测包群，在 单播条件下模拟多播包的发送过程。利用探测包群良好的相关性，将基于多播 的延迟时域特征参数估计方法应用在单播条件下。对延迟样式概率、平均高 ( 低) 延迟长度等延迟时域特征参数进行估计。使用n s 2 对该估计方法进行 了仿真实验，并获得了良好效果。 关键词：网络层析成像，单播，突发性丢包，时延，时域特征参数估计 a b s t r a c r a bs t r a c t n e t w o r kt o m o g r a p h yc a l li n f e rd i v e r s i f i e dn e t w o r ks t a t u sp a r a m e t e r si n c l u d i n g t o p o l o g yw i t h o u tt h ec o o p e r a t i o no f i n t e r n a ln o d e s r e c e n t l y , i th a sb e e np o i n t e do u t t h a tl i n k - l e v e lt e m p o r a lp a r a m e t e r s p a r a m e t e r st h a tc a nr e f l e c tt h eb u r s t yn a t u r a lo f n e t w o r kt r a f f i cb yc h a r a c t e r i z i n gt h ep e r f o r m a n c eo fal i n kw h e ns u c c e s s i v ep a c k e t s p a s si t c a nb eo b t a i n e db yu s i n gn e t w o r kt o m o g r a p h y h o w e v e r , t h em e t h o d sf o r i n f e r i n gl i n k - l e v e lt e m p o r a lp a r a m e t e r sw h i c h h a v eb e e np r o p o s e da r ef a i l e dt or e f l e c t t h eu n i c a s tl i n k 1 e v e lt e m p o r a lc h a r a c t e r i s t i c sb e c a u s et h e ya le a l lm u l t i c a s t - b a s e d a i m i n ga tt h e s ed e f i c i e n c i e s ，an o v e lu n i c a s t - b a s e dm e t h o df o rb u r s t y l o s s t e m p o r a lp a r a m e t e r se s t i m a t i o nh a sb e e np r o p o s e di n t h i sp a p e r c o n t r i b u t i o n sa r e ： q ) b a s e do na n a l y s e so fp r i o rw o r kc o n c e r n e du n i c a s tl i n kl o s si n f e r e n c e ，w ea d v o c a t e u s i n gm u l t i p a c k e ts t r i p ea sp r o b i n gm e t h o d ，a i m i n g t os i m u l a t et h em u l t i c a s tc o n d i t i o n q p o i n t i n go u tt h a tm u l t i c a s t - b a s e dt e m p o r a lp a r a m e t e r se s t i m a t i o nm e t h o d c a l lb eu s e d i nu n i c a s tn e t w o r kb yu s i n gm u l t i p a c k e ts t r i p e ( 亘) b a s e do nt h ec o m b i n a t i o no f m u l t i p a c k e ts t r i p ea n dt h et e m p o r a lp a r a m e t e r se s t i m a t i o nm e t h o d ，w ep r o p o s e da n m u l t i p a c k e ts t r i p e - b a s e du n i c a s tb u r s t yl o s st e m p o r a lp a r a m e t e r se s t i m a t i o nm e t h o d ， e s t i m a t e dt h el o s st e m p o r a lp a r a m e t e r ss u c ha ss u c c e s s i v ep a s s a g ep r o b a b i l i t i e sa n d m e a nl o s s - r u n t h ef e a s i b i l i t ya n da c c u r a c yo fo u rm e t h o dh a v eb e e nv a l i d a t e db y s i m u l a t i o no nn s 2 f u r t h e r m o r e ，w ea l s od e v e l o p e da l lu n i c a s t - b a s ed e l a yt e m p o r a lc h a r a c t e r i s t i c s i n f e r e n c em e t h o d w ep r o p o s e dam u l t i p a c k e ts t r i p e - b a s e dm e t h o df o ri n f e r r i n gd e l a y t e m p o r a lp a r a m e t e r s w es i m u l a t et h em u l t i c a s tc o n d i t i o nb yu s i n g m u l t i p a c k e ts t r i p e ， a d a mm u l t i c a s t - b a s e dd e l a yt e m p o r a lp a r a m e t e r se s t i m a t i n g m e t h o di n t ou n i c a s t n e t w o r k ，a n di n f e rd e l a yt e m p o r a lp a r a m e t e r s ，s u c ha sp r o b a b i l i t i e so fa r b i t r a r yp a t t e r n s o fd e l a y , m e a nd u r a t i o no f h i g h - d e l a y - r u n so rl o w d e l a y - r u n so v e ru n i c a s tn e t w o r k n s 2 s i m u l a t i o ns h o w st h ev a l i d i t yo f t h ep r o p o s e dm e t h o d k e yw o r d s ：n e t w o r kt o m o g r a p h y ；u n i c a s t ；b u r s t yl o s s ；d e l a y ；t e m p o r a lp a r a m e t e r i n f e r e n c e 图目录 图目录 图2 1 网络拓扑结构示意图1 1 图2 2 一个简单的网络逻辑拓扑结构1 2 图3 1 一个简单的网络拓扑1 7 图3 2 丢包过程示意图1 8 图3 3 简单的二叉树2 0 图3 4 链路1 上传输概率的估计误差与连续传输概率的估计误差3l 图3 5 链路2 上传输概率的估计误差与连续传输概率的估计误差3 1 图3 6 链路3 上传输概率的估计误差与连续传输概率的估计误差3 1 图3 7 链路4 上传输概率的估计误差与连续传输概率的估计误差3 1 图3 8 链路5 上传输概率的估计误差与连续传输概率的估计误差3 2 图3 - 9 链路6 上传输概率的估计误差与连续传输概率的估计误差3 2 图3 1 0 链路7 上传输概率的估计误差与连续传输概率的估计误差3 2 图3 1 1 链路1 上连续传输概率的估计误差比较：3 3 图3 1 2 链路2 上连续传输概率的估计误差比较3 3 图3 1 3 链路3 上连续传输概率的估计误差比较3 4 图3 1 4 链路4 上连续传输概率的估计误差比较3 4 图3 1 5 链路5 上连续传输概率的估计误差比较3 4 图3 1 6 链路6 上连续传输概率的估计误差比较3 5 图3 17 链路7 上连续传输概率的估计误差比较3 5 图3 1 8 链路1 上平均丢包长度与平均传输长度的估计误差3 5 图3 1 9 链路2 上平均丢包长度与平均传输长度的估计误差3 5 图3 2 0 链路3 上平均丢包长度与平均传输长度的估计误差3 6 图3 - 2 1 链路4 上平均丢包长度与平均传输长度的估计误差3 6 图3 2 2 链路5 上平均丢包长度与平均传输长度的估计误差3 6 图3 2 3 链路6 上平均丢包长度与平均传输长度的估计误差3 7 图3 2 4 链路7 上平均丢包长度与平均传输长度的估计误差3 7 图4 1 延迟过程示意图3 9 图4 2 一个简单的网络拓扑4 1 图4 3 仿真网络拓扑钾 图4 - 4 链路1 平均高延迟长度与平均低延迟长度相对估计误差4 9 图4 5 链路2 平均高延迟长度与平均低延迟长度相对估计误差4 9 图4 6 链路3 平均高延迟长度与平均低延迟长度相对估计误差。5 0 图4 7 链路4 平均高延迟长度与平均低延迟长度相对估计误差5 0 图4 - 8 链路5 平均高延迟长度与平均低延迟长度相对估计误差5 l 图4 9 链路6 平均高延迟长度与平均低延迟长度相对估计误差5 l v 图目录 图4 1 0 链路7 平均高延迟长度与平均低延迟长度相对估计误差5 2 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 硌壅型嗍纠瘁伽3 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 一苕翱 签名：侈_ 导师签名：趔垒邋 日期：弘。年月罗e l 第一章绪论 1 1 研究背景及意义 第一章绪论 随着互联网的飞速发展，互联网在人们日常生活中的重要性越来越大。网络 性能对人们的工作、学习、生活的影响也与日俱增。这对于网络管理者来讲，如 何设计、控制和管理网络是非常重要的。要想做到这一点，就需要对网络的行为 和内部特性有很好的了解和掌握。网络的性能通过各种参数来体现，比如网络链 路的丢包率和时延，网络拓扑结构、o d 流等。网络链路性能的时域特征，即链路 在连续处理、传输多个数据包时所表现出的性能特征，可以从时域上反映出网络 的性能状态。能够了解掌握这些网络性能参数，特别是网络链路性能的时域特征 参数，可以更好的帮助我们设计j 管理和维护网络。 获得网络状态性能参数主要采用网络测量的方法，我们通常可以通过直接的 测量方式，即基于路由器的测量方法来获得这些参数。直接测量方法需要各个网 络节点路由器的协作才能完成测量工作。但是，要想实现各互联网运营商共同协 作测量网络参数是非常困难的。即便是在同一运营商的网络内，由于安全性等因 素，也不可能使全部路由器都协作测量网络参数i 同时，直接的网络测量方法通 常会极大地消耗每个节点的各种资源，比如带宽等，并增大每条链路的额外网络 流量开销。直接测量方法由于受到以上两个问题的严重困扰，它的应用受到了越 来越大的限制。 另一种网络测量方法是端到端的测量方法。端到端的测量方法是相对于直接 测量方法的，它主要在网络边缘的节点上收集相关数据。网络层析成像( n e t w o r k t o m o g r a p h y ) 技术可以在没有内部网络节点协作的情况下，通过端到端的测量方 法，通过数理统计和推理，来估计网络链路级的性能参数，为网络性能参数的估 计提供了一种新的方法，弥补了直接测量方法的不足，被认为是网络测量领域最 具发展潜力的测量方法之一，并成为国内外网络研究领域共同关注的前沿研究课 题。 网络层析成像( n e t w o r kt o m o g r a p h y ) 由医学、地震学、地质勘探等领域成熟 的理论和方法衍生而来0 1 1 2 1 3 1 ，它采用端到端的测量方法，主动发送探测包或被动 电子科技大学硕士学位论文 收集网络内部通信数据，通过在接收节点统计分析得到的观测数据( 网络路径级 性能参数) ，来统计和推断诸如时延、丢包率等各种链路级的网络性能参数。由于 采用的是端到端的测量方法，使得网络层析成像技术突破了直接测量方法所受的 限制：缺乏网络节点协作和网络流量负担的增加。在缺乏网络节点协作的情况下， 网络层析成像不但可以获得端到端的网络路径级( p a t h - l e v e l ) 性能参数，更可以 通过推理来获得网络内部链路( 1 i n k l e v e l ) 级的性能参数。同时该方法只需利用网 络中部分内部节点和终端节点就可以对整个网络的内部性能参数进行估计，一次 测量可以获得多条链路的性能参数，不需要巨大的节点资源，以较小的系统开销 来获取准确、实时的网络状态评估。 根据估计对象的不同，网络层析成像可以分为两大类：网络链路级 ( l i n k l e v e l ) 参数估计层析成像和网络o d ( o r i g i n d e s t i n a t i o n ) 流量估计层析成 像。网络链路级参数估计层析成像采用端到端的测量方法，即通过主动发包探测 或者被动收集网络内部实际通信数据的方法获得网络路径级观测数据，在此基础 上，利用统计学理论推导出网络链路级的估计参数【4 2 5 】。网络o d 流量估计层析成 像是网络链路级参数推理的反过程，主要是利用基于链路级网络测量数据来得到 路径级的估计参数，其目的就是从可测量得到的各链路级的测量数据中估计出路 径级的网络参数。 根据所考虑的网络内部行为的统计特性的不同，网络层析成像可以分为平稳 网络层析成像和非平稳网络层析成像两大类。在一般的平稳网络层析成像中，假 定网络链路参数的概率密度函数在测量周期内是固定不变的( 或者说是平稳的) ， 由测量结果所推测得到的各种性能参数的估计值，比如时延、丢包率等，是测量 周期内的平均值。尽管在平稳网络层析成像中，有着诸多对网络流量建模的方法， 以及多种为求解该模型所采用的估计方法1 6 , 1 2 , 1 7 1 8 ，2 2 之5 1 ，但是，由于本身在建模过 程中就没有考虑真实网络的时变特性，从而平稳网络层析成像的结果难以真实的 反映出网络链路参数的随着时间的变化情况。在非平稳网络层析成像中，利用随 机信号来模拟链路参数的变化情况，并且假设该随机信号是非平稳的，即概率密 度函数在测量周期内是时变的，从而能够追踪链路参数随时间变化而发生的波动， 更好地模拟真实网络环境【1 3 。1 6 1 。 根据网络通信方式的不同，网络层析成像可以分为单播网络层析成像和多播 网络层析成像。在网络中有两种通信方式：单播通信和多播通信。单播是指源节 点把一个数据包仅发给一个目的节点，而多播则是源节点把一个数据包发送给一 2 第一章绪论 组目的节点。多播包在传输路径上遇到分叉节点时会复制包，并分别向通往目的 节点的分叉链路发送。对于一次固定数目的测量，采用多播探测包的测量方法会 得到比采用单播探测包方法更多的测量数据，并且基于多播包探测的网络层析成 像有较好的可扩展性。然而，一方面某些网络可能不支持多播，另一方面单播包 相对于多播包有更大的灵活性。在当今网络中，大部分网络通信是采用单播方式 进行的。由于路由器采用不同的方式处理单播包和多播包，这使得基于多播的网 络层析成像方法无法估计得到单播包的运行特征。这些因素使得基于单播探测包 的单播网络层析成像成为当前网络层析成像的研究热点之一。 传统的平稳网络层析成像方法估计得到的结果通常是在测量周期内的均值， 无法作为时域特征参数来反映链路性能的时域特征。网络链路性能的时域特征参 数，比如网络链路的连续传输概率( 连续成功传输2 个数据包的概率) 、平均丢包 长度( 连续丢失数据包个数的平均值) 、平均高延时包长度( 连续处于高延时水平 的数据包个数的平均值) 等，可以反映出网络流量的突发性。能够感知网络链路 性能的时域特征参数，对于更加全面的了解和掌握的网络内部特性，更为精准的 感知网络状态有着极为重要的意义。在实际的网络应用及维护，如智能路由、瓶 颈链路检测、拥塞控制和v o l p 等对突发性丢包和延迟很敏感的网络应用中，获取 网络性能的时域特征参数往往更为重要。近年来，有关网络性能的时域特征参数 估计方法的研究开始出驯2 睨引，相关研究方法的提出丰富了网络层析成像理论， 提供了一种更为细致的观测网络性能参数的视角。 1 2 研究现状 马萨诸塞州大学的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 l c h a r a c t e r i s t i c s ) 【2 9 】项目一直致力于研究估计推导网络内部链路状态参数的方法， 提出了多播网络层析成像的数学模型，并论证了求解模型的算法，是多播网络层 析成像方法研究的先驱者，并刺激了网络层析成像领域的蓬勃发展 4 , 7 , 9 , 1 2 , 1 7 ，2 0 , 3 0 , 3 。 如今网络链路级参数估计层析成像的研究大多集中在网络链路时延估计和丢包率 估计上。根据网络通信方式的不同分为多播网络层析成像和单播网络层析成像。 1 2 1 多播网络层析成像 多播网络层析成像方法最早出现【4 1 。端到端测量方法的核心在于，利用端到端 3 电子科技大学硕士学位论文 路径上，数据包在传输过程中的相关性，来推断网络交叉路径中公共链路上的网 络性能参数。多播探测包则刚好具备这种相关性，在源节点发送大量的多播探测 包到多个目的节点，通过在目的节点观察收到的探测包的情况，来推断估计网络 内部链路的性能参数。在一般的网络拓扑结构中，利用最d , - 乘估计算法就能够 很容易的计算出超定方程的解，得到较为精准的估计值。问题在于，由于所使用 的超定方程具有病态性，导致估计误差不稳定，尤其是在大尺度网络层析成像问 题中，最小二乘法准确性较差，因此需要更为有效也更为复杂的算法来进行求解。 1 9 9 9 年，c a c e r e s 和n g d u f f i e l d 等人率先在多播网络中，利用端到端的测 量方法来估计网络链路丢包掣4 】。他们在多播探测包的强相关性以及各个链路的丢 包相互独立的假设条件下，使用独立的贝努力分布来描述网络链路丢包，并采用 最大似然估计进行求解，最终估计出各条链路的丢包率。并且可以据此来标识引 起服务降级的高丢包率链路。 2 0 0 2 年，l op r e s t i 和n g d u f 6 e l d 介绍了在多播网络中，采用端到端的测量 方法，如何对网络内部的延迟分布进行估计。他们讨论了可观测的端到端的路径 延迟，和所感兴趣的网络内部的链路延迟之间的关系，在延迟独立的假设条件下， 推导出了估计每条链路延迟的离散分布的算法，并具有较高的估计精度【2 0 1 。 多播测量的优势是效率高，可扩展性强。在测量过程中，n 个多播测量节点 所造成的额外的网络流量负担，即使是在最坏的情况下，也仅仅是n 的线性函数。 而在单播情况下，根据网络拓扑的不同，引起的网络流量负担至少是n 的二阶函 数。 尽管多播测量有着自己的优势，但是在实际情况中，由于可测量性和可控性 的限制，许多网络并不支持网络级的多播通信，大部分通信都是采用单播方式进 行的；另一方面，路由器通常采取不同方式来处理多播包与单播包，不同通信方 式下的网络链路性能参数并不相同。多播条件下估计得到的参数，无法反映出网 络在单播通信时的性能。因此，多播条件下的网络链路性能参数估计方法并不适 用于单播网络中。尽管单播测量比多播测量更为复杂和困难，但是出于实际应用 的考虑，单播网络层析成像的研究也是研究热点之一。 1 2 2 单播网络层析成像 单播网络层析成像研究的必要性和重要性很早就引起了人们的重视1 7 - 9 。早在 4 第一章绪论 2 0 0 0 年，m j c o a t e sa n dr n o w a k 发展了使用“背靠背”包做为探测包的方法， 利用背靠背包的相关性对单播网络丢包率进行估计。他们的方法使用了极大似然 估计和e m 算法【7 j 。 次年，n gd u f f i e l d 和f - l p r e s f i 等人将 4 1 0 7 的方法移植到了单播网络中， 通过发送探测包组的方法进行端到端的测量，来估计丢包率f 8 】。 背靠背包同样被用在了网络延迟的估计中。m c o a t e s 和r n o w a k 在【1 7 】中 提出了采用极大似然和e m 算法进行网络延迟估计的方法。同时他们还提出了基 于贝叶斯估计和粒子滤波器方法的延迟估计方法【1 3 】。t b u 和n d u f f t i e l d 在此 基础上，将基于极大似然估计和e m 算法的单播网络层析成像扩展为使用一般网 络e m 算法的方法，可以对一般网络拓扑进行参数估计【3 2 】。 背靠背探测包由于其良好的相关性，在单播网络层析成像中被广泛采用。2 0 0 3 年，m f s h i h 和a o h e r o 提出了使用混合高斯e m 聚类算法对网络延迟进 行估计的方法 6 1 。同年，y t s a n g ，m j c o a t e s 和r n o w a k 在延迟估计中使用 了m m p l e 方法【2 。他们的方法都是使用背靠背包，并且基于极大似然估计的方 法。 n gd u t t i e l d 则尝试了在简单网络中，用单播包作为探测包，使用二值网络 层析成像方法对网络链路参数进行估计，也取得了不错的效果【3 3 1 。g u od o n g 和 x i a o d o n gw a n g 在 2 5 1 q b 阐述了利用背靠背包作为探测包的单播网络层析成像方 法。这种方法使用贝叶斯估计的m c m c 方法。 n d u f f i e l d 和el p r e s t i 在背靠背包的基础上，提出了探测包组方法【8 】，提高 了探测包之间的相关性，使得估计精度有了提高。x i a 和y t s e ，d 将有限混合 指数模型e m 算法应用到延迟估计中! 矧。 单播网络层析成像的难点在于，单播探测包无法提供足够的信息，因此无法 建立链路级参数到路径级参数上的唯一映射。解决单播网络层析成像中的欠定性 问题非常关键。通过使用不同的探测包发送方法，可以搜集到更多的信息，这些 信息有助于帮助我们解决这个问题。背靠背包单播探测包对克服了欠定性问题， 它的基本原理是：两个紧密连续发送的包，在其通往各自接受节点的路径中，会 存在一部分公共链路。由于两个探测包一前一后紧密相连，因此在公共链路上他 们的延迟或者丢包是具有一定的相关性的。比如在丢包率问题中，包对中第二个 包在第一个包成功传输的条件下，也被成功传输的条件概率非常接近于1 。这个现 5 电子科技大学硕士学位论文 象已经在真实网络中经实验验证过的【3 4 】。探测包之间的相关性对于估计结果的精 度的影响是比较大的。为了加强背靠背探测包对的相关性，探测包组的方法做为 背靠背探测包对的改良被应用于单播网络层析成像中【9 】。三包组方法减小了由于包 对相关性不足而带来的估计误差，但是大量的探测包发送增大了网络的负担。探 测包群方法是在包组方法基础上提出的，并可以应用在单播网络的链路丢包率估 计中【3 5 1 。探测包群在保证了探测包之间相关性的前提下，不但大幅的减少了探测 包的发送数量，同时还扩展了联立方程组的方程数目，提高了利用最d x - - 乘法解 超定方程的求解精度。 经过多年的研究与发展，各种对网络性能参数进行数学建模的方法，以及相 应的求解算法不断的被提出，并在估计性能上取得了优异的表现，但是这些工作 通常着眼于算法的可靠性、复杂性和准确性上。各种估计方法所估计的对象并没 有得到较大的扩展。 1 2 3 链路性能参数时域特征参数估计方法的研究现状 近年来，在平稳网络层析成像中，有关网络链路性能的时域特征参数估计方 法的研究开始出现。一些研究表明，在多播网络中，通过在观测节点统计时域相 关的观测结果，可以对网络链路级性能的时域特征参数进行估计推断。 2 0 0 3 年，d o n gg u o 和x i a o d o n gw a n g 在 2 7 】中将链路丢包过程看作马尔可夫 过程，将链路分成“丢包”与“不丢包”两种状态，且两种状态间按照一定的转移概率 发生转换。并提到一条链路的平均连续丢包长度与转移概率之间的关系。文章较 早的从时域角度考虑网络链路性能特征。然而未对链路性能时域特征参数进行深 入研究。 d u f f i e l d 等人在多播条件下，对链路丢包和延迟的时域特征参数的估计方法进 行了深入的研究 2 6 , 2 8 ，并提出了估计链路丢包和时延的时域特征参数的估计方法。 2 0 0 7 年，v i j a ya r y a 、n g d u f f i e l d 和d a r r y lv e i t c h 在 2 6 】中对网络链路丢包的时域 特性估计方法进行了研究，给出了多播情况下采用端到端测量，基于子树分解 ( s u b t r e ep a r t i t i o n i n g ) 技术的丢包时域特征参数估计方法。并对丢包样式的概率 ( p r o b a b i l i t i e so f a r b i t r a r yl o s sp a t t e r n s ) 、平均丢包长度( m e a nl o s s - r u nl e n g t h ) 和丢 包长的分布( 1 0 s s - r u nd i s t r i b u t i o n ) 进行了估计。并指出，在已知平均传输概率和 连续两个包成功传输的连续传输概率的情况下，足以估计出链路的平均传输长度 6 第一章绪论 以及平均丢包长度。 2 0 0 8 年，他们又在多播网络中，对网络链路延迟的时域特征参数的估计方法 进行了研究。他们将延迟离散化成若干种延迟状态，根据需要将链路延迟划分成 “好”和“坏”两种状态，给出了连续多个数据包的“延迟样式 概率的估计方法。并 指出已知延迟样式概率，就可以对连续处于“好”状态( 或者“坏”状态) 的数据包的 平均数目，即平均高延迟长度与平均低延迟长度进行估计【2 8 1 。 以上研究工作扩展了网络链路参数估计的内涵，开辟了一个新的研究方向， 从传统的着眼于平均值的估计，扩展到了网络性能参数在时域上的特征参数的估 计，使得网络链路参数估计的估计结果能更细致的更全面的反映出网络的性能表 现，更加具有实际应用价值，并由此激发了本文的研究思路。 1 3 本文研究思路和研究内容 网络链路性能的时域特征参数对于实际的网络应用与管理有着非常重要的意 义。现有的链路时域特征参数估计方法都是基于多播的。在实际网络中，有些网 络可能不支持多播通信；在支持单播和多播的网络中，绝大部分的网络通信都是 以单播方式进行的。因此研究网络在单播条件下链路的时域特征是非常重要的。 由于当前网络中路由器是采用不同的方式来处理单播包与多播包的，这使得单播 包在网络中的运行特征与多播包的运行特征是不同的，单播与多播条件下网络链 路性能的时域特征也并不相同，所以基于多播的估计方法得到的结果不能用来描 述单播包的运行特征。 本文针对这一问题，将研究重点集中在基于单播的时域特征参数估计方法研 究上。在诸多体现网络链路性能的参数中，丢包率是和时延是非常重要的两个参 数，同时链路丢包和延时在时域上的特征，能很好的反映出网络流量的突发性。 本文主要研究了网络突发性丢包和延迟的时域特征参数估计方法。主要工作有： 在分析比较当前基于单播的链路参数估计方法的基础上，提出采用探测包 群作为探测包的发送方法，来模拟多播条件下探测包发送的过程。 深入研究了当前基于多播的链路时域特征参数估计方法，发现借助探测包 群内探测包之间良好的相关性，在基于探测包群测量方法的基础上，可以成功的 将基于多播的链路时域特征参数估计方法应用到单播条件下。 7 电子科技大学硕士学位论文 将探测包群与时域特征参数估计方法结合到一起，提出了基于探测包群的 单播突发性丢包时域特征参数估计方法，并对连续传输概率、平均丢包长度等丢 包时域特征参数进行了估计。 通过n s 2 仿真实验，验证了文中提出的估计方法的可行性与估计结果的准 确性。仿真实验结果表明，基于探测包群的单播的突发性丢包时域特征参数估计 方法具有较高的准确性。 1 4 论文的章节安排 本文一共分为五章，其内容安排如下： 第一章简要的介绍了研究课题的背景和意义，以及当前的研究现状，简要介绍 了本文的研究内容以及研究成果。 在第二章中介绍了网络层析成像的理论基础。简要介绍了在多播网络和单播网 络中，网络链路级参数估计的主要方法。 第三章讨论了详细论述了单播网络中网络链路丢包率的估计方法，讨论了网络 链路丢包的突发性，以及这种突发性在时域上的特征体现。并介绍了如何在单播 网络中，如对突发性丢包的时域特征参数进行估计的方法。使用仿真实验验证了 估计方法的性能。 第四章详细论述了单播网络中链路延迟的时域特征参数，以及在单播网络中对 平均低延时包长度的估计方法。使用仿真实验验证了估计方法的性能。 最后在第五章总结了全文，提出了未来的工作方向。 8 第二章网络层析成像基本理论 第二章网络层析成像基本理论 在大尺度网络中，终端系统不能依靠网络本身的协作来直接测量网络的性能 参数。直接测量方法有着非常严重的缺陷：在管理多样化的网络中，得到网络内 部节点的高度协作是很难实现的。这就促使了人们寻找一种新的，基于端到端的 测量来推断网络内部性能参数的方法这就是所谓的“网络层析成像 方法。 网络层析成像有多种分类方法。根据数据收集的方法可以把网络层析成像分 为基于主动发探测包的主动网络层析成像技术( a c t i v e n e t w o r k t o m o g r a p h y ) 和基 于被动方法的被动网络层析成像技术( p a s s i v e n e t w o r k t o m o g r a p h y ) 。根据网络的 通信方式的不同可以分为多播网络层析成像和单播网络层析成像。根据估计对象 不同可以分为网络链路级( l i n l ( 一l e v e l ) 参数估计层析成像和网络o d ( o r i g i n d e s t i n a t i o n ) 流量估计层析成像。 2 1 网络层析成像理论基础 网络层析成像方法中一个最基本的思想是端到端的测量。这使得网络层析成 像无需网络内部节点的协作，通过主动发送探测包或者被动收集信息，使用统计 学方法，就能推理出大尺度网络中所感兴趣的链路上的q o s 参数。网络层析成像 可以用线性模型来建模： y = a 秒+ 占 ( 2 - 1 ) 其中y 为端到端测得的数据；秒为待估计的链路性能参数向量，比如网络链路 的丢包率、时延、带宽等q o s 参数；a 代表路由矩阵，在网络拓扑结构已知的条 件下，a 也是已知的；f 为误差项，它可能是观测数据y 的加性噪声，也可能是p 的方差等等。这个线性模型可以描述平稳网络的网络行为。当考虑到实际网络的 动态本质时，可以用式( 2 1 ) 的时变形式来描述非平稳网络： 只= a ，包+ 岛 ( 2 2 ) 此时岔为链路性能的时变参数，有许多方法，如经典的卡尔曼滤波方法、m c m c ( m a r k o vc h a i nm o n t ec a r l o ) 方法等可以用来追踪岔的时变特性。 9 电子科技大学硕士学位论文 从数学和统计学的角度看，网络层析成像是比较典型的反问题。它首先使用 有参数的数学模型对网络的行为特性进行建模，然后通过观测得到的统计结果来 对模型的参数进行求解。我们如果把式( 2 1 ) 和式( 2 2 ) 中的口、p 看作网络模 型参数，把y 和) ，看作观测结果，那么线性模型( 2 1 ) 和( 2 2 ) 同样反映出了网 络层析成像的反问题本质。 通常，我们称反问题的求解过程为“反演 。在反演过程中，由于观测结果是 有限的，通常情况下，观测结果无法提供足够的反演所需的信息，同时还不可避 免的会受到噪声的干扰，这些因素使得反问题往往是多解的，也就是说，反问题 的解通常是不唯一的。 根据网络规模的不同，路由矩阵a 可以是几乘几的小矩阵，也可以是几千乘 几千的大矩阵。不同维度的a 使得方程( 2 1 ) ( 2 2 ) 的性质不同，从而有着不同 的解法。当a 满秩时，方程( 2 1 ) ( 2 2 ) 是超定方程，利用伪逆法或者最小二乘 法就可以轻松求解。在大尺度网络推理中，a 的维度非常大，使得( 2 1 ) ( 2 2 ) 是成为一个经典的反问题，其反演过程主要依靠s 的本质特征和a 矩阵本身，并且 通常无法直接求解，需要使用迭代算法进行求解。同时，不满秩的a 矩阵还会使 得方程( 2 1 ) 和( 2 - 2 ) 成为欠定方程，从而带来反问题求解中的病态性问题或者 不适定性问题。由于网络层析成像问题本身在端到端的测量过程中，观测结果所 带来的信息量相比于待估计的参数数量非常至少，使得反问题求解的过程当中还 要考虑唯一性的问题。 这些都是网络层析成像方法所面对的困难。当今诸多的网络层析成像方法提 出了各种方法来解决反问题求解过程中遇到的困难。比如通过特殊的探测包发送 方法以便在观察结果中获取更多的有用信息，从而增加方程组的方程数目，来提 高方程( 2 1 ) ( 2 。2 ) 的可辨识度【8 ，9 3 5 】；使用不同的数学模型，以及求解这些模型 相应的估计算法来减少s 带来的误差等。这些数学模型有：基于累积量生成函数 ( o m a u l a n tg e n e r a t i n gf u n c t i o n s ：c g f ) 模型【1 2 1 ，基于离散【1 7 2 2 1 或者连续【6 ，2 3 】概率 密度函数模型等。各种求解算法，包括广义逆的最t j 、- - 乘法【1 2 j ，极大似然法以及 求解极大似然值所用到的e m ( e x p e c t a t i o nm a x i m i z a t i o n ) 算法i r 7 】等都可以应用到 网络层析成像的求解过程中。 网络层析成像根据估计对象的不同，可以分为网络链路级( l i n k - l e v d ) 参数 估计层析成像和网络o d ( o r i g i n - d e s t i n a t i o n ) 流量估计层析成像。其中网络链路 1 0 第二章网络层析成像基本理论 级参数估计层析成像是网络层析成像中的一个重要内容，下面我们详细介绍网络 链路级参数估计层析成像。 2 2 网络链路级参数估计 网络链路级参数估计层析成像又可称作网络链路级参数推理、网络链路参数 估计，是网络层析成像的一个重要内容。弄清链路与路径的概念，会有助于我们 更好的理解链路级参数推理。链路是指两个节点，不经由其它节点而直接相连的 连接。路径则是由链路组成的，是两个节点，经由其它节点而相连的通路。在主 动网络层析成像中，我们选取一个网络节点作为源节点，发送探测包到一组目的 节点。在这种情况下，网络拓扑可以表示成一棵有向树的形式，如图2 1 所示。节 点0 可以看作源节点， 4 ，5 ，6 ，7 ) 为目的节点， 1 ，2 ，3 ) 为内部节点。从节点0 到节点 1 之间就是一条链路，从节点0 到节点4 之间的通路则是一条路径，这条路径由3 条 链路组成。我们假设，只能在边缘节点，即 o 4 5 ，6 ，7 ) 处来测量统计网络流量信息， 而无法从内部节点，即 1 ，2 ，3 处获取网络流量信息，这种测量方法即为所谓的端 到端测量方法，它不需要网络内部节点 1 ，2 ，3 ) 的协作即可完成测量。端到端的测 量结果得到的是路径级( p a t h l e v e l ) 的数据。我们通过各种统计方法，根据测得 的路径级的数据来推断出网络内部链路上的链路级( l i n k - l e v e l ) 性能参数，这就 是网络链路级参数估计层析成像的基本思想。 0 4 5 6 7 图2 1 网络拓扑结构示意图 电子科技大学硕士学位论文 当今网络链路级参数推理的研究主要集中在网络链路的丢包率、延迟分布、 带宽等q o s 参数的估计上。为了便于确定测量框架以及数学建模，在推理过程中 我们事先提出了若干关键的假设条件，比如，在整个测量周期内，假定网络拓扑 是已知且暂时不变的，即路由矩阵a 是已知且固定的。尽管在实际情况中并不如 此，但是网络路由矩阵的更新间隔一般以几分钟为单位，因此该假设是成立的。 在一般情况下，我们还假定网络链路的性能参数特征在空间上是统计独立的。在 时延估计中，还要假定源节点和目的节点在时间上可以获得同步。 下面分别在多播和单播网络中讨论网络链路丢包率的估计方法。 2 2 1 多播网络丢包率估计方法 多播测量的测量方法有效率高、可扩展性强、方法简单等优点。最早的网络 链路参数估计方法就是基于多播测量的估计方法。 我们考虑比较简单的二叉树网络逻辑拓扑结构，如图2 2 中所示，我们以节点 0 为源节点，节点2 和3 为目的节点发送一个多播探测包。该探测包将通过公共链 路1 ( l i n k1 ) 来到节点1 ，被复制并分别发往节点2 和节点3 。我们在目的节点2 和3 处观察探测包的到达情况：如果节点2 收到探测包，那么说明该探测包肯定 经由链路l 到达了节点1 ，此时如果节点3 没有收到探测包，则证明在链路3 上发 生了丢包。通过重复测量，链路2 和链路3 上的丢包率就可以被推测出来。 0 l i 2 3 图2 - 2 一个简单的网络逻辑拓扑结构 假设各个链路上的传输概率为 ，) ，易，ie2 ，3 为探测包在目的节点