（通信与信息系统专业论文）网络流量的性能分析及模型研究.pdf

浙江工业大学硕士学位论文 网络流量的性能分析及模型研究 摘要 随着网络通信技术不断地发展，宽带网络的结构变得越来越复杂。为了能更有效地管 理和维护网络，就需要对网络进行性能评价，从而达到优化网络配置的目的。随着网络自 相似的发现，大量的关于自相似网络的研究不断涌现，而这些研究成果正是分析网络流量 自相似性的有力工具。 目前，自相似的研究大量地集中于网络流量的长相关模型以及表征自相似程度的 h u r s t 参数估计的研究。但是研究发现，小时间尺度上的网络流量呈现明显的局部奇异特 性，需要用多分形模型来刻画，而局部h 6 1 d e r 指数和多分形谱就是用来评价网络流量多 分形特性的。 本文首先阐述了自相似、长相关、h u r s t 参数和重尾分布等概念，在此基础上展开了 对实际网络流量自相似的验证。采用了经典的r s 参数估计法，对网络流量进行了h u r s t 参数估计，证明了实际的网络流量具有很强的突发性。为了验证网络流量存在重尾特性， 在介绍了一种重尾分布a l p h a 稳定分布的基础上，拟合出了实际流量的分布。验证结 果表明，网络流量存在重尾现象。另外，a l p h a 稳定分布的特征指数也验证了网络流量存 在自相似性。 在网络流量多分形模型的研究上，本文进一步提出了一种以乘法模型为基础的多分形 乘法模型( 可变尺度参数柯西乘法模型，v s c m ) 。通过仿真实验一一局部h 6 1 d e r 指数 和多分形频的验证，表明该模型的确存在明显的多分形特征。与原始流量数据比较后发现， 提出的模型数据能够很好地拟合原始流量数据。 关键宇：网络流量，自相似，长相关，重尾，多分形 浙江工业大学硕士学位论文 r e s e a r c ho np e r f o r m 队n c ea n a l y s i sa n d m o d e lo fn e t w o r kt r a f f i c a b s t r a c t w k ht h er a p i dg r o w t ho fc o m m u n i c a t i o nt e c h n o l o g y ，t h eb r o a d b a n dn e t w o r kb e c o m e s m o r ea n dm o r ec o m p l i c a t e d t om a n a g ea n dm a i n t a i nt h en e t w o r km o r ee f f i c i e n t l y , w en e e dt o e v a l u a t et h en e t w o r kp e r f o r m a n c eb a s e do nw h i c ht h en e t w o r kc o n f i g u r a t i o nc a nb eo p t i m i z e d a l o n gw i t ht h ed i s c o v e r yo fs e l f - s i m i l a r i t yi nn e t w o r kt r a f f i c ，al a r g en u m b e ro fr e s e a c hi nt h i s a r e ah a v e b e e ne m e r g i n ga n dp r o v i d i n gp o w e r f u lt o o l sf o rt h ea n a l y s i so fs e l f - s i m i l a rn e t w o r k t r a f f i c m o s to ft h ec u r r e n tr e s e a c h e so n s e l f - s i m i l a r i t yf o c u s eo nt h em o d e lo fl o n g r a n g e d e p e n d e n c ea n dt h ee s t i m a t i o no fh u r s tp a r a m e t e r t h eh u r s tp a r a m e t e rr e p r e s e n t st h ed e g r e e o fs e l f - s i m i l a r i t y h o w e v e r , r e a s e a c hr e s u l t ss h o w e dt h a ts m a l ls c a l et r a f f i ci n d i c a t e dl o c a l s i n g u l a r i t y , w h i c hr e q u i r e dam u l t i f r a c t a lm o d e lt oc h a r a c t e r i z e t h u s ，t h el o c a lh t l d e ri n d e x a n dm u l t i f r a c t a ls p e c t r u ma r eu s e dt oe v a l u a t et h em u l t i f r a c t a lc h a r a c t e r i s t i co fn e t w o r kt r a f f i c i nt h i st h e s i s ，w ef i r s t l yi n t r o d u c et h ec o n c e p t so fs e l f - s i m i l a r i t y , l o n gr a n g ed e p e n d e n c e ， h u r s tp a r a m e t e ra n dh e a v y - t a i l sd i s t r i b u t i o n b a s e do nt h e s et h e o r i e s ，t h es e l f - s i m i l a r i t yo fr e a l n e t w o r kt r a f f i ci sv e r i f i e d w ea d o p tc l a s s i c a lk sm e t h o dt oe s t i m a t et h eh u r s tp a r a m e t e ra n d v e r i f yt h a tt h er e a ln e t w o r kt r a f f i ch a sas t r o n gb u r s t n e s s s e c o n d l y ，t op r o v et h eh e a v y - t a i l s c h a r a c t e r i s t i ci nn e t w o r kt r a f f i c ，a h e a v y - t a i l sd i s t r i b u t i o n ( a l p h a s t a b l ed i s t r i b u t i o n ) i s i n t r o d u c e d b yf i t t i n gt h er e a lt r a f f i cw i t ht h ea l p h a s t a b l ed i s t r i b u t i o n ，w es h o wt h a tt h et a i l d i s t r i b u t i o no ft h er e a ln e t w o r kt r a f f i ci sm u c hh e a v i e rt h a nt h eg a u s sd i s t r i b u t i o n m o r e o v e r , t h ec h a r a c t e r i s t i ci n d e xo fa l p h a s t a b l ed i s t r i b u t i o na l s ov a l i d st h a tt h en e t w o r kt r a f f i c h a s s e l f - s i m i i l a f i t y f i n a l l y ，m u l t i p l i c a t i v em o d e li su s e dt om o d e lm u l t i f r a c t a ln e t w o r kt r a f f i c ，a n di nt h i sb a s i s ， an e wm u l t i f r a c t a lm o d e l ( w h i c hi sc a l l e da sv a r i a b l es c a l ep a r a m e t e rc a u c h ym u l t i p l i c a t i v e m o d e l ，v s c m ) i sp r o p o s e d t h r o u g hs i m u l a t i o n so nt h el o c a lh 6 1 d e ri n d e x 锄dt l l e i i 浙江工业大学硕士学位论文 m u l t i f r a c t a ls p e c t r u m ，i tp r o v e dt h a tt h ep r o p o s e dm o d e li sm u l t i f r a c t a l ，a n df i tt h eo r i g i n a l n e t w o r kt r a f f i ca c c u r a t e l y k e yw o r d s ：n e t w o r kt r a f f i c ，s e l f - s i m i l a r , l r d ，h e a v y t a i l s ，m u l t i f r a c t a l 1 u 浙江工业大学硕士学位论文 图例 图2 1 二维c a n t o r 集6 图2 2 网络流量时间序列图( 时间间隔分别为5 0 s ，1 0 s ，l s ，0 5 s ) 7 图2 3= 3 的o n o f f 源以及它们的聚合过程1 3 图3 1 ( a ) 用r s 法估计的实际网络流量数据( 流量数据间隔为5 0 s ) 1 9 图3 - l ( b ) 用p u s 法估计的实际网络流量数据( 流量数据间隔为1 0 s ) 1 9 图3 - 1 ( c ) 用r s 法估计的实际网络流量数据( 流量数据间隔为1 s ) 2 0 图3 - 1 ( d ) 用r s 法估计的实际网络流量数据( 流量数据间隔为0 5 s ) 2 0 图3 2 不同的口对应的概率密度曲线2 2 图3 3 不同的对应的概率密度曲线2 2 图3 4 ( a ) 实际网络流量的直方图( 流量数据时间间隔为1 0 s ) 2 6 图3 - 4 ( b ) 实际网络流量的直方图( 流量数据时间间隔为1 s ) 2 7 图3 5 时间间隔为l o s 的流量数据概率密度曲线2 8 图3 6 时间间隔为l s 的流量数据概率密度曲线2 8 图3 - 7 时间间隔为1 0 s 的流量数据概率密度尾部曲线2 9 图3 8 时间间隔为l s 的流量数据概率密度尾部曲线2 9 图3 9 时间间隔为1 0 s 流量的a l p h a 分布p p 图一3 0 图3 一1 0 时间间隔为1 0 s 流量的正态分布p p 图3 1 图3 l l 时间间隔为1 s 流量的a l p h a 分布p - p 图3 1 图3 一1 2 时间间隔为1 s 流量的正态分布p - p 图3 2 图4 l 原始数据的分割函数图3 6 图4 - 2 原始数据的尺度函数图3 7 图4 - 3 原始数据的多分形谱3 7 图4 - 4 二项式乘法模型构建过程示意图3 9 图4 5 ( a ) 第3 层的乘数分布概率密度图4 0 图4 - 5 ( b ) 第7 层的乘数分布概率密度图4 0 图4 - 6 ( a ) 估计所得的柯西分布位置参数口4 1 浙江工业大学硕士学位论文 图4 6 ( b ) 估计所得的柯西分布尺度参数b 图4 7 ( a ) 原始数据与聚合值的一阶矩比较 图4 7 ( b ) 原始数据与聚合值的二阶矩比较 图4 7 ( c ) 原始数据与聚合值的三阶矩比较 图4 7 ( d ) 原始数据与聚合值的四阶矩比较 图4 8 聚合值的分割函数 图4 9 原始数据与聚合值的分割函数 图4 一l o 原始数据与聚合值的( 口) 的比较 铊 躬 躬 钳 钙 牝 浙江工业大学硕士学位论文 第1 章绪论 1 1 课题研究的背景 传统的流量模型，如马尔可夫模型( m a r k o vm o d e l ) 、泊松模型( p o i s s o nm o d e l ) 、 高斯模型( g a u s s i a nm o d e l ) 和其它随机模型，它们产生的流量通常在时域仅具有短程相 关性( 即在不同尺度上有不同特性) ，随着流量聚集，突发会趋于平稳状态。很长一段时 间内，在通信领域，泊松模型足以描述语音流和数据流，且可以进行准确的分析和有效的 控制。但是，由于i n t e m e n t 技术的不断更新，用户对网络资源的需求持续增长，网络业 务的不断扩大，互联网的行为机制和管理模式描述更加困难，传统流量模型已经无法承担 起这个重任了。 i n t e m e t 在地域和拓扑结构上的复杂性变化，网络层次结构的复杂性变化，都在网络 流量统计特性的变化方面起着重要的作用。网络连接带宽和传输控制协议的选择在流量数 据的复杂性方面也扮演着主要的角色。由于网络结构随着时间变化而变化，这就要求资源 共享和管理能进行动态调整。另外，网络规模逐年递增，而网络服务的重点也转移到实时 数据( 音频，视频) 的传输和电话会议等方面，这些通信流量对平滑网络作业和管理有着 至关重要的影响。所有这些网络流量的复杂性描述，都可以概括为以下三层： ( 1 ) 地域复杂性。地域复杂性在网络复杂性中起着重要的作用。网络通信节点距离 的巨大变化导致网络拓扑结构错综复杂。其次，低速调制解调器到干兆以太局域网的接入 带宽也呈现出了显著的变化。而且，随着移动网络的来临，网络数据的空间复杂性也会剧 增。另外，网络流量的变化与用户的行为、新的网络的应用、路由的选择，节点的增长以 及子网的重新装配都有着精密的联系。 ( 2 ) 行为复杂性。基于流量的行为复杂性与流量需求的多层特性有关。例如由各种 用户随机发起的典型的网页会话，其活动层次变化巨大。同样，由用户开启的网络应用会 用到各种协议从而产生各种流量类型。更重要的是，数据的不同类型( 文本，音频，视频 等) 拥有不同的特性。近年来，各种研究表明网络数据存在重尾特性n j 。多个用户的行为 及其不同类型的数据在同一时间通过网络使得流量的复杂性不断增加。 ( 3 ) 时间复杂性。以上提到的两种现象都是随着时间变化的。网络流量的时间尺度 从几微秒变化到以天和周为周期。不同的时间尺度呈现不同的特性。例如，大时间尺度存 浙江工业大学硕士学位论文 在自相似性，而小时间尺度呈现明显的多分形现象 2 3 。在二十世纪早期，研究人员首次发 现测量的网络流量具有尺度变化特性儿引。 流量特征已经发生了显著的变化，泊松模型不再能充分反映当前网络流量的复杂性。 流量建模的主要问题是如何有效且经济地对实际网络流量进行仿真。复杂的网络流量需要 用非传统的建模及分析方法来研究，传统的建模工具与技术只能在一个很局限的范围内对 宽带流量行为进行描述。自从l d a n d ，t a q q u ，w i l l i n g e r 和w i l s o n h m ”等人首次提出将自 相似性作为网络流量研究( 包括网络流量模型和性能分析) 的重要考虑因素，引发了对网 络自相似性的大量研究。 自相似过程是在统计意义上具有尺度不变性的一类随机过程，从这点上来说，自相似 过程实际是在随机过程中引入了分形( f f a c t a l ) 哺1 的概念。网络通信量的自相似性程度不 仅与观察数据的尺度分辨率有关，且与分形维数有关。分形是研究自相似现象的有力数学 工具，而自相似现象产生的动力学基础是混沌吸引子。自相似性是分形理论的重要特征， 它表征分形在通常的集合变换下具有不变性。实际网络流量的自相关函数随间隔增大呈双 曲函数衰减，具有长相关( l o n gr a n g ed e p e n d e n c e ，l r d ) 特性。长相关性是自相似的重 要概念之一，在实际网络流量的描述中，通常认为自相似性和长相关性是一致的。这种基 于自相似的模型仅用一个h u r s t ( 赫斯特) 参数就能反映出l r d 特性来。进一步的研究表 明，真实网络环境中的网络流量呈现出相当明显的时域上和空间上的突发性和不稳定性， 可以把流量数据看成通过网络的突发流。 1 2 课题研究的意义 随着通信技术的不断发展以及宽带网络需求的激增，网络规模越来越大，为了能更好 地管理和维护网络，就需要用有效的措施提取网络性能参数，从而对网络性能进行分析理 解，优化网络配置，发现潜在的威胁。如何合理、准确、可靠地描述网络流量的真实特性 就显得尤为重要。网络流量模型是进行网络性能评价，认识和分析网络行为及其变化规律 的基础，这就需要找到合适的流量模型，并通过有效的方法对其性能进行分析评价。 网络流量自相似的发现，开拓了全新的研究领域，经典的理论依据( 如泊松过程和马 尔科夫模型) 不再适合现代网络的分析和建模。而目前，大量的关于网络流量的长相关模 型研究以及描述自相似特性i 拘h u r s t 参数的估计方法 鲫阳1 不断涌现，这些研究成果在分析 网络流量自相似方面是非常有力、值得借鉴的工具，而且这方面的数学理论也日渐成熟。 此外，不同时间尺度的网络流量呈现不同的特性，在小时间尺度上呈现出明显的局部 浙江工业大学硕士学位论文 奇异特性，而目前的自相似模型大多集中于对长相关特性的捕获。但小时间尺度上的局部 特性无法仅用自相似模型来描述，需要用多分形模型来刻画。这时，仅用一个h u r s t 参数 来刻画网络流量特性也是不够的。小时间尺度与网络的运行和控制机制紧密相关，所以小 时间尺度的分析和研究对流量控制和资源配置算法的发展有很大的帮助。 1 3 国内外研究现状及趋势 9 0 年代初，文献 1 首先发现了局域网环境( 以太网) 中存在自相似性，文献 1 0 证 实了w w w 广域网p 流量的自相似突发性，文献 1 1 也证明了w w w 流量具有自相似性。 大量的研究表明，自相似突发性不是一个孤立、虚假的现象，而是网络中普遍存在的特征。 目前，关于流量自相似的研究方法主要可分为以下几类：第一类方法是以测量为基础 的流量模型阳埘n 1 1 2 3 ，收集和分析来自物理网络的流量数据，从而探测、识别、量化流量 的相关特性。第二类方法是研究物理模型，模型基于网络机制和以实验为主的分布式系统。 这类模型可以阐述网络流量自相似性的物理成因，也就是在网络层的复用节点中引发自相 似突发。第三类研究方法是从排队论意义上来提供长相关流量数学模型n 3 儿1 4 1 5 3 。 j i n c a o 等人利用分形和差( f s d ) 模型n 6 1 深入研究了网络流量的非平稳性，指出非平 稳特性在网络流量中普遍存在，并且认为多个独立的h t t p 业务的叠加是造成网络流量具 有非平稳特性的主要原因。非平稳性不但会对网络流量的长期变化特性产生严重的影响， 而且h u r s t 指数的估计对网络流量的非平稳特性极为敏感。另外由于网络流量特性大多具 有重尾分布特性，因此网络流量特性也具有非高斯性。这两种特性的存在使自相似框架下 的网络流量特性描述变得非常困难。当前对网络流量的研究大多集中于如何准确地捕获网 络流量的长相关性及如何高效、准确地估计流量序列的h u r s t 参数，从而研究产生了众多 自相似或长相关的数学模型。对自相似流量的描述，其中比较经典的有以下几种模型， o n o f f 模型、分形布朗运动( f b m ) n 刨、分形高斯噪声( f g n ) 模型n9 j 、分形自回归 ( f a r i m a ) 模型乜们以及a l p h a 稳定( a l p h a s t a b l e ) 分布模型哑n 等。它们有各自的优缺点： ( 1 ) o n o f f 模型的结构简单，物理意义明确，能把复杂的聚合流量的特性分析细 化到每个信号源的分析，且它又能从数学意义上描述自相似通信量的统计特点。但建立这 种模型需要很多前提假设，与实际情况不符，不适于网络细节的描述。 ( 2 ) f b m f g n 模型简单、易于处理，有坚实的数学理论基础，可以很方便地应用 于流量的实时仿真。但是f b m 是严格自相似的，无法描述网络业务的短相关性，而且它 带有高斯性，不能很好地分析非高斯信号。 浙江工业大学硕士学位论文 ( 3 ) f a r m a 模型的优点在于它具有灵活性，能够同时对长相关性与短相关性的随 机过程建模。但在描述网络突发上显得不足，且由于模型复杂参数又多，因而运算量过大 无法符合实时性要求。 ( 4 ) 基于a l p h a 稳定过程的网络流量模型分别有s 4 模型和葛晓虎模型，它们都能给 予物理上的解释，也能对自相似网络流量的统计特性进行灵活地描述。但是因为a l p h a 稳定分布不具有闭式概率密度表达式，给进一步的研究带来了困难。 自相似框架下的网络流量模型能够较好地刻画网络流量长期的行为特征，但对其短期 行为的细微特征描述方面显得不够充分。r i e d i 等人对广域网汇聚流量进行尺度分析瞳副的 基础上首次发现：流量过程在较大时间尺度下呈现渐近自相似特性，而在几百毫秒以下的 小时间尺度下呈现出明显不同的局部奇异特性，无法用长程相关模型来描述。网络流量的 多尺度行为导致了其具有更复杂的特性，而自相似作为多分形的一种特殊情况，并不能完 全刻画网络流量，需要用多分形( m u l t i f r a e t a l ) 模型进行刻画。基于乘法模型儿2 4 儿2 5 2 6 3 的 网络流量分析方法是常用的多分形分析方法，而多分形小波模型( m w m ) 心”就是基于乘 法模型的多分形模型。乘法模型具有很好的网络物理意义，与t c p 口从应用层到传输层的 工作机制有关。而基于小波分析的m w m 模型能够对短相关和长相关的网络流量进行描 述，且能很好地吻合实际网络流量在小时间尺度下的多分形特性，有望在流量预测上进行 突破。但该模型也有缺点一一小波系数并非在每个尺度下都独立，且小波基的选取也会影 响模型质量。故而论文在多分形模型上还需要进行进一步的分析研究。 目前，网络流量模型的研究已经取得了一定的成果，但与实用性要求还有很大的距离。 总结上面所阐述的流量模型可以知道：目前大部分网络流量模型的工作大多集中于长相关 性的研究以及表示白相似程度的参数h u r s t 的度量；基于小时间尺度的局部奇异性行为的 研究还处于初始阶段；模型的复杂度与准确性相矛盾，很难用尽量简单的模型来描述网络 流量的特性。 1 4 主要研究内容和组织结构 本文主要是在自相似理论基础上，研究能准确和全面刻画网络流量序列的模型。从自 相似的长相关性、多分形特性入手，研究符合实际流量的模型。用m a t l a b 和相关的数 学统计软件进行理论研究与验证。 本文共有五章，主要的组织结构包括： 第一章绪论部分介绍了课题研究的背景，以及课题研究的目的和研究意义，接着分析 4 浙江工业大学硕士学位论文 了国内外研究现状，在章节的最后罗列了论文的组织结构。 第二章介绍了网络流量的自相似性，阐述了自相似的相关理论( 二阶自相似、长相关、 重尾分布) 以及这几个概念之间的关系。此外，简略介绍了几种经典的自相似流量模型， 以及表征网络流量自相似程度的h u r s t 参数。 第三章先从h u r s t 估计方法一一r s 法入手，阐述了r s 估计法的原理及算法实现步 骤，并对其可靠性进行了验证。以德雷克赛尔大学通信与信号实验室的研究人员收集的实 际网络流量数据为参考，做了实际网络流量的h u r s t 参数估计，表明网络流量的自相似性。 本章还重点介绍了一种重尾分布模型一一a l p h a 稳定分布，对实际的网络流量序列的重尾 分布进行实证，表明网络流量存在重尾现象。 第四章首先介绍了单分形( 单一白相似) 和多分形的区别，多分形的定义以及多分形 测度一一多分形谱。并且在多分形理论的基础上提出了一种新的多分形模型s c m ) ， 比较了实际流量数据和模型仿真数据的统计特性和多分形特征，仿真结果表明所提出模型 是合理性的。 第五章是对全文的总结，除了归纳本研究工作的结论与成果之外，对未来的发展方向 和可扩展研究的内容进行了展望分析。 浙江工业大学硕士学位论文 第2 章网络流量的自相似特性 2 1自相似的物理描述 这里用分形的思想来描述自相似性，分形的概念是由b m a n d e l b r o t 晦1 首先提出的。自相 似和分形描述了物质的这样一种特性，比如一幅图像，一个动力系统的收敛子域，或一个 时间序列哉们感兴趣的一些数学物质，在空间尺度或时间尺度上维持不变。如果一物 体是自相似的或分形的，当它被放大时，它的局部在一定意义上相似于整体状态。例如， 二维c a n t o r 集，在a = 0 ，1 1 ，0 】内，它是由一个实心或黑色的单位正方形组成的。将其尺 寸缩t j , 至l j l 3 ，然后在四个角上放置四个缩放后的a 的复本。如果同样的缩放过程无限递归 下去，极限集就是所定义的二维c a n t o r 集。此建立过程如图2 1 所示。对象如此重复，如果 任何一个角适当地“扩大”，那么局部放大的形状相类似于整体的形状，这就是自相似。 当然，从以上的递归建立过程可知，此物体具有尺度不变性。 一日日 l r 一。r 一一一一n - r i l luu u i nnnr pu l u l l q 专；! 专l 专 专 一2 窖 图2 1二维c a n t o r 集 h 一 i t ul hp r mng q “i 一uu 那什么是网络流量自相似呢? 与上面所阐述的确定性分形不同，图2 2 中的对象，其整 体和局部在细节上没有精确的相似性。网络流量具有随机自相似性，随机自相似性允许测 量的流量存在不确定性，但整体与局部的统计特性趋势是相同的。尽管如此，随机自相似 性仍然是一种可以直观阐述的特性。图2 2 ( 左上角) 显示了一个实际的网络流量序列，绘 制了以包个数为单位的数据包流量，其中单位时间间隔为5 0 s 。也就是说，一个单独的数据 点是5 0 s 间隔内到达的数据包个数。图2 2 ( 右上角) 是同一个流量序列前1 0 0 0 0 s 的数据被 放大了5 倍的图。因此，被截断的时间序列的时间间隔为l o 秒。其它两幅图是图2 2 ( 右上 角) 初始阶段的数据依次放大1 0 倍和2 0 倍得到的。从图中我们可以看到，实际网络流量的 突发性不随时间轴单位的变化而变化。依照传统模型的结论来说，当数据源数目增加时， 6 浙江工业大学硕士学位论文 其聚合流量的突发性将会被吸收而变得更平滑。但对于自相似性来说，突发性却没有改变。 事实上，对于流量的测量，观察地越精确越好。很多网络事件( 例如，源数据抵达行 为) 的随机性质共同影响了实际的网络流量，使得确定的自相似性掺入了随机性。我们放 宽自相似的度量条件，将重点放在流量时间序列的统计特性上，那么，数学意义上的精确 相似性和具体实现过程的大致相似性就不冲突了。二阶统计是捕获突发性和可变性的统计 特性，而自相关函数是一个定义尺度不变性的标准。需要注意的是，白相似性与长相关性 有一定的联系和区别，在2 2 节具体讨论。 10 4 8 6 籁 - - 4 固 2 0 4 0 0 0 3 0 0 0 辍 牛2 0 0 0 固 1 0 0 0 0 05 0 01 0 0 0 时间间隔5 0 s 05 0 01 0 0 0 时间间隔1 s 2 1 5 藕 厶 1 固 o 5 0 2 5 0 0 2 0 0 0 蒎1 5 0 0 - - 圃1 0 0 0 5 0 0 0 1 0 4 05 0 01 0 0 0 时间间隔1 0 s 05 0 01 0 0 0 时间间隔0 5 s 图2 - 2 网络流量时间序列图( 时间间隔分别为5 0 s ，l o s ，l s ，0 5 s ) 2 2 自相似和长相关 2 2 1 二阶自相似和平稳性 考虑一个离散时间随机序列或时间序列x ( ，) ，t z ，这里( ，) 可以解释为流量时间 序列( 以包、字节、位为测量单位) ，时间为，。另外一种解释是，j ( ，) 是从0 时刻到，时 刻的总流量。为了避免混淆，我们采用“积累 的观点，用】，( f ) 表示过程，那么x ( f ) 为 相应于j ，( ，) 的增量过程，即z ( ，) = ，( ，) 一y ( ，- 1 ) 。 7 山| f 山 一 堑鋈三些奎兰堡主兰竺堡圣 从建模的目的出发，希w x ( o 是稳定的 ，即它的行为或结构关于时移不变。换句 话说，作为绝对参照系的责任解除。如果( z ( ) ，x ( t ：) ，x q 。) ) 和 ( 工( z ，+ 七) ，x ( t 2 + 露) ，x ( t + 露) ) 对于所有的，7 z + ，k z ，拥有相同的联合分布，那么x ( f ) 是严平稳的。将位移为| i 的过程或时间序列标记为五，x 和五在有限维的意义上分布等 同，可以表示为x = dk 。但是严平稳的条件过于严苛，可以采用更弱的平稳形式二 阶平稳，这就需要自协方差函数y ( 厂，s ) = e i ( x ( r ) 一) ( j ( 5 ) 一) 】满足位移不变性，即对于 所有的，s ，k z ，y ( ，s ) = r ( r + 七，s + 七) 。假设前两个时刻存在且有限，并设= 日x ( 纠， 仃2 = e 【( x ( ，) 一) 2 】，t z ，如果= 0 ，那么r ( r ，s ) ：y ( r - s ，0 ) ，自协方差函数标记为，( 足) 。 为了描述尺度不变性，首先定义x 的聚合过程( a g g r e g a t e dp r o c e s s ) x ，聚合级数 为聊， x m ( j ) = = 1 兰x ( f ) ( 2 1 ) ，行，：，= 万j 、+ 1 上述公式表示，x ( f ) 被分割成互不重叠，大小为m 的模块，取模块的平均值，f 为索引值。 在二阶平稳的假设下，得出以下二阶自相似的定义。 , 定x z l 二防茸耢7 甜设离散随机过程( ( ，) ，t z ) ，对于任何k 1 ，有： y g ) ：宰缸+ 1 ) 擅一2 k2 日+ ( k - 1 ) 2 日) ( 2 2 ) 则称该过程为具有自相似指数h u r s t ( 简写为日( 1 2 日 1 ) ) 的精确二阶自相似过程。 定义2 2 旃近= 玢茸耜倒如果随机过程x ( f ) 的聚合过程满足： 。l i + r a 。， ) = 等妣+ 1 ) 捕一2 k 2 h + 一1 ) 2 h ) ( 2 - 3 ) 则称该过程为渐近二阶自相似过程。可以验证公式( 2 2 ) 对于所有的m 1 ，有 y ) = y ( ”( k ) 。因此，二阶自相似具有这样的特点，当时间序列叠加时协方差的结构保留 了下来。用于仿真时，其主要结构就是渐近二阶自相似过程。而这里的公式( 2 2 ) 它意味着 进一步的结构长相关。 2 2 2 长相关 之前一直在讨论二阶自相似性的定义问题，很少考虑到日的作用和值的范围。回到 8 浙江工业大学硕士学位论文 二阶自相似以及自协方差函数r ( k ) 的定义，令厂 ) = y ) 仃2 表示自相关函数。对于 0 日 1 ，_ r h 1 2 ，它可以表示为： r ) 日( 2 日一1 弦2 肛2 ，kj ( 2 - 4 ) 特别地，n1 2 日 1 时， ) 渐近表示为政，这里o 枷，、，、 7 _ 一= 瑚 、 满足下面特性，即 r ( u ) - c t v r 口，v 寸0 ( 2 - 6 ) c 0 是一个常数且0 口= 2 日一1 1 。因此，r ) 在零点附近发散，这是由频率的低频成 分引起的。 h 的值对厂 ) 的影响表现在以下几个方面。首先，如果日= 1 2 ，那么厂 ) = 0 ，x ( ，) 是一个短相关过程( 相当于随机游走过程) ，服从高斯分布。当0 日 1 2 时，我们可以 得到厂伍) = 0 ，这种情况很少在应用中遇到。日= 1 是没有意义的，因为对于所有的j | 1 量： 它使得厂 ) = 1 。考虑到x ( ，) 的稳定性，日的值不可能大于1 。而1 2 日 1 则表征随机过 程的长相关性，可以描述网络流量的突发性。日越接近1 突发程度越强，长相关性使得 网络流量的突发性不会因为聚合而变得平滑。 最后值得一提的是，对于长相关过程，其聚合过程的方差，当聊一时， v a r ( x ”) 仃2 m 一声( 0 1 ，日= 1 一3 2 ) ，其衰减速度要比册一1 慢。而短相关过程，当 m o o 时，v a r ( x ”) 仃2 聊，其衰减速度与历一1 相同。 浙江工业大学硕士学位论文 2 2 3自相似和长相关的关系 自相似过程不一定是长相关的，反之亦然。例如，布朗运动是一个1 2 - s s s i 过程( 自 相似参数月为1 2 的稳定增量过程) ，它的增量过程是一个高斯白噪声，但不是长相关的。 相反的，相当一部分的f a r j m a 时间序列产生长相关性，但是在分布的意义上它们不是 自相似的。在渐进的二阶自相似情况下，由于定义中的1 2 h x ) c x 一口，x - - + ( 2 7 ) 这里0 a 2 被称作尾指数或形状参数，c 是一个正常数。 这样分布的尾部衰减呈渐近双曲线形状。这和轻尾分布( 1 i g h tt a i l s ) 相反，例如指数 分布和高斯分布，它们拥有一个指数衰减的尾部。而重尾分布与之明显的区别是，在 0 口 2 内具有无限方差，而当0 a l 时，它又具有无限均值。研究网络流量时，主要 讨论1 口 2 的这种情况。经常用到的一个简单的重尾分布是p a r e t o 分布，它的分布函数 是 p r z x ) = ，一( 兰) 。，6 x c 2 8 ) l x 这里，0 0 为流量方差， m 是业务的平均到达率，e 为标准的布朗运动。 这两种模型是严格自相似的，对短相关的流量描述不够，但是它们具有良好的数学基 础，且参数估计简单。 2 4 2o n o f f 模型 o n o f f 模型具有n 个独立的流量源x ，g ) ，7 【l ，n 】，每个流量源是一个0 1 交替的过 程，这里0 代表o f f 周期的状态，1 代表o n 周期的状态。x ，o ) = 1 理解为有数据包在传送。 因此，一个o n 周期可以认为是一个“包传送”过程b “，而o f f 周期就是传输间隔。图2 - 3 描述了三个这样的o n o f f 源和它们的聚合过程。& o ) = 兰。五o ) 代表时间t 的聚合流量， 积分过程y ) 被定义为： k ) ：r f 兰x ，g ) k ( 2 1 2 ) ，：1 这里t 0 是一个重新调整时间因子。因此) 计算了0 时刻到t t 时刻的总流量。如果 和t 足够大，民) 的统计特性就依赖于o n 周期和o f f 周期的分布。 浙江工业大学硕士学位论文 墨( ，) k ( r ) 五( ，) 墨( ，) 图2 - 3n = 3 的o n o f f 源以及它们的聚合过程 令彳。表示o n 周期持续时间的随机变量，r 谚表示o f f 持续时间的随机变量，则 尸b 。 x ) c x - a , x - - - 0 0 ( 2 1 3 ) 在这里1 o 表示散度参数，意义 相当于高斯分布中的方差；5 r 表示分布的位置参数。 当口= 2 时，a l p h a 稳定分布退化为均值万的高斯分布：当口= 1 ，夕= 0 时，a l p h a 稳 1 4 浙江工业大学硕士学位论文 定分布退化为柯西分布；当口= 1 2 时，分布服从l e v