（计算机应用技术专业论文）网络流量自相似特性与预测研究.pdf

浙江大学硕十学位论文摘要 摘要 网络流量特性的研究，以及流量建模和流量预测，大多是基于统计学的时间 序列分析理论。时间序列是所研究系统的历史行为的客观记录，时间序列分析就 是对这些历史记录进行分析，找出数据之间存在的统计上的依赖关系，把握系统 的结构特征和运行规律，从而可以对系统的将来行为作出预测。 分形理论在各个领域得到了广泛的应用，其最明显的特性就是自相似特性。 自相似序列具有长相关特性，其自相关函数值随着间隔值的增大呈渐近双曲线衰 减。自相似特性在2 0 世纪9 0 年代被正式引入到网络流量特性的描述之中，其后， 网络流量的建模与预测也将网络流量的自相似特性考虑在内，而h u r s t 参数表征 了序列自相似性的强度，因此如何较准确地估计h u r s t 参数对于研究网络流量自 相似特性具有重要意义。本文通过实验对h u r s t 参数估计的各种方法做了准确性 和稳定性的比较与分析。此外通过网络仿真，对网络流量自相似特性及其成因进 行了分析和验证。 网络流量预测对于设计新一代网络协议、网络管理以及提高网络的服务质量 等都具有重要意义。本文通过实验对大量实际网络流量数据按不同的时间尺度与 时序模型进行了建模和预测，比较了不同时间尺度下各时序模型的预测性能，经 过分析得出以下结论：时序模型在毫秒级和秒级时间尺度下，有较大的预测误差， 而在分钟级时间尺度下，能达到较好的预测效果。 关键词：流量预测，时序模型，自相似，h u r s t 参数 浙江火学硕l ：学位论文a b s t r a c t a b s t r a c t t h ef e a t u r eo fn e t w o r kt r a f i l ei ss t u d i e dm o s t l yb a s e do nt i m es e r i e sa n a l y s i so f s t a t i s t i c s t i m es e r i e sa r ei m p e r s o n a lr e c o r d so fh i s t o r i c a lb e h a v i o ro ft h es y s t e m s t u d i e d ，a n dt i m es e r i e sa n a l y s i si st oa n a l y z et h e s er e c o r d si no r d e rt of i n dt h em u t u a l s t a t i s t i c a l d e p e n d e n c eb e t w e e nt h e s er e c o r d sa n dg e tt h es t r u c t u r a lf e a t u r e sa n d b e h a v i o r a lr u l e so ft h es y s t e ms t u d i e d t h e nw ec a np r e d i c tt h ef u t u r eb e h a v i o ro ft h e s y s t e mb a s e do nt h es t r u c t u r a lf e a t u r e sa n db e h a v i o r a lr u l e s f r a c t a lt h e o r yi sw i d e l yu s e di nv a r i o u sf i e l d s ，a n di t sm o s to b v i o u sc h a r a c t e ri s s e l f - s i m i l a r i t y s e l f - s i m i l a rs e r i e si sl o n gr a n g ed e p e n d e n t ，a n di t sa u t o c o r r e l a t i o n f u n c t i o nd e c a y sa s y m p t o t i c a l l yi nh y p e r b o l i cm a n l i e rw h e nt h el a gi n c r e a s e s h u r s t p a r a m e t e rr e p r e s e n t s t h e i n t e n s i t yo fs e l f - s i m i l a r i t yo f t i m es e r i e s e v e rs i n c e s e l f - s i m i l a r i t yw a si n t r o d u c e di n t ot h ed e s c r i p t i o no fn e t w o r kt r a f f i c ，i th a sb e e nt a k e n i n t oc o n s i d e r a t i o ni nn e t w o r kt r a f f i cm o d e l i n ga n dp r e d i c t i o n s o ，h o wt oe s t i m a t e h u r s tp a r a m e t e rm o r ea c c u r a t e l yp l a y sa ni m p o r t a n tr o l ei nr 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 y t h i sp a p e rc o m p a r e st h ea c c u r a c ya n ds t a b i l i t yo ft h em e t h o d sf o r e s t i m a t i n gh u r s tp a r a m e t e rt h r o u g ha ne x p e r i m e n ta n dv a l i d a t e st h er e a s o n sf o r s e l f - s i m i l a r i t yo fn e t w o r kt r a f f i ct h r o u g has i m u l a t i o ne x p e r i m e n t n e t w o r kt r a f f i cp r e d i c t i o np l a y sa ni m p o r t a n tp a r ti nd e s i g no fan e wg e n e r a t i o n o fn e t w o r kp r o t o c o l s ，n e t w o r km a n a g e m e n ta n dd i a g n o s i s ，d e s i g no fh i g hq u a l i t y r o u t e ra n di m p r o v e m e n to fq u a l i t yo fs e r v i c e ( q o s ) f r o mt h ep e r s p e c t i v eo fd i f f e r e n t t i m es c a l e sa n dd i f f e r e n tt i m es e r i e sm o d e l s ，t h i sp a p e rm o d e l sa n dp r e d i c t s 谢mt h e t r a f f i ct r a c ed a t aw h i c ha r et a k e nf r o mt h ei n t e m e tt r a f f i ca r c h i v ea n df r o mr e a l e n v i r o n m e n t t h i sp a p e ra l s oc o m p a r e st h ep r e d i c t i o np e r f o r m a n c eo fd i f f e r e n tt i m e s e r i e sm o d e l su n d e rd i f f e r e n tt i m es c a l e s b a s e do nt h ea n a l y s i so fr e s u l t so fa l lt h e e x p e r i m e n t s ，w ed r a wt h ec o n c l u s i o nt h a tt i m es e r i e sm o d e l sp r o d u c el a r g ep r e d i c t i o n e r r o ru n d e rs m a l l e rt i m es c a l e s ( m i l l i s e c o n da n ds e c o n d ) a n dp e r f o r m a n c ew e l lu n d e r 1 a r g e rt i m es c a l ef m i n u t e ) k e y w o r d s ：t r a f f i cp r e d i c t i o n ，t i m es e r i e sm o d e l s ，s e l f - s i m i l a r i t y , h u r s tp a r a m e t e r 浙江大学硕士学位论文图目录 图目录 图2 1 高斯白噪声及其自相关函数8 图3 1 具有不同h u r s t 参数值的时间序列2 6 图3 2 对5 0 组，每组2 0 0 0 个数据的高斯白噪声进行h u r s t 参数估计3 2 图3 3 对4 0 组，每组2 0 0 0 个数据的分形高斯噪声( h = o 8 ) 进行h u r s t 参数估 十3 3 图4 1 第一部分实验的仿真网络场景3 8 图4 2p a r e t o 流聚集的h u r s t 参数，传输层使用u d p 协议。4 0 图4 3 第二部分实验的仿真网络场景4 1 图5 1 不同时间尺度下的流量序列，从l o m s 到l o o s 时间尺度内都具有突发性 4 7 图5 2 序列的自相关函数图，5 个不同时间尺度的序列的自相关函数都呈渐近双 曲线形式递减。5 0 图5 3 序列t s 2 及其一阶差分后的自相关函数5 1 图5 4 平稳时序模型对流量序列进行一步预测的结果5 3 图5 5 平稳时序模型对流量序列的多步预测结果5 5 图5 6f a r i m a 模型一步预测值，图中实线为实际观察值，虚线为一步预测值5 8 图5 7f a r i m a 模型的2 0 步预测值5 9 图5 8b r a n d e i s 大学2 0 0 8 年3 月1 4 日中心路由器流量数据6 3 图5 9t s b 的自相关函数6 3 图5 1 0a r i m a 模型对t s b 的一步预测( 后1 0 0 个数据) 6 4 图5 1 1a r i m a 模型对t s b 的一步预测( 第1 0 1 2 0 0 个数据) 6 4 图5 1 2t s b 2 0 步预测值，左边的为高阶a r 对t s b ( 1 0 1 ：1 2 0 ) 的2 0 步预测，右 边为高阶a r 对t s b ( 1 7 9 ：1 9 8 ) 的2 0 步预测6 5 浙江人学硕上学位论文表目录 表目录 表4 1p a r e t o 流聚集的h u r s t 参数，传输层使用u d p 协议3 9 表4 2 仿真实验的网络参数及b c 链路流量的h u r s t 参数4 2 表5 1 不同时间尺度下的聚集序列( l b l t c p 3 ) 4 6 表5 2 不同时间尺度聚集序列的h u r s t 参数估计4 7 表5 - 3 时间序列的自相关函数4 8 表5 4 差分后序列的自相关函数值，显著性区间同表5 3 一5 1 表5 5 根据时间序列的特征拟合平稳时序模型5 2 表5 6 平稳时序模型一步预测的r m s e 和r r m s e 值5 3 表5 7 使用平稳时序模型进行多步预测的r m s e 与r r m s e 值。5 4 表5 8f a r i m a 模型拟合流量数据，并获得一步预测的r m s e 和r r m s e 5 7 表5 9 使用f a r i m a 模型进行多步预测的r m s e 与r r m s e 值5 8 表5 1 0 不同时间尺度的聚集序列( a u 9 8 9 ) 6 1 表5 1 1a r i m a 模型与f a r i m a 模型进行单步和多步预测的r m s e 值6 1 表5 1 2a r i m a 模型与f a r i m a 模型进行单步和多步预测的r r m s e 值6 2 表5 1 3 序列t s b 的多步预测结果6 5 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝鎏盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：古代机氏 签字日期：加哆年二月么日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘鲎可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 氏 导师签名： 签字日期：a - 口。8 年b 月b 日 签字日期：c p 年占月工日 浙江大学硕七学位论文第1 章绪论 1 1 研究背景 第1 章绪论 9 0 年代初，l e l a n d 等人通过对局域网的流量分析1 l 【2 l ，p a x s o n 和f l o y d 对万 维网( w o r l dw i d ew e b ) i p 业务流量进行研究【3 1 ，g a r e t t 和w i l l i n g e r 对v b rv i d e o 业务流量进行研列4 1 ，都发现了网络流量具有自相似特性，提出了实际网络流量 序列的自相关函数随着时间间隔的增大呈渐近双曲线衰减而非负指数衰减，网络 流量是具有长相关特性的。 随着计算机网络的不断发展，网络规模日益扩大，新应用不断涌现，网络流 量承载的数据已经涵盖了包括文本、语音、图像、视频、实时业务等各种各样的 信息，从而使网络流量特性呈现出更高的复杂性、突发性和分形特性。 自从分形【5 1 【6 j 【7 j 【踟概念由b b m a n d e l b r o t 于1 9 7 5 年在他的分形几何学中提出 以后，分形概念就被广泛运用到其他领域，包括计算机网络流量的分形特性。网 络流量的分形特性涉及自相似、多重分形、幂律、重尾分布等概念，通常是对网 络流量过程与其归一化后的时间尺度扩展过程进行统计分析。分形特性广泛存在 于各种类型数据网络的流量过程中，而且其尺度范围非常大。在很大时间尺度范 围内( 毫秒级和秒级) 都具有分形特性。在较大时间尺度上网络流量的分形特性 较明显，且相对容易理解，然而在小时间尺度上，网络流量的特性则表现出更强 的突变性、更高的复杂性和不确定性。 网络流量特性在网络协议设计、性能优化和网络设备研究等方面起着至关重 要的作用，因而网络流量特性及模型的研究长期以来受到研究人员的高度重视。 上个世纪7 0 年代，对网络流量特性的研究主要借鉴公众交换电话网( p s t n ) 的 泊松模型。8 0 年代伴随数据网络和w e b 应用的出现，网络流量特性发生了显著 变化，这使得原来的泊松模型已不能充分反映网络流量的高可变性。随着研究的 浙江人学硕十学位论文第l 章绪论 深入，逐渐引入了各种推广的泊松模型和其它的随机模型，但这些模型的共同特 点是只能描述流量序列的短相关性。 流量工程( t r a f f i ce n g i n e e r i n g ) 就是采用科学的原则对网络流量进行测量、 分析刻画和建模，寻找影响网络性能的特性，对网络流量实施控制，最终达到提 高和优化网络性能的目的。因此对流量特性进行分析刻画和建模是网络流量工程 的基础，是实现流量工程性能目标、优化网络性能的重要环节。 对网络流量进行建模是流量预测和控制、网络性能分析与提高的基础，建模 过程在于将一些相对次要的因素忽略，简洁、全面而准确地刻画出真实流量数据 中对网络性能有显著影响的主要因素。网络流量模型主要是基于时间序列模型的 建模，其中主要有短相关流量模型、长相关流量模型和多重分形流量模型。 在网络流量建模的基础上，进行网络流量预测对于设计新一代网络协议、网 络管理与诊断、设计高性能路由器和负载均衡器等网络硬件设备以及提高网络的 o o s 都具有重要意义。基于以上流量模型进行的预测各有利弊，因此对各种模型 进行深入研究，并分析其在实际网络流量预测中的性能和适用性具有重要的现实 意义。 1 2 研究内容 网络流量的自相似特性( 或分形特性) 被发现以后，人们在流量建模和预测 过程中都开始考虑自相似特性，深入理解网络流量的自相似特性对于流量建模和 预测都具有重要的指导性意义。 h u r s t 参数【9 1 表征了网络流量的自相似特性或者是突发特性，因此对网络流 量自相似特性的研究中，必须对网络流量的h u r s t 参数进行估计，本文对h u r s t 参数估计的各种方法，涉及时域、频域和小波三大类的估计方法进行了深入研究， 并使用这些方法对仿真数据和实测数据进行估计，在对估计结果进行分析的基础 上，比较各种估计方法的优劣，为鉴别网络流量自相似特性提供了较为可靠的分 2 浙江大学硕士学位论文第1 章绪论 析工具。 本文还通过网络仿真实验对网络流量的自相似特性和成因进行了研究和分 析，分别研究并验证了o n o f f 流聚集和t c p 协议的拥塞控制机制对网络流量自 相似特性的影响。 网络流量预测具有重要的现实意义，因此本文还深入研究各种了基于时间序 列模型的网络流量模型，并使用各种流量模型对实际流量数据进行建模和预测， 比较这些模型的优劣。 1 3 研究意义 深入研究了各种h u r s t 参数估计的理论方法，并用算法的形式具体化了这些 估计方法，在对比各种方法的基础上为h u r s t 参数估计方法的选择提供了指导性 建议，从而为较精确地估计h u r s t 参数，更好地认识和研究网络流量的自相似特 性提供了较为可靠的分析工具。 研究了网络流量自相似特性同o n o f f 流聚集以及t c p 协议的拥塞控制机制 的关系，使得对网络自相似特性的成因有了更加具体的认识。从理论上对基于时 间序列模型( 包括a r 、a r m a 、a r i m a 以及f a r i m a 模型) 的网络流量建模和预 测进行了深入阐述并在实践上基于这些模型进行流量预测，从不同时间尺度角度 以及不同流量模型角度对流量预测过程进行了对比分析，得出各个流量模型的适 用性，并在预测结果的基础上对各个模型的优劣进行了比较，这对网络流量预测 来说具有重要的实践意义。 1 4 论文组织 本文共分为六章。第二章介绍了时间序列理论，主要从平稳时间序列和非平 稳时间序列的角度介绍了常用的时间序列模型，再次基础上还介绍了基于时间序 列模型的时间序列预测方法，为基于时间序列模型的网络流量预测作方法论指导； 3 浙江人学硕士学位论文第1 章绪论 第三章介绍了分形理论和h u r s t 参数估计，从数学角度介绍自相似特性，从而为 更好地理解网络流量自相似特性铺路，该章还重点介绍了分形特性的h u r s t 参数 和h u r s t 参数的估计的各种方法( 包括时域、频域和小波三大类方法) ，并用实 验进行了对比分析，为识别网络流量自相似特性提供了较为可靠的分析工具；第 四章介绍了网络流量的自相似特性，在总结并分析了各种网络流量自相似特性成 因的基础上，用网络仿真实验对流量自相似特性进行了研究，基于仿真实验验证 了o n o f f 流聚集以及t c p 拥塞控制机制与流量自相似特性的关系；第五章介绍 了网络流量预测的各种方法，并使用a r 、m a 、a r m a 、a r i m a 和f a r i m a 模型对 网络流量序列进行建模和预测，分析了各个模型在不同时间尺度上对流量序列预 测的性能和准确度。并且通过实验发现时序模型对较大时间尺度( 分钟级) 的流 量序列具有较好的预测性能，而对于较小时间尺度( 毫秒、秒) 的流量序列预测 性能并不理想；第六章为总结和展望。 4 浙江大学硕上学位论文 第2 章时间序列理论 2 1 前言 第2 章时间序列理论 时间序列1 6 1 就是将某一个指标在不同时间上的不同数值，按照时间的先后顺 序排列而成的数列。这种数列由于受到各种偶然因素的影响，往往表现出某种随 机性，彼此之间存在着统计上的依赖关系。 时间序列是所研究系统的历史行为的客观记录，因而它包含了系统结构特征 及其运行规律。所以我们可以通过对时间序列的研究来认识所研究系统的结构特 征( 如周期波动的周期、振幅、趋势的种类等) ；揭示其运行规律，进而用以预 测、控制其未来行为；修正和重新设计系统( 如改变其周期、参数) ，使之按照 新的结构运行。 时间序列具有如下特点：首先，序列中的数据或数据点的位置的严格函依 赖于时间，即数据的取值依赖于时间的变化，但不一定是时间数。其次，每一时 刻上的取值或数据点的位置具有一定的随机性，不可能完全准确地用历史值预测。 再次，前后时刻( 不一定是相邻时刻) 的数值或数据点的位置有一定的相关性， 这种相关性就是系统的动态规律性。最后，从整体上看，时间序列往往呈现某种 趋势性或出现周期性变化的现象。 时间序列根据所研究的依据不同，可有不同的分类：按照研究的对象的数目 分，有一元时间序列和多元时间序列；按照时间的连续性分类，有离散时间序列 和连续时间序列；按照序列的统计特性分，有平稳时间序列和非平稳时间序列两 类。按序列的分布规律来分，有高斯型时间序列和非高斯型时间序列，服从高斯 分布( 正态分布) 的时间序列叫做高斯型时间序列，否则叫做非高斯型时间序列。 2 2 平稳时间序列 平稳随机过程：统计特性不随时间的推移而变化的随机过程。有相当多的随 5 浙江大学硕上学位论文第2 章时问序列理论 机过程，不仅它现在的状态，而且它过去的状态，都对未来状态的发生有着很强 的影响。严格地说，如果对于任意的7 l = 1 , 2 ，t 1 ，t 2 ，t n t 和任意实数 ， 当t 1 + h ，t z + 也，t n + j l t 时，维随机变量： ( c 1 ) ，x ( t 2 ) 一，x ( k ) ) 与 ( x ( 亡1 + ) ，x c t 2 + ，1 ) ，x ( t n + j f l ) ) 具有相同的分布函数，则称随机过程弘( 亡) ，t 7 ) 具有平稳性，并同时称此过程 为平稳随机过程，简称平稳过程。这是严格意义上的平稳。 平稳时间序列就是平稳随机过程的一个实现，其直观意义就是序列中不存在 任何趋势性和周期性，其统计意义就是一阶矩为常数，二阶矩存在且为时间间隔 t 的函数。平稳时间序列表明该序列的前期演变过程的统计相关规律在未来的一 段时间内是不变的，也就是说序列的数学期望和方差是不随时间变化的，而且序 列的相关函数只与时间间隔有关而与时间无关。 严平稳和宽平稳：严平稳是一种条件比较苛刻的平稳性定义，它认为只有序 列的所有统计性质都不会随着时间的推移而发生变化是，该序列才被认为是平稳 的。宽平稳是使用序列的特征统计量来定义的一种平稳性。它认为序列的统计性 质主要由它的低阶矩决定，所以只要保证序列低阶矩( 二阶) 平稳，就能保证序 列的主要性质近似稳定。 满足如下条件的序列成为宽平稳序列： 1 e x 0 0 v t t 2 ) e x t = 睢v t t 3 ，r ( t ，s ) = r ( k ，k + s c ) ，v t ，sk ，k + s t t 平稳时间序列的统计性质：常数均值；自协方差函数和自相关函数只依赖于 时间的延迟长度而与时间的起止点无关。样本统计性质如下： 样本均值： 6 浙江大学硕士学位论文第2 章时间序列理论 口= 元= 丢冬。托 公式( 2 1 ) 样本自协方差： 矿( 足) = i i i 厶y n c ：- 1 k t n v c 一) 0 k + 七一弘) ，0 艮 礼 公式( 2 2 ) 样本自相关函数：耻鬻= 鼍料，o 1 时，预测值满足模型差分方程形式的自回归部分 爱( f ) 一妒1 ( f 一1 ) = 0 从而，2 1 时，预测值为 盅( f ) = ( x t 一象口c ) 妒i 公式( 2 4 3 ) 可以看出，如果把预测值& ( f ) 看作2 的函数，则预测函数的形式是由模型的 自回归部分决定的，滑动平均部分用于确定预测函数中的待定系数，使得预测函 数“适应 于观测数据。 1 m a ( 1 ) 模型 x t = a c 一8 1 a t 一1 是( 1 ) = f , ( x t + 1 ) = e ( 口c + 1 一日1 c l c ) = 一日1 口c公式( 2 4 4 ) 其中d c = 鼍一戈卜1 ( 1 ) = x t + 8 1 # l c + 1 可以递推算出。 & ( 2 ) = e ( x c + 2 ) = e ( a t + 2 一日1 口t + 1 ) = 0 一般地，有 浙江大学硕上学位论文第2 章时间序列理论 贾c ( 1 ) = 0( f 2 )公式1 2 4 s ) 类似地，对于m a ( m ) 模型而言超过m 步的预测值均为零，这与m a 序列的 短记忆性是吻合的。 2 4 1 3a r m a 模型预测的一般结果 a r m a 模型的表达式见公式( 2 1 6 ) ，l 司样地，我们按照求解条件期望的方式 求序列噩的向前f 步预测值震( f ) 。求解过程使用递归方式逐一求出丘，= 1 ，2 ，3 ，f 一1 ，最终求出霄c ( f ) 。具体计算过程如下所示： ( 1 ) = e ( x t + 1 ) = e ( 妒1 x t +