（通信与信息系统专业论文）时空关系约束的流量矩阵估计方法研究.pdfVIP

中文摘要 中文摘要 随着i n t e m e t 飞速发展，网络结构也在发生深刻变化，要成功设计、控制和管 理网络，就需要了解和掌握网络的内部特性。流量矩阵作为网络流量工程的重要 参数，可以为网络规划、拥塞控制、流量检测、故障诊断等流量工程和网络管理 提供有力保障。由于网络日益向着大型化、异构化、分布化发展，通过直接进行 网络测量的方法来获得流量矩阵信息是非常困难的，因而通过链路流量数据估计 流量矩阵成为当前的热点研究问题。流量矩阵估计问题本身是一个欠定反问题， 存在多解性，要获得真实解，需要根据流量矩阵估计问题的特点，引入o d 流量 矩阵的一些约束信息，缩小解空间，从而克服流量矩阵估计的多解性。在本文中， 我们认为在一定时间内流量矩阵在时间上和空间上存在某种关系，利用这种时空 关系，可以获得更加准确的流量矩阵估计结果。 针对大尺度骨干网流量矩阵估计具有高度病态性的特点，利用模拟退火方法 简单并且容易搜索到局部最优解的特点，提出了基于模拟退火算法来求解流量矩 阵估计问题的方法。采用了以下策略来提高估计精度：( 1 ) 针对不同初始猜测带 来的多解性，采用i p f p ( i t e r a t i v ep r o p o r t i o n a lf i t t i n gp r o c e d u r e ) 校正后的流量矩 阵各o d ( o r i g i n d e s t i n a t i o n ) 流量历史均值作为初始猜测值，历史流量均值作为 初始猜测值利用了o d 流量在时间上的相关性，i p f p 校正利用了o d 流量在空间 上的相关性，这样的选择可以使初始值接近真实值，提高求解精度。( 2 ) 在模拟 退火搜索过程中，利用链路流量信息，求出每条o d 流的范围，然后将模拟退火 解的搜索空间限制在该范围内，缩小了解空间的范围，降低了流量矩阵估计的多 解性。仿真结果表明该方法实时性高，估计精度优于基于广义重力模型的流量矩 阵估计方法。 本文还提出了一种基于时空关系的粒子滤波器估计方法，假设各个时刻的o d 流量为一阶马尔可夫过程，利用贝叶斯推断方法求取后验均值获得估计结果，为 提高方法的实用性，采用了如下策略：( 1 ) 针对该方法对先验值敏感，导致流量 矩阵估计的多解性，假设o d 流服从更能反映o d 流真实分布的g a m m a 分布，引 入方阵形式的o d 流的时空关系，从而建立更为精确的关于o d 流量矩阵估计的动 态贝叶斯模型，从而引入更多的o d 流先验信息，减少了后验模型；( 2 ) 为降低 求解的复杂度，本文采用基于采样重采样m c m c 的粒子滤波器估计方法进行参 中文摘要 数估计，完成了g a m m a 模型下的动态贝叶斯模型参数估计：( 3 ) 为进一步提高求 解精度，在滤波过程中对g a m m a 分布参数进行采样，达到增加o d 流值采样空间 的目的，从而使粒子滤波结果更加精确。仿真结果表明，基于时空关系的粒子滤 波估计方法估计精度优于基于模拟退火的流量矩阵估计方法以及基于广义重力模 型的流量矩阵估计方法。 关键词：流量矩阵，模拟退火，g a m m a 模型，动态贝叶斯模型，粒子滤波器 a b s t r a ( 了r 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 ei n t e m e t , t h es t r u c t u r eo ft h en e t w o r kh a s 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 og e ti n t ot h ei n n e rp r o p e r t yo ft h es p e c i f i cn e t w o r k t od e s i g n , c o n t r o la n dm a n a g ei ts u c c e s s f u l l y t r a f f i cm a t r i xi sa ni m p o r t a n tp a r a m e t e r o fn e t w o r kf l o w e n g i n e e r i n g , i tc a np r o v i d es t r o n gg u a r a n t e ef o rn e t w o r kf l o w e n g i n e e r i n ga n dn e t w o r km a n a g e m e n ts u c ha sn e t w o r kp l a n n i n ga n do p t i m i z a t i o n , t r a f f i cc o n g e s t i o nc o n t r o l ，t r a f f i ca n o m a l yd e t e c t i o n i ti sd i f f i c u l tt om e a s u r et r a f f i c m a t r i xd i r e c t l ya st h ei n t e m e ti sb e c o m i n gm a s s i v e , d i s t r i b u t e da n dh e t e r o g e n e o u s e s t i m a t i n gt r a f f i cm a t r i xf r o ml i n kd a t an o w i sb e c o m i n gar e s e a r c hf o c u s ，t r a f f i cm a t r i x e s t i m a t i o ni sa l li l lp o s e dp r o b l e m ，i th a sm u l t i p l er e s u l t s ，i no r d e rt og e tr e a lc o r r e c t r e s u l t , w en e e ds o m ec o n s t r a i n ti n f o r m a t i o na c c o r d i n gt ot h ec h a r a c t e ro ft h et r a f f i c m a t r i xe s t i m a t i o n ，s h r i n k i n gt h es o l u t i o ns p a c e , t os o l v et h em u l t i p l er e s u l t sp r o b l e m i n t i f f sp a p e r , w ei n t r o d u c et i m ea n ds p a c er e l a t i o n s h i p sa m o n gt r a f f i cm a t r i xa tac e r t a i n p e r i o do ft i m et ot r a f f i cm a t r i xe s t i m a t i o nm e t h o d sa n dg e tm o r ea c c u r a t er e s u l t s l a r g e s c a l ei pt r a f f i cm a t r i xe s t i m a t i o ni sh i g h l yi l lp o s e d s i m u l a t e da n n e a l i n gi s s i m p l ea n dc a ne a s i l yg e tt h el o c a lo p t i m a ls o l u t i o n b a s e do nt h e s ef e a t u r e s ，w e i n t r o d u c e dan e wa l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n ga l g o r i t h mt os o l v et r a f f i c m a t r i xe s t i m a t i o n w ea d o p tt h ef o l l o w i n gs t r a t e g i e st oi m p r o v ee s t i m a t i o na c c u r a c y ： ( 1 ) f o rt h em u l t i p l es o l u t i o n sc a u s e db yd i f f e r e n ti n i t i a lg u e s s ，u s i n ge v e r yo dt r a f f i c h i s t o r i c a la v e r a g er e s u l tr e g u l a t eb yi p f p ( i t e r a t i v ep r o p o r t i o n a lf i t t i n gp r o c e d u r e ) t o b et h ei n i t i a l g u e s s ，h i s t o r i c a la v e r a g er e s u l tr e f l e c tt h et i m er e l a t i o n s h i p ，i p f p r e g u l a t i o nr e f l e c tt h es p a c er e l a t i o n s h i p ，t h i si n i t i a lg u e s sa p p r o a c hm o r et ot h er e a l t r a f f i c ，c a ni m p r o v et h ea c c u r a t eo fs o l u t i o n ( 2 ) i nt h ep r o c e s so fs i m u l a t e da n n e a l i n g , w eg e te v e r yo dt r a f f i c sr a n g ef r o ml i n kt r a f f i c ，t h e nn a r r o wt h es o l u t i o nr e a c h i n g s p a c e , r e d u c et h em u l t i p l es o l u t i o n s s i m u l a t i o nr e s u l t ss h o wt h a tt h i sa l g o r i t h mh a s l l i g hr e a l - t i m ep r o p e r t y , t h ee s t i m a t i o na c c u r a t eb e t t e rt h a ng e n e r a l i z e dg r a v i t ym o d e l i n t h i sp a p e rw ei n t r o d u c ea n o t h e r p a r t i a lf i l t e ra l g o r i t h mb a s e do nt i m ea n ds p a c e r e l a t i o n s h i p ，i ta s s u m et h a to dt r a f f i ci sa1 - t i m em a r k o vp r o c e s s ，u s i n gb a y e s i a n m e t h o dt og e tp o s t e r i o ra v e r a g ea se v e n t u a le s t i m a t i o nr e s u l t i no r d e rt oi m p r o v et h e a b s t r a c t p r a c t i c a l i t y , w ea d o p tt h ef o l l o w i n gs t r a t e g i e s ：( 1 ) t h em e t h o di ss e n s i t i v et ot h ea p r i o r iv a l u ec a u s i n go fm u l t i p l er e s u l t s ，w em o d e lt h eo d t r a f f i cu s i n gg a m m am o d e l t h a tr e f l e c t so dt r a f f i c sc h a r a c t e rm o r er e a l i s t i c a l l y w ei n t r o d u c et h et i m ea n ds p a c e r e l a t i o n s h i pb ym a t r i xf o r m ；e s t a b l i s hm o r er e a l i s t i c a l l yd y n a m i cb a y e s i a ns y s t e m ， r e d u c et h ep o s t e r i o rm o d e l ( 2 ) i no r d e rt or e d u c et h ec o m p l e x i t yo ft h i sm e t h o d ，w eu s e p a r t i c l ef i l t e rb a s e do ns a m p l e - - r e s a m p l e - m c m ct oe s t i m a t et h ep a r a m e t e ro fg a m m a m o d e ld y n a m i cb a y e s i a ns y s t e m ；( 3 ) i no r d e rt of u r t h e ri m p r o v ea c c u r a c y , f i r s t l yw e s a m p l eg a m m am o d e lp a r a m e t e rt oe x p a n dt h es a m p l es p a c eo fo d t r a f f i c s i m u l a t i o n r e s u l t ss h o wt h a tt h i sa l g o r i t h mi sb e t t e rt h a nt h ee s t i m a t i o nm e t h o db a s e do ns i m u l a t e d a n n e a l i n g a n dg e n e r a l i z e dg r a v i t ym o d e l k e y w o r d s ：t r a f f i cm a t r i x ，o dt r a f f i c ，s i m u l a t e da n n e a l i n g , p a r t i a lf i r e ，g a m m a m o d e l ，d y n a m i cb a y e s i a ns y s t e m 图目录 图目录 图1 1o d 流的两级分类方式2 图1 2 流量矩阵估计过程5 图1 3o d 流量估计简单拓扑结构6 图2 1i p 网络各元素及术语1 4 图2 2i s p 网络中的不同o d 流量1 5 图3 1 模拟退火估计方法的系统框图2 2 图3 2 搜索空间2 4 图3 3a b i l e n e 网络拓扑结构2 5 图3 44 8 号o d 流估计结果对比图一2 7 图3 59 6 号o d 流估计结果对比图2 8 图3 6 时间相对误差对比图2 9 图4 _ 1o d 流状态空间模型3 5 图4 _ 2 动态贝叶斯模型3 7 图4 3 基于粒子滤波器的o d 流估计流程图3 8 图4 - 4 真实流量与p f t 估计结果对比图一4 4 图4 - 5s a ，p f t 时间相对误差对比图。4 5 图4 _ 66 7 ，11 6 号o d 流p f t ，p f t s 结果对比图。4 7 图4 _ 79 6 ，1 4 1 号o d 流p f - t ，p f - t s 结果对比图一4 8 图4 88 7 ，1 0 8 号o d 流p f t ，p f t s 结果对比图4 9 图4 9p f t s ，p f t 时间相对误差对比图5 0 j ，i l 表目录 表目录 表1 1简单网络路由表6 表2 1o d 流估计方法分类10 表3 1t m 估计中的i p f p 算法2 1 表4 - 1第四章符号说明3 4 缩略词表 英文缩写 t m o d s p t m l e q o s i s p c b r i u - r p o p e m o s p f b r 缩略词表 英文全称 t 】阻佑cm a t r i x o r i g i n d e s t i n a t i o n s h o r t e s tp a t ht r e e m a x i m u nl i k e l i h o o de s t m a t i o n q u a l i t yo fs e r v i e e i n t e m e ts e r v i c e sp r o v i d e r c o n s t a n tb i tr a t e r o u n dt r i p 乃功e p o i n to f p r e s e n c e e x p e c t a t i o na n dm a x i m i z a t i o n o p e ns h o r t e s tp a t hf i r s t b a c k b o n er o u t e r i x 中文释义 流量矩阵 源到目的节点流量 最短路径树 极大似然估计 服务质量 网络服务提供者 固定比特率 往返时间 汇接点 期望最大化 开放最短路径优先 骨干路由器 独创性声明 一 本人声明所里交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：星之堡堕三 日期：2 哆年6 月，日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：二至盟 导师签名：型烨 日期：1 年月日 第一章绪论 1 1研究背景及意义 第一章绪论 随着i n t c 苴n e t 网络的飞速发展，网络的规模日益庞大，结构也越来越复杂，对 其监控、管理也越来越困难。为了更好地进行网络管理、网络设计、路由配置、 网络监控等，迫切需要有关流量方面的信息。如果能够监控网络流量的全部状态， 以全网的观点来观察和了解网络流量的特性及流向情况建立网络流量的完整视 图，从而有望在确保网络正常运行的基础上，更好地进行网络管理、网络设计， 优化网络的规划和路由配置。于是研究者引入流量矩阵( t r a f f i cm a t r i x ) 的概念， 它反映了网络中所有源节点到目的节点即o d ( o r i g i n d e s t i n a t i o n ) 对间的流量情 况，它作为网络流量工程的重要输入参数，受到国内外理论界和工业界的广泛重 视，现已成为i n t e m e t 的一个重要研究热点【l 。1 0 】。 由于流量矩阵需要捕获网络流量的全局状态，而互联网络规模己经非常庞大， 直接监控测量代价非常高，在实际上几乎是不可行的。由间接观测进行流量矩阵 估算是目前获得骨干网络流量矩阵的主要方法。近年来，已成为一个非常热门的 研究领域。本章将简要的介绍o d 矩阵研究的背景及意义，以及o d 流量矩阵估计 算法的研究分类。最后介绍了本论文的总体结构和拟展开的工作。 1 2 流量矩阵定义 网络中从源节点传输到目的节点的流量叫o d 流( o r i g i n d e s t i n a t i o nf l o w ) ， 一系列在网路传输的从源到目的地的流对用流量矩阵( t r a f f i cm a t r i x ，t m ) 来描述。 流量矩阵反映了一个网络中所有源节点和目的节点对之间的流量需求( t r a f f i c d e m a n d ) 。根据源节点目的节点的不同类型，o d 流量矩阵能定义在任何尺度上。 m e d i n a 等根据节点汇聚类型，在g r o s s g l a u s s e r 和r e x f o r d 2 】在o d 流的空间表 示给出的三种标准类型基础上，提出了o d 流的两级分类方式，如图1 1 所示： 电子科技大学硕士学位论文 一级 二级 图1 - 1o d 流的两级分类方式 一级：基于空间表现方式的分类 点对点流量矩阵( p o i n t - t o p o i n tt r a 伍cm a t r i x ) 该类型的流量矩阵定义了点对点流量矩阵，描述了在源目的点集合以s ，d ) 中， 所有源( s ) 目的( d ) 节点对间的流量集合。该类型流量矩阵描述了整个网络的流量 分布情况。 路径流量矩阵( p a t hm a t r i x ) 该类型的流量矩阵定义了从对于给定源节点( s ) 目的节点( d ) 所经历路径p 上 的流量v ( s ，d ，p ) ，它不仅表示网络流量大小，而且表示流量在网络中的流通路 径。 点到多点流量矩阵( p o i n t t o m u l t i p o i n tt r a f f i cm a t t r i x ) 该类型的流量矩阵定义了从对于给定源节点( s ) 到目的节点集合 q ，q ，见) 的流量v ( s ，d 。，d i ，见) 。这种单源多目的类型的流量存在于多播， 内容分发，多人游戏流量模型中。 二级：基于节点聚合类型的分类 i p 地址日订缀级流量矩阵( p r e f i x t o p r e f i x ) i p 地址前缀级是网络中最低级的流量聚合级别。i p 地址前缀级网络流量矩阵 描述了网络中所有i p 地址前缀对的的流量情况。 链路级流量矩阵( l i n k t o l i n k ) ： 2 第一章绪论 链路级流量矩阵可以用来描述任何对等链路间的流量( 比如接入链路( a c c e s s l i n k s ) 、p o p 间链路( i n t e r - p o pl i n k s ) 、p o p 内链路( i n t r a - p o pl i n k s ) 等) 。 l i n k - t o l i l l k 流量矩阵最适用于描述汇聚节点为接入链路的流量情况，描述端到端 的流量情况。 路由级流量矩阵( r o u t e r - t o r o u t e r ) ： 路由级流量矩阵描述了网络中路由级拓扑中，所有路由器对间流量情况，该 流量为流入和流出该路由器的链路流量集合。 p o p 级流量矩阵( p o p - t o p o p ) ： p o p 是最高的汇聚级，它由路由器集合而成，p o p 级流量矩阵它表示网络p o p 级拓扑中，所有p o p 间流量的流动情况。 由流量矩阵的分类可知流量源和目的可以是主机，路由器甚至是p o p 网络， 因此一个具体的流量矩阵需要指明源、目的聚合尺度。在本文中，讨论的流量矩 阵为大尺度骨干网中路由级流量矩阵。网络规模日益庞大，流量矩阵的直接获取 是非常困难的，下文就对流量矩阵的直接获取方式做简要的介绍。 1 3流量矩阵的获取方式 o d 流矩阵反映了所有o d 对之间的流量强度大小，实时、动态的获取p 网 络中的流量分布状况是非常重要的，流量矩阵对于预测网络带宽需求、网络协议 的设计，网络路由配置，预警当前网络状态下的拥塞，发现网络资源滥用都有重 要的作用。它的获取也是流量工程研究的一个热点。当前研究者们提出了以下获 得o d 流数据的方法，有的已经有商业实践。 ( 1 ) 基于链路的测量f 3 】。在传统i p 网络中运用s n m p ( s i m p l en e t w o r k m a n a g e m e n tp r o t o c 0 1 ) 模型在每条链路上进行业务流量测量，然后再综合所有测 量结果进行业务流量矩阵的计算。该方法有其缺陷，即是在骨干网络链路进行测 量会造成很大的网络开销。现在已有一些商业软件可以用于测量网络实际o d 流 量。比如，c i s c o 公司的n e t f l o w 软件，该软件采样流经路由器的数据包，通过 分析这些数据包中的包头信息来获取数据包的源目的地址，从而确定网络o d 流 量。但是这种直接测量的方法存在以下问题。1 、为了得到全局全网络的o d 流量 信息，必须在所有的核心路由器上安装n e t f l o w 软件，而n e t f l o w 相当的昂贵且只 支持c i s c o 公司的路由器。2 、专业测量软件需要耗费大量的路由器c p u 资源用 于包的采样及分析，这样影响了大网络中路由器的性能。3 、同步每个路由器上 3 电子科技大学硕士学位论文 n e _ t f l o w 采集的数据以及对这些测量数据的存储也需要耗费大量的网络资源。4 、 最重要的是，这种基于采样分析的测量不能保证很好的符合真实网络o d 流量的 分布。 ( 2 ) 基于流的测量【4 】。该方法不需要在核心网络节点处进行测量，只需要在 m 网络的接入边界进行业务流级的测量，根据边界的测量结果来估算网络的业务 流量矩阵。这种测量方式的不足是：1 、在骨干网络的边界同时存在的流的数目非 常大，对每个流进行实时动态的测量是比较困难的。2 、测量结果的数据集非常大 会增加计算分析的难度。3 、还需要从网络中每个路由器提取路由配置信息，这会 大幅增加网络的开销，而提取的路由信息也不能保证是实时准确的。 ( 3 ) 基于采样技术的测量。n g d u f f i d d t 5 1 等人提出了一种利用采样技术获取 口网络业务流量矩阵的方法，该方法克服了基于流测量所存在的困难。通过选用 一个合适的h 嬲h 采样函数生成测量数据包，然后进行业务流量矩阵的估算。该方 法的优点在于不需要了解网络的拓扑结构和路由信息。该方法也存在缺陷：l 、需 要准确的选取一个能够代表所有网络中传送的业务流的数据包子集。2 、需要一个 合理的散列采样函数，然后用于业务流量矩阵的采样统计，而这在实际应用中几 乎是不可能的。 由此可见，流量矩阵直接测量是非常困难的，尤其在大型骨干网络中。于是， 可以考虑采用间接的方式来获取流量矩阵。鉴于网络中路由器对s n m p 协议的普 遍支持，我们可以很容易地从路由器端口获得连接该端口链路上的流量信息。于 是考虑从链路流量( l i l l l ( l o a d s ) 和路由信息估计出o d 流量矩阵，是一种获取流 量矩阵的有效方式，也是本文的研究重点。下一节对流量矩阵估计问题进行阐述。 1 4 流量矩阵估计 在大尺度i p 骨干网络中，链路流量表示相邻两节点问链路上的流量，是网络 中的o d 流量在路由矩阵控制下，在链路上的聚合。链路流量利用s n m p 7 , s 1 从路 由器端口上直接测量获得，而路由矩阵通过网络状态和配置信息得到。因此，流 量矩阵估计就是在已知网络链路负载和路由矩阵的情况下，获得流量矩阵的估计 值【6 1 。图1 2 表示了流量矩阵估计过程【9 1 。 4 第一章绪论 m i l o a d s 2 阳衔c m a t r i x r o u 虹n jm a t d x 图l - 2 流量矩阵估计过程 令y = ( y l ，一，y a 表示一个网络中所有链路的流量值，表示链路的总数，y ，表 示第歹条链路的流量。x = ( 五，而) 为网络中所有o d 对之间的流量需求组成流 量矩阵，j 表示网络中o d 对的总数，五表示第i 个o d 对之间的流量。么是一个j * i 阶的0 1 矩阵，它的每一行代表一条链路，每- - n 代表一个o d 流。如果链路在 o d 对f 流经的路径上，则口。= 1 ，否则口。= 0 ；a 的列表示某条o d 流在网络中所 要流经的全部链路的集合，即是这条o d 流的路由，由此可知彳为一个包含了实 际路由信息的矩阵，由网络拓扑结构以及路由策略决定。它们之间的关系可以用 下面的线性方程表示： y = 4 r( 1 1 ) 流量矩阵估计算法的目的就是在已知彳的情况下，从观测数据】，中尽可能完整 且准确地恢复出x 。为了更好的描述o d 流估计问题，列举如图1 3 这样的简单 例子说明。 5 电子科技大学硕士学位论文 2 4 图1 - 3o d 流量估计简单拓扑结构 3 图1 3 所示为一个有4 个节点的简单网络，有4 条输入链路及4 条输出链路， 一共1 6 条o d 流。假设路由器既不是源结点也不是目的结点，流入它的总流量应 该等于流出它的总流量。路由矩阵彳如表1 1 所示： 表1 1 简单网络路由表 1 , 1 1 , 21 31 , 42 。12 , 22 。32 , 43 。l3 , 23 33 , 44 , 14 , 24 , 34 , 4 l2345678 9 1 0 1 1 1 2 1 31 41 51 6 0 1l1ll 0 21ll1 0 31lll 0 4ll11 d 1llll d 2 111 l d 3l1l1 d 41l1l 其中，0 1 ( o r i g i nf r o mn o d e1 ) 表示从节点l 到路由器的单向链路，d 1 ( d e s t i n a t e t on o d e1 ) 表示从路由器到节点1 的单向链路，彳矩阵的每一列代表一条o d 流， i 3 比如第3 列3 表示第3 条o d 流从节点1 流向节点3 。 在该网络中，1 6 条o d 流量通过路由矩阵彳汇聚在8 条链路上，从路由器的 四个接口测量得到8 条链路流量的测量值，此时式( 1 1 ) 中方程个数为8 ，未知 数个数为1 6 。在不加任何限制的条件下，方程组为欠定方程，没有唯一解。 通常随着网络的扩大，网络节点数，z 的增多，网络中链路数成咒级数增加，而 6 第一章绪论 o d 流个数成n 2 级增加，因而网络中o d 对的数量要远大于链路数，即j “i ，a 不是一个满秩方阵，这意味着方程( 1 1 ) 将有无穷多组可能解，所以对x 的估计 问题是一个欠定反问题。又因为网络中路由的非对称可能导致彳矩阵中元素的相 似性以及对】，测量误差的存在，所以对x 的估计问题也是一个病态反问题。 o d 流估计问题的病态性是o d 流估计方法研究中的一个关键问题，为了解决 这个问题，在o d 流的估计问题中，必须引入更多的约束条件来确保解的可辨识 性及稳定性。在本文中，通过引入o d 流间的时空相关性来引入约束条件，我们 认为在一定时间内流量矩阵在时间上和空间上存在某种关系，利用这种时空关系， 引入o d 流量矩阵的一些约束信息，缩小解空间，从而克服流量矩阵估计的多解性， 从而可以获得更加准确的流量矩阵估计。o d 流的时空约束关系的表现形式是本文 的一个研究重点，本文提出了两种形式的时空关系，一种是口f p 校正后的历史均 值，其中历史流量均值利用了o d 流量在时间上的相关性，i p f p 校正利用了o d 流量在空间上的相关性；另一种是方阵形式的时空关系，表示当前时刻o d 流与 前一个o d 流之间的关系，方阵的对角线元素表示了流量变化中的时间相关性， 非对角线元素表示了o d 流量的空间相关性。将这两种形式的0 d 流量矩阵的时空 关系应用到o d 流估计算法中，都取得了较高的估计精度。 1 5 本文的工作 本文主要研究大尺度i p 骨干网络的流量矩阵估计问题，针对流量矩阵估计的 高度病态特性，本文进行深入研究，提出了一些新的思路和有效的估计算法。本 文的主要贡献： ( 1 ) 对传统的o d 流矩阵的估计算法进行了分类研究。从先验信息角度，对 o d 流估计算法进行分类研究，分析各种算法的优缺点，总结o d 流估计问题的特点， 并详细介绍了拥有较好估计结果的基于广义重力模型的o d 流估计方法。 ( 2 ) 针对o d 流估计的病态性，利用模拟退火方法简单并且容易搜索到局部 最优解的特点，提出了利用模拟退火方法来估计o d 流这一非线性的估计算法。在 算法中，采用i p f p 校正后的流量矩阵的o d 流量历史均值作为初始值，引入了o d 流的时空关系，并且在模拟退火过程中充分利用链路流量信息，缩小模拟退火解 的搜索空间，降低流量矩阵估计的多解性，从而提高了估计精度。利用a b i l e n e 网 络真实数据仿真结果表明，该算法比基于广义重力模型的o d 流估计算法有更高的 估计精度。 7 电子科技大学硕士学位论文 ( 3 ) 本文提出了一种基于时空关系的粒子滤波器估计方法。此方法用一阶马 尔可夫过程进行建模，然后利用贝叶斯推断方法来最大化后验证获得优化估计结 果。由于粒子滤器等贝叶斯方法对先验信息敏感，而o d 流估计问题本身存在病 态性，导致后验建模异常困难。通过提高先验建模正确性来提高估计精度：首先 使用更能反映o d 流真实分布的g a m m a 分布来对o d 流建模，同时引入方阵形式 的o d 流的时空关系，从而建立更为精确的关于o d 流量矩阵估计的动态贝叶斯模 型，其本质就是引入了更多的o d 流先验信息。然后使用基于采样重采样m c m c 的粒子滤波器估计方法求解g a m m a 模型下的动态贝叶斯模型参数，最后得到o d 流估计结果。利用a b i l e n e 网络真实数据仿真结果表明，基于时空关系的粒子滤波 估计方法比基于模拟退火的o d 流估计方法，以及基于广义重力模型的o d 流估计 方法都具有更优的o d 流估计性能。 1 6论文结构及内容安排 整个论文各章节安排如下： 第一章首先简要的介绍了研究课题的内容，从研究课题的背景和意义以及研 究方向和研究问题的难点进行了阐述。 第二章系统分析了文献中的各类o d 流估计方法，总结o d 流估计问题的特点， 分析各种算法的优缺点，并详细介绍基于广义重力模型的o d 流估计方法。 第三章介绍了基于模拟退火的o d 流矩阵估计方法，详细讨论了o d 流时空关系 的引入，以及对估计结果的影响。并采用美国的a b i l c n c 网络的数据进行仿真，仿 真结果验证了该算法的能够提高o d 流的估计精度。 第四章介绍了基于粒子滤波器的o d 流矩阵估计方法，详细讨论了o d 流量 g a m m a 模型的选取，动态贝叶斯估计模型的建立，以及粒子滤波器的实现，同样 采用美国的a b i l c n e 网络的数据进行仿真，仿真结果验证了该算法在估计精度上比 模拟退火方法有更多的提高。 第五章是全文的总结，提出了未来的工作方向。 一8 第二章流量矩阵估计方法综述 第二章流量矩阵估计方法综述 网络o d 流量矩阵估计的目的是从容易测量得到的链路级数据中估计出路径 级网络参数。由于流量矩阵的需要捕获网络流量的全局状态，直接监控代价非常 高，实际上几乎是不可行的。近年来，由间接观测进行流量矩阵估算已经成为了 一个非常热门的领域。 o d 流量矩阵估计问题在第一章1 5 节已经做了详细的介绍。流量矩阵，路由 矩阵，链路流量三者之间存在以下线性关系： y = a x ( 2 1 ) 在网络中，由于o d 流的数量要远远多于链路的条数，意味者式子( 2 1 ) 将 有无穷多个可能的解，是病态反问题( i 1 1 p o s e cl i n e a ri n v e r s ep r o b l e m ) ，因此求解 以上问题，需要许多先验信息来克服欠定性或者病态性问题。许多学者围绕流量 矩阵的估计方法等相关问题进行了大量的研究，提出了很多的估计方法，也取得 了一定的成效。本章将对这些流量估计方法做一个系统的描述，从先验信息角度， 我们可以把现有的o d 流估计方法分成如表1 2 所示的三类方法：无先验方法、确 定性分布模型先验方法和智能先验方法。接下来，我们对这三种方法进行一个详 细的介绍。 2 1 无先验方法 无先验方法主要可以分为两类：p c a ( p r i n c i p a lc o m p o n e n t sa n a l y s i s ) 方法 和线性规划l p ( l i n e a rp r o g r a m m i n g ) 方法【2 7 1 。 ( 1 ) p c a 方法 基于p c a 方法的流量矩阵估计方法研究了流量矩阵的特征流向量，用特征流 向量来表示流量矩阵，将流量矩阵估计问题转化为求其特征流向量的问题。其基 本思想就是：不是估计所有的n 个o d 流，而是仅仅估计k 个最重要的特征流。 通常特征流向量的维数比o d 流集合的维数小很多，于是这样通过降维的方法， 降低o d 流估计问题的求解难度。因为k n ，所以从链路流量估计特征流的问题 就变成了非病态系统的问题。l a k h i n a 等人使用了p c a 方法来估算流量矩阵【2 5 1 ， 他们研究发现在长时间尺度情况下，特征流的低维表示可以捕获o d 流，于是在 o 电子科技大学硕士学位论文 这种情况下利用p c a 方法来进行流量矩阵估计。下面对p c a 模型做简单介绍。 设x 表示所有o d 流的时间序列，其维数为r 奉刀，使用p c a 可以将其分解为 x = u s v r ，当挑选出k 个最主要的成分时流量矩阵可近似为： = v s 红1 ， ( 2 - 2 ) 其中，r 是包含最主要成分的n x k 阶矩阵，s 是对角矩阵，元素s ( f ，f ) 是测量主成 分i 捕获的能量，且“由k 个最重要的特征流时间序列组成。如式( 2 2 ) 所示， p c a 模型表示了整个o d 流在长时间上的相关性，也表示了o d 流的空间相关性。 使用a v s 的伪逆来获得估计值，再利用式子( 2 2 ) 获取估计值t ，并利用2 4 小时对流的直接测量来校正。因此，基于p c a 模型的估计方法估计过程是一个简 单的伪逆求解过程，降低了求解的复杂度。 ( 2 ) 线性规划l p 方法 线性规划l p 方法的核心是如何选择合适的目标函数。e u m 等人【3 0 】使用单纯型 法进行估算，并证明了内点方法可以产生精确的估算结果。v a t o n 等人d 3 1 指出：解 决约束过少的线性系统的经典方法是最小化欧几里德范式，但这是不现实的。 g o l d s c h m i d t 利用权重和目标函数来表示o d 流估计问题。g u n n a 等人 2 9 1 应用l p 方法来寻找o d 流可能值的边界，并为o d 流的最坏界( w o r s tc a s eb o u n d s ) 进行了 公式化表示。但很多情况下对某些o d 流来说可能会找到更紧凑的边界值，某些 o d 流的边界值非常接近。然而，由于对每个o d 流都需要求解两个l p 问题，所 以该方法的计算量是相当大的。由于通过上界和下界的均值从最坏界中获得先验 信息的分布是完全可能的，于是g u n n a r 等人就利用这种方法，从而得到了非常好 的估算。 表2 1o d 流估计方法分类 分类 模型方法 线性规划方法 无 先 无模型 w o r s tc a s eb o u n d sb yl p 验 p c a 方法 确 贝叶斯方法 犁霍泊松分布迭代贝叶斯方法 箍翁 模 二阶矩方法 1 0 第二章流量矩阵估计方法综述 最大似然方法 扩展似然方法 高斯分布伪似然方法 q u i c km e t h o d 卡尔曼滤波器 对数高斯分布粒子滤波器方法 混合高斯分布高斯混合模型方法 简单重力模型方法 广义重力模型方法 重力模型 c h o i c em o d e l 智 t o m o g r a v i t y 能 模 信息理论方法 型 先 验扇出模型扇出模型 i c 模型i c 模型 日趋势波动过 程模型 路由改变算法 2 2确定性分布模型先验方法 确定性分布模型先验方法是指待估计的o d 流服从模型分布的，在