（计算机应用技术专业论文）自相似业务网络仿真与性能评价研究.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 网络业务自相似性的发现对网络业务建模、性能评价和网络控制技术的研 究产生了重要影响。传统的网络模型在描述实际网络业务时，认为网络通信量 具有m a r k o v 性，并在此基础上建立了以p o i s s o n 过程为主的数学描述模型，这种 模型具有短程相关结构。大量实际测量发现网络通信量具有普遍的自相似性 ( 或长程相关性) 。长程相关性在多个时间尺度上存在，并且在大时间尺度上对 网络时延、抖动、丢包率以及吞吐量等网络性能具有重大的影响。传统的网络 业务模型忽略了自相似的重要特性，不能真实地刻画实际的网络业务。 本文深入研究自相似业务网络仿真和性能评价问题论文首先介绍自相似 的常见定义，描述自相似过程在数学和物理上的若干特征：研究网络自相似业 务的建模与流量数据生成方法，并对这些业务模型的性能进行了分析；通过仿 真实验研究了自相似特性对网络性能的影响。 论文在归纳总结自相似基本概念的基础上，研究了常见自相似业务模型如 o n o f f 、f g n 、f b m 、f a r i m a 等的实现过程，并分析了基于这些模型所产 生的自相似流量序列的准确性。研究结果表明o n o f f 模型生成的序列接近期 望值，但序列的h u r s t 系数是不稳定的，随序列长度改变而改变。相比其它模 型，f g n 模型产生的业务序列比较稳定和准确。f a r i m a 模型具有长短交织 的相关函数结构，与实际中的大部分流量的分形相关函数结构吻合，是目前为 止较为理想的一种算法。 论文接着对网络性能评价的相关模型、指标进行了讨论，重点分析了f b m 、 f a r i m a 模型的排队性能。然后对本论文使用的仿真模型和实验数据来源进行 了讨论，通过仿真实验对自相似网络排队性能进行了分析总结。 在网络性能分析中排队性能是一个重要的指标。本文采用自相似业务模型 产生的不同数据来驱动o p n e t 的6 m 1 模型进行仿真，讨论了影响排队时延、 队长和包丢失概率的因素。研究结果表明发包间隔时间的分布特征决定了排队 性能，0 n o l 下模型的排队性能与o n o f f 的p a r c t o 分布有直接关系，自相似序 列比短相关序列有更大的排队时延和丢包率，而且变化也更剧烈。方差对排队 性能指标有重要影响。 关键词：网络流量；自相似；长相关；业务建模：性能评价 西南交通大学硕士研究生学位论文第n 页 a b s t r a c t t h ed i s c o v e r yo ft h es e l f - s i r e i l a rc 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 ch a sg r e a t i n f l u e n c eo nn e t w o at r a f f i cm o d e l i n g , p e r f o r m a n c ee v a l u a t i o na n dn e t w o r kc o n t r 0 1 t r a d i t i o n a lp o i s s o n - b a s e dm o d e l so fn e t w o r kt r a f f i ca r eb a s e do nt h eh y p o t h e s i so f m a r k o vw h i c hh a st h en a t u r eo fs h o r t r a n g ed e p e n d e n c e ( s r d ) r e c e n tt r a f f i c 7 a n a l y s i sf r o mv a r i o u sp a c k e tn e t w o r k ss h o w st h a tn e t w o r kt r a f f i cp r o c e s s e se x h i b i t u b i q u i t o u sp r o p e r t i e so fs e l f - s i m i l a r i t ya n dl o n gr a n g ed e p e n d e n c e ( u t d i e o f c o r r e l a t i o no v e raw i d er a n g eo ft i m es c a l e s l r de x i s t so nm u l t i p l et i m es c a l e sa n d h a s g r e a ti n f l u e n c e so bn e t w o r kp e r f o r m a n c e ss u c h a sd e l a y , j i t t e r , c e l lt o s sr a t ea n d t h r o u g h p u to n t h el a r g et i m es c a l e n et r a d i t i o n a lp o i s s o n b a s e dm o d e l sn e g l e c tt h e i m p o r t a n t c h a r a c t e r i s t i co fs e l f - s i m i l a r i y t h e yc a nn o tc a p t u r et h e a c t u a l 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 c c u r a t e l y i nt h i st h e s i s ，t h ea u t h o rs t u d i e st h ep r o b l e m so fn e t w o r ks i m u l a t i o na n d p e r f o r m a n c e e v a l u a t i o no fs e l f - s i m i l a rt r a f f i cw i t h d e p t h f i r s t l y , s e v e r a l m a t h e m a t i c a ld e f i n i t i o n so fs e l f - s i m i l a r i t ya r eg i v e n s o m em a t h e m a t i c a la n d p h y s i c a lf e a t u r e sd e s c r i b i n gt h es e l f - s i m i l a rp r o c e s s e sa r ed e s c r i b e d 田l cm e t h o d s o fm o d e l i n ga n dg e n e r a t i o no ft h es e l f - s i m i l a rt r a f f i ca r er e s e a r c h e da n dd i s c u s s e d t h ep e r f o r m a n c eo ft h e s cm o d e l si s a n a l y z e d t h e i n f l i l c n c eo fn e t w o r k p e r f o r m a n c eo ns e l f - s i m i l a r i yi ss t u d i e dt h r o u g hs i m u l a t i o n b a s e do nt h ec o n c l u s i o no ft h ec o n c e p t so fs e l f - s i m i l a r i t y , t h ei m p l e m e n t a t i o n o ft h es e l f - s i m i l a rm o d e l s , s u c ha so n o f f , f r a c t i o n a lg a u s s i a nn o i s e g n ) ， f r a c t i o n a lb r o w n i a nm o t i o n m ) ，f r a c t i o n a la u t o - r e g r e s s i v ei n t e g r a t e dm o v i n g a v e r a g e ( f a r l m a ) , a r ei n t r o d u c e d n ep r e c i s i o no fs e l f - s i m i l a r i t yt r a f f i cs e r i e s g e n e r a t e db yt h e s em o d e l si sa n a l y z e d t h cr e l u l t sr e v e a lt h a ta l t h o u g ht h eh u r s t c o e f f i c i e n to ft r a f f i cs e r i e sg e n e r a t e db yo n o f fm o d e li sc l o s et ot h ee x p e c t e d v a l u e i t sh u r s tc o c f f i c i e n td o e sn o tr e m a i ns t a b l ea n dc h a n g e sa c c o r d i n gt ot h e l e n g t ho ft h es e r i e s c o m p a r e dt oo t h e rm o d e l s f g nm o d e li sm o r ep r e c i s ea n d s t a b l e f a r i m am o d e li sc o n s i s t i n gw i t hb o t hl o n ga n ds h o r tr a n g ed e p e n d e n t s t r u c t u r ea n ds u i tt ot h ea c t u a lf r a c t i o n a ls t r u c t u r e s oi ti sm u c hb e t t e rt h 姐o t h e r m o d e l s s e c o n d l y r e l a t i v em o d e l s ，p a r a m e t e r sa n di n d e x e so fn e t w o r kp e r f o r m a n c e 西南交通大学硕士研究生学位论文第m 页 e v a l u a t i o na t ea n a l y z e d t h ca u t h o rf o c u s e so nt h eq u e u i n gl x f f o r m a n c eo ff b m a n de 蛾眦1 1 埒s i m u l a t i o nm o d e la n dt h es o u r c eo fs i m u l a t i o na l ed i s c u s s e d 西# p e r f o r m a n c eo fs e l f - s i m i l a l t r a f l ci sa n a l y z e da n ds u m m e du pt h r o u g h e x t e n s i v es i m u l a t i o n q u e u i n gp e r f o r m a n c ei sak e yi n d e xo f n e t w o r kp e r f o r m a n c e sa n a l y s i s i nt h i s t h e s i s b a s e do nt h eo p n e ts i m u l a t i o nw h i c hi sd r i v e nb yt h et r a c e sg e n e r a t e dw i t h s e l f - s i m i l a rt r a f f i cm o d e ld e s c r i b e da b o v e ，t h ep e r f o r m a n c e sa n di t si n f l u e n c e f a c t o r so fg m 1q u e u i n gm o d e la r ea n a l y z e d t h ea u t h o rf o c u s e s0 1 1t h es t u d yo f i n f l u e n c ef a c t o r so nn e t w o r kp e r f o r m a n c e s s u c ha sq u e u i n g d e l a y , q u e u el e n g t ha n d c e l ll o s sr a t e 1 1 地r e s e a r c hr c s u l t sd e m o n s t r a t et h a tt h eq u e u i n gp e r f o r m a n c ei s d e t e r m i n e db yt h ed i s t r i b u t i o no fp a c k e ti n t e r v a lt i m e t h cq u e u i n gp e r f o r m a n c eo f o n o f ft r a f f i cm o d e li sr e l a t e dt op a r e t od i s t r i b u t i o no fo no r0 f fp e r i o d s e l f - s i m i l a rt r a f 蕾cr e s u l t si nm u c hw o r s eq u e u i n gp e r f o r m a n c et h a ns h o r tr a n g e d e p e n d e n c et r a f f i c , a n dt h ev a r i a t i o no ft h ep e r f o r m a n c eo fs e l f s i m i l a lt r a f f i ci s m o r ev i o l e n t v a r i a n c eo ft h es e l f - s i m i l a rt r a f f i ch a sag r e a ta f f e c to nt h eq u e u i n g p e r f o r m a n c e 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 i t y , l o n g - r a n g ed e p e n d e n c e ，t r a f f i c m o d e l i n g , p e r f o r m a c e e v a l u a t i o n 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景 第1 章绪论 自相似的概念来源于分形( f r a c t a l ) ，首先应用于自然现象的描述。自相 似性是分形的重要特征。法国数学家b e n o i tb m a n d e l b r o t 于七十年代中期提出 了自相似与分形的概念【1 1 ，并创立了分形理论，该理论总结了自然现象中不规 则形态的自相似规律，进而用来解释复杂现象的几何特性和复杂性。 分形描述了自然界中很广泛一类物质的基本特性，包括了局部与局部、局 部与整体在形态、功能、信息、时间与空间等方面具有某种意义上的自相似性， 自然界存在的许多结构都具有这种潜在的几何规律性，也称之为标度不变性 ( s c a l ei n v a r i a n c e ) ( 2 1 。 网络自相似的研究始于二十世纪末当时d v w i l s o n 等开始使用一种精密 的网络监测设备，对b e l l c o r e m o r r i s l v d 中心的若干个以太网中的业务流进行 了深入研究【3 悯，在1 9 8 9 年更将该设备的时间分辨率由1 0 0 u s 提高到2 0 u s ，并 在随后的三年中进行了更为系统的研究分析。对他们所得到的数百万个实际网 络传输的数据包的统计分析表明，l a n 业务的统计特性是基于泊松或贝努利过 程的传统业务流模型所无法描述的，突出表现为突发没有明确的长度，在不同 的时间尺度下表现出相同的突发特性，即业务是长相关的( l o n gr a n g e d e p e n d e n c e ，l r d ) ，不能将它平滑掉。然而传统模型一般是基于泊松( 连续 时间) 或贝努利( 离散时间) 过程的，这些模型只能处理短相关( s h o r t r a n g e d e p e n d e n c e ，s r d ) 业务。实际网络业务普遍存在统计上的自相似性，该特性 与业务发生的时间、地点或编码方式无关。 在这个发现的带动下，各国研究人员对其他网络业务进行了澳0 量和分析， 均发现了网络业务具有自相似性。主要的测量研究活动有： r 1 ) p a x s o n 等l 6 1 采集了大量有关广域网w a n 业务的数据，其中包括许多 t c t 到达过程，并对这些数据进行了详尽的分析。 ( 2 ) k l i v a n s k y 等人( 7 1 对分布于全美的多个n s f n e t 中的核心交换机进行了 采样，并在p a c k e t 级上分析了n s 旷域网的业务特性。 西南交通大学硕士研究生学位论文第2 页 ( 3 ) 贝尔实验室对使用信令系统7 号协议( 8 5 7 ) 的公用通道信令网络c c s n ( c o m m o nc h a n n e ls i g n a l i n gn e t w o r k ) 进行了观测，d r i l 叫8 】等对有关业务数 据进行了分析。 ( 4 ) a c k c r l e y 分析了从英国电信网b t ( b r i t i s ht e l e c o m ) 上采集的c c s n 业 务数据 ( 5 ) a d d i e 等 9 1 观测分析了澳大利亚高速数据网f a s t p a c ，该网可提供速 率为2 m b p s 至u 1 0 m b p s 的服务，联结了澳大利亚主要城市的d q d bm a n 。 ( 6 ) c r o v e l t a 纠1 q 1 1 1 观测分析t w w w 业务，这些业务反映了数以百万计的 文档请求。 渤h e y m 姐等人【2 】测量并分析t a t m 网络中传输视频会议业务表现出的 一些特性。 通过采用分形思想进行分析；他们发现实际网络业务序列的自相关函数随 时间间隔增大呈双曲函数衰减，不同于传统模型，实际网络业务具有长相关性。 这一发现揭示了现代网络业务的真实特性，标志着网络业务建模和性能分析进 入一个新阶段。 随着网络研究的深入与测量技术的发展，不断有研究人员对传统模型的有 效性提出质疑1 9 t 1 0 】。随着现代网络技术的飞速发展与网络应用范围的扩大，新 型网络业务的不断出现，使得网络业务的突发性和复杂性大大超过传统通信 网。为了合理描述网络业务的真实特性，必须提供新的、正确有效的模型。网 络业务的自相似性也给网络性能带来了意想不到的影响，因此针对自相似业务 的网络性能评价和网络仿真研究也需要进一步展开。 1 2 课题研究意义 传统模型一般是基于泊松( 连续时间) 或贝努利( 离散时间) 过程的。虽 然随着研究的深入逐渐引入了各种推广的p o i s s o n 过程和其它较为复杂的随机 模型，如马尔科夫调制p o i s s o n 过程( m a t k o v m o d u l a t e d p o i s s o n p r o c e s s ，m m p p ) 等等。这些模型的共同特点是所描述的流量序列具有短时相关性，即业务序列 的自相关函数随序列间隔增大呈指数衰减趋势。当时间标度增加时，统计上单 位时间内得到的数据包数将趋于白噪声，所以这些模型所表示的业务流在不同 的时间标度下具有不同的特性由于一般它们假设业务的到达模式具有马尔柯 西南交通大学硕士研究生学位论文第3 页 夫特性，使得相应的队列系统及网络性能评价易于数学解析 而最近的大量研究结果表明，现代网络业务的一个关键特性是分形或自相 似特性，即网络数据在绝大部分时间尺度范围内容具有统计相似性( 高度相关) 和重尾特性( 高变化或突发) 。它们不适合于用传统的网络业务模型，如 m a r k o v ，p o i s s o n 或g a u s s i a n 等来描述1 1 2 ，t 3 , 1 4 各种具有突发特性的业务源呈现出的自相似特征严重影响到网络的传输 性能和流量控制策略。自相似性对网络性能产生的这些意想不到的影响，例如 对时延、丢包率、吞吐量等网络性能指标的直接影响，使网络的设计、控制、 分析和管理变得复杂。通过基于自相似业务流量的网络性能评价，才能掌握在 自相似业务下网络所表现出来的特性，减少流量自相似所带来的不利影响，使 网络性能得到优化。而网络业务的排队性能分析，是网络性能评价中一个重要 的指标。因此，对自相似业务源的数学建模和排队分析已成为当前网络性能评 价和优化、流量控制和业务量管理中不可缺少的要素 流量建模影响到网络的性能分析、网络的设计、网络中的流量控制等，在 整个网络评价和优化过程中起着很重要的作用。对于网络业务模型的研究，还 必须考虑其精确性和易实现性，数学工具的选择非常重要。而自相似模型与往 常使用的马尔可夫模型不同，用于传统网络性能分析的马尔可夫数学解析模 型，技术手段都相对成熟，自相似模型的研究还处于起始阶段，对于流量的描 述刻画精确性和易实现性都还不是非常理想。因此对于自相似业务的数学建 模，更深入的研究是很有现实意义的。 另外，传统的网络性能分析往往采用p o i s s o n 模型或其它马尔科夫模型进 行数学解析，通过排队论的推导，得到其性能指标，建立相应的性能评价模型。 而自相似过程研究还缺少大量有效的数学方法和技术手段，围绕自相似性的数 学解析难度要大得多。自相似业务的作为突发业务的一种建模方法，对业务突 发特征的参数描述也远未能达成一致，难于进行排队解析，相关性能评价研究 显得比较困难，建立相应的网络评价数学模型也显得比较困难。而这正是我们 需要进行的研究 正是由于自相似数学解析方面的困难，使得仿真方法成为进行自相似业务 下的网络系统性能评价的重要手段。仿真可以为建模和性能评价过程中的两个 重要问题提供解决方法：首先是已经建立的模型的正确性和准确性的验证。自 相似业务建模的探索，需要仿真手段来进行验证。自相似业务模型是否能够正 西南交通大学硕士研究生学位论文第4 页 确、准确地描述业务的自相似性，其导致的网络性能的变化是否和现实网络的 特性相一致，需要通过网络仿真来验证通过仿真模拟现实的条件和环境，观 察网络性能的变化，可以对模型进行进一步的改进和完善。其次，通过仿真可 以观察和总结自相似业务下一些未知的网络新特性。基于数学模型的仿真参数 选取可能会导致性能的极大变化，而某些极限情况下的网络特性在现实和数学 模型中无法描述，例如缓冲区无限大网络业务本身也可能导致网络性能在某 个临界点发生突变，这些情况只能通过大量的仿真来观察和总结。因此，自相 似业务的网络仿真对于网络性能的评价研究具有非常重要的意义。 1 3 国内外研究现状 随着自相似业务的物理解释和对其产生原因的理解的深入，以及自相似性 和长相关性对网络性能影响的实例越来越多，业务的自相似性和长相关性已得 到了网络研究人员的广泛认同。 在自相似业务模型研究方面，现有的自相似流量生成方法主要有：基于分 形高斯噪音和分形布朗运动的流量生成方法【1 5 】；基于f a r i m a ( p ，d q ) 过程的流 量生成方法1 1 6 ；基于混沌映射的流量生成方法【1 7 1 ；直接叠加具有重尾特性的 o n o f f 业务源【1 s l ；利用m g 排队模型等。 在性能评价方面，大量研究表明基于m a r k o v 模型的网络性能评价技术在自 相似业务下是不适用的【1 恻。 e r r a m i l l ii z 2 1 等利用混沌映射对自相似业务进行了研究。这种构造方法可使 研究人员通过解析复合系统的非线性方程来获得有关队列系统的瞬态和稳态 性能，研究人员可通过选取业务源不同的o n , o f f 特性，得到相应的队列性能 评价。p r u t h i 利用此方法得到了以下结论：( 1 ) o n 周期具有轻尾分布、o f f 周期 具有重尾分布的单个业务源产生的队列长度分布的尾部呈指数衰减；( 2 ) o n 和o f f 周期都服从重尾分布的单个业务源产生的队列长度分布具有幂函数特 性；如o n 阶段周期方差无穷，则平均队列长度无界。( 3 ) f b m 到达过程产生 的队列长度分布服从扩展的指数分布或韦伯分布。 另一方面国内外研究人员采用大偏差理论和极值理论对网络系统的渐进 性质进行了广泛研究。 o e o r g a n a s 与n l i k h a n o v ，b t s y b a k o v 等人对输入过程为白相似过程的队 西南交通大学硕士研究生学位论文第5 页 列系统的缓冲区溢出等进行了研究，给出了溢出概率的上下界t 2 4 , z s i 。他们的研 究结果表明，随着缓冲区的增加，溢出概率并非按负指数方式迅速下降，而是 下降的很慢 目前仍未找到对所有自相似业务到达过程都有效的数学描述，能用于分析 自相似业务下队列统计性质的解析工具还很少，因而有关队列分析的研究就显 得更为困难针对某一具体业务模型进行的队列性能的数学解析也并不是很 多。 由于数学解析方面的困难，通过快速生成具有自相似特性的业务源进行排 队仿真分析研究，是目前一种有效的研究方法。但目前的仿真研究一般情况下 都是基于两种方式：一是通过叠加o n o f f 数据源做为自相似业务源来进行仿 真分析，o n o f f 数据源可以自己编写程序产生或者借助予仿真工具自带的 o n o f f 源( 如o p n e t 的r p g 模型) 叠加这种方式的缺陷是只能仿真o n o f f 源模型输入的自相似网络性能，且参数不易确定，叠加数目巨大，不利于与数 学解析模型相结合另一种方式是基于排队论的数学解析，直接将业务模型产 生的流量按照所得排队性能评价数学模型进行仿真，通常通过m a t i a b 实现。 这种方式的缺陷是完全基于数学解析，所用模型的正确性和准确性还有待验 证，容易导致结论有失偏颇，同时也忽略了现实网络的某些影响，简化和理想 化了现实的网络行为。 从整体上讲，网络性能自相似性的研究活动已走出了初期以业务的测量分 析为主的阶段，转向了以自相似业务下的网络性能评价与工程应用研究为主。 但目前的研究工作还存在着一些问题和困难。在研究方法和手段上，自相似业 务的研究还缺少大量有效的数学方法和技术手段。与传统模型下的同类问题相 比，围绕自相似性的数学解析难度要大得多。正因如此，数学解析手段的加强 和自相似业务的网络仿真才更显得尤为重要。 综上可知，目前针对某一具体业务模型进行的队列性能的数学解析并不充 分，而用于自相似业务仿真的模型具有局限性，不能通用于各种业务流量模型 产生的流量，使网络性能的仿真受到一定制约。本文将就f b m 模型及f a r i m a 模型的队列性能进行分析讨论，提供一种在o p n e t 下实现的模型，可以输入不 同自相似业务模型产生的流量数据，对其进行队列性能的仿真研究。 西南交通大学硕士研究生学位论文第6 页 1 4 本人的研究工作及论文内容安排 围绕上述自相似性能研究领域的工作，我们课题研究小组在导师的带领下 对自相似性能进行了一些研究。由于自相似业务研究目前还缺乏一套完整有效 的研究方法和体系，研究人员必须从网络技术和工程实际的角度出发，在现有 的数学理论和工具中，选择适用于自相似业务研究的方法，建立一个包括业务 流量的建模分析、性能评价以及网络应用研究的体系。导师研究课题中主要研 究工作就是围绕着这个问题进行的，本论文是导师研究课题中的一部分。 论文在比较了几个不同的数学模型的基础上，引入了具有长相关特性的时 间序列分析方法，对自相似业务的建模分析、性能评价进行了较为系统的研究。 所做的工作主要有：自相似流量数据的产生，自相似业务识别与参数估计，自 相似业务建模，自相似业务下的网络性能仿真，自相似业务下的网络性能评价。 论文的组织结构如下： 第1 章绪论介绍了课题背景、国内外研究情况、研究意义及本论文的主要 研究内容 第2 章对自相似过程的定义和性质进行了描述，简要概括了自相似对网络 性能的影响。 第3 章介绍自相似业务的建模方法，重点阐述了统计模型尤其是f b m f g n 和f a r i m a 模型的原理和生成方法，并对生成算法进行了讨论。 第4 章简述了网络性能评价的方法、指标，简单讨论了短相关业务的网络 性能，对f b m 、f a r i m a 两种自相似业务的性能评价模型进行了重点讨论。 第5 章提出了自相似网络性能分析的实验方法和模型，对实验结果进行了 统计分析，验证和总结自相似特性对网络性能的影响。 结束语部分对本论文的主要工作进行总结，给出论文的不足，并提出该课 题进一步研究的个人见解。 西南交通大学硕士研究生学位论文第7 页 第2 章网络业务自相似特性 自相似随机过程理论是研究自相似业务的重要理论基础。本章将主要介绍 自相似的定义、特性与相关概念。对于网络自相似业务的产生原因，目前的解 释也都与重尾分布有关，可见重尾分布与自相似业务的有着紧密的联系。同时 本章也将简要分析自相似业务对网络性能产生的影响 2 1 自相似现象 m a n d e l b r o t 在研究海岸线等曲线时发现这类奇怪的曲线具有结构上的自 相似性，即取出该图形的任何一个部分，放大到原来的尺度后，得到的图形与 原图形有惊人的相似度。例如对于同一海岸线而言，在高空拍摄的1 0 0 公里长 的海岸线和在低空拍摄的其中1 0 公里的海岸线，这两张照片虽然两者视野不 同，其形状大体是相似的，而且用不同的步长单位去测量这类曲线的长短，结 果也不同。也就是说，在高空所看到的大范围海岸线的复杂性，在低空小范围 内仍然可以发现，这表明海岸线具有自相似性。 警等譬 圈2 - 1 自相似图形图2 2 分形方法生成的树 m a n d e l b r o t 对分形给出了一个定义 1 1 ：其组成部分以某种方式与整体相似 的形态叫做分形。即如果把一个分形物体分裂开来，无论怎样分裂，它的各个 小部分，看起来总与原来的整体相似。 自相似现象的直观表现如图2 1 和2 2 所示，分形描述了自然界中很广泛一 类物质的基本特性，包括了局部与局部、局部与整体在形态、功能、信息、时 间与空间等方面具有某种意义上的自相似性，自然界存在的许多结构都具有这 西南交通大学硕士研究生学位论文第8 页 图2 - 3 实际网络业务与传统模型产生业务的对比 种潜在的几何规律性，也称之为标度不变性( s c a l ei n v a r i a n c e ) 2 1 。在现实世界 中，大量存在的是统计自相似、渐进自相似和随机自相似，它们的特点是自相 似性在一定的标度范围内存在。 从1 9 8 9 年到1 9 9 3 年，经过3 年多的时间，d v w i l s o n 等采集b c l l c o r e m o r r i s r d 中心的以太网中的业务流的数百万个数据包。他们使用高精密的网 络监测设备，设备的时间分辨率由1 0 0 u s 提高到2 0 u s 。通过对大量实际业务数 据的分析，他们发现网络业务所表现的统计自相似性完全不同于传统的业务模 型，如图2 3 所示。图中左侧为实际网络流量，右侧是泊松分布产生的流量。， 网络业务中的自相似主要表现为突发存在于多个时间尺度上，而且具有相同的 统计特征，这与突发可以经统计平均而加以平滑的传统理论是互相矛盾的。 西南交通大学硕士研究生学位论文第9 页 2 2 自相似过程的定义 自相似随机过程指的是一类空间或时间尺度的改变并不会影响其统计特 性的随机过程，其定义如下： 定义2 1( 自相似随机过程的连续时间定义) 【冽：一个连续随机过程 z ( f ) ，f r 如果满足如下条件：对于任何d 1 ，6 , t 2 ，r 和口 o ，有 如下等式成立：僻0 f 1 ) ，x ( a t ：) ，z 0 ) ) - ( 4 8 z ( f 1 ) ，4 ”x ( t ：) ，口”x 也) ) 即对所 有的口，o ， x ( f ) ，t e r ) 的有限维分布与 a 睁x c t ) ，f r 】的有限维分布的统计 特性相同，那么就可以称x 是具有自相似指数日的自相似过程。 参数涨称为h u r s t 参数或自相似参数，它是自相似程度的一个主要度量。 更确切的说，h u r s t 参数是一种随机现象的持续性的度量。日的取值区间为 o t 日c 1 ，如果妄t h t l ，表明具有长程相关性，日值越大，说明长程相关 二 性越强。实际网络中测得的日值一般大于0 8 。 由于网络业务流在数学上等效为一离散时间序列，下面给出自相似过程的 离散时间定义：设x o ) ，f z 是一广义平稳随机过程，x 具有恒定均值 p - 研x ( f ) 】和有限方差盯2 - e ( x ( f ) 一弘) 2 】，其自相关函数 r ( k ) e ( x ( t ) - g x x ( t + k ) - g ) ，( 七- o ，1 ，2 ，) 仅与k 有关。对疋( f ) 进行 u m 阶平滑处理，得到一个新的随机序列z ，z ( _ g ) 一三罗x ( f ) ，其自相 m f q i # 毛 “ 关函数记为y 似 ) 。 定义2 2 ( 严格二阶自相似过程) 2 6 1 ：如上所述的随机过程x ( f ) 如果满足 一2 r ( k ) 一冬( + 1 ) z s 一2 k 2 s + 一1 ) 2 x ) - r 。 ) ，k ：- 1 ，则被称为且具有h u 船t 参数 二 日g c 日( 1 ) 的严格二阶自相似过程。 西南交通大学硕士研究生学位论文第1 0 页 定义2 3 ( 渐近二阶自相似过程) 嘲：如上所述的随机过程z ( f ) 如果满足 一2 l i mr ( 。 ) 一冬( + 1 ) “一觋撕+ 一1 ) ”) ，k 1 ，则被称为具有h u r s t 参数 一 日仁t 日t 1 ) 的渐近二阶自相似过程。 2 由于网络数据量太大以及网络事件的随机本质，使得无法观察到准确的自 相似现象。但是如果我们将传输序列看作随机过程中的样本，同时放宽自相似 指标，即只关注重构时间序列中特定的几个统计指标，那么就可以观测到网络 传输业务的自相似性，一般称为统计自相似 二阶统计指标能够很好的反映随机过程的突发和变化，而自相关函数是反 映尺度不变性的一个很好的评价标准，同时自相关函数的形状在比较和重构时 间序列上扮演着重要角色。由自相关函数的特性可以得出长程相关的定义： 定义2 4 ( 长程相关) 1 2 6 ：对二阶自相似过程z ( f ) 的自相关函数r ) ，令 ，( 七) 之字，o c h t l ，且日一寻，则有r ) h ( 2 h 一1 ) 七z - 2k a o 。如果 ：1t 日t 1 ，r ( 七) 可近似表达为c k 一，c 为大于0 的常数，卢- 2 - 2 h ，显然有 罗r ( 七) - g o 。我们称满足如上条件的平稳随机过程工( f ) 是长程相关的。 愚 长程相关是自相似的最重要特征之一，渐近二阶自相似过程与长程相关在 概念上是等价的，由于实际网络业务只能用渐近二阶自相似过程描述，所以在 “网络”这个语义环境中，常常将自相似性等价于长程相关性。对于泊松分布 来说，其自相关函数了，( 七) t * ，因此是短程相关的。短程相关表明相距较远 t t 二 的数据之间的互相关函数的相关系数为0 ，而长程相关性意味着距离较远的数 据之间仍然有较强的相关性。 定义2 5 ( 重尾分布) 2 7 1 ：一个随机变量z 具有重尾分布特性，如果其概率 分布满足p r z ，工 一c x - a , x 一* 。其中c 是大于零的常数，a ( 0 ，2 ) 被称为尾 指标或形状参数。 这种分布的尾部衰减是呈双曲线型的，因此相对于尾部呈指数衰减的分布 西南交通大学硕士研究生学位论文第1 l 页 来说，其衰减过程要慢很多，这也是其被称为重尾分布的原因。相对应的，我 们将呈指数型衰减的分布称之为轻尾分布，如泊松分布和高斯分布等。 重尾分布的一个重要特性是当0 t at 2 时，具有无穷方差；当0 口s l 时， 具有无穷均值。这种特性导致一些小概率事件以不可忽略的概率出现，使得它 很适合于描述一些具有很强突发性的事件。通常在网络环境中，主要考虑 l 口2 的情况，最常用到的重尾分布是p a r e t o 分布。 定义2 6 ( p a r e t o 分布) 瞄l ：随机变量z 服从p a r e t o 分布，如果其概率密度满足 口 一l p r z x 1 一f 旦1 ，b s x ，其中0 at 2 ，6 是位置参数，其总体均值为_ 竺譬 工， a 一1 2 3 自相似过程的性质 自相似过程具有以下一些性质： 1 长相关性 如果罗r ( 七) - m ，则称平稳过程x 具有长相关性，其中， ) 是过程x 的 疗二 自相关函数，m a n d e l b r o t ( 曼德博罗，美籍法国数学家，是分形理论的创始人) 将长相关性称为约瑟夫效应( j o s e p he f f e c t ) 。由自相似定义可知，如果 ：1 日 0 5 时，h 邺t 效应表 明样本中极端值的持续时期应比较长，即所谓的持续性( p e r s i s t e n c e ) 如果这种 极端值持续时期理解为网络业务的突发性，则日可以用来描述业务突发性的 强度。而且，自相似性使得这种突发性不会因聚集而被平滑掉，即突发性呈现 嵌套特点。 3 方差衰减缓慢 若对所有的m - 1 ，2 ，3 ，均有 r ( _ ( 七) 一r ( ) 一k - p , 0 卢1 七一0 0 ( 2 - 4 ) 即x 为精确二阶自相似过程( e x a c t l y s e c o n d o r d e rs e l f - s i m i l a rp r o c e s s ) ，则式 ( 2 - 4 ) 等价于 v a r ( x 。) a m 当m - 雩( 2 5 ) 其中a 是独立于m 的正常数，的取值与( 2 - 4 ) 相同，这说明对于自相 似过程，其聚集过程方差的衰减速度要比分段长度m 的倒数慢。而对于传统 的短相关过程，可以证明 v a r ( x ( 曩) 一b m - 1 当m - o o ( 2 6 ) 其中b 是独立于m 的正常数。即通常用于分析分组数据传输的随机过程 的方差是以与1 m 成比例的速率减小的。 方差随着过程聚集而缓慢衰减，表明白相似过程的波动程度。 4 谱密度具幂指数特性 在频域上考察自相似过程时，由于它的持续性，低频处的谱密度非常大， 表现为在频率l 的零点附近谱密度函数翮服从幂指数函数，即 ，( ) 一a 一，当a o( 2 7 ) 其中0 ( r l r - 1 一卢，声的取值同式( 2 - 4 ) 。因此从谱分析的角度来看， 西南交通大学硕士研究生学位论文第1 3 页 长相关意味着当频率j ：【趋于0 时，其谱密度将趋于正无穷( 即1 ，噪声) 而 对短相关特性而言，在频率a 的零点附近，谱密度函数翮是一个有限正数。 2 4 自相似对网络性能的影响 在网络实际应用中，使用基于泊松分布的排队论分析的结果与实际的性能 有很大的差异，其原因在于排队论依赖数据通信量的泊松分布性质，网络业务 流的分布具有自相似性，不完全符合泊松分布的特性，它对依赖泊松特性设计 的网络性能有很大的影响。 自相似特性的第一个实际影响是交换机和多路复用器中的缓冲区需求比 传统排队论分析与模拟的预测结果要大的多。缓冲区越大，导致各个数据流的 时延比之原先预期的要越大。 自相似的另一个影响是报文丢失率缓冲区增大时报文丢失的减少要比预 期的要小的多，并且，稍微增加通过交换机的活动连接的数量将导致报文丢失 率的大大增加。 自相似的第三个影响是当缓冲容量比较大时，排队时延超线性地依赖于自 相似特性。l r d 源的队列长度分布的衰减速度较之s r d 源要慢得多。 自相似的第四个影响是通信链路的利用率。在时延限制条件下，链路分配 率接近于峰值信元速率，通常峰值要比平均速率要大得多，在大的突发的情况 下，链路利用率是非常低的。 自相似特性的第五个影响是自相似业务流经多路复用后产生一个聚合的 自相似业务流，网络业务不能通过不同的时间尺度来平滑，复用也不能导致业 务的平滑。 + 自相似特性的第六个影响是导致动态拥塞控制策略难于实现。动态拥塞控 制策略一般基于当前流量的测量，自相似会使得测量完全不能适应条件的快速 变化。另外，动态拥塞控制策略还需要利用未来流量的信息，以便作出流