（通信与信息系统专业论文）丢包率层析成像及在混合主动网下的实现.pdf

摘要 摘要 随着计算机网络的飞速发展，传统的网络测量方法面临着多供应商、多种异 构网络共存的测量问题，暴露出了它的严重不足。同时人们希望减小网络测量带 给网络的额外负载影响。网络层析成像无需内部节点协作，只在边缘节点进行信 息收集即可完成测量，受到广泛关注与研究。文中针对网络层析成像中的现有链 路丢包率估计方法存在的问题，提出了一套基于“包群+ 三叉树”的链路丢包率估 计方法，提高了方法的稳定性，极大地减少了探测包的数量。 目前采用的单播链路丢包估计的方法中，需要发送大量的探测包才能保证估 计的准确性。在实际网络特别是无线传感网络和无线自组织网络中，大量发送探 测包是不可接受的。本文在总结分析前人研究的基础上，提出了一些新方法及思 路，在保证估计精度的同时，减少了探测包发送数量。首先，在研究分析现存的 单播链路丢包率估计中采用的包队及三包组方法的基础上，提出一种新的探测包 群方法。包群的方法在保证估计准确性的情况下，大量减少了探测包发送的数目。 同时，提出一种三叉树的推导模型。三叉树模型对比传统二叉树模型能建立数目 更多的求解方程，从而提高利用最小二乘法解超定方程的精度和稳定性。三叉树 模型中，由于增加方程数目提高了解的精度，因而也可以发送相对较少数目的探 测包而得到一定估计精度的解。包群方法与三叉树模型都能在保证一定估计精度 的基础上，减少探测包的数目，从而减小由于发送探测包对网络流量和负载带来 的影响。在链路丢包率方程求解过程中，针对测量偏差及超定方程病态性问题， 使用最优化n e w t o n 反演法进行求解，提高了方程求解的精度，进而提高了最终 估计的准确性。 由于主动网在节点处具有可编程控制的能力，因而可以进一步提高网络层析 成像的效率，同时也可以提高估计结果的精度，增强使用实时性。由于主动节点 不可能迅速布置到整个网络中，混合主动网( 主动节点与被动节点并存) 将在今 后一段时间内存在于网络中，文中将链路丢包层析成像方法在混合主动网下进行 实现；考虑到主动节点与被动节点间的通信协作，设计利用移动代理实现了混合 主动网框架结构；文中还探讨了在主动网络环境下如何应用包群+ 三叉树模型，并 对其性能进行了仿真。 电子科技大学硕士学位论文 关键词：网络层析成像，链路丢包率估计，网络测量，混合主动网，o p n e t i i a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ec o m p u t e rn e t w o r k ，t h et r a d i t i o n a lc e n t r a l i z e d n e t w o r km e a s u r e m e n ts y s t e mi sc h a l l e n g e db yt h em e a s u r et om u l t i v e n d o ra n d m u l t i t e c h n o l o g yh e t e r o g e n e o u sn e t w o r ka n de x p o s e ss o m ed e f i c i e n c i e s a tt h es a l r l e t i m e ，p e o p l ew a n tt o d e c r e a s et h ee x t r al o a dt a k e nb yt h em e a s u r e m e n t n e t w o r k t o m o g r a p h yi san e wm e t h o do f n e t w o r km e a s u r e m e n t i td o e s n tn e e dt h ec o r p o r a t i o n o ft h ei n t e r i o rn o d e s ，a n dw i l lc o m p l e t et h et a s ko n l yb yc o l l e c t i n gm e s s a g ef r o mt h e e d g e t h i sm e t h o dd o e s n t h a sh i g hd e m a n do nh a r de q u i p m e n t s w i t ht h e s e c h a r a c t e r i s t i c s ，n e t w o r kt o m o g r a p h yi sc a l l e dt h en e wm e a s u r e m e n ti nc u r r e n tn e t w o r k i t san e wt e c h n o l o g yf o ri n f e r r i n gt h el i n kp a r a m e t e r s ，n e t w o r kt o p o l o g ya n d o d ( o r i g i n - d e s t i n a t i o n ) f l o w s i th a ss o l v e d t h e p r o b l e mi n t r a d i t i o n a ln e t w o r k m e a s u r e m e n tt h a tn e e d e dt h ec o o p e r a t i o no ft h ei n t e r i o rn o d e sa n dh a r dt or u ni n h e t e r o g e n e o u sn e t w o r k i nt h i st h e s i s ，i tm a k e sa ni n d e p t hr e s e a r c ho nt h er e l a t e d t e c h n o l o g yo f i n f e r r i n gt h el i n kl o s s e si nu n i c a s tn e t w o r k t h ec u r r e n tm e t h o d so fi n f e r r i n gl i n kl o s s e si nu n i c a s tt o m o g r a p h yn e e dt os e n d m u l t i p l ep r o b ep a c k e t s w h e r e a s ，t h el a r g e n u m b e r so fp r o b ep a c k a g e si sn o t a c c e p t a b l ef o rs o m en e t w o r ke n v i r o n m e n t ，e s p e c i a l l yi nw i r e l e s ss e n s o rn e t w o r k w e w i l lp r o p o s eo u ri d e a sa b o u tt h ep r o b l e md e s c r i b e da b o v e ，a n dg i v es o m en e w a l g o r i t h m sb a s e do u r i d e a s f i r s t l y , a i m sa tt h ec h a r a c t e r i s t i c sa n dw e a k n e s so f t h es t r i p e so f p a c k e t s ( w i t hn o d e l a yb e t w e e nt r a n s m i s s i o no fs u c c e s s i v ep a c k e t sw i t h i nas t r i p e ) ，w ei n t r o d u c e sa n e w l i n k - l e v e ll o s se s t i m a t em e t h o dc a l l e dm u l t i p a c k e ts t r i p e t h i sn e wm e a s u r e m e n tc a n d e c l i n et h en u m b e ro f p r o b ep a c k e t sa tt h eb a s i co f i n s u r i n gt h ea c c u r a c y s e c o n d l y , b a s e do nt h et w o l e a f t r e em o d e ，w ep r o p o s e dt h et h r e e l e a f t r e em o d e t h i sn e wm o d ec a nb u i l dm o r ee q u a t i o n st h et w o l e a ft r e e w ec a no b s e r v eg o o d e s t i m a t ea c c u r a c yw i t hi t i no t h e rw o r d s ，w ec a l ld e c r e a s et h ep r o b ep a c k e t sa n dg e t a c c u r a t el i n k l e v e l1 0 s se s t i m a t e s b o t ht h em u l t i - s t r i p ep a c k e ta n dt h r e e - - l e a f 臼e em o d ec a r lg e tf r u i t f u li n f e r e n c eo f i i l i v 主要符号表 q o s r t t i s p o d c t m i n c c b r h a n s n o s e e a a a n e p h a n h m a m c t s c l d b o s a r p a c l 主要符号表 主要英文缩写及其全称列表 q u a l i t yo fs e r v i c e 服务质量 r o u n dt r i pt i m e 往返时间 i n t e m e ts e r v l c e sp r o v i d e r o r i g i n - d e s t i n a t i o n c o m p u t e r i s e dt o m o g r a p h y m u l t i c a s t i n f e r e n c eo fn e t w o r k c h a r a c t e r i s t i c s c o n s t a n tb i tr a t e h y b r i da c t i v en e t w o r ks y s t e m n o d e o p e r a t i o ns y s t e m e x e c u t i o ne n v i r o n m e n t a c t i v e a p p l i c a t i o n a c t i v en e t w o r ke n c a p s u l a t i o np r o t o c o l a c t i v en o d eo f h y b r i da w i v en e t w o r k m o b i l ea g e n to f h y b r i da c t i v en e t w o r k m a i nc o n t r o l l e r t a s ks c h e d u l e r c o d el i b r a r y d a t a b a s e o u t p u ts c h e d u l e r a g e n tt r a n s f e rp r o t o c o l a g e n tc o m m u n i c a t i o nl a n g u a g e v i l 网络服务提供者 源到目的节点流量 计算机层析成像 网络性能的多播推导 固定比特率 混合主动网络系统 节点操作系统 执行环境 主动应用 主动网封装协议 混合主动网下主动节点 结构 混合主动网下移动代理 主控器 任务调度队列 代码库 数据库 输出调度队列 移动代理传输协议 移动代理通信协议 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名： 麴：蔓日期：z 一衫年月1 9 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 到杰导师签名：趟鱼亟 日期：2 0 。g 年月1 5 日 第一章绪论 1 1 研究背景意义 第一章绪论 随着互联网的飞速发展，网络已成为人们生活中不可缺少的一部分，同时网 络结构也发生了根本的变化。随着网络规模的增长和网络体系结构的复杂，i n t e r n e t 的控制机制和行为特征日趋复杂并且难以理解。为了更好的设计、控制和管理网 络，必须高速感知网络状态参数( 包括拓扑结构、流量、时延、丢包率等) 和网络状 态参数的动态变化，从而找出网络上存在的瓶颈，并及时优化网络配置、加强网 络管理、提高网络的稳定性和利用率、改善服务质量等。 同时，随着网络技术的发展，用户对网络资源的需求不断增长。然而，计算 机网络规模和复杂度的不断扩大导致网络资源分配不均，从而造成网络拥塞增大、 网络性能降低、服务质量( q u a l i t yo fs e r v i c e ，q o s ) 下降等。要解决这些问题就需 要将业务流量合理分配在现有网络拓扑结构上，优化网络资源的使用。要达到这 些目标就需要对网元设备的性能参数进行提取和分析。要改善和提高网络性能， 也需要更深入地认识现有i n t e r n e t 的一些内在机制。而认识事物的第一步就是要测 量它，并用数字表示出来。由此，网络测量这个新研究领域应运而生。 1 1 1 网络测量概述及研究意义 网络测量通常是指利用有效的网络探针和工具软件，对网络各项运行指标及 参数进行测量，以提取各种关于网络健康状况的参数指标。从概念上讲，网络测 量是收集和分析网络协议运行性能的手段，可以帮助人们搞清网络( 局域网或广域 网1 有时不能正常工作的原因。从研究实质上看，网络测量是获得第一手网络行为 指标和参数的最有效手段。在对网络进行测量和测试的基础上建立网络行为模型， 并用模拟仿真方法搭建从理论到实践的桥梁，是理解网络行为有效的途径。 网络测量有不同的分类方、法【2 】： ( 1 ) 按照测量过程中测量设备是否主动发送探测包可分为主动测量和被动测量 两类。主动测量是基于往返时间r t t ( r o u n d t r i p t i m e ) 钡i j 量，测量装置主动向网络 发送探测包，然后根据返回的参数来判断网络现有状况，这些参数包括响应时间 和丢包率等。主动方式会增加网络的负荷并引起网络的拥塞，但是可以了解整个 电子科技大学硕士学位论文 网络的行为，获得端到端的信息。在被动测量方式中，测量装置( 可以是端节点或 路由器等中间节点) 被动地根据一定需求来监测和采集网络上特定链路、特定时段 的流量。被动测量很难获得对网络整体的了解，也很难对网络终端到终端之间的 性能做出准确的分析，但是不会增加网络的负荷。 ( 2 ) 按照测量系统所处的位置，又可分为基于路由器的测量、端到端的测量以 及路由器协助的测量【3 】。 网络测量的内容很广泛，包括网络拓扑发现，时延、丢包率、带宽测量，网 络距离测量，路由器调度策略和“瓶颈”缓冲器容量测量，以及路由器流量监测。 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 的管理。这就 使得网络测量成为越来越迫切的需求。然而现存的网络测量方法存在以下限制及 不利因素【4 】： ( 1 ) 目前广泛使用路由器测量方法，也就是常说“内在”的方法，在网络节点或 者网络节点之间直接主动或者被动测量，这方法有许多潜在的限制：对一般用 户是不可能得到的。可能不会覆盖到你所感兴趣的路径上。在网络高负载 的情况下，不可能进行测量的。大尺度网络上，存在测量和测量数据收集的问 题。将每个测量点测量得到数据组成一个端到端的路径数据信息，是很困难的 任务。 ( 2 ) “外在”方法，即假定没有节点的配合下，通过端到端的测量来诊断问题。 目前已有许多实际工具来测量端到端的性能。如p i n g 和t r a c e r o u t e 等诊断工具广 泛用来确定口网络连通性、r o u n d t r i p 丢失及延迟信息；p a t h c h a r 和t r a c e r o u t e 用 来估计链路级的可用带宽，延迟，丢包率等。这些方法也存有潜在的缺陷：i c m p 包在路由器里处理的低优先级，使测量得到的延迟不能代表正常流量的延迟。 有些工具需要一些特殊的假设，如路由节点不能存在防火墙，需要存储与转发路 由器等。i c m p 包不能被网络管理员认可，经常被i c m p 包过滤器过滤掉，以至 不能进行响应。需要路由器的协作。 正是由于网络朝着分布化，非协作，异质管理和基于边缘控制的方向演变， 导致这些传统工具的使用受到限制，研究人员致力于新的网络测量方法的开发研 究。 第一章绪论 1 1 2 网络层析成像概述及研究意义 为了弥补传统网络测量方法的不足，国际上多个研究机构都在寻找其它途径 来研究网络的整体性能及其相互影响。将医学、地震学、地质勘探等领域成功应 用的成熟理论和方法应用于通信网络领域，衍生出了网络层析成像( n e t w o r k t o m o g r a p h y ) 5 1 。它是基于一种端到端的技术来获取网络中那些不能直接观察到的 信息，通过发送多种探测包( p r o b ep a c k e t ) 给指定的接收器( 服务器) ，观察并分析接 收器所获得的信息，通过统计和推断来获得各种网络信息。网络信息包括链路级 的参数和拓扑结构等。从反问题求解角度来看，网络层析成像进一步还可以包括 网络o o ( o r i g i n d e s t i n a t i o n ) 流量强度估计，它实际是对网络链路级( l i n g - l e v e l ) 参数 推理的反过程，其目的就是从可测量得到的各链路级的测量数据中估计出路径级 的网络参数。这两者求解都反映了网络层析成像反问题求解的本质，因此可以归 纳到网络层析成像这样同一个主题下。 目前，c t 技术在医学工程上已经成一套完善的理论和方法，广泛应用于医学 临床诊断和病理研究。与此同时在医学工程上己成功应用的一些成熟的理论和方 法还被应用于射电天文学、雷达探测、电子显微镜图形学、无损探伤、地震学、 地质勘探等非医学领域【7 】【8 【9 】。 网络层析成像技术在没有内部节点协作的条件下，通过主动发包方法或被动 收集网络内部有用信息的方法，运用统计学方法能够很好的推理出大尺度网络上 链路q o s 参数，如丢包率和延迟分布等，识别网络拓扑结构和进行o d 流的估计。 特别是被动的方法因为不发送探测包，很适合在高负载的网络中使用。 目前网络层析成像主要由两个部分组成【6 】，第一部分为测量数据的收集，其中 主要研究如何收集网络内部的相关有用信息，第二部分为统计推理，它主要是根 据收集的数据来发现网络内部的信息和规律。根据数据收集的方法可以把网络层 析成像分为：基于主动发探测包的主动网络层析成像技术( a c t i v en e t w o r k t o m o g r a p h y ) 和基于被动方法的被动网络层析成像技术( p a s s i v en e t w o r k t b m o 孕a p h y ) 。 网络通信有两种方式：单播与多播。在单播通信中，每个数据包只发向一个 而且仅仅是一个目的节点。在多播通信中，源节点可以有效的把每个包发向一组 目的节点，在每个分叉点的路由器上，多播包被复制和延着分支路径传送出去。 同样网络层析成像可以分为多播网络层析成像和单播网络层析成像。 网络链路级( l i n k l e v e l ) 参数推理是指：从可测量得到的路径级( p a t h l e v e l ) 数 电子科技大学硕士学位论文 据中估计出网络链路级的参数，比如丢包率，延迟分布等。如果网络中节点能够 协作的话，网络链路级的参数能从直接的测量中估计出来，执行类似功能的工具 有很多，比如p a m c h a r ( p c h a t ) ，t r a c e r o u t e ，c l i n k 和p i p e c h a r 等，它们通过发送i c m p 包 来估计网络链路级的丢包、带宽。但是许多路由器不能产生或者响应i c m p 包或者 以非常低的优先级来处理i c m p 包，因此出现网络链路级参数推理方法，使得参数 估计不依赖节点的协作或者最小化对节点协作要求。 当今的链路级网络层析成像研究主要集中在时延分布、丢包率和带宽的参数 估计上。更一般的问题则扩展到其他参数，比如可用带宽和服务原则的重建等。 在网络层析成像技术中有许多关键的假设，用于决定测量的框架和数学模型。 这些假设为：路由矩阵a 假定为已知的，而且在整个测量时间内都是固定的。 虽然网络路由矩阵是定时更新的，但是这些变化是以几分钟为间隔发生的。当然， 路由矩阵的动态特性限制了能用作收集和推理的数据的数量；目前大多数方法 通常都是假设每个链路上的性能特征是相互统计独立的，在许多例子中也将它们 假设为暂时平稳的；在链路级的网络时延层析成像中，一般也假定在源节点和 目的节点的时间是同步的。 1 1 3 混合主动网的研究意义 随着网络技术的发展， i n t e r n e t 用户正在急剧的膨胀，用户对网络所能提供 的服务种类和服务质量有各自不同的要求，这对现有的i n t e r n e t 提出了挑战。未来 的i n t e m e t 将是一个多服务的平台，支持实时通信和复杂的多用户服务【1 0 。这对网 络管理也提出了更高的要求。 为了解决这些问题，加之对未来网络模型的预测是一件非常困难的事情， d a r p a 研究协会于1 9 9 4 年提出了主动网络的概念口”。d a r p a 认为，主动网络是 解决目前i n t c r n e t 问题的可行方案，是未来网络发展的方向之一。事实上，主动网 络技术本身并不是一个全新的概念，它早已应用于现有网络中。 主动网络为传统网络中存在问题的解决提出了新的途径。主动网络打破传统 网络的存储一转发模式，将程序代码的运行嵌入其中，使得网络具有一定的计算 能力，并且这种计算可以是基于用户或应用的，从而使网络服务的定制成为可能。 建立一个类似因特网的全新的主动网络是不切实际的，如何利用现有的因特网来 传输携带程序代码的主动包，使得主动包能顺利通过传统节点到达主动节点，在 主动节点上得以识别并执行是当前主动网研究的内容之一【1 2 】。 4 第一章绪论 传统网络仅仅负责在各终端之间传输数据，网络是被动的完成各项数据转 发的任务，即便是在面向对象及分组交换网络中，计算也只是在执行协议及处理 分组头时出现，对数据本身并没有进行操作【”】。也就意味着在路由器，交换机等 交换设备处，仅仅实现选路，转发等功能，不能对数据自主的操作。这就是所谓 的“被动”网络。被动网络中，由于投资，网络设施的限制，新的技术难于运用于其 中；另外，新标准的制定运用是个漫长的过成，它总是落后于用户的需求，很难 快速的满足各类用户。而现今网络的迅速发展使得对网络的要求加强，需要它有 很强的处理能力，对数据不仅仅完成转发的功能。要对数据进行处理。例如：防 火墙，w e b ，移动代理等。 随着i n t e r n e t 的发展，基于t c p i p 的传统网络将面临许多挑战。这些挑战主要 集中在对网络异构性、服务质量、移动性、扩展性和安全性的支持十分乏力，特 别是在扩展性和服务质量上。因此主动网络被d a r p a 提出作为解决目前i n t e m e t 问题的可行方案。虽然主动网络体系结构的研究还处于起步阶段，在安全性、性 能、互操作性等方面不尽人意，但它代表了下一代网络的发展方向。 s a r p a 主动网研究组的k c a l v e r t 对主动网的主要功能构件进行了抽象的描 述，在其实现方式上留有相当大的余地，成为参考模型【1 。为了是主动网具有向 后兼容性，允许主动网中存在非主动节点及非主动包。 主动网络具有传统网络无法比拟的优越性，但建立一个象i n t e m e t 这样的主动 网络的可能性太小。如果能在传统网络中加入主动设备，让主动设备所需的主动 数据能在传统网络中自由传输，就可以实现主动网络与传统网络的有机结合。这 种新的网络环境就是混合主动网环境( h y b r i d a c t i v e n e t w o r ke n v i r o n m e n t ，h a n e ) 。 在体系结构上，主动网络本身要求建立一个全新的网络体系结构，但考虑到 网络发展是一个漫长的进化过程，现实中的网络己被广泛接受了，这些设施花费 了大量的资金和人力，我们不能完全抛弃这些设施。目前，主动网络还处于实验 进化阶段，实际为人们能够使用到的只能是建立在传统网络上的主动网络，一方 面使用户真正能够使用到主动网络的服务，同时能够做一些主动网络的实验，为 未来的主动网络提供理论和实践的基础。可以预测，在今后很长一段时期内，对 主动网络的研究仍然会基于i p 网络，要在全网范围内建立真正意义的主动网络体 系结构在短期内是不可能实现的。因此，混合主动网环境将在很长的时间内存在。 电子科技大学硕士学位论文 1 2 研究现状 1 2 1 网络层析成像研究现状 无论是国内还是国外，在网络层析成像技术领域，研究的重点还是在估计方法 上【l ”。根据测量目标的不同，当前网络层析成像主要是在链路时延及链路丢包上 进行研究【l “。下面将介绍网络层析成像在链路时延及丢包率估计方面的一些研究 现状。 马萨诸塞州大学的m f n c 【1 7 】工程是多播网络层析成像方面研究领先者，刺激了 当今这个领域研究工作的发展【1 8 】 1 9 【2 们。并且l op r e s t i ，n gd u f f i e l d 等提出了基于 多播端到端测量的内在队列延迟分布算法【2 ”，描述了估计链路延迟分布的p m f s 函 数，使其估计结果逼近真实值。 在时延估计方面，c o a t e sa n dn o w a k 提出了单播包对思路，通过发送一组包对 到边缘节点，利用最大似然算法，推导链路的时延特性 2 ”。同时，使用基于内在 延迟估计的序贯蒙特卡洛方法来追踪时变网络延迟行为f 2 ”。 网络丢包率信息使网络工程师能优化网络设计，增强对网络控制，对于 i s p s ( i n t e m e ts e r v i c ep r o v i d e r s ) 决定网络代价策略也非常重要【2 4 】。因此网络链路级 丢包估计作为网络层析成像重要研究部分，国外许多研究机构在这方面进行了大 量研究2 5 1 。r c 矗c e r e s 【2 6 】等首先采用最大似然估计方法来估计多播树的链路丢包率， 这种方法能很好的对链路级丢包进行估计，也存在不足。第- - i n t e m e t 中仍然有很 大一部分并不支持网络级的多播；第二路由器处理多播与单播是不同的，通过多 播包观察到的网络内部特性与通过单播观察到的有很大的不同，因此多播估计不 能很好反映实际网络特性【2 ”。 针对多播探测方法的缺陷，m a r kc o a t e s 和r o b e r tn o w a k 28 】等提出使用单播背 靠背探测包对( 即包对中包先后在极短的时间内发送) 来测量路径的丢包，然后通过 求解最大似然方程来估计链路的丢包率。t i a nb u 2 9 等把该方法扩展到非树状单播 网络中，进行链路丢包估计。由于单播包对在传输过程中不能完全保证同时被丢 弃或是正确传输，即不能完全达到多播传播的效果，文献【3 0 】中提出采用三包组 ( t h r e e p a c k e ts t r i p e ) 的方法来解决这一问题。包组中的探测包在严格队尾丢包的情 况下，将以极大的概率同时被丢弃或是被正确传输，产生近似于多播的效果。 文献【3o 】的方法虽然提高了方法的精度，但还存在以下两个缺陷：( 1 ) 实际网络 中，有时为了提高网络层析成像方法的精度和稳定性，需要发送较多数量的探测 第一章绪论 包，这将加大网络的负载，对于有些网络影响将非常大，对于a dh o c 网络特别是 无线传感网络将是不可接受的；( 2 1 现有的网络层析成像方法所能建立的方程数目 有限，不能得到高精度，稳定的解。在本文中提出一种基于探测包群的单播链路 丢包率估计的方法，这种方法能够显著减少探测包发包数量，减小网络负载。同 时，建立三叉树模型，进步减少探测包数量，增加丢包率估计所使用的方程数 目，进而提高求解的精度和稳定性。 1 2 2 主动网研究现状 主动网络从提出以后，就得到了许多研究机构的重视，但其研究还主要集中 在理论阶段。目前主动网的研究主要是由美国国防高技术研究计划局d a r p a 资助 和管理的 3 u ，在该机构有关主动网的资助项口列表中列举了5 6 项口前正在进行的 研究，其中涉及了主动网研究的各个方面，资助的范围囊括了从公司到大学，从 计算机软件到通信网络等几乎所有与信息技术相关的研究单位和人员。由此不难 看出美国军方对这一研究领域的关注程度。在d a r p a 及部分公司如i n t e l 和s u n 等的赞助下，m i t , 宾夕法尼亚大学、华盛顿大学、哥伦比亚大学、加州大学、b b n 等学校和组织己经开展了主动网络的研究。其中比较著名的是：m i t 计算机科学 实验室的主动网络传输系统吲( a c t i v en e t w o r kt r a n s p o r t a t i o ns y s t e m ，a n t s ) ； b b n 公司的项目s m a r t p a c k e t ” ；哥伦比亚大学研究的主动网络项目n e t s c r i p t 等。 目前，国内对主动网的研究还基本处于起步阶段，但已经引起了有关方面的 注意【1 ”。例如，国家“十五”，“8 6 3 ”计划中，“信息技术领域通信技术主题课题申 请指南”的“新一代信息网创新技术研究( 开放课题) ”中将主动网技术列为其中一个 方向，其它支持主动网研究的基金项目或受资助单位还有：国家自然科学基金( 上海 交大、北邮国家重点实验室、国家“9 7 3 ”信息技术与高性能软件基础规划项目( 东南 大学) 、国防科研基金( 电子科大光线传输与通信系统技术实验室) 。南京大学、西 安交通大学等单位或组织己开发出自己的主动网原型系统。 1 3 本文研究主要内容及意义 本文在对现有网络层析成像的研究基础上，提出了套基于“包群十三叉树” 的链路丢包率估计方法。针对传统链路丢包率层析成像方法中存在的探测包数目 过大的问题，设计提出了一种新的探测包群方法，同时提出一种新的三叉树模型。 在三叉树模型中，更能有效的发挥探测包群的优势，大量减少所需发送的探测包 电子科技大学硕士学位论文 数量。使用三叉树模型将比传统二叉树模型建立更多的链路传输概率方程，从而 提高最小二乘法解超定方程的精度，得到的链路丢包率估计更加准确。这些改进 与提高在一些网络环境中，特别是在无线传感网络与无线自组织网络中，将显得 十分重要与有意义。 文中研究的另外一点是，考虑到现有网络环境下，主动网不可能迅速完全布 置到传统网络中去，同时一些网络环境不适合或是不能布置成主动网，就必然形 成主动网与传统被动网络长期共存的混合主动网络环境。混合主动网下也需要对 链路丢包率及时延信息进行收集。在混合主动网下进行网络层析成像研究具有更 多的优越性及必要性。因此设计了混合主动网下网络层析成像的实现。网络层析 成像研究的内容众多，文中主要研究了单播链路丢包率的实现方法。同时，考虑 要使研究的链路丢包率层析成像方法具有实用性，也需要考虑在混合主动网下的 实现。 1 4 论文结构与内容安排 本文共分六章。第一章概述网络测量、网络层析成像方法以及混合主动网的 研究意义，网络层析成像是网络测量中使用的一种新方法。给出了网络测量的几 种常用方法及关键技术；重点介绍了网络层析成像的的研究内容、方法及研究现 状；给出了混合主动网的体系结构和目前的一些研究现状。第二章研究了网络层 析成像中时延估计及链路丢包率估计，在分析当前网络层析成像中使用三包组方 法进行单播链路丢包率估计的基础上，提出包群+ 三叉树模型一种单播探测包群的 方法，研究分析了包群方法大量减少了探测包的发包数量，并使用o p n e t 进行了 仿真验证。另一方面，针对传统二叉树推导模型，提出一种新的三叉树网络模型， 分析三叉树模型能增加传输概率方程个数，提高最小二乘法解超定方程的精度， 也使用o p n e t 搭建仿真环境进行了验证。第三章中针对包群+ 三包组方法中测量 误差及超定方程病态性问题，提出使用最优化n e w t o n 反演法进行求解。并通过仿 真进行分析。第四章分析了现有主动网体系结构，重点介绍混合主动网的节点结 构、主动包的传输处理流程及封装模式，提出了一种新的利用移动代理实现的混 合主动网结构。新结构中考虑在主动网与传统被动网络进行信息交互协作时，利 用移动代理来实现。给出了混合主动网中主动节点的结构、处理流程，并对如何 利用移动代理进行信息交互进行了详细描述。第五章主要介绍了利用移动代理实 现的混合主动网结构中进行链路丢包层析成像研究。分析了新的体系结构中进行 墨二雯丝堡 层析成像研究的优越性，并对整个单播链路丢包率估计的测量过程进行了详细介 绍，画出了流程图。最后通过仿真验证新结构提高了估计精度。第六章总结全文 并给出了需要进一步研究的问题。 电子科技大学硕士学位论文 2 1 相关技术 第二章链路丢包率层析成像研究 2 1 1 网络层析成像基础 大尺度网络推理的问题根据数据获取类型和感兴趣的性能参数来区分，为了 区分这些问题，先定义链路与路径的基本概念，链路但i n k ) 是指两个节点之间没有 中间节点直接相联系，而且可以是单向或者双向的。路径( p a t h ) 是指两个节点之 间相联系，中间有一个和多个链路，信息从源节点发送到目的节点沿着一条路径， 该路径一般要经过好几个节点。v a r d i 是第一个研究大尺度网络推理问题的，由 于网络推理与医学层析成像类似，所以把它称为“网络层析成像”( n e t w o r k t o m o g r a p h y ) 。网络层析成像可以分为两类：基于端到端的路径级网络流测量来 得到链路级的参数估计 2 7 】 2 8 】 3 0 1 ；基于链路级网络流测量o d 路径级网络流强 度估计 3 5 】。 网络层析成像可以用线性模型来建模，该模型用如下式子表示： y = a 0 + 占 ( 2 - 1 ) 式中y 为可测量的向量，比如：根据在网络不同测量点测量到的发包数目所 确定的路径传输概率，端到端的延迟等。p 为包参数向量，比如每条链路加妨的 平均延迟，包成功传输概率的对数等。a 为路由矩阵，占为测量数据y 产生的加性 噪声，也可能是0 关于其均值产生的随机偏差。 ( 2 1 ) 式的线性模型可以进一步表示为时变的形式： y ，= 4 0 , + q ( 2 - 2 ) 式中t 表示为时间。这时估计的问题涉及到时变参数的追踪，实际上，( 2 2 ) 式表示的时变情节更能反映实际网络的动态本质。有几种方法用来尝试追踪非平 稳网络行为，包括经典的卡尔曼滤波器方法。 第二章链路丢包率层析成像研究 ( 2 - 1 ) ( 2 2 ) 估计问题是反问题的典型例子。反问题在信号处理领域【3 ”，统计学 3 7 】和应用数学【3 8 】具有很多的相关文献，这些反问题的求解主要依靠噪声s 的本质 特征和a 矩阵。由于它不能直接求解，所以一般需要用迭代算法来求解。一般来 说a 不是满秩，所以导致了方程的可辨识性问题，要么能解决参数线性联合的问 题，要么能用统计方法引入正则性和促使可辨识性。在大多数网络层析成像问题 中，噪声向量占为逼近的独立高斯，泊松，二项式，多项式分布。当噪声向量占为 独立高斯分布时，递归线性最小二乘法能用与共轭，g a u s s - s e i d e l 与其他迭代方 程的求解。当噪声向量占为泊松，二项式，多项式分布时，更多的统计方法比如 说加权最小非线性二乘法，利用e m 算法的极大似然法，利用m c m c 算法的m a p 算法进行方程的求解。 2 1 2 网络链路级( l i n k - l e v e l ) 参数推理研究 网络链路级旺i n k - l e v e l ) 参数推理是指：从可测量得到的路径级( p a t h l e v e l ) 数 据中估计出网络链路级的参数，比如丢包速率，延迟分布等。当网络中节点能够 协作的话，网络链路级的参数能从直接的测量中估计出来，执行类似的功能的工 具有很多，比如p a t l l c h 砥p c h a r ) ，t r a c e r o u t e ，c l i n k 和p i p e c h a r 等，它们通过发送i c m p 包来估计网络链路级的丢包，带宽。但是许多路由器不能产生或者响应i c m p 包或 者以非常低的优先级来处理i c m p 包，因此需要发展出网络链路级参数推理方法使 得链路级参数估计不依赖于节点的协作或者最小化对节点协作要求。 链路级网络层析成像研究主要集中在延迟分布，丢包率和带宽的参数估计上， 更一般的问题扩展到其他参数比如可用带宽和服务原则的重建。马萨诸塞州大学 的m i n c 工程是多播网络层析成像方面研究领先者并且刺激了当今这个领域研究 工作的发展。 在网络层析成像问题中有许多关键的假设，用于决定测量的框架和数学模型， 这些假设为：路由矩阵爿假定为己知的，而且在整个测量时间内都是固定的，虽 然网络路由矩阵是定时更新的，但是这些变化是以几分钟的间隔发生。当然，路 由矩阵的动态特性限制了能用收集和用作推理的数据的数量；目前大多数方法 通常都是假设每个链路上的性能特征是相互统计独立的，在许多例子中也假设暂 时平稳的；在链路级的网络延迟层析成像，一般也假定在源节点和目的节点的同 步时间是可以获得。 网络通信有两种方式：单播与多播。在单播通信中，每个包只向一个而且仅 电子科技大学硕士学位论文 仅是一个目的节点。在多播通信中，源节点可以有效的把每个包一组目的节点。 在每个分叉点的路由器上，多播包被复制和延着分支路径传送出去，同样链路级 的网络层析成像可以分为多播网络层析成像和单播网络层析成像。 2 1 3 多播链路丢包率估计 随着i n t e r n e t 的不断增大及多样化，其内部的性能越来越难以进行测量任何 组织仅仅能对网络内部很少部分的节点进行管理，而基于经济原因，各个组织又 不可能共享网络内部数据。m i n c ( m u l t i c a s t i n f e r e n c eo f n e t w o r kc h a r a c t e r i s t i c s 网 络性能的多播推导) 是解决这一问题的一种方法。通过使用端到端的多播测量方法 来研究多播接收端观察到的数据，推导出链路级的丢包率及延迟特性。这些测量 方法不依赖于对网络内部节点的管理，而仅仅是使用目的主机接收到的信息来推 导。 对网络内部给定节点丢包率的推导，可以直接从经过该节点的源到目的接收 端的路径上包的情况来推导。如果这个包到达了目的接收器，那么它一定先到达 内部节点。在已经到达给定节点后部节点的条件下，就可以推导出给定节点的成 功传输概率。通过有效的算法可以推导出丢包率，时延分布，时延变化及逻辑上 的多波拓扑结构。 基于多播探测的网络层析成像技术是网络层析成像技术的第一种方法。假如 一个多播探测包从源节点0 发送被目的节点2 而不是被目的节点3 接收。则马上 能决定在链路，发生了丢包。通过进行这样的重复测量，那么链路2 和3 上丢包 速率能够得到估计。这些估计和测量能够用来进行链路j 上丢包速率的计算。 2 3 3 图2 - 1 网络的逻辑拓扑结构 第二章链路丢包率层析成像研究 为了举例说明，口，口：，a ，表示为网络中链路1 ，链路2 ，链路3 的传输成功概率 的对数。p ：1 ，表示在节点2 与节点3 同时收到多播探测包数目与在节点3 收到的多播 探测包数目的比率。因此，p ：| ，是在链路3 探测包成功的条件下，链路2 的经验传输 成功概率，它能提供口：一个简单估计。以同样的方式定义p 3 p i , i = 2 , 3 节点f 接 收到的多播探测包的数目与发送到节点i 多播探测包的数目的比值。 l o g l o g l o g l o g 110 1ol 01o 001 引 ( 2 3 ) 口0 蓑d , - 乘算法估计很容易能够用来计算方程的超定系数。能够从大尺度 网络层析成像问题中衍生出有效的复杂的算法【3 9 。 2 1 4