（通信与信息系统专业论文）网络流量自相似特性模型分析与研究.pdf

中文摘要 中文摘要 9 0 年代初，l e l a n d 等第一次明确提出了网络流量中存在着自相似现象。此后， 网络研究人员通过对实际网络进行测量与分析，得出了这样的结论：不论网络的 拓扑结构与业务如何，网络流量中都存在自相似统计特性，即长相关特性。 传统的基于泊松到达通信量的假设，不能够真实地描述网络业务的实际情况。 为了真实地反映网络数据通信量的特性，需要重新建立模型来描述网络中的自相 似现象。 席文首先介绍了网络中的自相似现象，接着给出了自相似的数学定义，并描 述了它的统计特点；在简要分析了自相似性对网络性能的影响后，指出了如何识 别自相似序列以及估计日参数的方法，然后通过实例证明了网络中确实存在着自 相似觋象。 通过对现有自相似模型的深入研究和计算机仿真，比较了各种模型的优缺点 和算法的复杂度，指出了现有模型的特性和应用范围。仿真结果表明：模型精度 要球决定了算法复杂度，即精度要求越高，则算法复杂度越高，反之亦然。 本文在基于o n o f f 模型和混沌映射模型思想的基础上提出了一种新的映射 模型。该模型简化了混沌映射模型的映射函数，通过选取带有随机变量的线性分 段函数，使模型状态的逗留时间服从重尾分布。这样，模型能够捕获网络流量的 自相似特性。在介绍了模型构建思想的基础上，通过数学分析给出了它的统计特 性。然后采用0 n o f f 模型理论，建立起该模型参数与自相似参数之间的关系， 增加了模型的可控性，使其能够产生具有不同突发程度的自相似流量。仿真结果 表明模型拟合的日参数与理论值基本吻合。最后对提出的模型进行了排队分析， 从理论上推导了排队系统队列长度的分布特性，为自相似过程的排队性能分析提 供了理论依据。 本文提出的模型在一定程度上能够很好地拟合不同网络的流量特性，为网络 构建、网络特性分析和网络性能评估提供了重要的理论基础。 关键词：自相似，h u r s t 参数，重尾分布，o n o f f 模型 a b s t r a c t a b s t r a c t s i n c el e l a n d ，t a q q u , w i l l i n g e ra n dw i l s o np o i n t e do u tt h ee x i s t e n c eo f s e l f - s i m i l a r i t yi nt h en e t w o r kt r a f f i c , r e s e a r c h e r sw o r l dw i d em e a s u r e da n da n a l y z e dt h e n e t w o r ko nt h er u n , t h er e s u l to ft h a td e m o n s t r a t e dw h a t e v e rt o p o l o g yi s ，s t a t i s t i e s b e h a v i o ro f s e l f - s i m i l a r i t yc o u l db ef o u n d t r a d i t i o n a lm o d e lb a s e do np o i s s o na r r i v a lp r o c e s sc a nn o tc h a r a c t e r i z et h e b e h a v i o ro fr e a ln e t w o r kt r a f f i c i ti sq u i t en e c e s s a r yt oe s t a b l i s hn e wm o d e lt or e f l e c t t h ec h a r a c t e r i s t i c so f s e l f - s i m i l a rt r a f f i c t b i st h e s i sf i r s t l yi n t r o d u e e sw h a ti st h es oc a l l e ds e l f - s i m i l a r i t y , n a m e l yl o n g r a n g ed e p e n d e n c e ，i t sm a t h e m a t i c a l d e f i n i t i o na n ds t a t i s t i c s c h a r a c t e r s ，a n dt h e i n f l u e n c et h es e l f - s i m i l a r i t yo f n e t w o r kt r a f f i cb r i n gt on e t w o r kp e r f o r m a n c e a f t e rt h a t ， i td i s c u s s e st h em e t h o dh o wt od e t e c ts e l f - s i m i l a r i t yi nag i v e np r o c e s ss e r i e s ，t h ew a yt o e s t i m a t ei t sh u r s tp a r a m e t e r f i n a l l yi ts h o w st h a tt h e r ed o e se x i s ts e l f - s i m i l a r i t yi nt h e r e a ln e t w o r kt r a f f i ct h r o u g ha ne x a m p l e s e l f - s i m i l a rm o d e lo f t e nu s e dn o w a d a y si sd e e p l ys t u d i e da n ds u m m a r i z a t i o ni s g i v e n ，i n c l u d i n gt h em e r i t sa n dd e m e r i t so ft h em o d e l s ，a l g o r i t h mc o m p l e x i t y , a n dt h e b e s tw a yt h em o d e l sa d a p t i n gt ob s e w ed oa l lt h i st h r o u g he x t e n s i v es i m u l a t i o nw h i c h s h o w st h e r ei sd e p e n d e n c eb e t w e e np r e c i s i o na n dc o m p l e x i t yo f t h em o d e l ，n a m e l yt h e m o r ep r e c i s i o nt h em o d e lr e q u i r e s ，t h em o r ec o m p l e xt h em o d e li s m a j o rw o r ko ft h i sa r t i c l ei st od e v e l o pan e ws e l f - s i m i l a rn e t w o r kt r a f f i cm o d e l b a s e do no n o f fm o d e lm a dc h a o t i cm a pm o d e l 1 1 l em o d e ls i m p l i f i e st h em a p p i n g f u n c t i o no fc h a o t i cm a pm o d e la n di tm a k e st h es t a t es o j o u r nt i m es t i l lh a v eah e a v y - t a i l d i s t r i b u t i o nw i t hr a n d o mp a r a m e t e r si n v o l v e d t h ei d e aw h y t oc o n s t r u c tt h i sm o d e la n d c h a r a c t e r i z a t i o no fs t a t i s t i c a lb e h a v i o ro ft h em o d e lt h r o u g hm a t h e m a t i c a la n a l y s i si s i n t r o d u c e d t h e ni te s t a b l i s h e st h ec o n n e c t i o n sb e t w e e nt h em o d e lp a r a m e t e ra n dt h e s e l f - s i m i l a rp a r a m e t e rt h r o u g ho n o f fm o d e lt h e o r y , w h i c hm a k e st h em o d e lu n d e r c o n t r o la n dc a p a b l eo fc a p t u r i n gd i f f e r e n tr e a ln e t w o r kt r a f f i c s i m u l a t i o nr e s u l t d e m o n s t r a t e st h a tt h ee s t i m a t e dh u m tp a r a m e t e rd oa c c o r dw i t ht h et h e o r e t i c a lo d e f i n a l l yt h es t a t i s t i c a lh e h a v i o ro fs i m p l eq u e u i n gs y s t e mw i t ht h et r a f f i cg e n e r a t e db y h a b s t r a c t t h em o d e lh a sb e e nd e d u c e dw h i c hp r o v i d e sat h e o r e t i c a lb a s i sf o rq u e u i n ga n a l y s i s t h em o d e lb r o u g h tf o r w a r di nt h i st h e s i sc o u l dc h a r a c t e r i z et h es t a t i s t i c a lb e h a v i o r o fn e t w o r kt r a f f i ct os o m ee x t e n ta n di tp r o v i d e sa ns o l i df o u n d a t i o nf o rc o n s t r u c t i o n ， a n a l y s i sa n de v a l u a t i o no f t h en e t w o r k k e yw o r d s ：s e l f - s i m i l a r , h u r s tp a r a m e t e r , h e a v y 一“ld i s t r i b u t i o n , o n o f fm o d e l i i i 图目录 图目录 图1 1 不同时间尺度下的以太网流量2 图2 一l1 9 8 9 年8 月份和1 0 月份采集网络流量时实验室的网络拓扑1 8 图2 - 21 9 9 0 年1 月份采集网络流量时第二个实验室的网络拓扑1 8 图2 31 9 9 0 年2 月份采集网络流量时m r e 主干网的网络拓扑1 9 图2 - 4 四种不同的方法对网络流量进行日参数估计2 0 图3 1h = 0 5 的r m d 序列图2 5 图3 2h = o 6 5 的r m d 序歹0 图2 6 图3 - 3h = 0 8 的r m d 序列图2 6 图3 4h = 0 9 5 的r m d 序列图2 6 图3 5 图3 1 序列的自相关函数2 7 图3 - 6 图3 3 序列的自相关函数2 7 图3 7 图3 。1 的v 珂估计2 8 图3 - 8 图3 3 的v t 估计2 8 图3 - 9 图3 2 的r s 估计2 9 图3 1 0 图3 _ 4 的r s 估计2 9 图3 1 1d = 0 的f a r i m a ( o ，吐o ) 序列图3 7 图3 1 2d = 0 2 的f a r i m a ( 0 ，吐o ) 序列图3 7 图3 1 3d = 0 4 5 的f a r i m a ( 0 ，反o ) 序列图。3 8 图3 1 4 图3 1 2 序列的自相关函数3 8 图3 1 5 图3 1 1 的v - t 估计3 9 图3 1 6 圈3 。1 3 的v t 估计3 9 图3 1 7p a r e t o 分布与指数分布密度函数比较4 1 图3 1 8 对数函数下对图3 1 重绘4 2 图3 1 9o n o f f 模型聚合示意图4 3 图3 - 2 0 映射函数迭代示意图4 7 图3 2 1 混沌映射模型示意图4 7 图3 2 2s i m 模型的队长仿真图4 8 图3 2 3d i m 模型的队长仿真图4 9 图3 - 2 4 两种模型的聚合流量示意图5 0 图3 - 2 5 聚合s i m 流量模型的队长分布图5 0 图3 2 6 聚合d i m 流量模型的队长分布图5 1 图4 1 模型迭代示意图5 5 图4 2 恕f1 时模型迭代示意图5 6 图禾3 岛的密度函数。5 7 图4 - 4 恕的密度函数5 7 图4 5o n 状态逗留时间的c d f 函数图5 8 图目录 图4 - 6 模型生成的自相似流量图6 2 图4 7o n o f f 均为f i g h t - t a i l 情况的v t 图6 2 图4 - 8a o n = a o f f = 1 5 流量图6 3 图4 - 9a o n = a o v e = 1 5 时的v - t 图。6 3 图4 1 0a o n = a o r r = 1 5 时的r s ( n ) 图6 4 表目录 表目录 表2 - 1 自相似性参数与短相关参数性质比较1 2 表3 1r m d 算法生成的f g n 序列的日参数估计值与理论值对比3 0 表3 2 算法生成的f a r i m a ( 0 ，正o ) 序列的日参数估计值与理论值对比4 0 表3 3 白相似网络业务流建模方法的分析与比较5 3 表4 - 1o n - o f f 均为h e a v y - t a i l 且a o n = a o f f 6 4 表4 2o n o f f 均为h e a v y - t a i l 且a o n f f 6 4 表4 3o n 状态为h e a v y - t a i l 而o f f 状态为l i g h t - t a i l 6 5 表4 _ 4o n 状态为l i g h t - t a i l 而o f f 状态为h e a v y - t a i l 6 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名： 蠢盎 日期：如。弋年b 月le l 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：盏蠡导师签名：盘查亡 日期：上。文年b 月1 日 第一章绪论 1 1 研究背景 第一章绪论 自互联网问世以来，关于网络流量的研究一直在不断的探索中。随着i n t e r a c t 的快速发展和网络协议体系的变化，从共享以太网到交换以太网、a t m 、千兆以 太网、w i r e l e s se t h e r n e t ，1 0 ge t h e m e t ；i n t e r n e t 路由策略的变化从“f i r s tc o m ef i r s t s e r v e ”到公平的资源共享；网络应用的多样化，如g r i d ，p 2 p 、视频会议、i n t e r a c t m u l t i c a s t 应用、w e bc a c h e 、多人游戏等。伴随高速网络技术和多媒体技术的飞速 发展，人们越来越多地提出了包括多媒体通信在内的综合服务要求。而当今分布 式多媒体应用( 如视频电话、视频点播、口可视电话、远程教育) 不仅包括文本数据 信息，还包括语音、图形、图像、视频、动画这些类型的多媒体信息。这些应用 不但对网络有很高的带宽要求，而且要求信息传输的低延迟和抖动等，都为研究 网络流量特性提供新的契机。 随着宽带网络服务需求( 如多媒体、视频业务等) 的激增，高速网络传输技术成 为目前网络研究的热点。要想对网络业务拥塞控制、信息、监测、带宽分配及网 络性能评价等问题进行进一步的研究，建立一个能准确描述网络流量特征的模型 就是首先要解决的问题之一。 很长时间以来，网络流量的业务源都是用泊松过程来描述的，根据许多已存 在的马尔科夫分析的结论和排队分析的一些基本方法，人们能够对以泊松流作为 业务源的排队系统进行深入的性能分析，并且得到等待时间，队列长度性能参数 的精确结论。同时，泊松过程有着十分简单的相关结构这使得泊松到达排队系统 具有很好的性能。 然而，l e l a n d ，t a q q t hw i l l i n g e r 和w i l s o n 在9 0 年代初发表的具有开创性意义 的论文“o nt h es e l f - s i m i l a rn a t u r eo f e t h e m e tt r a f f i c 【1 1 1 2 1 及其修订版嘲中第一次明 确的提出了网络流量中存在着自相似现象。在这几篇论文中，l e l a n d 和w i l s o n t l l l 2 1 3 j 在对自己在b e l l c o r em o r r i s t o w n 的研究和工程中心的几个以太网网段上所采集的 大量的高分辨率( 2 嘞s 时间精度) 的网络流量数据进行统计分析，证实了真实的网络 流量具有统计上的自相似性( s e l f - s i m i l a r i t y ) 。这两篇文章打破了使用泊松通信量假 设进行直接的排队分析就足以描述所有网络通信量的幻想，发起了对数据通信信 电子科技大学硕士学位论文 能的重新研究，是近十年来互联网领域最重要的论文之一。 图1 1 来自文献 3 】，是b e l l z o r e 公司的局域网上的网络流量在不同的时间尺度 上的标示和仿真产生的泊松过程的网络流量在对应时间尺度上的表示。从图1 1 上可以很明显的观察到网络流量在多个时间尺度上具有自相似的统计特性，并且 在多个时间尺度上具有十分强的突发性。由此，我们可以得出在高速网络的突发 业务传输中，采用自相似模型比传统的m a r k o v 模型更接近实际业务的特性。 随着网络异质性的加剧，更多类型的业务和更多协议的出现将使网络流量的 自相似性更加普遍。对自相似业务的监测、参数估计、数学建模和排队分析己成 为高速网络流量控制和业务管理中不可缺少的要素。在网络流控上考虑自相似特 性，并指定相应的控制算法会取得较好的效果，将会对网络性能的优化和稳定有 重要意义。 图1 - 1 不同时间尺度下的以太网流量 - 2 第一章绪论 1 2 研究现状 自相似网络流量建模相关的研究主要分为两类，第一类是基于测量的网络流 量建模，而第二类则是基于物理模型的网络流量建模。 1 2 1基于测量的流量建模 在基于测量的网络流量建模的研究工作中，最早的也是最具有影响力的工作 就是l e l a n d ，t a q q u ，w i l l i n g e r 和w i l s o n 在9 0 年代初发表的论文“o nt h es e l f - s i m i l a r n a t u r eo fe t h e r n e tt r a f f i c 【1 心及其修订版【3 1 0 在这篇论文发表后不久，各国研究人 员开始对世界上现有的一些网络进行了测量和分析。这其中最重要的测量结果包 括：( 1 ) e r r a m i l l i 和w i l l i n g e r 等人 4 1 收集并分析了大量的从i s d n 、以太网和v b r 视频业务中得到的数据；( 2 ) p a x s o n 和f l o y d 5 】【6 】从广域网w a n 上收集并分析了大 量的业务数据；( 3 ) b e l l c o r e 的研究人员【7 】从使用7 号信令的共路信令网( c c s 上 收集了原始的业务数据；( 4 ) a d d i e , z u c k e r i i l a n 和n e a m e 8 】从澳大利亚高速数据网 f a s t p a c 上收集并分析了大量的业务数据；( 5 ) 洛桑e p f l 实验室【9 】测量了以太网 上的业务流；( 6 ) h e y m a n 等人【1 0 坝0 量并分析了a t m 网络传输的视频会议业务表现 出的一些特性，g a r r e t 等人【1 1 】对v b r 视频业务进行了分析；( 7 ) c r o v e l l a 等f 1 习观测 分析了w w w 业务，这些业务反映了数以百计的文档请求。 在这些基于测量的网络流量建模研究工作中，研究人员从实际的网络中采集 大量高精度的网络流量数据，并利用统计的方法对网络流量进行分析，来检测网 络流量中是否存在自相似特征，并且估计可以表征这种自相似特性的参数。所有 这些工作无一例外的说明：虽然网络的拓扑结构、用户数量、服务类型有一些变 化，但是通信量中的自相似性始终是存在的，从而为网络流量中存在自相似特性 提供了最有力的支持。 在对网络流量进行统计分析并证明了网络流量中具有自相似特性的同时，基 于测量的网络流量模型还进一步的假设实际的网络流量的特征可以通过统计上具 有自相似特性的随机过程来进行刻画，并且利用实际的网络流量来估计这些模型 的参数。通过这种假设和检验的方法，研究人员希望从具有复杂特性的大量网络 流量数据中提取最本质的特征，并且能够利用一种具有简单参数的模型来很好的 描述实际的网络流量。同时，这些研究也使得计算机能够快速的生成模拟网络流 量，从而对网络性能的自相似特性仿真研究提供了基础。 3 电子科技大学硕士学位论文 1 2 2 物理建模 第二类的网络流量建模工作是物理层次上的。这一方面的工作主要是试图解 释产生自相似业务流的物理原因，集中在研究是什么机制导致了网络层自相似突 发性，即何种网络协议与分布式系统的何种特性怎样共同作用，导致了自相似现 象的产生。物理建模的目的就是建立模型来解释实际网络中的何种机制产生了自 相似流量。 有一种观点认为，自相似流量的形成主要与单个数据源的到达模式有关，典 型的这样的数据源就是v b r ( v a r i a b l eb i tr a t e ) 视频。例如，m p e g 视频在多种时间 尺度都显示出可变性，于是有的研究认为，有可能是这一可变性导致了相继画面 更迭所需持续时间的可变性，而最终形成自相似流。然而，这种说法只可能是略 着边际。因为最早发现的自相似流是1 9 8 9 1 9 9 1 年从b e u c o r e 网络监测到的业务流 1 1 1 2 3 1 ，而当时v b r 视频还处于起步阶段，流量极少甚至等于0 ，不足以构成影响 因素。另外，众所周知，v b r 视频是可以用短程依赖的业务流来逼近的，从而可 以用马尔可夫分析来研究长程依赖结构对性能的影响。 另有一种观点提出，文件和被传输对象大小的重尾分布导致了自相似现象的 产生【1 2 】。根据对分布式系统的一些经验性的统计发现，在网络上传递的文件和网 页对象大小都呈重尾分布。简单的说，就是文件的大小在一个很大的范围内，其 中一些“很大”的文件也占有不可忽略的份量。通过协议栈的形式，上层应用的 重尾分布文件大小在网络层保持了下来，形成了近似重尾分布的忙时段。而如果 端节点间传递这样的文件，最终会在复用点的网络层产生自相似的业务流。这种 观点适用于一系列不同的传输层协议，例如t c p 的t a h o e , r e n o 和v e g a s 等不同实 现以及带流控制的u d p 协议。当然，如果不能说明为什么通过t c p 和u d p 协议 传输的重尾对象会在复用点导致自相似流，这种观点就毫无意义。因此，文献【1 3 】 采用了开关模型( o n o f fm o d e l ) ，并且证明大量的相互独立的重尾分布开关数据 源相叠加，最终会导致总流量的自相似特征，而其自相似的程度取决于开或关时 间段的重尾性。开关模型为许多网络流量模型提供了理论基础。这一理论连同观 测到的网络层的重尾分布持续时间一起，构成了对自相似现象的底层直接解释， 从而使网络流量开关模型受到了更为广泛的关注。 4 第一章绪论 1 3排队分析 以自相似的过程作为输入进行排队分析是自相似网络流量方面的一个重要的 工作。 当源端的输入是马尔科夫过程的时候，排队系统的队列长度分布是呈指数衰 减形式的；但是当源端的输入是具有自相似特性的随机过程时，排队的性能产生 了根本性的变化：排队系统的队列长度分布是呈次指数形式衰减的，即比指数衰 减要慢。事实上，根据考虑的排队模型的不同，当采用不同的具有自相似特性的 随机过程作为排队系统输入的时候，排队系统的队长分布可能呈现w 咖u u i a n 分 布或者幂分布形式。 这种以非马尔科夫过程作为输入来进行排队系统性能的分析具有很重要的价 值，它们有助于深入理解网络流量如何对网络性能产生影响，并且对网络资源的 配置决策有很重要的影响。例如，要减小网络中的丢包率，可以采用更大的缓存； 但是当网络流量是自相似的时候，排队长度是呈幂形势分布的，这说明，为了减 少丢包率，缓存必须很大，从而使得排队时间变得很长，导致网络延时的恶性增 长。由此，网络中应该采用比较小的缓存和比较大的带宽。这样的网络资源分配 方案可以减少排队带来的影响。而且，采用小的缓存可以减弱网络中的长相关特 性，从而减弱网络流量中的突发性。 但是现有的以长相关的过程作为输入的排队性能分析还存在着一些不足，这 种不足主要表现在下面的这些方面； 以长相关过程作为输入的排队分析都采用了渐进的分析方法【1 4 】【1 5 】【16 】【1 7 1 椰。例 如，在文献 1 5 1 中，作者假定缓存是无限大的，从而进行推导，得到当队长趋向于 无穷的时候，队长分布的上界和下界。对于那些“有限缓存”下关于队列溢出概 率的结论，其实也是在缓存容量变为无限大的时候推导出来的。 以长相关过程作为输入的排队分析都只是关注一阶的特性，例如平均时延， 却很少关注二阶或者二阶以上的特性，例如时延抖动( 延时的方差) 。例如，对于 两个有丢包的过程，两者可能具有相同的丢包率，也就是具有相同的一阶性能， 但是两个过程的二阶特性却可能有着很大的差异。可能其中的某个过程会有很强 的突发性丢包，从而有很大的方差。这些二阶特性对于网络，是十分重要的性能 参数。例如，多媒体数据流对于传输的实时性和抖动性能有很高的要求，如果不 能保证排队性能的二阶甚至更高阶的一些参数的性能，则无法实现媒体数据流的 服务质量保证。 5 一 电子科技大学硕士学位论文 1 4论文内容结构 本文主要讨论了网络中自相似流量的建模与预测问题。文章的结构如下： 第二章，我们主要讨论的是网络中的自相似现象。首先我们介绍了什么是自 相似现象，自相似现象数学上的定义，以及与自相似非常相关的长相关特性。随 后我们讨论了一个给定的流量数据中，如何检测其中的自相似特性，并且如何估 计该流量的自相似参数。 第三章，我们将详细的介绍现在常用于描述网络自相似流量的模型。将介绍 的模型包括：分形布朗运动和分形高斯噪音，a 分布的自相似过程，f a r i m a ( p ，反 们模型，o n o f f 模型和确定性的混沌映射模型。通过对模型进行仿真比较模型的 优缺点，算法的复杂度，适宜的研究目的。 第四章，我们将结合o n o f f 模型和混沌映射模型提出一种新的用于刻画网 络自相似流量的模型。首先介绍构建该模型的思想，然后通过数学分析给出模型 的特性。结合前面的o n o f f 模型建立模型参数与自相似参数之间的关系，使模 型能够控制产生不同自相似程度的模拟流量。我们将对生成的模拟流量做仿真分 析来印证这一关系是否成立。通过仿真来指出模型的优劣，以及提出改进的方案。 最后我们对模型生成流量做简单的排队分析。 第五章，对全文进行总结。 6 第二章自相似过程的特性 第二章自相似过程的特性 传统的网络流量模型包括m a r k o v 模型、泊松模型、a r m a 模型等。这些传统 模型产生的流量，通常在时域仅具有短期相关性，所以在经过时间上的平均以后 突发性会趋向于平稳状态。时间域上的短相关性对应于频率域上的高频成分，因 此这些业务模型产生的业务一般仅具有较多的高频成分，而低频成分却比较少。 所以它们都不能准确地描述真实的网络流量。尽管每个模型都有各自的特点，但 它们的相关结构都呈现指数衰减【l9 】。 传统网络流量分析模型具有很多不足：如数据包到达不是严格服从泊松到达； 大部分连接到达也不是泊松到达；连接排列不是正态对数( ( 1 0 9 n o r m a l ) ，也不是指 数分布；数据包到达是相关联的；连接到达也是相关的。传统的业务模型只存在 短相关性，即在不同的时间尺度上有不同特性。而在电话网设计中假设呼叫保持 时间和呼叫间隔时间服从指数分布，所以网络业务服从泊松模型。而经过对白相 似性的深入研究后发现，自相似性反映业务在较大时间尺度具有突发，对缓存的 占用比传统排队论的分析结果要大，这样会导致更大的延时。这说明泊松到达流 量模型不再适合当前的流量建模，否则会降低网络的性能；比如，缓冲区的线性 增长，数据包的丢失并不是呈指数幂律减少，这样导致网络的吞吐量降低；并且 缓冲区的增加使得数据包转发的等待时间变长，即延迟增大。因此，在自相似性 流量条件下，传统的流量模型将使得网络能力下降。因此，把握好自相似过程的 特性才能对实际网络业务流量做全方面的刻画。 2 1自相似过程 从数学统计的角度，关于自相似( s e l f - s i m i l a r ) 并没有统一的定义，几种不同的 定义也不能完全等价。以下介绍几种常用的定义。 自相似过程是在统计意义上具有尺度不变性的一种随机过程，从这一点上来 说，自相似过程实际上是在随机过程中引入了分形的概念。 定义2 1 一个连续时间的随机过程】，三似t 刀，如果y ( o 在时间上进行压缩 或扩展时，统计特性不变，即满足： 7 电子科技大学硕士学位论文 y ( f ) = 口一8 y ( a t ) ，v a 0 ，0 h 0 ) ，定义 白” x “( 后) = l m z ( f ) ，k = 1 ，2 ， 公式( 2 3 ) 自( k 一- i ) m “ 为相应的聚合序列，其聚合参数为m ，刃州中的每个元素是原x 序列中连续的m 个 元素“块”c o l o c k ) 的平均值，其中k 为索i ( i n d e x ) ，用来对“块”做标记。如果y 是符合公式( 2 1 ) 定义的自相似过程，而z 是过程y 的增量过程( i n c r e m e n tp r o c e s s ) ， 即坝0 = y ( f + 1 ) 一h i ) ，则对所有的整数州有 d x - m 1 8 x “ 公式( 2 4 ) 如果一个平稳序列胎擞f ) ，f 1 ) 对所有聚合参数m 二都满足公式( 2 4 ) ，则称该序 列为严格自相似( e x a c t l ys e l f - s i m i l a t ) 。该定义与式( 2 一1 ) 描述的定义密切相关，但并 不相同。当一个平稳时间序列在小一o o 时满足式( 2 4 ) 时，则称这个时间序列为渐进 自相似( ( a s y m p t o t i c a l l ys e l f - s i m i l a r ) 。与此类似，对于一个协方差稳定的序列j ，擞f ) ， f 1 ，如果m 1 。餐”与z 有相同的方差和自相关函数结构，则称序列x 具有严格 二阶自相似( e x a c t l ys e c o n d o r d e rs e l f - s i m i l a r ) 序列；同样，如果当所- ，f n l 。w “) 与石有相同的方差和自相关函数结构，则称工为渐进二阶自相似( a s y m p t o t i c a l l y s e c o n d o r d e rs e l f - s i m i l a r ) 序列。 另外，自相似过程与平稳过程之间没有必然的联系，自相似过程可以是平稳 的，例如g a u s s 白噪声和分形高斯噪声。当然，也可以不是平稳的，例如分形布 朗运动。但是，通常说来，常见的自相似过程都是非平稳的随机过程。 定义2 3 自相似过程有平稳增量( s t a t i o n a r yi n c r e m e n t s ) ，则该过程被称为 8 第二章自相似过程的特性 s s s i ( s e l f - s i m i l a rs t a t i o n a r yi n c r e m e n t s ) 。 性质1 随机过程 y ，允1 为s s s i 过程，则l ，具有以下性质 1 若司y ( 1 ) l o 有砸垆= 硬1 ) 以概率1 成立。 2 若司y ( 1 ) 1 o o ，如果o h i ，则e y ( 1 ) = o 。 3 对o ) ， 1 ，有矧y ( 1 ) lr o o ，则o 昂 l 印。 计算增量过程的均方差和协方差可得 e ( y o ) 一】，( j ) ) 2 = e y ( t j ) 2 = ( f j ) 2 8 e y ( 1 ) 2 c o v ( y ( j ) ，y ( f ) ) = 丢e y ( f ) 2 + e r ( j ) 2 一e ( y ( f ) 一y o ) ) 2 1 公式( 2 5 ) ：华 t 2 u + $ 2 h _ ( ) ” 满足上面情况的唯一均值为0 的过程称为分形布朗运动( f r a c t i o n a lb r o w n i a n m o t i o n s ) 【2 0 1 。而当h = l 2 时，公式( 2 5 ) 变为c o v ( y ( s ) ，取力) 钮y ( 1 ) 2 ，分形布朗运动 退化为标准布朗运动。令( 坎f ) ，企o ) 为f b m ，x = h 力r ( i - 1 ) ，i = l ，2 称为分形高斯 噪音，即分形布朗运动的增量过程称为分形高斯噪音( f r a c t i o n a lg a u s s i a nn o i s e ) 。 在实际中，通常考虑的自相似过程不是利用有限维联合分布的自相似性，而 是采用了绝对值矩的自相似性，即 细b ) = e p ，1 9 = e l l 芝那) | l - i 如果x 是自相似的，那么却( g ) 与，驴成正比，即 l o g z ”( g ) = ( g ) l o g m + c ( g ) 其e p f l ( q ) = q ( h - 1 ) 与自相似过程有着十分紧密联系的过程是长相关过程。在许多的自然现象中， 人们都能发现长程相关( 1 0 n gt e r md e p e n d e n c e ) 的特性。例如，在地球物理学的数 据中，数值会在很长的一段时间里以较大的概率出现较大的值( 或者在很长的一 段时间里以较大的概率出现较小的值) 。这样的现象通常被称为j o s e p h 效应，它 说明了过程中所具有的长时间记忆特性( 1 0 n gm e m o r y ) 。特别的，如果这个过程 是平稳的，那么相关函数是正的，且衰减十分缓慢，自协方差函数不可积，谱密 度在原点处是扩散的。 在给出长相关定义前，我们先给出两个与长相关概念有关的概念，即自相关 函数和功率谱的概念。 9 电子科技大学硕士学位论文 定义2 4 随机过程 坝嘎2 1 自相关函数( a l n o c o r r d a t i o nf u n c t i o n ) 定义为 ，( 七) 出墨二兰幽丛墨：! 二兰幽! e ( 石一研x 】) 2 公式( 2 6 ) 定义2 5 随机过程f 硬现仑1 ) 的功率谱( p o w e rs p e c t r u m ) 定义为 s ( c o ) = ；1 = r ( k ) e 晒 公式( 2 7 ) t = 其中一向为随机过程砸0 的自相关函数。 传统业务模型认为，当前时间t 与过去时间( t - s ) ，若j 足够大，则t 与( t - s ) 时的 业务量是不相关的，仅考虑j 较小时业务到达时间的相关性，因此这类模型是短相 关的。短相关的自相关函数随时滞的增加呈单调指数衰减。 考虑平稳随机过程f ，n = l ，2 ，) ，其均值为潞，方差为0 0 2 = v a r x o l l l n 。 p 。= c o r r ( x o ，x n ) ，n = 0 ，1 为相关函数。通常的统计模型：a r m a 过程，g a r c h 过程，m a r k o v 过程和m a r k o v 调制过程相关函数都是随着n 呈指数衰减的，即 圳 0 0 公式( 2 ，8 ) 考虑相关函数的部分和= x i + + 置，n l ，s o = o 。其方差 砌缄= c d v ( 五，乃) = 口2 q 州= 盯2 ln + 2 ( n - o p , i l = 1 ，= li = l1 = 1l = l 在可和性公式( 2 8 ) 的假设下有 l i m 竿卸2 【1 + 2 引 n _ ohi， 由公式( 2 。9 ) 可看出短相关部分和的方差是随n 成线形增长的。 对比传统的短相关业务，长相关定义如下 定义2 6 若一个平稳随机过程“幻，如果在延迟很大的时候， 是呈幂形式的缓慢衰减，即满足 y a k ) 巳盯9 ，0 1 公式( 2 9 ) 它的自相关函数 公式( 2 1 0 ) 那么称顶力具有长相关特性( 1 0 n gr a n g ed e p e n d e n c e ) 。 从长相关过程的定义可知，具有长相关特性的随机过程，它的自协方差函数 是不可积的。根据长程相关的相关函数的形式，可以知道长相关过程的功率谱在 1 0 第二章自相似过程的特性 密度l v i o 处的形式为瓜帅i v 一其中，a = l - p 。因此，我们也可以把在谱密度的 原点处具有幂形式发散的随机过程定义为长相关过程。