（通信与信息系统专业论文）约束网络层析成像及其在主动网中的仿真实现.pdf

摘臻 摘要 随蔫誊联弼酌飞速发鼹，网终鹅梅选在发生深刻变化，要成功设计、控制葶羹 管瑷网络，就嚣装了解和掌握网终豹内部特性。冀中链路孵延帮链路丢镪搴楚羹 要的网络性能参数。由予网络目益向着大趔化、异构化、分布化发展，邋过唐按 遴行网络测量的方法，采获褥网终内部链潞的时鬣稠丢包零参数靛变撂越来越困 难，网络屡析成像方法俸为一种通过端到端的测登数据来推断网络链路性能参数 的技术j e 裁为研究的热点之一。 现裔的网络屡析成像方法在 由计模型上不加入任何的约束信息，我们称为非 约泵网络层析成像。蓑估计算法大帮以似然方法为基础，在一定的假设葶掰理想的 清况下，能够获得较好的估计效采。然雨炎际的情况是狠复杂的，测量结果较理 想状况存在一定程度的偏麓，这种偏差可能会使得链路性能参数酌储计群出现较 大酶扰动。本文霭趱翁翦柬霹络屡轿成像技术秘掰鄢分两络节点瀚协彳乍瞧，收集 链路的网络性能约康信息，建立约涞最优化估计模型，很好地提高了非约束网络 瑟掇成像继诗算法筋稳定戆察求辫精度。 链路时延估计嫩网络屡析成像的重要研究内容之一。本文以链路时延估计为 蒌点，深入耱磷交了约索测络瑟辑成豫链潞薅延熬估计算法，详缁奔绥了算法静 推导求解过程以及o p n e t 网络仿真模型的实现，并对仿真结果进行了细致地分析 逡较。本文还讨论了终束嬲络凄褥藏豫丢像搴兹 蠢计算法及其实瑷，透过傍窦效 果说明将约束最优化估计模型推广剡约束黼络层析成像的其它研究部分是完全可 行鲍。 主动掰煨有对包流自定制计算的特点，被看佧今后刚络技术发展的重要趋势 之。在主劝网终强境下，鑫于主麓翳提供了节悫可编程瓣戆力，霾两瓣络滋耩 成豫勰题可以变貉爨方便豢接，约采网络瀑橱残像豹售息收集问磁也可以剥藤主 魂鼷终鹣特点寒瓣决。本文提出了一耱基予主动网瓣终衷瓣终滢掇残缳灞鬟槿蘩， 它态分利周主动网主动性、移动性葶瑾协 乍拣豹优点，不仪熊够合蠼地组织端到端 懿溅量蹙务，瞧戆够磐裁遗| | 雯集终藤售惠释溅量镶怠，透过努发诗簿经务裂各个 协 乍节点，减少引入的网络负载流凝，为约束最优化估计算法提供了有效应用的 基础秘锈蜜霹嚣翡测量方褰。本文遂行了纂予主动礴魏约寨瀚络鼷辑残豫镶潦瓣 延估计，仿真实验证明了方案的可行性和有效性。 ， 摘要 关键字：网络层轿成像，约束网络瑟柝成像，链路时延，链路丢包率，主动网 尹一 a b s t r a c t a b s t r a c t t h ek n o w l e d g eo fn e t w o r kp a r a m e t e r sa l l o w sn e t w o r ke n g i n e e r st oi m p r o v et h e n e t w o r kd e s i g n ，c o n t r o la n do p e r a t e i ti sh a r dt og e tt h ei m p o r t a n tp a r a m e t e r ss u c ha s l i n kd e l a ya n dl o s sr a t ed i r e c t l y , b e c a u s et h ei n t e r a c th a sb e c o m e sm a s s i v e ，d i s t r i b u t e d a n dh e t e r o g e n e o u s n e t w o r kt o m o g r a p h yi sn o wah o t s p o tf o ri n f e r e n c et h ei n t e r n a ll i n kd e l a ya n d l o s sr a t ew i t ht h ee n d - t o e n dm e a s u r e m e n td a t a w ec a l lc u r r e n tn e t w o r kt o m o g r a p h ya s u n c o n s t r a i n tn e t w o r kt o m o g r a p h yf o ri t sn o ta d d i n ga n yc o n s t r a i n tc o n d i t i o na n da l lo f t h e mn e a r l ya r eb a s e do ns o m el i k e l i h o o d a l g o r i t h m u n d e r s o m e p e r f e c ta n d h y p o t h e t i c a lc o n d i t i o n ，i tw o r k sw e l l u n f o r t u n a t e l y , t h er e a ls i t u a t i o ni sc o m p l i c a t e d a n dt h e r ei ss o m ed i f f e r e n c eb e t w e e nt h ea c t u a le l l d - t o e n dm e a s u r e m e n td a t aa n dt h e i d e a lo n e s f u r t h e r m o r e ，i tm a k e st h ee v a l u a t e dr e s u l t sf l u c t u a t i n gb a d l y _ i nt h i sp a p e r ， w ei n t r o d u c ean e wc o n s t r a i n tn e t w o r kt o m o g r a p h yt os o l v et h i sp r o b l e m ，w h i c h a d d ss o m ec o n s t r a i n ti n f o r m a t i o nc o l l e c t i n gw i t l lt h eh e l po fs o m ep a r t i a li n t e r n a ln o d e s t ot h em o d e l i nf a c t ，t h ec o n s t r a i n tn e t w o r kt o m o g r a p h yc a ni m p r o v et h ep r e c i s i o no f e v a l u a t e dp a r a m e t e r sb e t t e rt h a nt h eo t h e rm e t h o d e s p e c i a l l y , b o t ht h ec o n s t r a i n tl i n kd e l a yi n f e r e n c ea n dc o n s t r a i n tl i n kl o s sr a t e i n f e r e n c ea r e i n v e s t i g a t e d i nc h a p t e r2a n d3 ，w ei n t r o d u c eh o wt o b u i l dt h e m a t h e m a t i c a lm o d e lf o rt h e s ep r o b l e m sa n dt h es t e p st ot h ee s t i m a t e df i n a l r e s u l t s + b e s i d e st h i s ，i nc h a p t e r5 ，h o wt os i m u l a t et h ea l g o r i t h m su s i n go p n e tt o o l si s a l s o d i s c u s s e d c o m p a r i n g w i t ht h er e s u l t s i t p r o v e s m a t a p p l y i n g c o n s t r a i n t o p t i m i z a t i o nm e t h o dt on e t w o r kt o m o g r a p h yi sv e r ye f f e c t i v e a c t i v en e t w o r ki sr e g a r da st h em o s tp o t e n t i a lt e c h n o l o g yi nt h ef u t u r e ，a n di tc a n b ec u s t o m i z e dt oc o m p u t et h ep a c k e tf l o w i nt h ea c t i v en e t w o r kc i r c u m s t a n c e ，i ti s c o n v e n i e n tt oc o l l e c tt h em e a s u r e m e n td a t aa n dc o n s t r a i n ti n f o r m a t i o n ，a n do r g a n i z et h e m e a s u r e m e n tt a s kb e c a u s eo fi t s p r o g r a m m a b l e a n d c o o p e r a t i v ec a p a b l i l i t y b y d i s t r i b u t et h ec o m p u t i n gt a s kt ot h ec o o p e r a t i v en o d e s ，i tc a nd e c r e a s et h en e t w o r k a d d i t i o n a ll o a dh e a v i l yi nt e r m so fb a n d w i d t ha n dr e s o u r c e sa n dm a k e sn e t w o r k t o m o g r a p h ye a s yt oa p p l y f i n a l l y , w ed e m o n s t r a t ei t sp e r f o r m a n c eu s i n ge x t e n s i v e i i i a b s t r a c t o p n e ts i m u l a t i o n sa n di t sf e a s i b i l i t ya n de f f i c i e n c ya l ep r o v e db ye x p e r i m e n t s k e y w o r d ：c o n s t r a i n tn e t w o r kt o m o 掣a p h y ，l i n kd e l a y , l i n kl o s sr a t e ，a c t i v en e t w o r k i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得豹研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已i 经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我同工作豹同志对本研究所傲的任何燹献均己在论文中作了明 确的说明并表示谢意。 签名：塾坠 强期：湘6 年6 月6 丑 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部f 1 或机构送交论文豹复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复利手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：囱垒导师签名：丛坠幽 日期：乃d 6 年月多e t 第一章绪论 1 1 研究背景及意义 第一章绪论 网络时延和丢包率是网络性能的重要指标。作为关键的网络信息，这些信息 对于因特网服务提供商而言，在测试服务质量参数以及评估链路性能，进行网络 异常检测等方面具有重要意义。不仅如此，对于动态的路由算法和流量传输协议 的改进也是重要的参考依据。当网络拓扑发生变化，甚至遭受破坏时，及时掌握 各种性能参数，包括拓扑结构、流量、时延、丢包率，以保证网络的可靠、高效、 稳定运行也至关重要。 获得这些网络性能参数，通常是采用直接测量的方式。但是，随着网络向大 型化、异构化、分布化发展，使得i n t e m e t 结构日益复杂。如果直接测量网络中每 条链路的时延或者每条链路的丢包率，需要各个不同域内的通信节点的充分协作， 这样的协作是相当复杂的。而对于不同的因特网服务提供商而言，基于商业性的 考虑，通常只会提供部分节点来完成一定程度的协作工作，使得测量结果可能不 会覆盖到测量者所感兴趣的链路上。因此，要获得全面而准确的测量往往就很困 难。 实际上，采用直接的网络测量方法，由于总是针对各条链路进行测量，这就 导致每个节点会极大地消耗各种资源，每条链路将引入大量额外的网络流量开销， 严重地限制了直接测量方法的广泛应用。另外，在大尺度网络中，大量的测量数 据需要传回到测量发起节点，这种集中处理的方式也为网络带宽带来了不小的负 荷。 在这样的应用背景下，当前迅速发展的网络层析成像技术为网络性能参数的 估计提供了一种新的方法。 层析成像( t o m o g r a p h y ) 技术也称计算机层析( 断层) 成像( c o m p u t e r i z e d t o m o g r a p h y ) 技术，简称c t 技术，是本世纪7 0 年代初首先在医学工程上得以成功 应用并蓬勃发展起来的一项新技术。它的出现不仅促进了现代医学技术的发展， 而且还促进了计算机的应用，对电子学、数学、生物电子学及生物基础理论的研 究和发展也起了积极的推动作用。 国际上多个研究机构都在寻找不同于传统的直接测量的其它途径来研究网络 电子科技大学硕士学位论文 的整体性能及其相互影响，利用医学、地震学、地质勘探等领域成熟的理论和方 法应用于通信网络领域，衍生出了网络层析成像( n e t w o r kt o m o g r a p h y ) 1 1 2 1 ”， 它基于端到端的技术来获取网络中那些不能直接观察到的信息，通过发送多种探 测包给指定的接收器，观察并分析接受器所获得的数据，最后通过统计和推断来 获得各种网络信息，包括链路级( l i n k l e v e l ) 的参数和拓扑结构等。 总的来说，网络层析成像技术，由于测量的是端到端的数据，该技术比较直接 测量每条链路的方法，无需大量增加网络负荷。同时，一次测量能够获得多条链 路的性能参数，即使在网络的某个局部遭受灾害不能正常工作的情况，所受的影 响也远远较直接测量的方法更小。该方法只需使用网络中的一组节点，包括部分中 间网络节点和终端节点，即可完成对整个网络各种状态参数及其变化的推测，获 得整个网络状态的精确描绘。这样就可以有效的克服直接测量方法要求每条链路 协作的缺点，不需要消耗庞大的节点资源，极大地提高网络状态评估的准确性和 及时性，并减少测量的系统开销。 由于完全是采用端到端的测量，在估计方法上也未使用任何的网络约束信息， 也可以将这些网络层析成像方法称为非约束的网络层析成像。现有的网络层析成 像都是这种类型，即非约束网络层析成像。根据采用不同方法的探测包，它们可 以分为基于多播探测包和基于单播探测包两种。比较这两种不同类型的探测包技 术，对于一次固定数目的测量，多播测量提供了比单播更多的数据，并且基于多 播包探测的网络层析成像有较好的可扩展性。然而，一方面某些网络可能不支持 多播，另一方面单播包相对于多播包有更大的灵活性，这两个主要的因素使得基 于单播探测包的链路级参数估计成为当前网络层析成像的研究热点。在本文中， 采用的网络探测包也是基于单播的。 在理想情况下，非约束网络层析成像尽管能够有效的获得测量值。然而由于 估计方程通常都具有病态性，使得估计方程总是超定方程。这样，目前的算法对 不能很好地收敛到真实值，且估计值不稳定，这是非约束网络层析成像通常都是 采用似然算法为基础的固有原因造成的。我们研究发现，在网络域当中，还有许 多的辅助信息可以收集加以利用，这些约束信息可以通过一定的网络技术比如移 动代理和主动网等网络技术，采集部分链路待估计参数的确定性范围或者确定值 来获得，也可以通过其它的途径来确定，比如传输链路的性能参数限制范围等等。 在通过统计学反问题求解链路级参数的过程中，将这些信息作为约束条件，可以 使得估计结果更加精确。引入约束信息到估计算法当中，与非约束网络层析成像 技术相比，主要带来以下几个优点： 2 第一章绪论 似然函数为多峰的情况，约束条件有助于迭代算法避免陷入局部最小值， 提高解的精度和稳定性，同时可以避免迭代进入边界极大值，导致所谓边界效应。 由于测量误差和求解系统方程的病态性，导致了参数解的多解性，采用约 束条件，则可以有助于排除不符合约束条件的解。 约束条件有利于确定迭代初始值，可以减少迭代的步数，从而减少计算时 间。 约束条件更有助于提高解的稳定性，即在存在测量偏差的情况下，能够尽 可能的减小估计值的波动。 因此，本文提出了一种新的约束网络层析成像方法来改善估计解的稳定性。 约束网络层析成像是指通过将网络约束信息引入到估计算法，以此作为网络层析 成像反演过程中的先验信息的方法。在本文中，我们以较为复杂的方式来收集约 束信息，即基于一定的网络技术之上从各个协作节点收集。这种全新的约束方法 比较非约束网络层析成像而言，引入了更大的主动性，但也要求基于一定的有利于 信息收集的网络技术之上，并且需要网络中部分节点一定程度上的协作。这就要求 网络主动性，协作性更强。主动网作为一种全新的网络体系结构，为约束网络层 析成像提供了良好的技术平台。因此，结合约束网络层析成像的特点，利用主动 网技术的主动性、移动性、灵活性，就可以为约束网络层析成像进一步应用奠定可 靠的基础。 主动网络( a c t i v en e t w o r k ) 是美国国防部高级研究计划署( d a r p a ) 为解决网 络技术的快速发展带来的问题于1 9 9 4 。1 9 9 5 提出的“3 主动网中传输的分组不仅可 以携带用户的数据，而且可以携带用户定制的一段程序代码，使得分组在经过网络 节点转发处理时，可以通过运行分组携带的代码，来修改、存储或重定向网络中的 数据流，为分组的转发和处理提出建议。这样，由于增加了网络中间节点的计算能 力和可编程能力，使得网络能够根据应用和用户的需要定制分组转发的行为。 主动网是一种全新的网络体系结构“3 ，它具有移动代理技术的优点，而又更具 强大的灵活性和处理能力，在约束网络层析成像中，不仅可以为网络约束信息的收 集提供良好的平台，由于其更底层的处理能力，使得在处理网络级的测量时更加高 效。因此，我们考虑通过利用主动网技术的可编程特性、协作性构建一套基于主动 网的约束网络层析成像测量系统，通过建立基于主动网技术的约束网络层析成像 估计模型，来估计链路级的性能参数。 在主动网下，应用约束网络层析成像，当前还缺乏一个高效的测量框架的支 持，因而无法构建全局的测量域，收集测量数据。要保证约束网络层析成像技术 电子科技大学硕士学位论文 发挥全局动态监控，快速感知网络状态的优势，还需要一个有效的测量框架来完 成测量的组织进行、测量任务的分发、测量数据的收集等工作，这方面的内容也 是目前网络层析成像技术研究的重点，本文将对这个方面的内容进行讨论。 1 2 研究方向和现状 约束网络层析成像的研究内容同非约束网络层析成像一样，目前根据估计对 象的不同分为链路级参数估计约束网络层析成像，网络拓扑估计约束网络层析成 像，网络o d 流估计约束网络层析成像三个大的方面。 本文的研究主要集中在链路级参数估计约束网络层析成像方面，包括链路级 时延估计约束网络层析成像和链路级丢包率估计约束网络层析成像。研究工作由 以下两个部分组成： 第一部分为统计推理算法的研究。根据收集的测量数据来发现网络内部的信 息和规律。主要涉及提出新的约束反演估计模型，即链路级时延约束网络层析成 像算法和链路级丢包率约束网络层析成像算法。 第二部分为信息收集框架的研究。这个框架应该为各种信息的收集提供可行 方案，包括探测数据的收集和网络内部的相关链路参数约束信息的收集等。另外， 框架应该同时适用于链路级时延估计约束网络层析成像以及链路级丢包率估计约 束网络层析成像方法。 1 2 1 估计方法的研究现状 时延估计方法的研究现状 在网络链路级参数估计方面，研究重点集中在估计延迟分布和丢包率，更一 般的问题可以扩展到其他参数比如可用带宽和服务原则的重建。 在国际上，马萨诸塞州大学l op r e s t i 和n g d u f f i e l d 等学者在2 0 0 2 年提出了 基于多播端到端测量的内在队列延迟分布估计算法“1 ，使网络层析成像的估计结 果与实际值更逼近。由于i n t e r n e t 对多播协议的支持是有限的，他们的方法要求使 用多播探针，这就需要网络提供多播会话的协作，这样该方法的使用受到了较大的 限制。 莱斯大学c o a t e s 和n o w a k 发展了单播“包对”探针的机制。这种机制通过发 送一组紧密相关的“包对”到边缘节点，通过这组“包对”之间的相关性，进一步 利用最大似然( m a x i m u ml i k e l i h o o dv i ae x p e c t a t i o nm a x i m i z a t i o n ，m l e m ) 算法， 4 第一章绪论 推导链路的时延特性。他们还尝试了基于内在延迟估计的序列蒙特卡洛方法，这 个方法能够追踪时变网络延迟行为”1 。不仅如此，还采用了多个背靠背“包对”应 用于单播网络层析成像，取得了不错的估计效果。 gl i a n g ”1 和y o l a n d at s a n g 。1 分别提出了基于极大似然估计器的内在延迟 估计算法，但是在迭代求解极大似然值的时候，前者采用了e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 算法，后者用了m m p l e ( m u l f i s c a l em a x i m u mp e n a l i z e dl i k e l i h o o d e s t i m a t o r ) 算法，两者都取得了良好的估计效果。 密歇根大学m e n g - f us h i h 和h e r o 发展出基于链路延迟累积量生成函数 ( c u m 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 ) 方法“”，最近他们又提出了使用有限混合 模型来估计网络链路延迟p d f 函数“。 以上的算法在一定的条件下都取得了较好的效果。在实际中，由于测量的准 确性依赖诸多条件的限制，不可避免的存在端到端时延测量精度偏差问题，而通 常我们使用的估计方程又往往是超定的，这就使得估计解存在稳定性不好的缺点。 作为估计依据的端到端测量数据发生扰动时，估计值将发生剧烈的波动，另外其 收敛于真实解的精度也会降低。这就是说，在存在较大测量误差的情况下，以上算 法的估计精度会受到极大影响。 在这些研究当中，尤其突出的是m e n g f us h i l l ，他提出的是一种非参数化估计方 法，通过建立链路时延与端到端时延的关系方程，将链路时延转化为己知测量结 果推导参数的反问题，来估计链路的时延分布特征。本文提出的链路级约束网络 层析成像算法主要以m e n g f us h i h 时延估计算法为例来比较，来说明算法的有效 性。 丢包估计方法的研究现状 在非约束网络层析成像中，网络链路级参数估计的另外一个重点是链路丢包 率估计。 在国际上，c a c e r e se ta l 率先使用基于多播的方法建立包对相关性【1 2 】，进而估 计丢包率。他为每一条链路构建了基于贝努力分布的丢包模型，通过生成一个高 阶多项式来描述一个节点与其予节点之间的丢包相关性。然后迭代求解这个多项 式，则可以估计出各条链路的丢包率。 h a r f o u s b c t a l 和c o a t e se ta l 则提出了一种基于单播的方法来推导丢包率 1 3 】。 他们使用e m 算法来估计“包对”之间的相关性。 l i m a g 和y u 在h a r f o u s hc ta l 和c o a t e se ta l 算法的基础上提出了一种 p m l e ( p e n a l i z e dm a x i m u ml i k e l i h o o de s t i m a t e ，p m l e ) 的算法来加速估计过程，他 电子科技大学硕士学位论文 们将任意两个接收端的包关联起来以构造一个似然关系式，然后最大化所有的这 些“包对”似然来求解【l ”。 在当前的研究当中，比较突出的算法是由m e n g f us h i h 和h e r o 针对e m 算 法提出的一种补偿最大似然e m 算法【l5 1 ，这种算法在一定的条件下具有较好的效 果，然而它仍然是基于似然解法的，所以似然算法具有的缺点也没有克服。 综合来看，网络层析成像参数估计的研究现状，最常用的估计模型是基于最 大似然方法。从当前的研究现状可以看出，最大似然方法在网络层析成像参数估 计中取得了非常好的效果，但是，由于最大似然方法本身固有缺陷： ( 1 ) 初始值敏感。 ( 2 ) 只能假设测量的误差为高斯分布，而非高斯情况，似然方法将不能适用。 ( 3 ) 高计算复杂度。 ( 4 ) 局部最优化，在碰见似然函数为多峰情况下，似然函数往往会陷入局部最 优化境地。 ( 5 ) 边界效应，由于似然函数边界处往往认为无穷大，似然方法有时会误认边 界处即为最大值，从而陷入无解境地。 另外，现有的网络层析成像方法大都假定网络状态参数在一定的时间范围内 是非时变和稳定的( 即变化范围很小，可以忽略) ，由于实际网络中网络状态是不 断变换的( 即网络状态参数是时变、非平稳的) 。从测量的角度来看，都是有误差 的。由于网络环境复杂性和非平稳性，两个目的节点上测量得到的误差不可能是 相同的。从路由矩阵角度来看，由于路由算法具有很大相似性以及背靠背包对技 术的采用，导致各方程系数具有非常高的相似性。所得到的线性方程组常是病态 的，测量数据以及计算过程中的微小误差也会造成结果的很大偏离。 因此，在约束网络层析成像中，针对( 1 ) ( 2 ) ( 3 ) 缺陷，本文引入最优化反 演方法来克服这些缺陷。对( 4 ) ( 5 ) 缺陷，通过网络层析成像观测值与待估计参 数之间关系，设定约束条件来进行约束。 1 2 2 信息收集框架的研究现状 在被动网络条件下，国内外已经提出了各种测量体系结构，比如n a i ( n e t w o r k a n a l y s i si n f r a s t r u c t u r e ) ! 阍，n i m t ( n a c i o n a l i 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 ) 埘， p i n ge r ( p i n ge n d - t o e n dr e p o r t i n g ) t 18 1 ，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 ) 【1 9 】 g i m i ( g l o b a l i n t e r n 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 ) 2 0 , l i p m ( l a r g es c a l ei n t e r n e t 第一章绪论 p e r f o r m a n c em o n i t o r m o d e l ) 2 1 1 , n a p m ( n e t w o r ka p p l i c a t i o n p e r f o r m a n c e m e a s u r e m e n t ) 2 2 1 ，d n m a i ( d i s t r i b u t e d n e t w o r km e a s u r e m e n t a n d a n a l y s i s i n f r a s t r u c t u r e ) 2 ”。这样的测量框架往往是基于直接测量方法的。当前，无论是国内 还是国外，在网络层析成像技术领域，研究的重点还是在估计方法上。然而，无论是 对于估计方法的实时应用评估，以及未来的实际应用，都需要结合信息收集方案， 构建一套可行的测量框架。 因此，本文结合主动网的特点，提出了一种基于主动网络的约束网络层析成 像测量系统( l i n kc o n s t r a i n e dt o m o g r a p h ym e a s u r e m e n ts y s t e mb a s e do na c t i v e n e t w o r k ，l c t m s ) 。l c t m s 实际上是一种分布式的测量框架，这样的框架能够有 效实现约束网络层析成像测量任务，收集网络约束信息，为约束网络层析成像的进 一步应用奠定基础，。 l c t m s 采用模块化设计的思想，可扩展性强、适应性强、测量效率高。它利用 主动网的分布式、智能化控制技术，充分发挥主动网技术的优势，能够通过主动节点 的可编程特性，将测量任务分散到各个协作的主动节点，很好的提高了测量的效率， 通过节点之间的协作，剪裁测量结果的额外通信量，极大的减轻了引入的网络负载。 另外测量中心也可以设计为根据网络状况的变化，主动的迁移到新的节点，有效的 增强了系统的健壮性。 1 3 作者的主要工作 本文主要工作集中在以下几点： _ 约束最优化链路时延估计算法的研究 约束最优化链路丢包率估计算法的研究 约束最优化链路时延估计算法的仿真验证 _ 约束最优化链路丢包率估计算法的仿真验证 基于主动网的链路约束网络层析成像测量系统的研究 _ 基于主动网的链路级时延约束网络层析成像仿真测量方案的设计 1 4 论文的章节安排 整个论文各章节安排如下： 本章首先简要的介绍了研究课题的内容，并从研究课题的背景和意义以及研究 电子科技大学硕士学位论文 方向和现状方面进行了阐述。 第二章详细论述了约束最优化链路时延估计算法。首先介绍在网络层析成像 中有效使用的m e n g f us h i h 链路时延估计算法，接着提出了约束最优化链路时延 估计算法，分析了算法的数学原理，并通过仿真结果比较了二者的估计效果。 第三章提出了约束最优化链路丢包率估计算法。在网络层析成像链路丢包率 估计的模型中，本章利用最小二乘迭带求解的方法来估计链路的丢包率。由于这 个方法依然存在解的稳定性问题，因此提出了链路丢包率估计的约束最优化算法， 将约束信息用在估计丢包率的数学模型上，来提高估计的精度和稳定性。 第四章介绍了本文提出的基于主动网的链路级约束网络层析成像测量系统。 首先，对主动网技术进行了概述，从主动网技术的实现方式、节点模型和包处理 方式等方面介绍了当前主动网技术的现状和技术基础。另外，本章对基于主动网 的链路级约束网络层析成像测量系统进行了阐述，介绍了测量系统的目标、框架 结构以及节点相关的组件设计，详细的描述了整个测量系统的框架设计以及具体 的协作过程。 第五章详细描述了网络仿真模型的实现。系统的阐述了被动网络下链路时延 的测量模型、丢包率测量模型。最后，比较分析了仿真结果。 第六章是全文的总结，提出了未来的工作方向。 第二章约束最优化链路时延估计算法 第二章约束最优化链路时延估计算法 2 1 最优化理论在网络层析成像中的应用 2 1 1 基本原理和假设 假设x = ( ) ( 1 ，x j ) n j 维随机向量，反映感兴趣的网络动态参数，比如说链路 延迟，某个时间间隔的网络流量等。y = ( y 1 ) ，y 。) 7 为i 维的测量向量。网络层析成 像的目的就是从观察得到y 进而估计出x 。对于一般网络层析成像问题可以表示如 下： a x + 0 = y ( 2 - 1 ) a 为已知道的i x j n 路由矩阵，由网络的拓扑结构和网络中每个路由器的路由 表决定。0 为测量噪声，随x 变化。方程( 2 1 ) 反映了网络测量的集合本质，因而， x 分布的估计是一个反问题。 2 1 2 反问题的适定性 方程( 2 1 ) 为良态方程的条件有以下三个： 在定义域内，对应每一个y ，都有解x 存在。 解x 是唯一的。 当y 有微小的扰动时，在不另加限制条件的情况下，解x 只产生微小的变 化。 第一个条件为解的存在性条件。第二个条件为唯一性问题，不满足则常常被 称为“伪逆问题”。第三个条件为稳定性条件，被称为病态问题。以上三个解的 存在性、唯一性和稳定性条件总称为反问题的适定性。 反问题的唯一性与可辨识性是紧密相关的，其中一个重要而难度极大的问题 便是提出反问题可辨识的充要条件。由于受测试条件限制，在一般网络层析成像 问题中，a 一般都不是满秩的正矩阵。因此不能保证网络层析成像问题反演解的稳 定性，即对不同的初始估计值将得到不同的辨识结果。因此需要加入一些限制条 电子科技大学硕士学位论文 件，以便于保证模型的可辨识性。一个关键的假设就是x 的所有因子相互之间都是 统计独立的。更多假定： 墨2 ( g ) ，j = 1 , k ，j ( 2 2 ) f j # b 密度函数，其中0 i 是它的参数，那么所有的模型的参数为e = ( o 。0 j ) 。对于 网络单播c g f 估计f j h 一指数函数分布。 一般而言，如果网络层析成像反问题研究对象x 的参数分布很均匀，待辨识的 物性参数可简化为有限的几个常量。实际测量得到的数据多于未知量数目，此时 的反问题易得到唯一解。但是由于网络环境的复杂性，导致估计对象x 具有较强非 均匀性，待辨识的参数分布复杂，有限的观测信息不能完全确定参数的时空分布， 此时反演解是不唯一的，难以精确的反解。 反演问题的另一个特征是非线性，即观测数据和相关参数之间，由于后者的 极小变化将引起前者的很大变化。而且，由于任何观测资料都存在干扰和误差， 这种畸变的观测数据也会使反演计算不稳定，即观测数据中少量的误差将引起待 辨识参数的很大变动，而不稳定的程度与所采取的反演方法密切相关，严重的情 况下甚至会使计算结果失真。 因此，对于网络层析成像反问题，实际遇到的是解的唯一性和稳定性这两个 问题。对不适定问题可从以下几个方面来提高参数辨识的可信度：依据先验信息 建立合理的初始模型，若该问题属于多子问题的藕合，则也应该建立相应子问题 的模型对测试数据作细致的预处理，不仅要剔除误差大的不合理数据，更重要 的是使反演使用的测量值和正演模型计算理论值有相同的意义，或者说具有同等 可比性最后迫切需要开发一种可靠的、受人为影响因素较小的、全局收敛的非 线性优化算法。 而对于稳定性问题，则是本节主要关注的方面。在网络层析成像链路时延的 估计问题当中，尽管存在许多的估计模型，但是在解的稳定性上都不很理想，为 此，本文提出了利用网络约束信息，建立网络层析成像链路时延估计的约束最优 化算法来提高解的稳定性，下面先从介绍网络层析成像链路时延估计的基本原理 和模型开始。 第二章约束最优化链路时延估计算法 2 2m e n g - f us i nih ( 1 d f s ) 链路时延估计算法 2 2 1 基本原理和假设 网络内部链路时延主要由两个方面构成：链路传播时延和链路排队时延。前 者主要是数据包在传播过程中经历媒质的时间，在一次测量的时间间隔内往往是 不变的量。后者是数据包经历路由器的过程中在队列中的排队时间和处理时间之 和，它和网络的背景流量，路由器的处理能力，以及其它的网络条件息息相关， 因此是时变的。 假设在一个域内路由矩阵是已知的r = e r i j ，r i j = o ，1 ) 为路由矩阵中第i 条探针 路径经历第j 条链路的路由系数，当第i 探测包路径包含链路j 的时候，r i j = 1 ，否 则r i j = o 。i = l ，2 ，n 为第i 探测包路径，j = 1 ，2 ，m 为第j 条网络内部链路， 假设在测量时间内，链路时延分布是平稳的，则第i 探测包路径经过的端到端时延 可以表示为： z 。- z n + + mz w2 暑。z f ( 2 - 3 ) 式中随机变量x d 表示第i 探测路径经过第j 条链路的时延。下面，分别作出以下 两点空间独立以及稳定性的假设： 链路时延x 日相互之间假设是独立同分布的，互不相关，其中j m i ，i = l ，2 ，n 。 如果第i 探测包路径和第k 探测包路径之间经历相同的链路j ，那么) ( i j 和 x k j 应认为是一致的。 在这个基础上，采用随机变量y 。的累积量生成函数( c g f ) 来描述端到端时延 的统计特征： k y ( t ) = l g e l 毋】 ：i g e i j k i k 、 = di - i e e 7l( 2 4 ) j “。j = k x ：俐 = r k x ( t ) i = 1 , 2 nt ( ) 电子科技大学硕士学位论文 这里r i ) 描述的是路由矩阵r n 。的第i 行代数和，而k x ( t ) = k x l ( t ) ，k ；m ( i ) 】to 这样 当n 之m ，矩阵r n 。是满帙的，则r 可逆，那么链路时延的c g f 可以表示为： k a t ) = ( r 7 r r “r k d t ) ( 2 - 5 ) 令b = ( r t r ) r t ，式( 2 4 ) ，( 2 - 5 ) 可以得到： k x j 俐= 毛俐= b k l 俐 ( 2 - 6 ) 另外，在针对大规模网络的实际测量中，构建满帙矩阵r 是比较困难的，方面 需要很多探针，另外一方面也可能遇到无法协作的节点，此时只能获得一些链路时 延的线性组合。然而，我们可以比较理想的在局部构建满帙矩阵，获得该区域内各 个链路的时延特征。 2 2 2 链路时延c g f 的偏差校正 链路时延的c g f 值可以这样进行估计： h ( f ) = b j i l g ( 寺c t y , * ) ( 2 7 ) f ；l iv i k = l 式中n i 为收集到的探测包个数，然而由于l g 函数的非线性，因此，通过这种方式 推导的是时延c g f 偏差估计值( b i a sd e l a yc g fe s t i m a t i o n ) ，因为这里1 9 函数的引 入，带来了非线性失真。注意到，l g ( 1 + u ) = u - u ：2 + h o t ，式( 2 - 7 ) 结果可以采用以下 方法进行校正： 霞芹。( f ) = 1 9 0 ( q i 。p ) ) 如) = l g 兀e b 瞳( f ) 卜( 兀e 如 也( f ) 卜1 7 eo ) ) 如) ) 地t 肿n 蚋 邓一糌1 2 , m m f = llilvlr i i = k x j 。) 一国，一i 1 ，2 其中，= ，一糌，因此可以得到链路c g f 的无偏差移估计： ( 2 8 ) 第二章约束最优化链路时延估计算法 霞_ ( f ) = l g ( 寺艺e t r a ) + 廓q 】+ 吉自回】 i 4o lt i l 二 其中，反1 描述的是经验平均值 e c c o ；】= 1 一 研； = 1 一 m n ( f ) 2 兀二缸_ ( f ) ) b 】 矿 n 三雪 h ( f ) ) 2 “】 m ；。( f ) 尬t ( f ) = 兀e ( f ) ) 如 ( 2 9 ) ( 2 1 0 ) 日( m ，( f ) ) 知 计算可以通过滑窗法或者蒙特卡罗方法o “。m f s 算法尽管在一 定的情况下能够取得较好的效果。因为测量数据的经验平均，在测量结果很准确 的情况下，校正可以有效的去处1 9 函数带来的非线性偏差。然而，一旦测量误差 增大，这种校正方法就无法起到修正作用，反而会极大的增大估计值与真实值之 间的误差。仿真结果也验证了这一点。针对这些缺点，我们提出了新的约束最优 化链路时延估计模型。 2 3 约束最优化链路时延估计算法 用最优化方法解决最优化问题包含两个方面的内容： ( 1 ) 最优化目标模型 即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所 要达到的目标和各种约束条件。在本节的第一阶段，将构建链路时延估计的最优 化模型。 ( 2 ) 最优化算法 数学模型建好以后，选择合理的最优化方法进行求解。 2 3 1 基本的数学模型 通过链路时延估计模型可以获得时延的估计值，然而这种方法在测量存在误 差的情况下估计值和真实值的偏差是相当大的，另外如果探测路径矩阵存在严重 电子科技大学硕士学位论文 病态性的时候，估计值很不稳定。我们考虑到在网络当中存在许多可以利用的i 网络 信息，可以为求解提供约束条件，从而使得估计值的精度很大程度上的提高。在这 个基础上，本文提出的约束最优化链路时延估计模型如下，由式( 2 4 ) 定义函数： f ( k x ( 呦= 扣”铲蓦悔，旷 ( 2 _ 1 1 ) 则可以将链路时延估计转化为以下约束最优化问题： m i n f ( k x ( f ” s t g f ( k z o ) ) 0i = 1 , 2 ，一，三 h s ( k x ，( f ) ) 0 j 2 1 , 2 ，三 r 2