（计算机应用技术专业论文）网络流量自相似特性分析及其应用研究.pdf

摘要 随着网络的普及以及新的应用如v o d ，v o l p 的出现，网络的突发业务流量 急剧增加，使得基于传统的p s t n 的流量特征不再适合当前网络流量的分析。 山于自相似模型能够更加真实地描述网络传输的特性，因此通过生成自相似性 的流量进行仿真研究，是一种有效的研究方法。 本文首先介绍了国内外对自相似流量的研究现状，包括自相似流量生成方 法、描述流量自相似程度的h u r s t 参数估计方法、自相似流量的成因及对网络 性能的影响。然后，利用院网络中心的入侵检测系统对局域网流量进行测量， 通过处理得到不同时段的分组到达过程，采用经验r s 分析方法，对h u r s t 参 数进行估计，判断此分组到达过程的统计特征是否具有自相似性。同时，通过 采用多个独立的o n o f f 周期内p a r e t o 分布的流量进行叠加产生自相似过程的方 法，在网络模拟器n s 下对生成具有白相似特征的网络流量进行建模仿真，同 样采用经验的h u r s t 参数估计方法，与测量得到的实际流量进行比较，验证仿 真流量可以有效地反映真实网络流量。接着，我们在有限的网络资源下将t c p 协议和源端流量自相似性相结合，研究了自相似流量对网络性能的影响，发现 源端流量的自相似性与网络状态无关，而t c p 流控制可以自适应改变网络状态， 从而间接改变网络流量的自相似性，但并不能消除源端流量的自相似性。同时， 我们发现随着u d p 负载增加，分组丢弃率明显上升，如果降低分组到达速率将 使得分组丢弃率降低，特别是在网络负载轻时，分组丢弃率的降低尤为明显。 t c p 负载增加时，分组丢弃也呈增长趋势，但是分组丢弃率的幅度同u d p 下的 分组丢弃率相比要小些，表明t c p 流控制从某种程度上降低了分组丢弃率，从 自相似程度来看，却增强了流量的自相似性。随着汇聚节点的缓冲容量增加， 分组丢弃率总体呈下降趋势。 最后，我们对网络流量自相似性在网络安全中的应用这个新的研究方向进 行了探讨，根据网络流量的变化直接影响流量的自相似性程度，在入侵检测系 统中对网络流量异常引起自相似性变化明显的数据进行研究。基于建立的用户 正常行为的网络流量模型，通过比较描述网络流量自相似性的h u r s t 参数值来 判断网络是否异常，并进行及时预警。 关键词：长相关；自相似流量；h u r s t 参数；网络性能；入侵检测系统；预警 a b s t r a c t t h e p o p u l a r i z a t i o n o fn e t w o r ka n d o u t s p r i n g o fn e w a p p l i c a t i o n s m a k e n e t w o r kt r a f f i c i n c r e a s i n gr a p i d l ys u c h a sv o da n dv o l pe t c ，s ot h a tt r a d i t i o n a l p s t nt r a f f i cc h a r a c t e rw i l ln ol o n g e rb ea d o p t e dt oc u r r e n tn e t w o r kt r a f f i c t h e e f f e c t i v em e t h o df o rs t u d y i n gs e l f s i m i l a rt r a f f i ci st ob u i l dm o d e l sw h i c hc o u l d d e s c r i b en e t w o r kc h a r a c t e r sm o r er e a l i t y , a n db ea p p l i e dt os i m u l a t i o nr e s e a r c h i nt h e p a p e r ，w e i n t r o d u c er e s e a r c h b a c k g r o u n d o fs e l f s i m i l a r t r a f f i c ， i n c l u d i n gs e v e r a lc o m m o nm e t h o d so fc r e a t i n gs e l f - s i m i l a rt r a f f i ca n de s t i m a t i n g h u r s tp a r a m e t e r s 、t h ec a u s ea n di n f l u e n c et on e t w o r k p e r f o r m a n c eo fs e l f s i m i l a r t r a f f i c f u r t h e r m o r e ，h a v i n gm e a s u r e dl o c a ln e t w o r kt r a f f i cw i t hi n t r u s i o nd e t e c t s y s t e m o fn e t w o r kc e n t e r ，w ed e a lw i t h p a c k e t a r r i v a l p r o c e s s a n d a d o p tr s m e t h o dt oe s t i m a t eh u r s tp a r a m e t e r ，w h i c hi su s e dt od i s t i n g u i s hw h e a t h e r p a c k e t a r r i v a lp r o c e s si ss e l f s i m i l a ro rn o ti ns t a t i s t i c s i no r d e rt om o d e ls e l f s i m i l a r n e t w o r kt r a f f i cs o u r c ea n dm a k es i m u l a t i o ni nn s ，w eu s et h es u p e r p o s i t i o no fa n i n f i n i t en u m b e ro fs o u r c et r a f f i cw h o s ed u r a t i o n so ft h eo n o f fp e r i o d sa c c o r d i n g t op a r e t o d i s t r i b u t i o n c o m p a r i n g w i t hm e a s u r e dt r a f f i cb a s e do nt h es a m e e s t i m a t i n gm e t h o do fh u r s t ，w ev a l i d a t et h ee f f e c t i v e n e s so ft h ew a yf o rc r e a t i n g s e l f - s i m i l a rt r a f f i c i na d d i t i o n ，w em a k ef u r t h e rs t u d yo nc o m b i n i n gt r a f f i cs o u r c e w i t ht c p p r o t o c o lt ou n d e r s t a n dt h e i re f f e c t so ns e l f s i m i l a r i t y ，b yw h i c hw ec a n k n o wt r a f f i cs o u r c es e l f s i m i l a r i t yi s i n d e p e n d e n tt on e t w o r k ，w h i l ef l o w sc o n t r o l a l g o r i t h m o ft c p c h a n g i n g n e t w o r ks t a t u s a u t o m a t i c a l l y c o u l da l t e rt h e s e l f s i m i l a r i t y o fn e t w o r k t r a f f i c h o w e v e r ，i t c a n n o t l a y t r a f f i cs o u r c e s e l f 。s i m i l a r i t ya s i d e m e a n w h i l e ，t h ep a c k e td r o pr a t ew i l lr i s eu pa c c o m p a n y i n g w i t ht h ei n c r e a s i n go fu d p l o a d s ，a n df a l ld o w nb yr e d u c i n gp a c k e ta r r i v i n gr a t e ， s p e c i a l l ya tl o wl o a d w eg e ts i m i l a rr e s u l t sb yu s i n gt c p ，b u tt h er a n g eo fp a c k e t d r o p p i n gr a t ei s s m a l l e rt h a nt h a tw h i l eu s i n gu d p i ts h o w st h a tt c p w i t hf l o w c o n t r o lc a na l l e c i a t e p a c k e td r o p p i n gt os o m ee x t e n ta n de n h a n c et h ed e g r e eo f s e l f s i m i l a r i t y b yi n c r e a s i n gb u f f e rl e n g t ha tb o t t l e n e c kl i n k ，p a c k e td r o pr a t ew i l l d e c l i n es o m e w h a t l a s t ，w ed i s c u s s n e wf i e l d a b o u tn e t w o r kt r a f f i cs e l f - s i m i l a r a p p l i e d i n n e t w o r ks e c u r i t y c o n s i d e r i n gt h a tt h ea m o u n to 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 y e f f e c t so ni n t r u s i o nd e t e c ts y s t e m ，w es t u d yt h ec h a n g eo fs e l f s i m i l a r i t yc a u s e db y a b n o r m i t y o fn e t w o r kt r a f f i ca n db u i l dan e t w o r kt r a f f i cm o d e lb a s e do nu s e r n o r m a lb e h a v i o r ，w h i c hc a na l a r mo nt i m ew h e t h e rt h en e t w o r ki sa b n o r m a lo rn o t ， b ym e a n so fc o m p a r i n gs e l f s i m i l a rt r a f f i c sh u r s tp a r a m e t e r k e yw o r d s ：l o n g r a n g ed e p e d e n c e ；s e l f s i m i l a rt r a f f i c ：h u r s tp a r a m e t e r n e t w o r kp e r f o r m a n c e ；i n t r u s i o nd e t e c ts y s t e m ：a l a r m i n g 儿i 湖南大学 学位论文原创性声明 本人郧重声明：所呈交的论文是本人存导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完伞意识到本声明的法律后果 由本人承担。 作者签名： 何晶日期：如争年f 月甲日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电f 版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印1 1 r l “ - 一l 保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： ，f 可品日期：跏牛年月9 日 导师签名二三罗、夕灸日期：即铲年月7 日 第1 章绪论 1 1 课题来源、目的及意义 本课题得到湖南省自然科学基金项目( 0 3 j j y 3 1 0 0 ) 资助。 自互联嘲问世以来，关于网络流量的研究一直在不断的探索中。在通信网 络技术发展的3 0 年罩流量模型研究一直倍受人们关注。上世纪7 0 年代和8 0 年代早期人们主要借鉴p s t n 的流量模型，用泊松( p o i s s o n ) 模型来描述数据 网络的流量。在公共交换电话网中，泊松模型的确能够较好的描述实际呼叫的 到达过程，并且在当时网络应用单一，数据传输量较小的情况f ，泊松模型对 网络流量的模拟起到了积极的作用。町是自上世纪9 0 年代以来，网络节点数 呈指数式地增加和新的应用( 如v o d ，v o l p 等多媒体业务) 的出现，特别是 不同的网络应用具有不同的流量特征和q o s 需求，使得传统流量模型不再适用 于分组网络流量的分析。9 3 年，l e l a n d 、t a q q u 等人对以太网和可变比特率的 视频业务数据进行测试并分析结果，发现以太局域网流量到达过程呈现突发性 和间歇性，分组流量描述为到达间隔时间呈重尾衰减，方差以样本大小的分数 幂衰减，功率谱离散接近原点，相关性体现为氏相关【l i 。自相似过程是一种研 究较为广泛的简单的长相关性模型。 自相似过程与传统的泊松或马尔可夫业务模型相比具有许多不同的统计 性质，最主要的一点是能够反映业务流量在任意时间范围内的长相关特性，即 当对业务流进行较大范围时间尺度( 从毫秒到小时) 的测量，业务流会产生相 似的特性，而传统的业务流模型只存在短相关性，在不同的时间尺度上有不同 特性。有研究表明，流量的自相似性会导致缓冲溢出率高，延时长和持续周期 性拥塞，直接影响到新一代网络的设计、控制、分析和管理。 随着i n t e r n e 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 r n e t ；i n t e r n e t 路由策略 的变化从“f i r s tc o m e ，f i r s ts e r v e ”到公平的资源共享；网络应用的多样化，如 g r i d 、p 2 p 、视频会议、i n t e r n e tm u l t i c a s t 应用、w e bc a c h e 、v r m l 、多人游 戏，这些为研究网络流量特性提供新的契机。 网络流量特征是分析和研究网络性能、规划网络建设的基石 i j 。网络流量研 究中关键的问题是如何合成网络真实流量并进行分析，由于自相似模型能够更 加真实地描述网络传输的特性，因此通过生成自相似性的流量进行仿真研究， 是一种有效的研究方法。探讨自相似流量的产生原因，生成具有自相似性的网 络流量并进行仿真研究，了解网络行为随参数变化的情况，这对网络的设训、 控制、分析和管理是非常有实际意义的。同时，我们对网络流量自相似性在网 络安全中的应用进行了探讨，为新一代网络设计所需的系统分析、性能预测和 安全管理提供了重要的理论依据。 1 2 研究背景 l e l a n d 等通过对l a n 的流量分析和k l i v a n s k y 等对w a n 流量的测试分析 发现流量具有自相似性。流量到达过程呈现突发性和间歇性，分组流量捕述为 到达间隔时间呈重尾衰减，方差以样本大小的分数幂衰减，功率谱离散接近原 点，相关性体现为长相关。这个结果引发了对流量到达过程新模型的大量研究， 同时也影响剑传统的队列行为。文献【2 指出在w a n 流量中，泊松过程仅用于 对用户会话到达( t e l n e t 连接，f t p 连接) 的建模，而对于其它w a n 到达过程 的准确建模是不行的。使用泊松或马尔可夫业务模型不能准确地反映实际流量 的长相关性，会导致分析时低估平均分组延时或最大队列长度等因素。因此， w a n 分组到达过程应采用能够表征长相关性的模型，自相似过程就是研究较 为广泛的简单的长相关性模型。自相似过程与传统的泊松或马尔可夫业务模型 相比具有许多不同的统计性质，最主要的一点是能够反映业务流量在任意时间 范围内的长相关特性，即当对业务流进行较大范围时间尺度的测量，业务流会 产生相似的特性，而传统的业务流模型只存在短相关性，在不同的时间尺度上 有不同特性。传统的排队分析基于泊松到达过程的假定，突发在短时间内发生， 从长时间看突发被平滑掉了，但是，白相似性反映业务在较大时间尺度具有突 发，对缓存的占用比传统排队论的分析结果要大，结果会导致更大的延时。 网络流量的自相似性体现在各种各样的网络环境中，其产生的原因归丁二多 方面的因素。有的研究认为网络流量的自相似性产生于业务源端和应用层行为 卜5 1 ，有的研究认为传输层协议的相互影响产生了自相似现象 9 - 1 2 。对流量自相 似性的研究可以分为两类：一类是关于流量特征的建模1 4 - 5j ，一类集中在性能评 价。第一类研究指出物理上网络测量的流量路径通常用来识别规模恒定突发的 存在，采用合成流量建模来匹配其特征。这些研究显示长相关是产生于局域网 和广域网流量中的现象16 - 7 1 。另一类研究指出长相关流量对网络性能有不利的影 响，最重要的结果是自相似流量下队列长度分布的衰减比短相关业务源( 如泊 松模型) 要缓慢。一一些不同的研究指出长相关对小缓冲容量或短时问尺度稍有 影响f h i 。 2 1 3 本文主要工作 自相似性对网络性能具有一定影响，但是自相似性的产生原因及对自相似 参数影响较大的因素还没有定论，在资源有限网络中自相似对网络性能的影响 也还没有进行深入研究，因此，本文中我们探讨了影响自相似程度的因素，在 有限的网络资源下将t c p 协议和源端流量自相似性相结合，研究了自相似流 最对网络性能的影响以及网络流量自相似性在网络安全方荷的应用。主要工作 有： ( 1 ) 采集校园网流量，对实际流量进行了统计分析。 ( 2 ) 采用生成多个独立的0 o f f 周期p a r e t o 分布的流量进行替加的方法， 对生成具有自相似特征的网络流量进行仿真研究，并验证了该方法的有效性。 ( 3 ) 采用方差一时间曲线、r s 图等方法来估计仿真流量的白相似参数( 又 称h u r s t 参数) ，并与实际流量的h u r s t 参数进行比较。 ( 4 ) 研究导致流量自相似性的原因以及影响h u r s t 参数的因素，在有限的 网络资源下，将源端流量自相似性和t c p 协议相结合研究自相似流量对网络 性能的影响。 ( 5 ) 由于网络流量的变化直接影响流量的白相似程度，建立了基r 用户 正常行为的网络流量模型，并将其应用于网络入侵检测系统，通过比较h u r s t 参数值来判定网络运行是否异常，以便及时预警。 1 4 论文结构 本文第2 章介绍了传统流量模型的特点，给出了自相似过程的数学描述。 第3 章介绍了自相似流量生成方法的研究、自相似参数的估计方法，分析了自 相似性对网络性能的影响。第4 章论述了在网络模拟器n s 下对自相似过程的 建模，探讨了影响自相似程度的因素，在有限的网络资源下研究了t c p 协议 和源端流量自相似性相结合时自相似流量对网络性能的影响。第5 章对网络流 量异常带来的自相似性变化进行了研究。最后是对本文工作的总结以及进一步 工作的展望。各章之问的联系与全文的结构如图1 1 所示。 第1 章 绪论 第2 章 白相似过程 的描述 第3 章 自相似流屋生成 方法及儿对性能 影响分析 第4 童 嘲络流量自相似性的 实验及结果分析 第5 童 网络流量自相似性在 蝌络安争中的麻朋 图11 全文结构框图 结论 1 5 小结 随着网络的普及，以及新的应用( 如v o d ，v o l p 等) 的出现，网络的突 发业务流量急剧增加，使得基于传统的p s t n 的流量特征不再适合当前网络流 量的分析。经典的流量模型( 如泊松，马尔可夫模型) 使网络资源的分配逐渐 出现不合理，网络的效率下降。网络流量自相似性的发现及其概念的提出，给 流量的建模丌辟了新的出口。 目前，网络流量的自相似性问题已成为网络研究中公认的热点和难点，本 文基于o n o f f 周期内p a r e t o 分布生成具有自相似性的网络流量，探讨了对自 相似程度影响较大的因素；并在有限的网络资源下，将t c p 协议和源端流量 自相似性相结合研究了白相似性对网络性能的影响，在深入了解网络流量白相 似性对网络性能影响的基础上，探讨了将描述网络流量自相似性的h u r s t 参数 进行比较来判定网络流量是否异常，以便对入侵检测系统进行及时预警，为新 一代网络设计的系统分析、性能预测和安全管理提供了藿要的理论依据。 4 2 1 引言 第2 章自相似过程的描述 网络设计中需要适当地引入流量的随机性，实际j 二，如果没有随机输入， 则可以忽略队列的产乍，也就不需要缓冲、过大的容量或复杂的流量管理。理 解流量到达过程的特征是设计好网络所必须的。本章介绍了传统网络流量模型 中描述流量到达的马尔可夫过程和泊松过程的特征 1 3 1 ，由于传统模型设计不能 提供足够的链路容量和缓冲空间来支持负载的波动，因此，我们采用显示长相 灭的自相似模型来代替传统马尔可夫模型进行研究。 2 2 传统网络流量模型的特点 传统的网络流量模型大多基于马尔可夫对流量到达过程和服务时间分布 的假设，分组和连接到达过程经常被看作是泊松过程，描述为到达间隔时间呈 指数衰减，方差以样本大小逆向衰减，功率谱收敛逐渐接近原点等等，这些导 致流量模型的短期相关，曾成功地用于电话网的设计和操作中。 2 2 1 马尔可夫过程 马尔可夫过程是具有无后效性的随机过程。所谓无后效性是指：当过程在 t 。时刻所处的状态为已知时，过程在大于t 。的时刻所处状态的概率特性只与过 程在t 。时刻所处的状态有关，而与过程在t 。时刻以前的状态无关。直观七看， 如果把t 。看做“现在”，则当t t 。，t 将成为“将来”；而t o t 。c t 2 j l c 石一，t a 2 ，丁存 在有限期望但是显示无限方差或高可变性。但是as 1 时，丁没有有限期望，因 此，c o x 结构主要在于会话长度或持续时间是1 c ac2 的重尾。直观上看，此特 性说明会话长度不是固定的，而是高可变显示无限方差且在较大范围尺度( 如 从千字节到兆字节或更大的千兆字节) 波动。应用层是产生i p 层聚集流量显 示自相似行为的根源。对于m a n d e l b r o t 结构5 f ，依靠o n o f f 过程，同样使用 重尾来解释聚集链路流量的自相似特征。o n o f f 源端相互独立，o n 周期分组 以固定速率h 发送，o f f 周期没有分组发送，o n 和o f f 周期相互交替。o n 周期 的随机变量a 有e a i = l h , ，o f f 周期的随机变量8 有e b i = 1 v 。o n o f f 源端的 平均速率则为 = h v ( + ，) 。与c o x 结构相似的是氏相关性可以用o n o f f 过程 的速率过程x ( t 1 柬表示，聚集大量的o n o f f 源端将使得链路流量显示自相似 行为收敛丁分形高斯噪声f g n 。 c o x 或m a n d e l b r o t 的结构模型不仅能解释自相似现象，而且可以从具有i p 分组头部的路径中提取数据去验证该解释。例如，由于许多应用的建克，对于 f t p 和t e l n e t ，与会话相关的一些实体如到达时间或分组级测量的持续时间， 显示与c o x 结构一致( 2 1 。对于h t t p ，存在包含的会话信息，但是h t t p 持续 时问的重尾特征的经验事实也被证实1 5 1 1 1 6 1 。 2 3 2 自相似过程的定义 自相似过程是基于连续时间变量的直接尺度变换。假定茗= 扛( i l f = o ，1 ，2 ，) 为广+ 义平稳随机过程 1 1 ，具有均值、方差盯2 和自相关函数r ( 七) ，k 0 ；令 x ”( i ) = 【x ( i ) + x o + 1 ) + + x ( i + m 一1 ) m ，( i = o ，1 ，2 ) ，对每个m ，上”( f ) 定义为一个 协方差平稳过程，4 幢) 为工“相应的自相关函数。 如果x 的自相关函数对所有m 具有如下形式： r ” ) = ， ) k ”( 0 1 )( 2 1 ) 则x ( i ) 为自相似参数h = 1 一( 卢2 ) 的精确二阶自相似过程。 如果x 的自相关函数对所有m 具有如下形式： r ” ) ，忙j ，当m 一。，( 2 2 ) 则工“) 为自相似参数h = 1 一( , 6 2 ) 的渐近二阶自相似过程。 精确或渐近二阶自相似过程的自相关函数，忙) 在k 一。的行为类似幂律， 指数由日决定。参数日又称h u r s t 参数，是描述自相似特性的唯一参数，更确 7 切地说，h 是统计现象的持续性度量，是随机过程长相关的一个度量。日的取 值范围在( 0 5 ，1 ) 。随着h 逐渐增大，亿) 在k m 的衰减越慢。在o 5 h 1 ， - f f r ( 女) = 。 2 。3 3 自相似过程的特性 由自相似的数学定义可知，自相似过程具有以下特性： ( 1 ) 堆叠过程j b ) 随着m 一0 ，自相关结构不变，或者说是非退化的，即对 于不同的m 值，盖) 直观上相似，也就是说它们有基本一致的自相关函数。 ( 2 ) 长相关性。其自相关函数随时滞的增加呈双曲线衰减( 幂律衰减) 。自相 似是长相关的简单模型。由此可知，啦) 是不可加和的，即r ( 尼) = 。 ( 3 ) 慢衰减方差。自相似过程方差满足：v a r b ”) 硎一，牌一。其中o b 1 ，a 是与m 无关的正常数。 ( 4 ) 谱密度，n ) 在原点附近服从幂律变化，即，n ) 以，a 一0 。其中o y 1 。 经典流量模型的短相关性和自相似性的比较见表2 1 。 表21自相似性和经典流量模型的短相关性的比较 臼相似短相关 r 仅) ，k 一。o ( o cb 1 )r 伍) p 。，k 一( o p 1 ) r ( 七) = * o cf r ( 七) c o 。 口 v a r b ( m ) ) 蜊，z 一* ( o c bc 1 )v a ，k ( m ) ) 硎，m 。 2 4 小结 由于网络上分组的到达过程是一个随机过程，本章对传统的流量模型基于 马尔可夫和泊松到达过程进行了介绍。假设分组到达过程是一个广义平稳过 程，讨论了反映目前分组交换网络中流量到达过程的自相似模型的起因，并对 自相似过程进行了数学描述，从中可以看到自相似过程具有长相关性、慢衰减 方差、幂律谱密度函数等特性。 8 第3 章自相似流量生成方法及其对性能影响分析 3 1 引言 网络流量研究中多用统计上的自相似过程作为网络分组到达过程代替传 统的泊松过程，但是，如何合成自相似流量的样本路径是一个难点。多数模型 在合成网络分组到达流时用到重尾分布合成长相关的机制。s m i t h l ”j 用重尾分 布去分析队列系统内部到达时间的性能。f i o r i n p ”】提出对一个调制的泊松过程 用重尾分布去驱动调制。p a x s o n l2 0 1 和e r r a m i l w ：i 提出合成近似分形高斯噪声 f g n ( f r a c t i o n a lg a u s s i a nn o i s e ) 的正交方法。t a q q u m 】提供了一种数学结果将 长相关性和重尾调制过程统一起来，并证明了无限个报文串源的叠加在o n o f f 周期内的持续时间是重尾分布产生具有长相关性的过程。这些研究为网络流量 模型中合成分组到达流量显示自相似性提供了理论基础和经验基础。 3 2 自相似流量的生成方法 日前，通过和真实业务流量数挠：比较认为适于作为突发业务建模的自相似 模型有分形布朗运动f b m ( f r a c t i o n a lb r o w n i a nm o t i o n ) 和分形白回归综合移 动平均过程f a r i m a ( 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 ga v e r a g e ) ， 它们都基于分形高斯噪声f g n ，其中f b m 的独立增量过程为分形高斯噪声， 而f a r i m a 过程可看作分形高斯噪声经过一个a r m a 参数为滤波器系数进行 滤波的结果。 对于一个随机过程工( f ) ，如果有一常量h ( h u r s t 参数) ，h ( 0 ，1 ) ，且工( f ) 的分布等同于“k 缸) ，( t ，。，o ) ，则称石( f ) 有自相似性。f b m 是。个经典自 相似的例子，显示x ( f ) 过程具有高斯增量，即： 初始值x ( o ) = 0 ； 增量工( f ：) 一工o 。) 对于所有f ， 0 ，x k( 3 1 ) 互补累积分布( c c d f ) 为： p j ，x 】= e ) ”( 3 2 ) k 参数k 为对应x 取最小值的位置参数，a 为形状参数，当ac2 时具有无限 方差的重尾分布，as 1 时分布具有无限期望。 如果随机变量x 的c m e 。是x 的递增函数，则c m e ：= 陋一z 陋z 石j 。当随机 变量x 代替等待时间，对于等待时间为轻尾分布例如均匀分布，c m e ，是x 的递 减函数，等待时间越长，结束越快：对于巾尾分布例如无记忆性的指数分布， 期望未来的等待时间独立于现在的等待时间；对于重尾分御，则等待时间越长， 期望未来的等待时间【l l 越长1 2 1 。 此方法用多路独立的r ( t ) 过程在o n o f f 周期的r ( t ) 数目来构造s n 过程， s n 对于n 趋于c o 是渐近自相似过程。在用s n 模拟合成自相似过程时，需要在 计算速度和与真实自相似过程接近程度之间作折中选择。 3 2 4h o s k i n g 算法 g a r r e t t 和w i l l i n g e r 提到h o s k i n g 算法j ，该算法根据f a r i m a 过程生成 样本路径。f a r i m a 模型如图3 1 所示： 砸芦匠菌n 为了决定a r 和m a 的值，需要从实际过程s ( n ) 中提取i 元件，根据图3 1 余下的a r m a 系列y ( n ) 和实际过程s ( n ) 有以下相关性： y ( z ) = s ( z ) c ( z ) = ( 1 一z 。1 ) 6s ( z )( 3 3 ) = 些些嬖型些丝型堡墼坚兰= = = = = 一 _ _ _ _ - - _ _ _ _ 一一 这样，y ( n ) 在f i r 过滤器输出处得到，其转换函数为( 1 一z 。1 ) 。，可以验证y ( n ) 是一个期望为0 ，有固定自相关系数的随机过程。a r 元件的转换函数可以表 示为： a ( z ) = ( 1 0 6 2 6 z a i _ 0 3 4 2 z 。2 ) 。 ( 3 4 ) 当y ( n ) 的a r 元件被提取出来，可对m a 元件进行分析，由图3 1 中y ( n ) 和x ( n ) n 相关性可以得到： x ( z ) = a 。1 ( z ) y ( z ) ( 3 5 ) 使用有转换函数为a ，( z ) 的f i r 过滤器，x ( n ) 可以当y o ) 输入时，在过滤 器输出端获得，m a 过程从以下转换函数得到： b ( z ) = 1 - 0 0 7 5 1 z 。1 + 0 2 2 1 z 。2 + 0 0 0 3 9 z 。- 0 1 8 1 6 z 一 最后，f a r i m a 模型可表示为： h ( z ) = y ( z ) w ( z ) = b ( z ) a ( z ) c ( z )( 3 6 ) 该算法的缺点在于要对6 i 面所有样本进行存储才能得到一个新样本，冈 此，算法需要较大可变大小的内存，而且每个新样本的生成时间需要很长，计 算量大。 3 3 自相似流量的参数估计 由于h u r s t 参数是表征业务突发程度的重要参数，也是描述自相似特性的 唯一参数，因此，根据一定时间范围业务流量的监测数据估计h u r s t 参数对自 相似业务的建模和流量控制是十分重要的。目前，估计h u r s t 参数的方法可分 为时域和频域两大类，其中时域法包括：r s 分析、方差时间分析；频域法包 括：w h i t t l e 最大似然估计和基于周期图的半参数估计等。时域法直接对样本 序列进行处理，作出分析曲线，用最小二乘拟合估计h u r s t 参数；频域法则利 用傅立叶变换对样本序列的谱密度在频域进行估计。 3 3 1r s 分析方法 基于r s 统计的时域分析是一种启发式图形化的方法，通过分析时间序列 相邻n 个子单元计算得来。对于一个长度为的样本x 。，k = 1 , 2 3 ，n ，将其 划分成k 个互相不重叠的块。每一块的开始点为t ，= 1 ， t ：= t + 1 ，t ，= 2 n k + 1 ，计算每一块前n 个点的重新调制尺度权差 尺( f ，h ) s t 。，n ) ，其中，n 满足t 。一1 ) + ns n 。令x 0 ，n ) ，s2 ( f ，”) 分别是序列x 。， 。：，z 。的样本均值和样本方差。月o ，+ n ) ；m a x ( o ，啊，j 吒) m i n ( o ，嵋，暇) ，其中，= x 。，+ z ”：+ + 彳。k x ( t 。，n ) 。l o g ( n ) ， l o g r ( t ，n ) s ( t ，n ) 分别作为横坐标和纵坐标，采用最小二乘拟合得到斜率为h 的散点图。 根据： 陋“) s 如霸一c n ”( 3 7 ) 两边取对数： i o g e r ( n ) s ( n ) h l o g ( n ) + l o g c( 3 8 ) 由公式( 3 8 ) 可知散点图中所有点分布在一条直线的两旁，这条直线的斜率 日反映了h u r s t 参数的大小。 3 3 2 方差时间分析方法 方差时间分析方法是h u r s t 参数估计的另一种常用方法。利用自相似过程 的慢衰减方差性质，对于有限长时间序列， 根据：阮r b j 叫 ( 3 9 ) 两边取对数：l o g ( v a r b ”) ) 一卢l o g 似) + l o g a( 3 1 0 ) 根据公式( 3 1 0 ) ，采用最小二乘拟合该散点图，在方差时问对数图上显示 为斜率为一声的直线，如果满足一l c 一筘c 0 ，利用关系式h = 1 一( f l 2 ) ，则町得 到该序列的h u r s t 参数值，以此判断过程的自相似性。 3 3 3w h i t t l e 最大似然估计方法 w h i t t l e 最大似然估计是在证明一个时间序列是自相似的情况下来计算 h u r s t 参数。基于3 2 2 节提到的f g n 过程的功率谱r ( z ，h ) ，w h i t t l e 最大似然 估计寻求h u r s t 参数使相关功率谱最接近对应的时问序列的周期图。利用自相 似过程的谱密度在原点附近近似幂律变化的特性，先对其协方差函数进行傅里 叶变换，得到功率谱，然后采用取对数的思路，以及和r s 分析、方差时间分 析方法相类似的解决方法得到所需的h u r s t 参数值。 r s 分析和方差时间分析方法都要求获得整个观察时间段内以最小间隔时 间采样的全部业务计数过程的样本序列，通过对有限长时间序列进行统计分 析，粗略估计给定的序列是否具有自相似性。而w h i t t l e 最大似然估计方法则 假定一个时间序列是一个实际形式的自相似过程，然后提供h u r s t 参数的估计 值并给出置信区间。 3 4 自相似对性能影响的分析 3 4 1t c p 协议对自相似的影晌 在2 3 1 节我们采用c o x 或m a n d e l b r o t 的结构模型从应用层和用户行为因 素的角度解释了自相似现象的产生原因，由于网络的复杂性和动态性，自相似 流量的产生也有可能在传输过程中受网络协议的影响。对于自相似性产生于流 量的源端还是体现在网络连接中，是流量内在的特性还是网络协议调制作用的 结果，一直引起人们的关注。文献【2 】中提出无限方差的重尾分布产生的高可变 性是网络流量自相似现象的可能原因。文献【2 6 对同一瓶颈链路的多个自相似 t c p 对话流进行累加，得到的流量和仍是自相似流，况明t c p 拥塞控制机制 本身就可以成为出现流量自相似的决定因素，高w 变性不是网络出现自相似现 象的唯一原因。由于当前所有的w e b 、f t p ( 文件传输) 和n n t p ( 网络新闻) 服务都使用t c p 在i n t e r n e t 中传输大量数据，因此需要分析t c p 协议对自相 似产生的影响。 t c p 协议的目的是提供可靠传输服务，为了保证可靠传输，每个分组都有 序列号，通过返回确认( a c k ) 分组表明分组被成功接收。t c p 协议的另一个目 的是提供有效传输。采用适应的窗n 流控制在任意时间只允许单一窗u 的数据 被传递。一旦个窗口的数据需要发送，发送方必须等到前一分组的确认信息。 这种方法受发送方控制非常有效，不管是接收方还是网络都不需要额外的信 息。t c p 有两个控制窗口；发送方窗口c w n d 和接收方窗口r w n d 。源端使用两 者中最小的。这里我们假设r w n d 不变，所有分组都有最大分段大小( m s s ) ， 则c w n d 的最大值对可变的动态性起着重要的作用。 具有窗口大小w 的源端的数据发送速率与确认r t t 的关系为： s e n d r a t e = 月玎。流控制中的关键在于如何选择c w n d 。理论上，窗口大小诈 好调到网络可用的带宽。如果带宽非常小，则会产生拥塞，然而，i n t e r n e t 带 宽可以从k b s 到g b s 变化，而r t t 可以从不到1 毫秒到1 秒变化，差别非常 大。t c p 流控制使用四种算法自适应选择窗口大小：慢启动、搁塞避免、快速 恢复和快速重传。这早我们简单讨论这四种算法。 慢启动和拥塞避免：慢启动开始时，首先设置c w n d 为初始值，通常采用 1 个分组。然后发送第一个窗口数据，对于每次接收a c k ，以1 m s s 增加窗口， 这样每次r t t 后会产生双倍c w n d 增加，即指数增加。窗口的快速增加允许 t c p 适应可用的网络带宽。当c w n d 超过慢启动阀值s s t h r e s h 时完成慢启动。 接着进入拥塞避免阶段，窗口的增长缓慢呈线性，通过 c w n d _ c w n d + m s s 2 t c w n d 。s s t h r e s h 的初始值没有规定的标准，在不同的情况 下从1 ( 如无慢启动) 到。之间变化。对于较小的传输，慢启动是协议中的主 要部分。当前i n t e r n e t 中短t c p 连接非常普遍，例如，只有3 - 4 k b 大小的w w w 文件传输，意味着至少一半w e b 传输不需要5 个分组。因此，下载带宽受r t t 的限制，与链路对多数源端的传输速度无关。在r t t 较大的无线链路中尤其 明显p l 。 丢失指标、晕传和恢复：慢启动和拥塞避免描述当分组被确认时，如果没 1 4 有丢失，窗口大小如何增加。如果出现分组丢失，t c p 协议则认为是出于拥塞 导致窗口大小的降低而产生，将会重传己丢弃的分组。分组丢弃有两种表示： 重传超时( r e t r a n s m i s s i o nt i m e o u t ，r t o ) ，其可靠但是慢；复制确认( d u p l i c a t e a c k n o w l e d g m e