（通信与信息系统专业论文）非平稳网络丢包率估计的层析成像方法研究.pdf

摘要 摘要 互联网已经由简单可控的小型网络，发展成为多种业务、多种平台、多种终 端的大规模复杂网络。然而互联网缺乏统一的管理和控制，且高度异构，从而无 法及时而准确地描述网络内部的各种状态参数及其变化情况，如链路丢包率、链 路延迟、链路带宽、网络拓扑结构等。为了提高互联网的管理和控制水平，进而 优化配置网络资源，一种新的估计网络内部参数的方法一“网络层析成像”，成 为了学术界和工业界共同关注的前沿课题。网络层析成像主要是基于端到端的路 径级网络测量数据，利用统计学方法，估计网络内部的链路级参数。传统的网络 层析成像方法假设链路参数的概率密度函数在探测周期内是不随时间变化而变化 的，即平稳网络层析成像，但是这种方法不能反映真实网络的时变特性，从而难 以实时追踪网络内部状态参数的变化情况。 针对传统网络层析成像方法在测量非平稳网络参数方面的不足，本文提出了 非平稳网络环境下的丢包率估计问题，将链路丢包率看作非平稳的随机信号实时 地进行追踪，解决了现有平稳网络层析成像丢包模型难以追踪链路丢包率随时间 变化而发生波动的问题，能以较小的代价获得网络链路丢包率的变化情况。 为了求解非平稳网络丢包率估计问题，本文借鉴解决反演适定性问题的理论 基础，提出了递归神经网络和最优化反演两种不同的估计方法。其中递归神经网 络主要是利用先验信息或部分网络协作信息对r m l p 网络进行训练，建立路径传 输率向量和链路传输率向量的映射关系，从而估计非平稳网络的丢包率。 最优化反演估计方法主要利用背靠背探测包对中两个分组经过共享链路时表 现出来的相关性，收集更多的统计信息，从而将欠定问题转换成为超定问题，以 实现在网络各个节点完全不协作的情况下求解非平稳网络的丢包率。 我们采用n s 2 仿真工具进行了实验，建立了统一的仿真模型，分别验证了两 种估计方法能够自适应非平稳网络丢包率随时间变化而产生的波动，以实时追踪 网络内部链路的丢包率。并根据实验结果，对这两种估计方法做了进一步的比较。 关键词：网络层析成像，非平稳网络，丢包率，递归神经网络，最优化反演 a b s t r a c t a b s tr a c t i n t e m e th a se v o l v e df r o ma s i m p l es m a l l - s c a l en e t w o r kt ot h ec o m p l e xl a r g e - s c a l e n e t w o r kw i t hm u l t i p l a t f o r m sa n dm u l t i - t e r m i n a l s b u ti n t e r a c tl a c k so fu n i f i e d m a n a g e m e n ta n dc o n t r o l ，s ot h a ti ti su n a b l et od e s c r i b et h ep e r f o r m a n c eo fn e t w o r k a c c u r a t e l y , s u c ha sl i n kl o s sr a t e , l a t e n c ya n dn e t w o r kt o p o l o g y t h et r a d i t i o n a lm e t h o d a c c e s s e st h en e t w o r kp e r f o r m a n c ef r o mi n t e r i o r , w h i c hm a yc a u s es o m ed i f f i c u l t i e s s u c ha s t h ec o s to fc o m p u t a t i o na n dc o m m u n i c a t i o n i no r d e rt oo v e r c o m et h e s e l i m i t a t i o n s ，i m p r o v en e t w o r km a n a g e m e n ta n dc o n t r o l ，t h e no p t i m i z et h ep e r f o r m a n c e o fn e t w o r k , i nr e c e n ty e a r s ，an e we s t i m a t i o na p p r o a c hn a m e d ”n e t w o r kt o m o g r a p h y ” w a sp r o p o s e d ，a n dh a sb e e nc o n c e r n e db yt h ea c a d e m i cc o m m u n i t y t h ee a r l yw o r k so fn e t w o r kl o s st o m o g r a p h yc o n c e r na b o u tt h el i n kl o s so f s t a t i o n a r yn e t w o r ku s e dm a i n l ys o m ea l g o r i t h mo fs t a t i s t i c s o b v i o u s l yt h i sa p p r o a c hi s u n a b l et ot r a c kt h er e a lt i m e - v a r y i n gc h a r a c t e r i s t i c so ft h en e t w o r k i nt h i sp a p e r , w e p r o p o s eal i n kl o s sm o d e li nn o n s t a t i o n a r yd a t an e t w o r k ，w h i c hw et h r e a ta sa n o n s t a t i o n a r yr a n d o ms i g n a l ，t h u st h el i n kl o s sc a nb et r a c k e dt i m eb yt i m e o u re s t i m a t i o nm e t h o dt os o l v et h el i n kl o s sp r o b l e mo fn o n s t a t i o n a r yd a t a n e t w o r ki sb a s e do nr e c u r r e n tn e u r a ln e t w o r ka n do p t i m i z a t i o ni n v e r s i o nm e t h o d r e c u r r e n tn e u r a ln e t w o r ki sm a i n l yt r a i n e db yp r i o ri n f o r m a t i o n ，t h e ne s t a b l i s ht h em a p b e t w e e nt h ee n d - t o e n dm e a s u r e m e n t sa n dt h ei n t e r n a ll i n kl o s sr a t e o p t i m i z a t i o ni n v e r s i o nm e t h o dm a i n l yu s e st h eb a c k - t o - b a c kp r o bp a c k e t st o c o l l e c tm o r es t a t i s t i c si n f o r m a t i o n ，w h i c hc a nc o n v e r tt h eu n d e r - c o n s t r a i n e dp r o b l e m i n t oo v e r - d e t e r m i n e do n e t h e nw eu s et h e o p t i m i z a t i o nm e t h o d t os o l v et h e o v e r - d e t e r m i n e de q u a t i o n sa n de s t i m a t et h en o n - s t a t i o n a r yn e t w o r kl i n kl o s sr a t e s i m u l a t i o n sa r ec a r r i e do u tu s i n gn s 2t od e m o n s t r a t et h ea c c u r a c yo fo u r e s t i m a t i o np r o c e d u r e ，w h i c ha l s os h o wt h ea b i l i t yo ft r a c k i n gt h el o s sr a t eo fl i n k si n r e a lt i m e w ea l s os h o wt h ef u r t h e rc o m p a r i s o no ft h e s et w oe s t i m a t i o nm e t h o d s k e yw o r d s ：n e t w o r kt o m o g r a p h y , n o n s t a t i o n a r yd a t an e t w o r k ，l i n kl o s s ， r e c u r r e n tn e u r a ln e t w o r k ，o p t i m i z a t i o ni n v e r s i o n i i 图目录 图目录 图2 1 系统反问题示例8 图2 2 互联网结构示意图9 图2 3 网络层析成像的物理拓扑树1 0 图2 4 网络层析成像的逻辑拓扑树1 4 图2 。5 具有4 个叶节点的完全二叉树一15 图2 6 路由矩阵4 15 图2 7 一颗简单二叉树1 6 图2 8 背靠背单播探测包18 图2 - 9 路径传输率己b ) 2 0 图3 1 神经元模型一2 4 图3 2 单层前馈网络2 5 图3 3 单层前馈网络求解分类问题2 6 图3 - 4 多层前馈网络一2 7 图3 5j o r d a n 递归网络2 8 图3 - 6 具有2 个隐藏层的r m l p 网络3 0 图3 7 有监督学习31 图3 8 链路丢包率的学习曲线3 7 图3 - 9 链路1 丢包率3 7 图3 1 0 链路2 丢包率3 8 图3 - 11 链路3 丢包率3 8 图3 1 2 链路4 丢包率3 8 图3 13 链路5 丢包率3 9 图3 1 4 链路6 丢包率3 9 图3 15 链路7 丢包率3 9 图4 1 牛顿算法框图4 4 图4 2 牛顿法的几何解释4 5 图4 3 牛顿算法的改进4 6 图4 4 链路l 丢包率4 9 图4 5 链路2 丢包率5 0 图4 6 链路3 丢包率5 0 图4 7 链路4 丢包率5 0 图4 8 链路5 丢包率5 1 图4 9 链路6 丢包率5l 图4 - 1 0 链路7 丢包率5l 图4 1 1 链路1 丢包率的拟合5 2 v 图目录 图4 1 2 链路2 丢包率的拟合5 2 图4 1 3 链路3 丢包率的拟合5 3 图4 1 4 链路4 丢包率的拟合5 3 图4 1 5 链路5 丢包率的拟合5 3 图4 1 6 链路6 丢包率的拟合5 4 图4 - 17 链路7 丢包率的拟合5 4 图4 1 8 两种估计方法性能比较5 5 v i 表目录 表目录 表3 1 激活函数r ：2 4 表3 2 异或( x o r ) 运算2 6 表3 3 多流d e k f 算法3 3 表3 4 仿真模型的链路参数设置3 6 表4 1 牛顿算法4 3 表4 2 递归神经网络和最优化反演估计方法性能比较5 5 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：三萆址日期：上佃绰f 月石日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：专i 特导师签名：叫内 日期：上咖了年f 月日 第一章绪论 1 1 研究背景 第一章绪论弟一早三百t 匕 为了满足人们越来越多的应用需要，互联网已经由简单可控的小型网络，发 展成为多种业务、多种平台、多种终端的大规模复杂网络。与另一个广泛应用的 电话网络不同，互联网缺乏统一的管理和控制机制，且高度异构，从而难以及时 而准确地描述网络内部的各种性能参数及其变化情况( 如链路丢包率、链路延迟、 链路带宽、网络拓扑结构等) 。 要更好地管理、控制和设计网络，就必须快速感知网络的各种状态参数及其 动态变化情况，如网络丢包率、网络延迟、网络拓扑结构、网络流量等，从而获 得整个网络的多域多层次的时空描绘。网络内部的各种状态参数的测量是准确实 施q o s 的保证，也是及时地评估网络性能，检测网络异常，优化网络设计等工作 的基础。目前，网络测量是获取网络状态参数的主要方法，它内容涵盖广泛，包 括：网络丢包率测量、网络时延测量、网络带宽测量、网络拓扑发现、网络距离 测量、路由器流量测量以及路由器调度策略和瓶颈缓冲器容量测量。 传统的网络测量方法主要是从内部获取网络的各种性能参数，即在网络节点 之上或者网络节点之间直接测量。但是，随着网络向大型化、异构化、分布化发 展，使得互联网结构日益复杂。如果直接测量网络中每条链路的丢包率或者每条 链路的时延等网络状态参数，需要各个不同域内的通信节点进行充分的协作。 然而，对于不同的互联网服务提供商而言，基于商业保密性的考虑，通常只 会提供部分节点来完成一定程度的协作工作，使得网络测量结果可能不会覆盖到 测量者所感兴趣的链路上。因此，要获得全面而准确的网络测量往往是很困难的。 实际上，采用从网络内部直接进行测量的方法，由于总是针对各条链路和各个节 点进行测量，这就导致每条链路都将引入大量额外的网络流量开销，每个节点都 会极大地消耗存储转发等各种计算资源。另外，在大尺度网络中，大规模的网络 测量需要大量中间路由器的配合，然而这在实际的大型网络中往往是难以办到的， 因为许多网络节点，特别是移动自组织网络中的节点，由于种种原因无法耗费大 量的资源( 如资源有限、不愿协作、或无法正常工作等) 用于大规模的网络测量。 电子科技大学硕士学位论文 正是基于以上各种原因，从而严重地限制了直接网络测量方法的广泛应用。 由于上诉内部网络测量方法的局限性，导致了端到端测量方法的引入，实际 应用的工具包括：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 包经 常被防火墙等设备过滤掉，以至于根本就不能响应，从而使这些方法也存在潜在 的缺陷。 随着互联网规模的不断扩大、结构日益复杂，服务质量保证、网络异常监测 等重大课题面临着前所未有的挑战。网络技术的飞速发展，使网络类型越来越多， 网络的结构越来越复杂，网络各种状态参数的变化也越来越复杂，为了更好地管 理、控制和设计网络，防止外来的攻击，就必须及时而准确地了解和掌握网络的 内部特性，高速感知网络状态参数的动态变化情况，从而获得整个网络状态的多 域多层次时空描绘。而在实现所有这些目标的同时，又不能大量增加网络负荷， 不能要求大量的路由器参与工作，而且在网络的某个局部遭受到灾害不能正常工 作的情况下，也能高速感知各种网络状态参数及其动态变化情况。但是不同组织 或部门之间不愿意分享其网络状态，缺乏相互协作又加剧了问题的复杂度。 为了实现上述高速感知各种网络状态参数及其动态变化情况的目标，提高网 络的管理和控制水平，进一步提高获取网络状态参数的实时性和有效性，国际上 许多研究机构和学者都在寻找新的途径来探测网络的性能。网络层析成像【2 ，3 】 ( n e t w o r kt o m o g r a p h y ) 就是目前在国际学术界备受关注的新技术之一。近年来， 该方法取得了长足的进步，取得了大量的研究成果，并得到了工业界的广泛关注。 网络层析成像主要是利用基于端到端的路径级网络流测量数据来得到链路级 参数的估计。通过主动发包探测或者被动收集网络内部实际通信数据的方法，网 络层析成像技术利用统计学理论能够很好地推理出大尺度网络内部链路的状态参 数及其变化情况。该技术的优势在于： 能够解决大规模网络测量问题。互联网是分散、异构的，一般测量方式只 能探测其中很小一部分，网络层析成像能对大规模网络进行测量，研究其性能分 布情况和拓扑结构，得到网络性能分布和拓扑结构的全局视图。 在缺少协作的条件下，一般的网络测量方法只能获得端到端的性能参数。 网络层析成像技术通过端到端测量技术和统计学方法，能够推导出网络内部的状 态特征，例如链路丢包率、链路延迟、链路带宽、网络拓扑结构等。 2 第一章绪论 网络层析成像技术利用端到端测量技术和统计学方法，只发送少量的探测 包，或者甚至直接通过被动采样正常通信数据，就可以获得大规模网络探测数据， 不会造成过多的网络负荷。 1 2 研究方向和现状 层析成像( t o m o g r a p h y ) 技术也称计算机层析成像( c o m p u t e r i s e d t o m o g r a p h y ) 技术f z 2 - 2 4 1 ，简称c t 技术，是本世纪7 0 年代初首先在医学工程上得以成功应用并 蓬勃发展起来的一项新技术。目前，c t 技术在医学工程上已经形成了一套完善的 理论和方法，广泛应用于临床医学诊断和病理研究。与此同时在医学工程上已被 成功应用的一些成熟的理论和方法还被应用于射电天文学、雷达探测、电子显微 镜图形学、地震学、地质勘探等非医学领域。c t 技术的出现不仅促进了现代医学 技术的发展，而且还促进了计算机的应用，对电子学、数学、生物电子学及生物 基础理论的研究和发展也起了积极的推动作用。 网络层析成像正是借鉴了层析成像技术的思想提出的一种新的网络测量方 法。网络层析成像可以分为两大类，网络链路级( 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 ) 流量估计层析成像： 网络链路级参数估计层析成像，主要是利用基于端到端的路径级网络测量 数据来得到链路级的参数估计【8 - 3 3 1 ，通过主动发包探测或者被动收集网络内部实际 通信数据的方法获得网络路径级观测数据，利用统计学理论推导出网络内部的链 路参数。 网络o d 流量估计层析成像，主要是利用基于链路级网络测量数据来得到 路径级参数的估计，是网络链路级参数推理的反过程，其目的就是从可测量得到 的各链路级的测量数据中估计出路径级的网络参数。 本文只讨论网络链路级参数估计层析成像，本文所提及的网络层析成像也仅 仅局限于网络链路级参数估计层析成像，该领域的研究主要集中在链路丢包率、 链路延迟和链路带宽等网络状态参数的估计上，更一般的问题可以扩展到其他参 数，比如可用带宽和服务原则的重建。 根据网络内部行为的统计特性可以把网络层析成像的研究分为两个大的方 向：平稳网络层析成像的研裂1o 】- 【1 5 1 和非平稳网络层析成像的研究【1 7 】【2 l 】。 3 电子科技大学硕士学位论文 1 2 1 平稳网络层析成像 平稳网络层析成像按照探测包的发送方式可以分为多播层析成像和单播层析 成像。在多播通信中，源节点可以把每个包发送给一组目的节点，在每个分叉点 的路由器上，多播包被复制并延着分支路径传送出去。而在单播通信中，每个包 只能被发送到一个，而且也仅仅是一个目的节点。 有关网络层析成像早期的工作【4 j - 【9 】主要是通过发送端到端的多播探测包，并分 析这些探测包的统计特性来估计链路的状态参数。马萨诸塞州大学的m 1 n c 工程 是多播网络层析成像方面的先驱。m i n c ( m u l t i c a s t - b a s e di n e f r e n c eo f n e w t o r k - i n t e n r a lc h a r a c t e r i s t i c s ) 项目主要是研究推导网络内部链路状态参数的方 法，该研究提出了多播网络层析成像方法的数学模型，论证了多播层析成像算法 的有效性、正确性和收敛性。该项目通过m t r a 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 等人在多播网络层析成像技术的基础上，研究并实现了单播网络层析 成像技术，在目前大多数网络不支持多播路由的背景下有很强的实际意义。他们 的工作是建立了网络内部链路丢包率的b e m u l l i 模型，并使用极大似然和e m 算法 求解了该模型。 之后，单播探测方法取得了长足的进步，除了采用背靠背探测包外，还出现 了采用三包组乃至多包组单播探测包的方法 1 0 1 - 1 5 1 。值得注意的是，虽然单播探测 方法把网络层析成像技术向实际应用推进了一步，但是由于其探测包对的相关性 较弱，且算法的复杂度较高，因此估计结果的准确度也有所降低。 无论是上诉的多播探测方法还是单播探测方法，都是假设测量的网络环境是 平稳的，网络内部链路参数的概率密度函数在探测周期内是不随时间变化而变化 的，即如果把链路的参数看作是随机信号，该随机信号是平稳的。我们统称这些 方法为平稳网络的层析成像。 平稳网络层析成像采用的模型与求解这些模型相应的估计算法主要包括：基 于累积量生成函数( 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 ) 模型，以及相应的广义 逆的最d x - - 乘法 1 6 】；基于离散【2 5 h 3 0 1 或者连续1 0 , 3 1 概率密度函数模型( 比如混合高 斯概率密度函数) ，以及相应的极大似然法，由于网络层析成像问题的复杂性，极 4 第一章绪论 大似然值很难直接得到解析解，故大多采用e m ( e x p e c t a t i o nm a x i m i z a t i o n ) 算法 【2 5 1 迭代求解；其它一些估计方法还包括：m c m c 方法【3 3 1 、有限混合指数模型e m 算法【3 1 1 、m m p l e 方法1 2 6 】、贝叶斯方法【3 2 】等。 平稳网络层析成像的主要局限在于假设了网络链路参数的概率密度函数在测 量周期内是固定不变的( 或者说非时变的) 。无论是以上哪种平稳网络层析成像模 型，以及为求解该模型所采用的估计方法，由于其模型本身无法反映真实网络的 时变特性，从而难以实时追踪网络链路参数的变化情况。 1 2 2 非平稳网络层析成像 针对传统网络层析成像方法的不足，非平稳网络层析成像把链路参数看作随 机信号，并且假设该随机信号是非平稳的，即概率密度函数在测量周期内是时变 的，从而能够追踪链路参数随时间变化而发生的波动，更好地模拟真实网络环境。 非平稳网络层析成像摆脱了平稳网络层析成像的局限，从而更能够反映实际网络 的动态本质。 非平稳网络层析成像的研究主要集中在网络延迟领域，其中m a r kj c o a t e s 和 r o b e r td n o w a k 等人建立了非平稳网络的延迟估计模型【l 刀，并采用序贯蒙特卡洛 方法( 即粒子滤波器) 来追踪时变参数，较好地估计了网络平均延迟。但是粒子 滤波器、卡尔曼滤波器等贝叶斯滤波性能依赖于估计模型的先验信息，而实际网 络中的队列延迟，很难用精确的数学模型来准确定义，这会导致该估计方法性能 下降或者不稳定。 文献 2 1 1 在上诉非平稳网络的延迟层析成像模型的基础上，采用了r m l p 递归 神经网络对非平稳网络的延迟模型进行估计，追踪了非平稳网络链路的平均延迟， 估计了链路延迟的概率密度分布，该算法较序贯蒙特卡洛方法具有更小的预测误 吉圭 z lo 由于非平稳网络层析成像问题比较复杂，故相关研究较少【1 7 】【2 1 1 ，且多集中在 网络延迟领域，关于非平稳网络层析成像另一个非常重要的领域网络的丢包 率，几乎还没有文献提出相应的模型，以及求解模型的估计方法，其研究内容仍 然停留在平稳网络的丢包率层析成像上，因而无法追踪网络链路的丢包率随时间 变化而发生的波动。 5 电子科技火学硕士学位论文 1 3 本文研究的主要内容及意义 针对现有网络层析成像丢包率模型难以追踪链路丢包率随时间变化而发生的 波动的现状，本文提出了一种非平稳网络丢包率模型，更好地模拟了真实的网络 环境。同时为了求解该模型，本文采用了递归神经网络和最优化反演两种不同的 估计方法，取得了较好的效果。本文所研究的内容丰富和扩展了网络层析成像的 研究领域，为非平稳网络层析成像的研究工作提供了新的思路和技术。 本论文的主要内容及创新点在于： ( 1 ) 非平稳网络丢包率问题的研究 网络的丢包主要是由于在流量高峰期，众多用户相互争夺链路资源，从而造 成路由或交换设备过载引起的，当然网络的丢包也可能是由于链路的噪声和存储 转发设备的故障。但无论是基于以上哪种原因，网络丢包现象都存在固有的随机 性，因此该问题可以归结为一个统计模型：y = a x + g 。 本文在以上模型的基础上，提出了非平稳网络丢包率模型：j ，( f ) = 似( f ) + 占( f ) ， 它能够进一步地追踪网络内部链路丢包率随时间变化而发生的波动，从而更好地 模拟了真实的网络丢包环境。 ( 2 ) 递归神经网络估计非平稳网络丢包率的方法研究 神经网络 3 4 , 3 5 】是由众多简单处理单元构成的大规模并行分布式计算系统，其 学习能力以及由此而来的泛化能力可以较好地逼近复杂的非线性问题。 递归神经网络是有反馈环的神经网络，反馈环的应用使得神经网络获得状态 的表示，从而具有联想能力，大大减少了记忆的需求，并在输入数据和输出数据 之间建立直接的映射关系，这使得它更适用于非线性预测和建模。 本文采用了r m l p ( r e c u r r e n tm u l t i l a y e rp e r c e p t r o n ) 递归神经网络【3 0 3 酬，利 用先验信息或部分网络的协作信息对r m l p 网络进行训练，建立路径传输率向量 y o ) 和链路传输率向量x o ) 的映射关系，解决了非平稳网络丢包率模型的欠定问 题，从而求解了该模型，同时不断追踪链路参数随时间变化而波动的情况，实现 了网络丢包率估计的的实时层析成像方法。 ( 3 ) 最优化反演估计非平稳网络丢包率的方法研究 递归神经网络估计方法虽然效果较好，准确度较高，但是需要网络的部分节 点协作，至少是在一定时间内进行协作，从而获得先验信息以完成对r m l p 网络 的初始化训练。 为了实现在网络各个节点完全不协作的情况下，求解非平稳网络丢包率模型， 6 第一章绪论 我们进一步发掘背靠背包的统计特性，利用背靠背探测包对中两个分组经过相同 链路时表现出来的相关性，将欠定问题转换成超定问题，利用最优化反演理论估 计非平稳网络各条链路的丢包率。 1 4 本文结构与内容安排 本论文的研究工作得到了国家自然科学基金( 6 0 5 7 2 0 9 2 ) “网络层析成像关键 技术研究”课题的支持。本文共分为五章，其内容安排如下： 第一章概述了本文的主要内容，介绍了研究背景、研究方向及其现状，提出 了本文的创新点和研究意义。 第二章首先介绍了网络层析成像的反问题模型，接着以此为基础，建立了非 平稳网络的丢包率模型，并提出求解该模型的两种层析成像估计方法递归神 经网络估计方法和最优化反演估计方法。 第三章重点论述了递归神经网络估计方法。首先概要介绍了神经网络基础， 并引出了递归神经网络模型；接着我们采用r m l p 递归神经网络估计了非平稳网 络的丢包率，描述了选用的r m l p 网络的网络结构和该网络的训练算法。为了验 证该估计方法的有效性和性能，我们利用n s 2 仿真工具建立了实验仿真模型，对 算法进行了仿真验证。 第四章提出了最优化反演估计方法，首先概要介绍了最优化反演方法的理论 基础，之后描述了牛顿算法及其改进，并采用它估计了非平稳网络的丢包率。该 估计方法同样利用n s 2 仿真工具进行了验证，最后我们还对第三章和第四章提出 的两种估计方法进行了比较。 第五章总结全文，提出了未来的工作方向。 7 电子科技大学硕士学位论文 第二章非平稳网络的丢包率估计问题 2 1 网络层析成像的反问题模型 2 1 1 反问题模型的提出 层析成像( t o m o g r a p h y ) 技术的实质是根据模型，利用观测结果估计模型参 数的反问题求解。在不同的科学技术领域中，对反问题的定义是不同的： 根据数学的观点，反问题是在给定的子空间中寻找与函数空间中根据反问 题预先确定的目的点最靠近的点。 根据统计学的观点，反问题是回归和参数估计问题。 根据信息论的观点，反问题实质是信息传递过程，后验信息= 先验信息 ( 经验信息) + 观测信息+ 理论信息。 从系统论的角度，反问题实际上需要求解的是系统模型的状态参数，是一 个系统辨识问题。 反问题的求解过程称为“反演”，这一术语与“正演”是相对应的。正演是根 据某些一般性原理和模型来预测具体的模型参数所激励的结果数据。而反演，恰 恰是处理与正演相反的问题，即从观测到的数据及某些一般性原理和模型出发， 来估计模型参数。它们可用以下过程来描述： 正演：模型参数一模型一观测数据 反演：观测数据一模型一模型参数估计值 系统输入x 系统输出y l 系统传递函数 l rr 彳 图2 1 系统反问题示例 对于线性系统反问题的形象表述如图2 1 所示，我们假设模型的观测数据为系 8 第二章非平稳网络的丢包率模型 统输出l 模型参数或其估计值为系统输入五系统传递函数为a ，于是我们可以 将上面的过程重新表述为： 正演：已知x 和么，求】， 反演：已知y 和a ，求x 一般而言，由于正演模型是确定的，模型参数是完备的和无噪的，所以正问 题的解都是唯一确定的。而在反问题中，实际观测数据总是含有噪声，并且在多 数情况下难于观测到全部的信息。因此，造成了反演问题通常具有多解性。 网络层析成像作为一种检测和研究网络的整体性能及其变化规律的技术，借 用上述的理论和方法，通过主动发包探测方法或者被动收集网络内部有用信息的 方法获得网络路径级观测数据，再根据统计学方法估计网络内部链路的状态参数 ( 包括链路丢包率、链路延迟、网络拓扑结构和网络流量等) ，这样就可以将网络 内部链路参数的求解看作一个反问题的求解。 图2 2 互联网结构示意图 9 电子科技人学硕士学位论文 以图2 2 所示的互联网结构示意图为例，来说明网络层析成像的反问题模型。 图中包括一个骨干传输网( 如广泛应用的s d h 光传输网) ，该骨干传输网向下连 接到多个区域i s p 。有多个局域网( 如以太网、f d d i 令牌环网) 接入到各个区域 i s p 网络中，局域网中主要是大量的互联网终端用户。s n a 网络直接接入骨干传 输网，它代表互联网中各种各样的数据中心，数据中心里的服务器为终端用户提 供千变万化、多姿多彩的互联网内容服务。图中的各个节点可以代表一台路由设 备，也可以代表一个子网。这个网络结构示意图和今天互联网结构的非常相似。 我们将s n a 数据中心网络中的服务器作为源节点，局域网中的各个终端计算 机作为目的节点，就可以将图2 2 的互联网结构示意图抽象为图2 3 所示的一颗物 理拓扑树，该拓扑树由计算终端、路由设备和物理链路构成，从源节点到目的节 点经过的多条链路构成了一条路径。 路由设备计算终端l 物理链路 图2 3 网络层析成像的物理拓扑树 我们假设x = 伍。，x ：，x j ) 7 为，维随机向量，它反映了如图2 3 所示网络 物理拓扑树中我们感兴趣的网络内部链路参数，如链路的丢包率、链路的延迟、 链路的带宽等。y = 瓴，砭，t ) r 为i 维的测量向量，表示网络中从源节点到目 的节点的端到端的观测数据，即与x 相对应的路径的丢包率、路径的延迟、路径 的带宽等。网络层析成像的目的就是从观察得到的路径级观测数据】，中估计出链 1 0 第二章非平稳网络的丢包率模型 路级状态参数兄更一般的，在图2 2 所示的互联网中，任意的源节点和目的节点 都可以组成一颗物理拓扑树，对于一般的网络层析成像问题可以统一表述为： y = a x + s( 2 1 ) 其中，彳为已知的，维路由矩阵，由网络的拓扑结构和网络中每个路由器 的路由表决定。值得注意的是，本文中我们严格假定路由是固定，并忽视路由动 态变化的可能，即在一次测量中4 是始终固定不变的。彳矩阵的行代表路径i ，列 代表链路，矩阵元素为0 或1 ，其中1 代表路径i 上有链路，。占可能是测量数据 y 产生的加性噪音，也可能是x 关于其均值的随机偏差，占的引入平衡了由于反问 题的求解而可能产生的各种误差。方程2 1 反映了网络测量的集合本质，因而，对 网络内部的链路状态参数x 的估计是一个反问题求解过程。 2 1 2 网络层析成像反问题的适定性 在网络层析成像反问题模型y = a x + s 中，我们不难发现，端到端的路径级 观测数据y 的维数，普遍小于网络内部链路级参数彳的维数，即通过端到端测 量获得的信息量不能满足求解网络内部链路级参数的要求，从而造成解的不唯一 或不稳定。这就是反问题求解的病态问题( i 1 1 p o s e dp r o b l e m ) 或不适定问题。对 于典型的不适定问题，在拟合误差很小的情况下，其反演结果仍然可能出现较大 的偏差。参数反问题的不适定性问题一直都是该领域的瓶颈，正是因为反问题的 不适定性，工程界对参数反演结果的可靠性需要进一步验证，这也是制约反演方 法更广泛应用于实践的一个主要障碍。 反问题的唯一性与可辨识性是紧密相关的，其中一个重要而难度极大的问题 便是提出反问题可辨识的充要条件。由于受测试条件限制，仅仅根据有限的观测 数据求解反问题，不能保证反演解的唯一性，即对不同的初始估计值将得到不同 的辨识结果。这种解的非唯一性不是由于反演方法和技巧上的缺陷引起的，而是 反问题本身存在的固有困难。 一般而言，若反问题研究对象的物性参数均匀，待辨识的物性参数可简化为 有限的几个常量，实测信息多于未知量数目，此时的反问题易得到唯一解。反之 若研究对象非均匀性较强，待辨识的参数分布复杂，有限的实测信息不能完全确 定参数的时空分布，此时反演解是不唯一的，不得不采取降低辨识精度( 相应减 少了待辨识的未知量) 的策略来达到可辨识的目的。网络层析成像正是属于这种 类型的反问题。 电子科技大学硕士学位论文 反演问题的另一个特征是非线性，即观测数据和相关参数之间，由于后者的 极小变化将引起前者的很大变化。而且，由于任何观测资料都存在干扰和误差， 这种畸变的观测数据也会使反演计算不稳定，即观测数据中少量的误差将引起待 辨识参数的很大变动，而不稳定的程度与所采取的反演方法密切相关，严重的情 况下甚至会使计算结果失真。 从式2 1 不难看出，网络层析成像的反演问题基本上都涉及解方程组，对于这 种模型参数较多的反演问题，会出现方程组的条件数不够的情况，使得解不适定。 根据以上理论，我们再次讨论方程2 1 ，该方程为良态方程需要具备以下三个条件： 在定义域内，对应每一个y ，都有解x 存在； 方程的解z 是唯一的； 当y 有微小的扰动时，在没有其他限制条件的情况下，解x 只产生微小的 变化。 如果上面三个条件任意一个不满足，就是病态的。第一个条件为解的存在性 条件；第二个条件为唯一性问题，不满足则常常被称为“伪逆问题 ；第三个条件 为稳定性条件，被称为病态问题。以上三个解的存在性、唯一性和稳定性条件总 称为反问题的适定性。 由于受测试条件的限制，在一般网络层析成像问题中，么一般都不是满秩的矩 阵，尺u 很典型的，也就是说方程为欠定方程，而欠定方程一般有无穷多个解。 因此不能保证网络层析成像问题反演解的唯一性，即对不同的初始估计值将得到 不同的辨识结果。因此需要加入一些限制条件，例如对于丢包率估计，可以加入 测量策略，使反演方程变成超定方程以便于保证模型的可辨识性。 在网络层析成像领域，一般假设x 向量中的所有元素相互之间都是统计独立 的，若每个元素表示为：x ，= ( 口) ，= 1 , 2 ，j ，其中，为密度函数，9 ，是 它的参数，那么所有的模型的参数就为秒= ( 幺，口：，9 ，) 。一般而言，如果网 络层析成像反问题研究对象x 的参数分布很均匀，待辨识的物性参数可简化为有 限的几个常量，实际测量得到的数据多于未知量数目，此时的反问题易得到唯一 解。但是由于网络环境的复杂性，导致估计对象x 具有较强非均匀性，待辨识的 参数分布复杂，有限的观测信息不能完全确定参数的时空分布，此时反演结果是 不唯一的。 因此，对于网络层析成像反问题，实际遇到的是解的唯一性和稳定性这两个 问题。对不适定问题可以根据以下的三个方法提高参数辨识的可信度： 1 2 第二章非平稳网络的丢包率模型 依据先验信息建立合理的初始模型，若该问题属于多子问题的藕合，则也 应该建立相应子问题的模型； 对测试数据作细致的预处理，不仅要剔除误差大的不合理数据，更重要的 是使反演使用的测量值和正演模型计算理论值有相同的意义，或者说具有同等可 比性； 最后需要开发一种可靠的、受人为影响因素较小的、全局收敛的算法。 本文正是根据这三条理论依据，选用了递归神经网络和最优化反演两种估计 方法，求解了非平稳网络的丢包率模型这一反问题。 2 2 非平稳网络的丢包率 根据网络层析成像的反问题模型基础，本节我们将建立非平稳网络的丢包率 模型，以便能够进一步地追踪网络内部链路丢包率随时间变化而发生的波动，从 而更好地模拟真实的网络丢包环境。 2 2 1 非平稳网络 为了建立非平稳网络的丢包率模型，我们首先需要定义非平稳网络的网络模 型。考虑这样一个场景，在图2 3 所描述的网络物理拓扑树中，一个源节点( 或一 组源节点) 向一组目的节点发送分组。从源节点到目的节点的端到端的路径级行 为可以通过一定的测量方法进行收集：在主动探测方法中，源节点向目的节点直 接发送探测包，通过收集和统计探测包的信息，从而获得端到端的行为特征：在 被动探测方法中，源节点和目的节点之间发送正常的通信数据包，源节点和目的 节点被动收集这些数据包的行为特征( 比