（通信与信息系统专业论文）广义线性反演在网络层析成像中的应用.pdf

中文摘要 中文摘要 随着h l t e l n e t 网络的飞速发展，网络结构也在发生深刻变化，要成功设计、控 制和管理网络，就需要了解和掌握网络的内部特性。其中流量矩阵和链路丢包率 是重要的网络性能参数。由于网络日益向着大型化、异构化、分布化发展，通过 直接进行网络测量的方法，来获得网络内部流量矩阵信息和链路丢包率参数就变 得越来越困难，网络层析成像方法作为一种通过端到端间接测量的数据来推断网 络状态参数的技术正成为研究的热点之一。 由于网络层析威像参数估计求解的复杂性，为了保证估计精度，现在所用方 法大多是基于最大似然模型的，饱受估计稳定性以及估计实时性问题的困扰，计 算复杂度太高限制了网络层析成像技术在大尺度网络中的应用。本文针对现有网 络层析成像方法求解稳定性、实用性展开讨论，将广义线性反演引入到网络层析 成像领域，用于0 d 流量估计和链路丢包率估计，并结合网络层析成像求解稳定 性和实时性问题，对广义线性反演法作了一些改进，在一定程度上解决了估计的 病态性，有效地提高了网络层析成像的实时性，使网络层析成像技术在大尺度网 络中更加实用。 o d 流量估计是网络层析成像研究的重要内容之一，本文重点研究了o d 流量 估计算法，鉴于喱方法极大的计算复杂度，提出一种通过计算流量方差从而估 计流量值的快速算法，并结合广义线性反演方法及滑动时窗机制分析了该算法的 在线估计实用性。将广义线性反演应用于大尺度网络层析成像1 m 矩阵估计，就 初值的约束以及部分测量信息的约束展开了讨论，提出了基于状态预测的方法和 基于历史窗口均值及重力模型r a t i o 相结合的方法，得到了较好的估计结果。 网络链路丢包率是网络性能的重要指标，在测试服务质量参数以及评估链路 性能，进行网络异常检测等方面具有重要意义。现有研究大多通过发送背靠背以 及三包组探测包，通过极大似然法对链路丢包率进行估计。本文将广义线性反演 应用于网络单播链路丢包率估计，并针对现有单播链路丢包率估算法只能对二叉 树或三叉树进行链路丢包率估计的缺陷，提出了在任意拓扑下的s p t ( 最短路径 树) 上各链路丢包率估计方法，极大地提高了方法的实用性。 关键词：广义线性反演，网络层析成像，流量矩阵，链路丢包率，最短路径树 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 毗o f 山ei n 啪t h cs t n 】c t l l l eo ft h en e t w o r kh 舔 c h a n g e dt h o r o u g h l y i ti sn e c e s s a r yt 0g e ti n t ot h ei n n e rp l q 船r 哆o ft h es p e c i 丘cn e t w o r k t od c s i 萨，n _ 缸o ia n dm 弛a g ei ts u c c e s s f l l h y t r a 伍cm a n 奴a n dl i n k 一1 e v e lp a c k e t1 0 s s 船t ea r ct h ei m p o 姗tp 缸锄e t c r st 0i n d e n t i f yt h ep e r f 曲m a n c eo f l en e t w o r k b mi ti s h a r dt om e 硒u r et i l e md 由e c n y 雒t h em t e m c ti sb e c o l i l i n gm a s s i v e ，d i s t r i b u t e da i i d h e 咖g e n c o u s n e 懈o r kt 0 m o 鲫h yi sa 妒渤砌n gt e c h i l o l o g ) rt oi 1 1 f c rn 他n e 脚0 r i 【p a r a m e 觚 t h r o u g hi i l d i r e c tm e 硒u 屺n t m l ei sw i d e l yu s e di nn e t w o f kt o m o 鲫h yf i e l dt 0 硒s u r ct h ca c c l i r a c yo ft i l cr e s u l t ，b u ti tb f i n g si nt h ep r o b l e mo fs 讪m t ya n du sa _ b i l i t ) r w l l i c hi st h cm a i nb o t n e n e c kt op u s ht h en e 柳o r kt o m o 乒a p h ye s t i l i l a t i o ni i l t op r a c t i c a l u s e t h cs 协i l i t ya i l dt l l eu s d b m yo ft h en e 脚o r kt o m o 掣a p h yt 葩h o n o l o g yi sd i c u s s c d h e f ；e w bi n t r o d u c e 龇g ua l g 鲥t h mi n t on e t w o r kt o m o 鲫h yf i e l dt oe s t i m a t co d 仃a 筋c 锄dn n k 1 c v dp a c k e tl o s sr a t e s 0 m ei m p r o v e m e ta r cm a d ei i ig ut om a k cm e a l g o r i t h mm o 心s t a b l e 锄dm o r ep r a c t i c a l ， 0 d 昀伍ce s t i 脚t i o ni so n eo ft l l ei m p o n 锄ta s p e c t so fn e 哪o r kt o m o g r a p h y w e 朋叩h 弧i o nt h ee x i s t i n ga l g 讲i n l 玎勰孤dp r o p o s ean e wa l g o 血t l i nw h k h i sb a s e do n 仃a 伍cc o v a i i 锄c e 1 k sn o v e la l g 嘶t h mi sp m v e dt 0b ee 硒e n c ta i l d f a s ti l p l 锄e n t e d w i t hg u 她dt h es l i p e w i n d o ws c b e m e w eu s eg ut oe s t i i n a t et t l e1 mi nl a r g es c a k n e 啪o r k d i 船r c n tc o n s t r a i n sb a s c do ni n m a l 面0 r 锄dc o n s 仃a i n sb a s e do np a n i a l m e 硒u r e i 咖ta r cd i s c u s s e d an e wm e t h o db a s e do ns t a t cp r e d i c t i o na n da n o t h e r m e t h o di nw h i c hl l i s t o r ym e a ni sc o m b i n e dw i t l lg r a v i t yi n o d e li sp r o p o s c d u n d e rt h e i m p l e m e n t a t i 伽o ft b ed i 圩b r e n tc o n s t m i n sa n di n c o i p o r 曲甜w i t hp a n i c a lm e 雒u 化m e n t ， w eg e ta 讲圮a l i n gr e s l 】t ，w l l i c hi sb e t t e rm a tg e n e r a l 伊a v i t ym e t l l o d l i i l l ( l e v e lp a c k e t1 0 s sr a t ei s 孤i i n p o n a i l tp a 姗嘲o fn e 哪o r kp e m m n a i l c e hi s v a l ua _ b l ei nm 锄a g e m e n to ft l en e t w o r k g l ii si n 旬r o d u c e di n t ot h i sf i e l d an e wm e t h o d i sp r o p o s c dt 0e s t i m a t el i l l k _ l e v e lp a c k e tl o s sr a t cu n d e rg e n e r a ls p tw h i l ee x i t i n g m e t b o dc a no l l l ys o l v et h i sp r o b l e mu n d e rc o n s t a l l tb i i l a r yo r ( h r 一1 e a f 仃e e a b s t r a c t k e y w o r d s ：g e n e r a ll j n e a rh l v e r s e ，n e t w o r k1 b m o f a p h y ，t r 施cm a t r i x ，l i n k - l e v e l l o s sr a t e s h o n e s tp a t l l 砥 一 图目录 图目录 图2 一l 线性系统反问题示例1 0 图2 2 一般网络拓扑结构图1 2 图2 3 广义线性反演流程图2 0 图2 _ 4 加入s v d 阻尼后的广义线性反演流程图。2 4 图3 1o d 流量估计简单拓扑结构。2 8 图3 2 链路流量测量数据2 9 图3 3i p 网络各元素及术语3 7 图3 4 i s p 网络中的不同o d 流量一3 9 图3 5 快速算法框图4 3 图3 6 快速算法滑动时窗4 4 图3 7 真实方差与估计方差对比图4 5 图3 8 方差快速算法结果4 5 图3 9m l e 结果图4 6 图3 1 0m a n a b 计时器4 6 图4 _ l 约束最小欧几里得长度解5 0 图4 - 2 滑动时窗5 2 图4 - 3t m 估计在线算法技术路线图一5 3 图钳a b i l e n e 网络拓扑结构5 4 图4 _ 5 简单重力模型值与真实值5 5 图4 _ 6 广义重力模型值与真实值5 5 图4 7 状态预测方法估计值与真实值对比图6 l 图4 8 历史均值方法估计值与真实值对比图6 5 图4 9 部分o d 流量估计结果对比6 8 图4 一1 0 各o d 流空间相对误差6 9 图4 - l l 空间相对误差对比图一7 0 图车1 2 主要流量空闯相对误差对比图7 0 图4 一1 3 时间相对误差对比图7 1 图4 1 4 部分测量对估计精度的影响。7 2 图5 1 简单二叉树模型7 5 图5 2 二叉树结构 7 8 图5 3 三叉树结构8 0 图5 - 4 实际网络拓扑结构8 l 图5 5 任意s p t 链路丢包率估计算法流程图8 2 图5 6 仿真流程图“ 图5 7 网络s p t 结构8 5 图5 8 节点模型图8 5 图目录 图5 9 进程模型图8 6 图5 一l o 任意s p t 树结构链路丢包率对比图8 7 图5 一1 1 任意s p t 树结构链路丢包率相对误差图8 7 一v 表目录 表目录 表3 1 简单网络路由表2 8 表3 - 2m l e 算法与方差快速算法的计算时间4 6 表禾lr i m 估计中的) f 算法。5 3 表年2 相对误差平均值7 2 缩略词表 英文缩写 t m 0 d s p t n 衄 q o s i s p c b r r t t p o p e m 0 s p f b r 英文全称 缩略词表 t 妇m cm a 廿投 o r i g i n d e s 缸a t i o n s h o n e s t p a l l l l h 圮 m a x i n m nl i k e l i h o o de s t i n 撕o n q u a l i t yo f s e 峨e i n “：m e ts e r v i c e sp r o v i d e r c o n s 协tb i tr a t c r o u n d t r i d n m e p o i n to f p f e s e n c e e x 口e 删o na n dm a x j l i z a t i o n o d e ns h o r t e s tp a t hl 证s t b a c k l ) 0 n er a u t e r 中文释义 流量矩阵 源到目的节点流量 最短路径树 极大似然估计 服务质量 网络服务提供者 固定比特率 往返时间 汇接点 期望最大化 开放最短路径优先 骨于路由器 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名： 盈豆j 茎日期：叼年月口日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：垂赴 导师签名：= 趔0 眦 日期：年月日 第一章绪论 1 1研究背景及意义 第一章绪论 流量矩阵、丢包率是网络性能的重要指标。作为关键的网络信息，这些信息 对于因特网服务提供商而言，在测试服务质量参数以及评估链路性能，进行网络 异常检测等方面具有重要意义。不仅如此，对于动态的路由算法和流量传输协议 的改进也是重要的参考依据。当网络拓扑发生变化，甚至遭受破坏时，及时掌握 各种性能参数，包括拓扑结构、流量、时延、丢包率，以保证网络的可靠、高效、 稳定运行也至关重要。 获得这些网络性能参数，通常是采用直接测量的方式。但是，随着网络向大 型化、异构化、分布化发展，使得h i t e m e t 结构日益复杂。直接测量网络中各种性 能参数越来越困难，需要各个不同域内的通信节点的充分协作，这样的协作是相 当复杂的。对于不同的因特网服务提供商而言，基于商业性的考虑，通常只会提 供部分节点来完成一定程度的协作工作，使得测量结果可能不会覆盖到测量者所 感兴趣的链路上。因此，通过其他测量途径高速感知网络状态参数以及网络状态 参数的动态变化，以获得整个网络状态的多域多层次时空描绘，有切实的现实意 义。 1 1 1网络测量 网络测量通常是指利用有效的网络探针和工具软件，对网络各项运行指标及 参数进行测量，以提取各种关于网络健康状况的参数指标【l 】。从概念上讲，网络测 量是收集和分析网络协议运行性能的手段，可以帮助人们搞清网络( 局域网或广域 网) 有时不能正常工作的原因。从研究实质上看，网络测量是获得第一手网络行为 指标和参数的最有效手段。在对网络进行测量和测试的基础上建立网络行为模型， 并用模拟仿真方法搭建从理论到实践的桥梁，是理解网络行为有效的途径。 网络测量有不同的分类方法闭： ( i ) 按照测量过程中测量设备是否主动发送探测包可分为主动测量和被动测量 两类。主动测量是基于往返时间r t t ( r 舢n d 确p n 屺) 测量，测量装置主动向阿络 发送探测包，然后根据返回的参数来判断网络现有状况，这些参数包括响应时间、 电子科技大学硕士学位论文 丢包率等。主动方式会增加网络的负荷并引起网络的拥塞，但是可阻了解整个网 络的行为，获得端到端的信息。在被动测量方式中，测量装置( 可以是端节点或路 由器等中间节点) 被动地根据一定需求来监测和采集网络上特定链路、特定时段的 流量。被动测量很难获得对网络整体的了解，也很难对网络终端到终端之问的性 能做出准确的分析，但是不会增加网络的负荷。 ( 2 ) 按照测量系统所处的位置，又可分为基于路由器的测量、端到端的测量以 及路由器协助的测量p 】。 网络测量的内容很广泛，包括网络拓扑发现，时延、丢包率、带宽测量，路 由器调度策略和“瓶颈”缓冲器容量测量，以及路由器流量监测。 1 1 2 网络层析成像研究意义 i n t e m e t 的飞速发展迫切需要提高它的性能。同时，人们需要良好的q o s 及安 全方面的保证，i s p ( h t 啪e ts e r v i c e sp r o v i d e r ) 也需要加强对h l t e m e t 的管理。这就 使得网络测量成为越来越迫切的需求。然而现存的网络测量方法存在以下限制及 不利因素h ： 目前广泛使用路由器测量方法，也就是常说“内在”的方法，在网络节点 或者网络节点之间直接主动或者被动测量，这方法有许多潜在的限制： 对一般用户是不可能得到的。可能不会覆盖到你所感兴趣的路径上。 在网络高负载的情况下，不可能进行测量。大尺度网络上，存在测 量和测量数据收集的问题。将每个测量点测量得到数据组成一个端到 端的路径数据信息，是很困难的任务。 “外在”方法，即假定没有节点的配合下，通过端到端的测量来诊断问题。 目前已有许多实际工具来测量端到端的性能。如p i n g 和t r a c e r o u t e 等诊断 工具广泛用来确定p 网络连通性、f o u n d t r i p 测量丢失及延迟信息、 p a t h c h a r 和仃a c e m u t e 用来估计链路级的可用带宽，延迟，丢包率等。这 些方法也存有潜在的缺陷：i c m p 包在路由器里处理的低优先级，使 测量得到的延迟不能代表正常流量的延迟。有些工具需要一些特殊的 假设，如路由节点不能存在防火墙，需要存储与转发路由器等。i c m 包不能被网络管理员认可，经常被i c m p 包过滤器过滤掉，以至不能进行 响应。需要路由器的协作。 正是由于网络朝着分布化，非协作，异构管理和基于边缘控制的方向演变， 导致这些传统工具的使用受到限制，研究人员致力于新的网络测量方法的开发研 一2 第一章绪论 究。 为了弥补传统网络测量方法的不足，国际上多个研究机构都在寻找其它途径 来研究网络的整体性能及其相互影响。将医学、地震学、地质勘探等领域成功应 用的成熟理论和方法应用于通信网络领域，衍生出了网络层析成像撇w o r k t o m o g r a p h y ) 嘲。它基于端到端的技术来获取网络中那些不能直接观察到的信息， 通过发送多种探测包给指定的接收器，观察并分析接受器所获得的数据，最后通 过统计和推断来获得各种网络信息，包括链路级的参数和拓扑结构等。从反问题 求解角度来看，网络层析成像进一步还可以包括网络o d ( o r i g i n d e s t i n a t i o n ) 流量强 度估计，它实际是对网络链路级( l j i l l 【儿v e l ) 参数推理的反过程，其目的就是从各 链路级的测量数据中估计出路径级的网络参数。这两者求解都反映了网络层析成 像反问题求解的本质，因此可以归纳到网络层析成像这样同一个主题下。 网络层析成像技术在没有内部节点协作的条件下，通过主动发包或被动收集 网络内部有用信息的，运用统计学方法推理网络上链路q o s 参数，如丢包率和延 迟分布等，识别网络拓扑结构和进行o d 流的估计。特别是被动的方法因为不发 送探测包，很适合在高负载的网络中使用。 目前网络层析成像主要由两个部分组成嘲，第一部分为测量数据的收集，其中 主要研究如何收集网络内部的相关有用信息。第二部分为统计推理，它主要是根 据收集的数据来发现网络内部的信息和规律。根据数据收集的方法可以把网络层 析成像分为：基于主动发探测包的主动网络层析成像技术和基于被动方法的被动 网络层析成像技术。 当今的链路级网络层析成像研究主要集中在时延分布、丢包率和带宽的参数 估计上。更一般的问题则扩展到其他参数，比如可用带宽和服务原则的重建等。 而路径级网络层析成像研究主要集中在o d 流量估计。 在网络层析成像技术中有许多关键的假设，用于决定测量的框架和数学模型。 这些假设为：路由矩阵a 假定为已知的，而且在整个测量时间间隔内都是固定 的。虽然网络路由矩阵是定时更新的，但是这些变化是以几分钟为间隔发生的。 当然，路由矩阵的动态特性限制了能用作收集和推理的数据的数量。且前大多 数方法通常都是假设每个链路上的性能特征是相互统计独立的，在许多例子中也 将它们假设为暂时平稳的。在路径级的网络o d 流量估计中，一般也假定源节 点和目的节点是相互独立的，各o d 流对之间相互独立。 3 电子科技大学硕士学位论文 1 1 3寻求在线求解稳定方法 网络层析成像参数估计的反问题本质决定了参数估计算法的复杂性。现在最 常用的估计模型是基于最大似然方法。从当前的研究现状可以看出，最大似然方 法在网络层析成像参数估计中取得了一定的效果，但是，由于最大似然方法本身 固有缺陷：( 1 ) 对初始值敏感。( 2 ) 只能假设测量的误差为高斯分布，而非高斯情 况，似然方法将不能适用。( 3 ) 局部最优化，在碰见似然函数为多峰情况下，似然 函数往往会陷入局部最优化境地。( 4 ) 边界效应，由于似然函数边界处往往认为无 穷大，似然方法有时会误认边界处即为最大值，从而陷入无解境地。( 5 ) 最重要的 一点，基于最大似然的算法往往计算复杂度很高，使得网络层析成像用于大尺度 网络参数估计时，饱受估计稳定性以及估计实时性问题的困扰。 因此，研究简单高效的统计方法，使大尺度网络参数估计更稳定更迅速，从 而将网络层析成像技术推向更实用的领域具有现实意义。 1 2网络层析成像研究现状 网络层析成像技术在无需其它节点的协作的情况下，只需使用网络中的一组 节点，即可完成对整个网络各种状态参数和状态参数变化的估计。它以成为国际 学术界备受关注的网络测量新技术之一，近年来得到了广泛的关注。当前，无论 是国内还是国夕 ，在网络层析成像技术领域，研究的重点还是在估计方法上。 大尺度网络推理的问题根据数据获取类型和感兴趣的性能参数来区分，为了 区分这些问题，先定义链路与路径的基本概念，链路( l i n k ) 是指两个节点之间没 有中间节点直接相联系，而且可以是单向或者双向的。路径( pa _ t h ) 是指两个节点 之间相联系，中间有一个和多个链路，信息从源节点发送到目的节点沿着一条路 径，该路径一般要经过好几个节点。v a r d i f 5 】是第一个研究大尺度网络推理问题， 由于网络推理与医学层析成像的类似所以把它称为“网络层析成像( n 烈w o 伙 t o m o 黟a p h y ) ”。网络层析成像可以分为两类：基于端到端的路径级网络流测量 来得到链路级的参数估计；基于链路级网络流测量来得到路径级o d 流强度估 计。 网络层析成像可以用线性模型来建模，该模型用如下式子表示： ) ，= a 口+ ( 1 1 ) 4 第一章绪论 式中y 为可测量的向量，比如：在网络不同测量点测量到的发包数目，端到端 的延迟，链路流量。疗为包参数向量，比如每条链路( “n k ) 的平均延迟，包成功传 输概率对数或者随机的o d 流向量。a 为路由矩阵，可能是测量数据y 产生的加 性噪声，也可能口关于其均值的随机偏差。 考虑到网络参数的时变性质，( 1 1 ) 式的线性模型可以迸一步表示为时变的形 式： 只= 46 + ( 1 2 ) 式中f 表示时间，这时估计的问题涉及到时变参数的追踪，实际上，( 1 2 ) 式表 示的时变情节更能反映实际网络的动态本质。有几种方法用来尝试追踪非平稳网 络行为，包括经典的卡尔曼滤波器方法。 ( 1 1 ) 、( 1 。2 ) 估计问题是反问题的典型例子。反问题在信号处理领域，统计学 和应用数学具有很多的相关文献，这些反问题的求解主要依靠噪声占的本质特征和 a 矩阵。由于它不能直接求解，所以一般需要用迭代算法来求解。一般来说a 不 是满秩，所以导致了方程的可辨识性问题，要么能解决参数线性联合的问题，要 么能用统计方法引入正则性和促使可辨识性。 1 2 1在链路级参数估计方面 马萨诸塞州大学的m 玳c m 工程是多播网络层析成像方面研究领先者，并且刺 激了当今这个领域研究工作的发展嘲1 们。 马萨诸塞州大学l op r e s t i ，n gd u f f i e l d 等在2 0 0 2 年提出了基于多播端到端 测量的内在队列延迟分布估计算法【1 l 】，描述了估计链路延迟分布的p n l f s 函数，使 网络层析成像的结果与实际值更逼近。由于h t e m e t 对多播协议的支持是有限的， 他们的方法要求使用多播探针，这就需要网络提供多播会话的协作，这样这种方 法的使用受到了较大的限制。 莱斯大学c o a t c s 锄dn o w a l 【发展了单播包对探针的机制，这种机制通过发送 一组紧密相关的包对到边缘节点，通过这组包对之间的相关性，进一步利用最大 似然( m a x i 舢ml 披e h h o o dv i ae x p c c t a t i o nma ) 【_ i m i z a t i o n ，m l 广e m ) 算法，推导链路 的时延特性。他们采用了多个背靠背包克服在单播网络层析成像方程欠定问题， 取得了不错的估计效果。另外，他们进一步的使用基于内在延迟估计的序贯蒙特 卡洛方法，这个方法能够追踪时变网络延迟行为【l2 】。 ql j 锄g 【1 3 1 和y o l a i l d at s a i l g 【1 川分别提出了基于极大似然估计器的内在延迟 5 电子科技大学硕士学位论文 估计算法，但是在迭代求解极大似然值的时候，前者采用了e m 算法，后者用了 m m p l e ( m u l t i s c a l em a x i m u m p e n a l i z e dl i k e l i h o o de s n m a 嘶) 算法，都取得了良好的 估计效果。密歇根大学m e n g f us h i l la 1 1 dh c r o 发展出基于链路延迟累积量生成函 数( c g f s ) 方法，最近他们又提出了使用有限混合模型来估计网络链路延迟p d f 函 数【15 1 。 网络丢包率信息使网络工程师能优化网络设计，增强对网络控制，对于 i s p s ( h l t e m e ts e r v i c ep r o v i d e r s ) 决定网络代价策略也非常重要。因此网络链路级丢 包估计作为网络层析成像重要研究部分，国外许多研究机构在这方面进行了大量 研究。r c 矗c e r c s 【1 6 】等首先采用最大似然估计方法来估计多播树的链路丢包率，这 种方法能很好的对链路级丢包进行估计，也存在不足。第一，h l t e m e 中仍然有很 大一部分并不支持网络级的多播；第二，路由器处理多播与单播是不同的，通过 多播包观察到的网络内部特性与通过单播观察到的有很大的不同，因此多播估计 不能很好反映实际网络特性。 针对多播探测方法的缺陷，m a r k c o a t e s 和r o b e nn o w 划”】等提出使用单播背 靠背探测包对( 即包对中包先后在极短的时间内发送) 来测量路径的丢包，然后通过 求解最大似然方程来估计链路的丢包率。t i a nb u 【1 8 】等把该方法扩展到非树状单播 网络中，进行链路丢包估计。由于单播包对在传输过程中不能完全保证同时被丢 弃或是正确传输，即不能完全达到多播传播的效果，文献口9 中提出采用三包组 ( t i l r e e - p a c k e ts n i p e ) 的方法来解决这一问题。包组中的探测包在严格队尾丢包的情 况下，将以极大的概率同时被丢弃或是被正确传输，产生近似于多播的效果。 1 2 2 在路径级参数估计方面 r u t g e r s 大学统计学系y v 打d i 【5 】是第一个进行o d 网络层析成像问题的研究。 他详细说明了在泊松模型条件下的同一性情况和发展出了一种基于链路数据上 e m 算法用于估计泊松模型的参数。用独立同分布的p o i s s o n 模型研究o d 流量，给 出了泊松模型下的可辨识条件，在确定路由和m a r k o v 路由策略两种情况下对链路 数据用e m 算法来估算p o i s s o n 参数。为了减轻e m 算法在p o i s s o n 模型下实施的 难度，他又讨论了正态模型对p o i s s o n 模型的近似。 1 e b a l d i 提出了b a y e s i a n 和m c m c 机制，但是仅仅处理单一测量间隔的链路 流量【删【2 l 】。普林斯顿大学r j v 柚d e r b e i 等发展出另一种e m 算法用于流量估计 【2 2 1 1 2 3 】。 贝尔实验室c a o 叫】等人使用实际采集的数据用来修订泊松模型和用于解决0 d 一6 第一章绪论 网络层析成像的非平稳性问题，他们的方法提出链路流量是o d 流量的线性函数 的函数。对于非平稳流量，用本地似然模型，即对一时刻f ，假定对称观测窗口 w = 2 h + l 中的数据是平稳的，且窗口内的数据独立同分布。m l e 用于模型参数的 估计，它通过e m 算法和二阶全局最优化的结合来实现。在得知链路测量值、估 计的m l 参数和o d 流量为正的假设后，用条件期望估计o d 流量。 1 3现有研究的不足 现有的网络层析成像方法大都引自医学层析成像，而医学层析成像问题中， 解的不适定问题相对不突出，其主要原因是信号的采集质量较高、人体的结构模 型相对比较清晰( 在层析成像前正常人体各部分的大致结构是已知的) 。但对网络 层析成像问题来说，情况有很大不同，解的不适定问题相对突出。再加上网络性 能参数估计问题本身的复杂性和所针对问题的特殊性，使得几乎现在所有的网络 层析成像估计都存在相同的病态性以及计算实时性的困难： ( 1 ) 方法的病态性问题：网络层析成像必须求解一个大型的方程组，有两个原 因使得方程组的稳定性受到影响，首先噪音的影响：现有的网络层析成像方法大 都假定网络状态参数在一定的时间范围内是非时变和稳定的( 即变化范围很小， 可以忽略) ，由于实际网络中网络状态是不断变化的( 即网络状态参数是时变、非 平稳的) ，在现有网络层析成像方法中将该时间范围内的参数变化看作噪音；第二 方程相似性的影响：方程组中a 是依据网络路由建立的，各种路由的相似性，也 带来了方程组各个方程之间的相似性。基于以上两个原因我们最终要求解的方程 组一定是一个病态的方程组，也就是说实际网络层析成像问题求解是不稳定的， 它的解可能不唯一，提高解的稳定性是该方法实际应用中必须解决的关键问题之 一 ( 2 ) 网络层析成像的实时求解问题：网络层析成像是对整个网络中参数的一个 估计问题，网络的各种参数( 包括流量、丢包率等) 又处于不断变化中，要完成 网络性能参数的实时动态监测，计算工作量很大。如何提高网络层析成像的计算 速度，开发出一种实时算法，使之能高速地估计出整个网络的状态参数也是实际 应用中必须解决的关键问题之一。 ( 3 ) 网络层析成像方法的实用性问题：由于网络层析成像参数估计求解的复杂 性，为了保证估计精度，现在所用方法大多是基于最大似然模型的，计算复杂度 太高限制了网络层析成像技术在大尺度网络中的应用。建立新的估计模型，开发 7 电子科技大学硕士学位论文 出简单高效的算法将网络层析成像技术推向更实用的领域也是实际应用中最关键 的问题。 1 4 本文的工作 ( 1 ) 根据网络层析成像过程中，路由矩阵不变的特点，将广义线性反演引入到 网络层析成像领域，用于o d 流量估计和丢包率估计。当进行在线参数反演时， 只要网络路由不发生变化，复杂网络层析成像计算问题，将通过几次( 与迭代次数 相同) 路由矩阵与向量的乘积运算得到，有效地提高了网络层析成像的实时性。 ( 2 ) 对广义线性反演方法作了一些改进，提出了一种确定阻尼系数的方法，在 一定程度上解决了网络层析成像参数估计病态性问题，为后续研究打下了良好的 基础。 ( 3 ) 通过现有o d 流量估计方法的研究，提出一种通过计算流量方差从而估计 流量值的快速算法。 ( 4 ) 将广义线性反演应用于o d 流量估计，通过初值的约束以及部分测量信息 的约束得到了较好的o d 流量估计，优于现有广义重力模型法。 ( 5 ) 将广义线性反演应用于网络单播链路丢包率估计，并针对现有单播链路丢 包率估算法只能对二叉树或三叉树进行链路丢包率估计的缺陷，提出了在任意拓 扑下的s p t ( 最短路径树) 上各链路丢包率估计方法，极大地提高了方法的实用 性。 1 5论文结构及内容安排 整个论文各章节安排如下： 第一章首先简要的介绍了研究课题的内容，并从研究课题的背景和意义以及 研究方向和现状方面进行了阐述。 第二章介绍了反问题的求解方法，重点分析了广义线性反演的原理以及广义 线性反演用于网络层析成像的实用性。并结合网络层析成像求解稳定性和实时性 问题，对广义线性反演法作了一些改进，在一定程度上解决了估计的病态性，有 效地提高了网络层析成像的实时性。 第三章详细讨论了1 m 矩阵估计方法。提出一种通过计算流量方差从而估计 o d 流量的快速算法，并结合广义线性反演算法及滑动时窗机制分析了该算法的在 8 一 第一章绪论 线估计实用性，最后通过仿真证明了该算法的有效性 第四章讨论了广义线性反演在，i m 估计中的应用。分别从初值约束以及部分 测量约束信息在广义线性反演算法中的使用两方面讨论了大尺度网络层析成像 i m 矩阵估计问题。提出了利用流量时空相关性的状态预测方法及历史均值方法， 并通过仿真对比了这两种方法与重力模型方法以及简单网络模型方法的估计结 果。最后分析了广义线性反演算法能作为在线算法用于t m 估计 第五章将广义线性反演应用于网络单播链路丢包率估计，并针对现有单播链 路丢包率估计算法只能对二叉树或三叉树进行链路丢包率估计的缺陷，提出了在 任意拓扑下的s p t 上各链路丢包率估计方法，极大地提高了方法的实用性。对于 包群法用于任意s p l r 模型的有效性，最后通过嗍t 搭建仿真环境，进行了验 证。仿真得到的数据通过m a 廿a b 进行处理，通过广义线性反演算法求得最后估计 结果。 第六章是全文的总结，提出了未来的工作方向。 9 - 电子科技大学硕士学位论文 第二章反问题的求解方法 层析成像( t o m 0 孕a p h y ) 也称计算机层析成像，简称c t 技术，是本世纪7 0 年 代初首先在医学工程上得以成功应用并蓬勃发展起来的项新技术。目前已在石 油勘探、雷达探测和医学工程上获得了成功的应用，而且已形成了完善的理论和 方法。特别是在石油勘探中，c t 技术不仅获得了广泛的应用，而且石油勘探中许 多反问题( h l v e r s i o np r o b l e m ) 的求解方法又反过来促进了c t 技术本身的发展。网络 层析成像作为一种检测和研究网络的整体性能及其变化规律的技术，借用上述已 成熟的理论和方法，通过主动发包探测方法或者被动收集网络内部有用信息的方 法，将网络状态参数的求解看作一个反问题，使用统计学方法估计网络的状态参 数( 包括丢包速率、延迟、网络拓扑结构和流量估计等) 或状态参数变化。网络 层析成像问题其本质是反问题的典型例子，由于观测数据总是含有嗓音的，同时 难于观测到全部信息，因此直接求解往往是困难的，一般需要用迭代的反问题求 解算法。 2 1 反问题概述 2 1 1反问题的提出 “反演”这一术语是与“正演”相对应的。正演的定义是，根据某些一般住 原理和模型来预测具体的模型参数所激励的结果数据。而反演，就是处理相反的 问题，即从观测到的数据及某些一般性原理和模型出发，来估计模型参数。它们 可用以下过程来描述： 正演：模型参数专模型专观测参数 反演：观测数据专模型专模型参数估计值 对于线性系统反问题的形式化表述如图2 1 。 系统输 图2 1 线性系统反问题示例 1 0 系统输出y 第二章反问题的求解方法 正问题：已知x 、a ，求y 反问题：已知y，求xa 已知y 、a ，求x 一般来说，由于正演模型是确定的，模型参数是完备的和无噪的，所以正演 问题的解都是唯一的。而在反演问题中，实际观测数据总是含有噪声，并且在多 数情况下，难于观测到全部的信息。因此，造成了反演问题通常具有多解性。 在不同的科学技术领域中，对反问题的定义是不同的。根据数学的观点， 反问题是在给定的子空间中寻找与函数空间中的某点( 根据反问题目的预先确定该 点) 最靠近的点。根据统计学的观点，反问题是回归和参数估计问题。根据信 息论的观点，反问题实质是信息传递过程，后验信息= 先验信息量( 经验信息) + 观测 信息+ 理论信息量。从系统论的角度，反问题实际上需要求解的为系统模型、状 态参数等，是一个系统辨识问题。 2 1 2 反问题的适定性 反问题的适定性是指解的存在性、唯一性和稳定性，并将不满足上述三个条 件任一个的定解问题称为病态问题( m p o s c dp r o b l e m ) 或不适定问题，反之称为良态 问题( w e l l p o s e dp r o b l e m ) 或适定问题。典型的不适定问题，在拟合残差很小的情况 下，其反演值仍可较大的偏离真实解。参数反问题的不适定性一直是该领域的瓶 颈，正是因为反问题的不适定性，工程界对参数反演结果的可靠性一直表现为不 信任，这也是制约反演方法更广泛应用于实践的一个主要障碍。 反问题的唯一性与可辨识性是紧密相关的，其中一个重要而难度极大的问题 便是提出反问题可辨识的充要条件。由于受测试条件限制，仅仅根据有限的观测 数据求解反问题，不能保证反演解的唯一性，即对不同的初始估计值将得到不同 的辨识结果。这种解的非唯一性不是由于反演方法和技巧上的缺陷引起的，而是 反问题本身存在的固有困难。 一般而言，若反问题研究对象的物性参数均匀，待辨识的物性参数可简化为 有限的几个常量，实测信息多于未知量数目，此时的反问题易得到唯一解。反之 若研究对象非均匀性较强，待辨识的参数分布复杂，有限的实测信息不能完全确 定参数的时空分布，此时反演解是不唯一的，不得不采取降低辨识精度( 相应减少 了待辨识的未知量) 的策略来达到可辨识的目的。 反演问题的另一个特征是非线性，即观测数据和相关参数之间，由于后者的 电子科技大学硕士学位论文 极小变化将引起前者的很大变化。而且，由于任何观测资料都存在于扰和误差， 这种畸变的观测数据也会使反演计算不稳定，即观测数据中少量的误差将引起待 辨识参数的很大变动，而不稳定的程度与所采取的反演方法密切相关，严重的情 况下甚至会使计算结果失真。 反演问题基本上都涉及解线性方程组，对于模型参数较多的反演问题，会出 现方程组的条件数很大的情况，使得求解不适定。对于网络层析成像反问题，实 际遇到的是解的唯一性和稳定性这两个问题。 2 1 - 3网络层析成像的反问题模型 图2 2 一股网络拓扑结构图 图2 2 为一般网络的拓扑结构，图中节点代表一台计算机或者子网。假设 x = ( x ，x ，) 为，维随机向量，反映感兴趣的网络动态参数信息，比如说链路丢 包率，某个时间间隔的网络流量等。l ，= ( x ，i ) 为j 维的测量向量，比如路径丢包 率，某个时间间隔内测得的链路流量等。网络层析成像的目的就是从观察得到的y 中估计出参数x 。对于一般网络层析成像问题可以表示如下：