（通信与信息系统专业论文）基于小波的网络流量自相似性的分析.pdf

l 海交通大学硕士学位论文 基于小波的网络流量自相似性的分析 摘要 f 白相似现象是指在很大尺度范围内呈现结构上相似的过程或现 象。随着对网络流量研究的不断深入，人们发现不论网络的拓扑结构、 用户数量、服务类型如何变化，网络流量中始终存在自相似性。 传统的网络研究是以短相关性为前提进行的，在这种前提下，排 队尾部呈现指数分布。但是，自相似网络流量相对应的是长相关性， 由它引起的排队尾部呈现w e i b u l l 分布。网络流量的这种自相似性会 对现有的网络理论如流量测量、排队性能、缓存大小、接入控制、拥 塞控制以及q o s 设计等产生深远的影响。 研究表明，小波分析在自相似网络流量分析中具有许多优点，例 如分析速度较快；小波理论开阔了研究的视角；最重要的是对于带有 长相关性的信号，小波变换会把它在小波域上分解成近似彼此不相关 j一 的过程，从而简化了分析。i ，7 ， 现有的自相似研究往往从聚合的网络流量的角度进行考虑，本文 则从网络连接的层面对网络流量进行分析。本文使用小波技术把网络 流量分解成a l p h a 流和b e t a 流。通过分离，a p h a 流包含了造成了 网络流量突发性的部分，而b e t a 流的传输速度分布符合现有自相似 网络流量的模型。在总网络流量中，b e t a 流占有绝大部分，a l p h a 流 上海交通大学硕士学位论文 仅占小部分。在排队分析中，本文发现在一般情况下，对于排队队 长较短的情况下，b e t a 流影响着排队性能；对于排队队长较长的情 况下，a l p h a 流影响着排队性能。 在网络流量自相似的研究中，网络流量自相似性的仿真是一个非 常重要的手段，本文提出系统仿真的观点，认为因为网络流量自相似 性受到网络整个系统许多因素的影响，对它的仿真应当从各个方面考 虑进行系统的仿真。 关键词；流量工程，自相似性，长相关性，小渡 v、 w a v e l e t b a s e da n a l y s i s o ft h es e i f s i m if a ri t yo f n e t w o r kt r a f f ic a b s t a c t s e l f - s i m i l a r p h e n o m e n o ni s t h e p r o c e s s o rp h e n o m e n o nw h i c hi s s i m i l a ro nd i f f e r e n ts c a l e s a s t h er e s e a r c ho fn e t w o r kt r a f f i c s e l f - s i m i l a r i t yd e v e l o p s ，p e o p l ef i n dt h a ts e l f - s i m i l a r i t y o fn e t w o r kt r a f f i c a l w a y se x i s t su n d e r v a r i o u sn e t w o r kt o p o l o g y , v a r i o u su s e rn u m b e r , a n d v a r i o u sn e t w o r ks e r v i c e t r a d i t i o n a ln e t w o r kr e s e a r c hi sb a s e do ns h o r tr a n g ed e p e n d e n t m o d e l s ，s u c h a sm a r k o vm o d e l t a i l q u e u ep r o b a b i l i t y d e c r e a s e s e x p o n e n t i a l l yu n d e rs u c h k i n do f m o d e l b u ts e l f - s i m i l a rn e t w o r kt r a f f i c i s l o n gr a n g ed e p e n d e n t ，w h i c h m e a n st h a tt a i l q u e u ep r o b a b i l i t y d e c r e a s e sl i k ew e i b u l ld i s t r i b u t i o n s ot h es e l f - s i m i l a r i t yc a na f f e c tt h e e x i s t i n gn e t w o r kt h e o r y , s u c ha sq u e u ea n a l y s i s ，b u f f e rd e s i g n ，a c c e s s c o n t r o l ，c o n g e s t i o nc o n t r 0 1 w a v e l e tb r i n g san e w a n g l et ot h i sa r e a i tp r o v e s t h a tw a v e l e tb a s e d a n a l y s i sh a sm a n ya d v a n t a g e si nt h er c s e a r c ho f n e t w o r ks e l f - s i m i l a r i t y , s u c ha sf a s ta n a l y s i ss p e e d t h em o s ti m p o r t a n tc h a r a c t e r i s t i co fw a v e l e t i st h a ti tc a nt r a n s f o r mh i g h l yc o c l u e dt i m ed o m a i ns i g n a li n t oa l m o s t ! 塑奎望盔堂堡兰垒堡兰一 i n d e p e n d e n t w a v e l e tc o e f f i c i e n t s ，w h i c hh e l p ss t u d ys e l f - s i m i l a r i t y m o s te x i s t i n gr e s e a r c ha b o u tt r a f f i cs e l f - s i m i l a r i t y c o n c e n t r a t e so n a g g r e g a t e l e v e lo fn e t w o r kt r a f f i c t h i sp a p e ra n a l y z e s t r a f f i c s e l f - s i m i l a r i t y f r o mal o w e rl e v e l ，t h ec o n n e c t i o nl e v e l w e d i v i d e n e t w o r kt r a f f i ci n t oa l p h at r a f f i ca n db e t at r a f f i cb y a ne f f i c i e n tw a v e l e t d e n o i s eb a s e dm e t h o d w e f i n dt h a t a l p h a t r a f f i ch a st h e b u r s t c 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 ca n db e t at r a 伍c h a st h eg a u s s i a n s e l f - s i m i l a r i t y q u e u ea n a l y s i si sp e r f o r m e dt o f i n dt h a ta l p h at r a f f i ci s r e l a t e dl o n gq u e u ea n db e t at r a f f i ci sr e l a t e dt os h o r tq u e u e t h ep a p e ra l s op u t sf o r w a r dt h ev i e wo fs y s t e m a t i cs i m u l a t i o no f n e t w o r kt r a f f i c s e l f - s i m i l a r i t y w e c o n s i d e rt h a ts e l f - s i m i l a rn e t w o r k s h o u l db es i m u l a t e di na l lt h ew a y s ，s u c ha sc a c h e ，s e r v e r , c l i e n ta n d e v e r yl a y e ro fn e t w o r k ，t og e tt h ec o m p l e t es i m u l a t i o n e f f e c t s k e yw o r d s ：t r a f f i ce n g i n e e r i n g ，s e l f - s i m i l a r i t y , l o n g r a n g e d e p e n d e n t ，w a v e l e t 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密曰。 ( 请在以上方框内打“4 ”) 学位论文作者繇鸶降扬指导教师签名：禾蚜枇 日期：2 鳓；年? 月o 日日期；2 ；年2 月夕日 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 乌9 派扬 日期：2 仞；年2 月i o 日 圭童銮望查堂堡圭堂焦丝生一 第一章引言 随着i n t e m e t 的飞速发展，人们对网络流量的研究不断深入，大量的流量监 测结果表明：无论是局域网上的数据还是v b r 流量，都在相当长的时间尺度下 呈现出统计自相似性。不论网络的拓扑结构、用户数量、服务类型如何变化，这 种自相似性始终存在。在图1 - 1 中，表示了这种自相似性。 ( c ) 10 分钟内流量情况 ( c ) t r a x 街cd u r i n gl om i n u t e s 图1 - 1 网络流量中的自相似性 f i gt - ls e l f - s 虹d l a r i 坶i na e t w k 蛾啦k 网络流量中的自相似性具有明显的长相关性，而传统的网络研究是基于短相 关性的前提进行的。传统网络理论中，排队尾部呈现指数分布，往往对性能做出 圭壁銮望查堂堡圭堂垡笙兰一 过于乐观的估计；种研究发现自相关的流量引起的排队尾部呈现w e i b u l l 分布。 因此，这种自相似性对现有网络理论产生很大影响。 小波的引入为复杂的自相似流量分析提供了一个新的工具。使用小波来分析 具有长相关性的自相似信号有很多优点。首先，小波分析的速度非常快。在生成 的厂过程的各种方法中，w o m e l l 提出的基于小波的方法时间复杂度只有 o f 7 w 【2 3 】，但是l e v i n s o n 算法的时间复杂度是。口昀，c h o l e s k y 算法的时间复杂 度是0 口n 。对于网络分析，一般需要n * 1 0 ，因此，基于小波的合成有很大的 吸引力。其次，小波分析可以用于非稳态的或者带有特定变化趋势的l r d 过程 ( 1 6 。因为无论在理论上还是工程上，其他方法都很难准确的区分是特定变化趋 势还是l r d 产生的长期方差变化，所以这个特点非常重要。 现有的研究多数从聚合的网络流量的角度进行分析，本文通过使用小波去噪 技术把网络流量分解成a l p h a 流和b e t a 流，从网络连接的层面对网络流量进行 了分析。扩展了现有的自相似研究，此外还提出了高效的小波去噪分离法来从网 络流量中分离出a l p h a 流和b e t a 流，并进步讨论了网络流量的排队问题和仿 真问题。 在后面的各章节中，第二章回顾了自相似相关的理论和现有对白相似网络流 量的研究；第三章从网络连接的层面对网络流量进行了分析，提出了运用小波去 噪分离法分离a l p h a 流和b e t a 流；第四章讨论了网络流量自相似性对排队的影 响：第五章讨论了对自相似网络流量的仿真。 第二章自相似网络流量的背景 在过去的十多年间，通过对l a n 数据和v b r 业务等高速网络中的大量流 量的精确测量发现：这些流量中普遍存在自相似性，这种自相似性与流量发生的 时间地点或信源编码方式无关。 对各种分组网络所进行的高精度测量数据的统计分析都显示了自相似的特 性，即在从毫秒级到分钟级甚至小时级的时间尺度上，相似的统计的特性会重复 的出现。 很多传统研究是基于短相关性的前提进行的，而自相似网络流量相对应的是 长相关性。传统网络理论中，排队尾部呈现指数分布，往往对性能做出过于乐观 的估计；一种研究发现自相关的流量引起的排队尾部呈现w e i b u l l 分布。长相关 性可能对流量测量、排队性能、缓存大小、接入控制、拥塞控制以及q o s 设计 产生影晌。 本章将对与网络流量自相关性相关的理论及研究进行综述和分析。 2 1 现有网络流量存在自相似性的证据 从1 9 8 9 年到1 9 9 2 年间l e l a n d 和w i l s o n 等人使用高时间分辨率的以太网监 视设备在b e l l c o r em o r r i s t o w n 研究和工程中心的几个以太网段上收集到了数百 万个实际传输的数据包 1 】。l e l a n g 等人根据这些数据第个发现：这种叠加的 l a n 流量所表现出的统计自相似性完全不同于传统的话务理论中所使用的 p o i s s o n 模型【2 】。这种区别使得我们需要重新对突发流量模型及其对宽带网性能 的影响进行研究。另外e r r a m i l l i 和w i u i n g e r 等人收集并分析了大量的从i s d n 、 以太网和v b r 视频流量中得到的数据 3 】：p a x s o n 和f l o y d 从广域网w a n 上收 集并分析了大量的流量数据【4 ：b e l l c o r e 的研究人员从使用7 号信令的共路信令 网( c c s n ) 上收集了原始流量数据；a d d i e 、z u c k e r m a n 和n e a m e 从澳大利亚 高速数据网f a s t p a c 上收集并分析了大量的流量数据【5 ；此外，h e y m a n 等人 测量并分析了m 网络中传输的视频会议流量表现出的些特性【6 】。 墨壅奎望盔堂堡圭堂焦堡苎 一 大量的流量监测结果表明：无论是局域网上的数据还是v b r 流量，都在相 当长的时间尺度下呈现出统计自相似性。不论网络的拓扑结构、用户数量、服务 类型如何变化，这种自相似性是始终存在的。这一切都说明：在高速网络的突发 流量传输中，采用自相似模型比传统的m a r k o v 模型更接近实际流量的特性。 2 2 基本公式 在这里首先列出网络流量研究中稳态随机过程的基本定义与公式，以方便后 文的论述。 设( f ) 是计数过程，它表示到时间t 为止到达的分组数，即 ( ) = f 柳( f ) ( 2 1 ) 其中，d n ( t ) 是质点过程，表示时间f 时分组的到达。 设随机时间序列j ，# 0 碥，n 是以露为基本时间尺度分组到达序列，其中 疋= n i n e 一 加一1 ) 霉】( 2 2 ) 与本文相关的主要统计特性有： 平均值 = 研以】( 2 3 ) 方差 仃2 = z a r 以】= e l ( 一) 2 】( 2 4 ) 标准差，又称均方差，其值为盯。 自相关函数 c o y ( x , ，x 。+ t ) = e 【x 。一卢) 【x 。+ 一) ( 2 5 ) 归一化白相关函数( a c f ) 肌刃= 掣 ( 2 6 ) 计数发散指数( i d c ) ，( 丁) = 丽v a r n ( r ) ( 2 7 ) 功率谱密度 4 圭塑銮望查兰堕圭兰堕笙兰一 s ( = r ( k ) e 2 “ ( 2 8 ) 其中，w = 2 丌。 如果其统计特性不随时间而改变，随机过程被称为是稳态的。也就是说 该过程没有特性尺度。如果其一阶和二阶统计特性不随时间而改变，它就被称为 二阶稳态或广义稳态。二阶稳态过程的平均值不变，方差是有限值，归一化自相 关函数只与时间差k 有关。 2 3 自相似现象与自相似过程 2 3 1 自相似现象 自相似现象是指在很大尺度范围内呈现结构上相似的过程或现象。换言之 就是结构或是过程的统计特性在很大范围内不随尺度的变化而变化，这些尺度可 以是几何方面、统计方面的或其他方面的。传统科学认为物理系统的特性能够由 时间、空间或其他的基本尺度来表征，自相似相关的理论则引入了尺度定律，即 中心矩发散的自然现象不应该用基本尺度，而是应该使用尺度之间的关系来描 述。 自相似的概念与分形理论有关。在几何尺度方面有名的例子是c a n t o r 集、 s i e r p i n s k i 三角形以及k o c h 曲线。在统计尺度方面有名的例子是经济学上的 p a r e t o 定律、语言学上的z i p f 定律以及社会学上的l o t k a 定律。 2 3 2 自相似过程 如果连续时间随机过程坦0 与n 诹口o 有相同的有限维分布，即 d x ( f ) = 4 “x ( a t ) ( 2 9 ) 其中，o 5 h 1 是所谓的h u r s t 系数，那么，嘏f ) 被称为是统计上自相似的。 h u r s t 参数，简写为鼠来自于水文学家h e h u r s t ，他通过长年的蓄水研究 发现尼罗河在8 0 0 年间的变化呈现自相似规律。h u r s t 参数表征了自相似的程度， 即统计现象持续的程度。如果日为0 5 ，那么说明没有自相似；如果胃接近i ， 圭塑銮堕查兰堡主兰堡堕墨一 那么说明自相似程度非常高，或是说呈现长相关性，即如果过程在过去是增长( 或 减少) 的话，z p z , e , 在将来也会增长( 或减少) 。 对于自相似过程，有以下性质 e i x ( 明= 譬掣 妇n x ( f ) j ：w r j x 矿( a o ( 2 1 1 ) 讹r ) = 丁r ( a t , a r ) ( 2 1 2 ) 对于离散时间随机序列l ，- 蜀，矿 在原时间序列上进行m 级平均，生成 它的m 级聚合过程是岩”k ，n e t ，其中 z = = 1 x i ( 2 1 3 ) m j ；4 看= 矗一” 掣m 是对原序列地分辨率的克隆。聊越大豇分辨率越低，搿1 的分辨率最高。 如果序列的统计特性不随聚合而改变，即那么就呈现了离散时间序列的自相似 性。一共有两种自相似过程，严格自相似过程与渐近自相似过程。 过程z 被称为是以芦( o f l 1 ) 为参数严格自相似的，如果对于肌矿，满 足以下条件 ，【 = v a k 厂x ( 2 1 4 ) n ( k ，”) = r ( j ，x )( 2 1 5 ) 其中，p 与h u r s t 参数的关系是 = 2 0 一日)( 2 1 6 ) 对于渐近自相似过程，只要求当k 和m 很大，即较大聚合程度时，满足以上 两个前提条件即可。 对于各态历经的稳态过程，芦= l 并且方差随m 衰减到0 。而自相似过程衰减 的速度则慢得多，义”衰减速度慢于m 。另一方面，当m 趋向予一时，自相似 过程的归一化自相关函数并不随m 而衰减。 2 4 自相似过程的性质 自相似过程有许多不同于传统短相关过程的性质，例如长相关性、慢衰减方 圭堡奎望查堂堡主堂堡垒! l 差、重尾分布特性和1 f 噪声特性等。对这些特性的了解有助于网络流量中自相 似性的检验，并为研究自相似对网络的影响提供理论依据。 2 4 1 长相关性 长相关性( l o n gr a n g ed e p e n d e n c e ，简称l r d ) 反映了自相似过程的持续性 现象，一般用过程的自相关函数来定义。如果给定乃，过程z 自相关函数不可累 加，即 c o y ( & ，以+ ) = 。 ( 2 1 7 ) 那么过程x 被称为具有长相关性。 这种定义不很直观，无法提供更多实用的信息。另一种定义来自于对自相关 函数尾部行为的描述：如果过程自相关函数以双曲线速度衰减，即 c o v ( x ，以+ ) 一 4 ，当寸时 ( 2 1 8 ) 其中，o f l l ，那么过程彳被称为具有长相关性。 与长相关性相对的概念是短相关性( s h o r tr a n g ed e p e n d e n c e ，简称s r d ) 。与 长相关性的两种定义相对应，具有短相关性的过程满足可累加性，即 c o v ( x ，以+ ) 。 k = 0 和自相关函数以指数速度衰减，即 c o v ( x , ，以+ ) a l l , ( o d o ，k o ) ，当x 时( 2 2 4 ) 分布函数是 即h 一时尚埘 工 其中，k 表示随机变量最小可能的取值。 尽管重尾分布特性不是自相似过程的必要条件，许多流量的自相似特性直接 起源于重尾分布特性。 2 4 41 ，f 噪声 自相似过程在频域上呈现1 f 噪声特性，即自相似过程的功率谱密度在频域 原点附近呈现幂律行为特性 高，( o y l 消l 叫训时 土壅奎望查兰堡圭兰些丝兰一 其中，y 与1 3 的关系是 y = 1 一p ；2 4 1 由上式可以看到，自相似过程在低频率附近发散。与此相对，短相关过程时， h = 0 5 ，y = o ，因此，在频域原点附近它是有限值，呈现平坦的特性曲线。用时 域来解释，就是短相关过程比长相关过程或自相似过程的自相关函数衰减速度要 快的多，从而使自相关函数的和为有限值。 2 4 5 小结 长相关性与慢衰减方差是与时间相关统计参数的尺度性质，这些统计参数有 自相关函数等。重尾分布性质则描述了自相似过程蜀的边缘分布特性，这种墨 在网络流量中，可以是分组的到达序列或是o n o f f 序列。l f 噪声则指出了自 相关过程在频域上的特性。以下是传统网络研究中所使用的短相关过程与新发现 的自相似过程之间的比较： 表2 - 1 自相似过程与短相关过程的比较 短相关过程自相似过程 v a r x “) t n 一v a r x ”l 】m 一9 c o v ( x 。，以+ 。) 。c o y ( x , ，以+ 1 ) = 。o k - o 功率谱密度在原点收敛功率谱密度在原点发散 2 5 检验自相似性存在的方法 如上所述，表征自相似程度的参数是h u r s t 参数t 它的取值范围是【o 5 ，1 o 】。 日值越大，自相似的程度越高。但是，要准确估计h u r s t 参数并非易搴。尤其在 现实工作中，只能够通过对有限时间内获得的数据的分析来估计h u r s t 参数。以 下是现有的对时间序列自相似性检测的手段。 9 圭壅奎垄查兰堡主兰焦堡塞 2 5 1r ，s 分析法 r s 分析法，又名变尺度范围分析( r c s c a l e dr a n g ea n a l y s i s ) ，由水文学家h u r s t 发明。其基本原理是：设样本序列为烀 焉，n 矿) ，则其r s 随机量的定义为 墨盟：里蜓! ：生：垒j 二婴璺! ! ：垒! ! ：! 垒2f 2 2 7 1 s 0 )s ( n ) 、 其中，a 。= x ，一k 牙，贾是样本平均值，酽( n ) 是样本方差，r ( h ) 是范围。 研究发现许多自然现象满足 e l 型生l 册一，当。_ 。时( 2 _ 2 8 ) l s ( n ) j 、 。 其中，c 是与”无关的正常数。如果把上式画在双对数坐标图上，则可以得到 根斜率为日的直线。r s 分析法不是一个精确估计法，一般只能够用来检验时间 序列是否有自相似性，并能粗略估计h 的大小。 2 5 2 方差一时间分析法 方差时间分析法( v a r i a n c e t i m ea n a l y s i s ) ，利用了自相似过程的慢衰减方差 特性。聚合的自相似过程的方差对于大m 满足 附i x ( m 】- r a d r x ( 2 2 9 ) 其中h = 1 一譬。 如果把上式画在双对数坐标图上，则可以得到一根斜率为b 的直线。如果 一l 。b o ，那么可以判断时间序列有自相似性。方差时间分析法也是一个粗略 的估计方法，只能够用来检验时间序列是否有自相似性，并粗略估计日的大小。 2 5 3 周期图法 周期图，又名强度函数定义为随机过程趣f ) 的在频率密度，即 = 击静e 加1 2 s 。， 1 0 占壅奎望查堂堡主堂垡丝生一 其中，w 是频率，忍是时间序列，是时间序列的长度。 一般，自相似过程的强度函数满足 “( w ) ”，当w - - * 0 4 ( 2 3 1 ) 如果把上式画在双对数坐标图上，则可以得到一根斜率为l 一2 日的直线( 在低频 率范围内) 。实际中般使用频率中的低1 0 部分。 周期图法( p e r i o d o g r a mm e t h o d ) 比以上两种方法要好，但是其计算量太大。 2 5 4w h i t t l e 法 w h i t t l e 法也是基于周期图，但是它不使用画图的方法。假设对自相似过程， 其频率密度s ( w ，奶已知，那么h u r s t 参数是使得w h i t t l e 表达式取得最小值的h 值，w h i t t l e 表达式的定义是 e 揣批 偿s z ， 通过最大似然估计( m a x i m u ml i k e l i h o o de s t i m a t i o n ，简称m l e ) 可以获得 带致信区间日，因此这种方法可以获得更好的统计性能。但是，它必须事先假定 一个频率密度模型，如果这个模型不正确，则会导致偏差，因此这个模型的健壮 性不好。此外，该模型的计算量非常大。 2 5 5 小波法 小波法与方差时间分析法有联系，它可以对时间信号同时在时域和频域进行 分析。小波法使用了离散小波变换，从而具备了基于聚合分析法和基于最大似然 估计分析法的优点，丽没有两者的缺点。小波自相似分析法利用了多分辨率分析 ( m u l t i r e s o l u t i o n a n a l y s i s ，简称m r a ) 。 小波法的核心公式为 b g ：陆弘u 刮2 ) ：( 2 川m a 亿， 其中， n ：= 2 - j ” 圭壁奎堕盔堂堕主兰垡堡苎； 一 为待分析流量数据的长度。 2 6 自相似网络流量的分析方法 正是网络流量的自相似性与经典分析模型的短相关性假设相矛盾，引起了人 们对传统网络理论的反思和创新。由于是在网络流量的自相似性被发现之后出现 的，新的流量分析模型都在不同程度上，试图对网络的特性进行比较完整的考虑。 例如分形布朗运动模型在数学上给出一个完美的模型：高可变o n o f f 源叠加模 型则是对传统模型的修正和扩展；而其他有利于进行长相关性分析的其他理论也 被引入流量分析。 2 6 1 分形布朗运动 分形布朗运动( i b m ) 是被使用最广的长相关网络流量模型。分形布朗运动 是种高斯自相似过程，其h u r s t 参数在 o 5 ，1 ) 范围里。分形布朗运动z f 可以通 过积分由布朗运动口( 订导出 z f = f ( f - - u ) “”d s ( u ) ( 2 3 4 ) 从上式可以看出，分形布朗运动增量之间的相关性可以说是无限。分形布朗运动 的增量过程称为分形高斯噪声( f g n ) ，在离散情况下，它的相关函数满足 展= 专f ( 女+ 1 ) ”一2 k 2 “+ ( | 】 一1 ) 2 ” k 2 “2 ( 2 3 5 ) 也就是说，分形高斯噪声是长相关性的。 n o r r o s 在 1 2 q h 。讨论了用分形布朗运动来对网络流量进行建模。设五是f b m 过程，令a ，表示在时间( o ，t ) 中分组到达的个数，那么 4 = m t + 4 m a z ,( 2 3 6 ) 其中，m 是网络流量平均速率，a 是网络流量方差。 分形布朗运动模型只需要平均速率m 、方差a 和h u r s t 参数三个参数就可以 完整的刻画整个模型。它在数学上有坚实的理论基础比较好处理，这是它受到广 泛研究的原因之一。另一方面应当指出，使用分形布朗运动分析网络流量有以下 不足：分形布朗运动是严格自相似的过程，可以用来对长相关数据进行建模，但 是对于有长相关特性但同时又带有与严格自相似不一致的短相关尺度特性的信 2 ! ：堑銮望查兰堕! 兰生笙苎 号不能准确建模：分形布朗运动带有高斯性，对于非负的信号，也就是非高斯性 的信号，它不能很好的分析。所以，分形布朗运动模型不能比较完整的描述实际 情况。 2 6 2 高可变o n o f f 源叠加模型 o n o f f 源叠加模型在传统分析中被大量使用，其基本思想是每个数据源一 直在o n 和o f f 两种状态之间交替变化，当某个时隙内有一个分组时数据源处 于o n 状态，当没有分组传输时则处于o f f 状态。但是传统分析用指数或是几 何分布描述源的o n 和o f f 的持续时间，导致所得到的排队分析与实际不符。 高可变o n o f f 源叠加模型不同于传统模型，它通过用无限方差模型描述数据源 的o n 和o f f 的持续时间，使得持续时间具有分形理论中的n o a h 效应。许多个 这样的数据源叠加在一起产生的聚合网络流量被发现呈现长相关性，即分形理论 中的j o s e p h 效应。 这个模型的优点是把复杂的聚合流量特征分析简化到每个信号源的分析。传 统的o n o f f 源叠加模型在持续时间满足指数分布的情况下，数学上处理比较方 便，从而得到比较广泛的应用。经过扩展后的高可变o n o f f 源叠加模型，在重 尾分布的数据源的前提下。数学上处理则有许多困难。但是应当指出，由于通过 刻画数据源得到长相关的聚合流量，高可变o n o f f 源叠加模型在网络仿真、流 量合成等方面有相当应用。 2 6 3 分形自动回归积分移动平均模型 分形自动回归积分移动平均模型f a 刚m a 印，d ，g ) 是自动回归积分移动平均 模型h r t m a ( p ，zg ) 的扩展。当参数p = 0 ，q = o ，0 b e t a 流的k u r t o s i s 指数。a l p h a 流和b e t a 流分离的标准是：a l p h a 流的k u r t o s i s 指数应该远大于3 ；b e t a 流的k u r t o s i s 指数应该在3 附近，而它的 s k e w 指数应该在0 附近。 按照这个标准我们首先否定了硬门限和随尺度变化的自噪声模型在一起的 4 种组合。在这4 种组合下，分离出的b e t a 流的k u r t o s i s 指数甚至大于原网络流 量，因此这4 种组合不适合我们的需要。 为了方便进一步的筛选出小波去噪的最佳组合，在图3 8 中画出了所有分离 出的b e t a 流大小的分布柱状图。 占堂奎望查兰塑主茎焦丝兰一 h a r d “廿c ，o l d i n s u a s c a l e dv h i t en o l f e s o f tz l 廿e j h o l d i n s h a r dt e # 0 1 d i n f tt 口e o l d i 毽 # c 4 l e dv h i t n o l h a r dt h v e s o l d i n g x 1 矿 ( a ) 严格s u r e 法 ( a ) r i g o r o u ss u r em e t h o d j o l tt i l r e l h o l d i n s h a r dt h f e s o l d l 叫 s o f tt h r e m h o l m q ( b ) 定值法 ( b ) f i x e df o r mm e t h o d ( d ) 最小最大法 ( d ) m i n i m u mm a x i m u mm e t h o d 图3 - 8 对a u c k l a n d 第1 小时网络流量1 6 种组合的小波去噪技术得到的b e t a 流的柱状图 f i g3 - 8h i s t o g r a m so f b e t at r a f f i ci s o l a t e dt h r o u g h1 6w a v e l e td e - n o i s em e t h o d s f r o mt h ef i r s th o u ra u c k l a n dn e t w o r kt r a c e 从表3 - 3 和图3 - 8 显示的结果来看，最好的组合为： ( 1 ) 定值法+ 不随尺度变化的白噪声+ 硬门限； ( 2 1 最小最大法十不随尺度变化的白噪声十硬门限。 为了进一步检验这些组合的性能，我们把a u c k l a n d 网络流量2 4 小时的记录， 以小时为单位划分成2 4 个样本，分别进行t a i l 试。测试发现以下结论： ( 1 ) 无论哪种组合，使用软门限分离出的b e t a 流都为欠高斯分布，其k t t n o s i s 指数在2 6 附近； ( 2 ) 硬门限和随尺度变化的白噪声模型如前结果相同，总产生k u r t o s i s 指数 大于1 0 0 0 的b e t a 流。 ( 3 ) 三种噪声模型中，由( 1 ) ( 2 ) 可知随尺度变化的白噪声模型不可行，非高斯 噪声模型不符合我们对b e t a 流分形高斯分布的假设，只有不随尺度变化 的白噪声模型适合我们分析的要求： ( 4 ) 剩下4 种组合都包含硬f - j 限+ 不随尺度变化的白噪声模型。在表3 - 4 中， 列出了这4 种组合分离出的b e t a 流的统计特性。其中定值法因为分离出 的b e t a 流的k u r t o s i s 指数绝大多数大于3 5 而被否定。严格s u r e 法和 渐近s u r e 法，虽然在第1 小时的样本中表现不佳，但是综合性能很好， 尤其是s k e w 指数，几乎都在0 0 2 以内。相比较而言，最小最大法不如 两种s u r e 法，但是仍可作为一种选择。 表3 - 4 四种门限确定法+ 硬门限+ 不随尺度变化的白噪声模型 所得2 4 个b e t a 流的统计特性 t a b l e3 - 4s t a t i s t i c so f 2 4p i e c e so f b e t at r a f f i cc r e a t e d b y4t h r e s h o l dd e t e r m i n a t i o nm e t h o d s + h a r dt h r e s h o l d i n g + u n s e a l e dw 1 l i t cn o i s em o d e l k u r t o s i s 指数s k e w 指数 平均值方差平均值方差 严格s u r e 法 3 1 l0 2 l0 0 20 0 2 最小最大法 3 2 30 1 70 3 1o 1 l 渐近s u r e 法3 1 s0 2 2o 0 2o 0 2 定值法3 8 7 0 3 7 0 5 50 1 8 最后的3 种小波去噪组合仍然不一定是合理的。因为我们的衡量标准只是必 要条件。而不是充分条件。在图3 - 9 中，画出了这三种组合生成的b e t a 流的分 圭壅奎垄查堂堡主兰些堕一一 布柱状图、自相关函数和频谱特性。可以看到，严格s u r e 法和浙近s u r e 法 生成的b c t a 流的自相关函数在原点附近有明显的负数方向的冲击，对应的频谱 特性不是白噪声。而最小最大法的自相关函数近似为标准的冲击相应，频谱特性 也接近白噪声。 ( a ) 严格s u r e 法 ( a ) r i g o r o u ss u r em e t h o d ( ”渐近s u r e 法 f o ) h e u r i s t i cs u r em e t h o d ( c ) 最小最大法 ( c ) m i n i m a x im e t h o d 图3 9 三种小波去噪组合的分布柱状图、自相关函数和频谱特性 f i g3 - 9h i s t o g r a m s ，a u t o c o r r e l a t i o n s ，a n df f rr e s u l t so f 3c o m b i n a t i o n s 经历了层层筛选后，我们找到了最佳的小波去噪组合，即表3 - 5 。 表3 - 5 最佳小波去噪组合 t a b l e3 - 5t h eb e s tw a v e l e td e - n o i s ec o m b i n a t i o n 小波变换 h a a r ( 前提) 小波变换级数 5 ( 前提) 门限确定策略最小最大法 门限应用方法硬门醺 噪声模型不随尺度变化的白噪声 3 6 本章小结 大量的自相似流量分析都是把网络流量聚合后进行分析，而很少从更精细的 角度去分析。聚合的网络流量实际是由许多个网络连接的流量叠加所得，本章提 出从网络连接的层面，对网络流量进行分析。 通过在网络连接层面上的分析，我们发现：网络流量的突发性只与少数高速 网络连接有关。这与在o n o f f 模型中聚合的网络流量的突发性来自于大量网络 连接共同作用所致的假设不符。 进而我们提出网络流量可以分解成两部分：a l p h a 流和b e t a 流。前者造成了 网络流量的突发性；后者的传输速度分布符合现有自相似网络流量的模型。由此 对现有网络流量的自相似理论进行延伸，不仅充分利用已有的大量研究成果，而 且可以使网络流量模型更贴近实际。 随后，本章讨论了从网络流量中分离出a l p h a 流和b e t a 流的技术。最大值 分离法的处理速度快但是效果不好，高斯分离法分离效果好但是处理速度慢。因 此，我们引入小波分析，利用小波去噪的理论来分离出a l p h a 流和b e t a 流。通 过详细的比较和试验，我们找到了最佳的小波去噪参数组合。相比较前两种方法， 因为我们选择自噪声作为小波去噪的噪声模型，这种方法具备很好的理论基础， 实际效果很好：其计算量主要与小波变换的复杂度有关，因为只使用离散小波变 换来实现，所以处理速度很快。 从网络流量中分离出来的b e t a 流呈现高斯分布，a l p h a 流呈现明显的超高斯 分布，即有明显的突发性；b e t a 流占据了网络流量中的绝大部分，而a l p h a 流只 占- - 4 , 部分。在第四章中，我们将继续讨论这两种流对网络的影响。 第四章网络流量自相似性对排队的影响 排队分析是网络设计和控制领域的基础，其作用非常重要。当网络流量的自 相似性参数h u r s t 参数大于o 5 时，排队性能会随着h u r s t 参数的增大而恶化。 排队分析直接影响：网络中许多关键设备的设计，例如路由器和交换机中的缓冲 设计；网络中许多策略的确定，例如呼叫接入控制( c a l la d m i s s i o nc o n t r o l ，简 称c a c ) 。 4 1 传统排队分析 传统的排队分析研究中，主要研究输入过程模型是p o i s s o n 过程、服务时间 是负指数分布的排队系统。在这种排