（模式识别与智能系统专业论文）网络业务量自相似性相关问题研究.pdf

摘要 摘要 近年来，对大量网络业务流的研究发现，真实网络、i k 务是有 自相似特性的，它严重影响到网络的流量控制和传输控制，尤其 在网络语音、视频业务的大量涌现后，对网络的服务质量提出了 更严峻的挑战，对网络自相似业务的检测、建模、排队分析已成 为迫切的需求。 本文首先讨论了现有网络流量的自相似现象建模的主要工 作，在给出了自相似的相关定义及其性质后，本文总结了自相似 网络模型、自相似序列h u r s t 参数估计方法以及自相似业务量预 测模型，分析了它们各自的特点。 论文提出了一种新的h u r s t 参数估计方法，即根据自相似过 程的自相关结构，推导出h u r s t 参数的迭代计算公式，证明了该 计算公式的收敛性。将该方法分别在分形高斯噪声和真实网络业 务数据上做了实验，结果表明，该方法在保证估计精度的情况下， 具有估计置信区间小，估计。速度快的特点。另外，该方法的迭代 特性特别适合将其应用于在线h u r s t 参数估计当中，论文电做了 这方面的仿真实验。 丈章最后分析了自相似网络业务形成的原冈，应用层文件大 小、连接时间等的重尾分布，以及网络层和传输层卧议的内在机 制都是导致业务流呈现自相似现象的原因。总结了现有的摹于流 量预测的网络控制技术，提出自相似参数可能会成为以后网络控 制的重要指标。 关键词：自相似迭代算法 h u r s t 网络控制 北京交通人学硕士学位沦文 a b s t r a c t r e c e n t l y s e l f - s i m i l a r i t yi sf b u n di nv a r i o u sn e t w o r kt r a f f i c i t a 丘、c c tt h en e t w o r kp e r f o m a n c es e r i o u s l y ，t h en a t u r ec h a l l e n g et ot h e q u a l i t yo fs e r v i c eg r e a t l y i nt h i s a n i c l e ， a f t e rt h ed e f i n i t i o n so f s e l f s i m i l a r i t y a n d l o n g - r a n g ed 印e n d e n c e ( u t d ) ，w ed i s c u s sh d wt oe s t i m a t ei t sh u r s t p a r 砌e t e fo fas e l f - s i m i l a rp r o c e s s w et h e ni n t r o d u c et h es e l f s i m i l a r n e t w o r kt r a 埘cm o d e l sa n dt r a f ! f _ i cp r e d i c t i o nm o d e l s c h a r a c t e r i s t i c o ft h em o d e l s 盯eg i v e a l s o w ep r e s e man o v e lh u r s tp a r a m e t e re s t i m a t j o nm e t h o d ，d e d u c e a ni t e r a t v ef b n t l u l at oe s t i m a t eh u r s tp a r a m e t e ri nt e n so f c o h e l a t i o ns t n l c t u r eo fs e l f - s i m i l a r p m c e s s c b n v e r g e i l c eo ft h e f b 瑚u l ai sp m v e d 1 1 1 e nw ea p p l yt h em e t h o dt of r a c t i o n a lg a u s s n o i s e 锄dr e a ln e t w o r kt r a 彤c ，e x p e r i m e n td e m o n s t r a t e st h a tt h i s m e t h o di sm u c hf a s t e ra n dh a ds m a l l e rc o n f j d e n c ei n t e a lc o m p a r e d w j t ht r a d i i j o n a lm e t h o d s i na d d i t i o n ，w ea l s oa p p l yt h em e t h o dt o o n l i n eh u r s te s t i m a t i o n i nt h ee n d ， w e 百v et h e r e a s o n so f s e l f _ s i m i l a r i t yn a t u r e o f n e m o r kt r a f f i c ，t h e s ei n c l u d eh e a v y t a i l e dd i s t f i b u t i o no ff i l es i z ea n d a c t i v et i m eo na p p l i c a t i o nl a y e r ，a n di n t r i n s i cf a c t o ro ft r a n s p o r t p r o t o c 0 1o nn e t w o r kl a y e lw es u m m a r i z e dc u r r e n tn e t w o r kc o n t r 0 1 m e t h o db a s e do nt r a f f i cp r e d i c t i o n ，a n dp o i n to u tt h a th u t s tp a r a m e i e r i sl j k e l yt ob ea ni n l p o n a n ti n d e xf b fn e t w o r kc o n t r 0 1 k e yw o r d s ：s e i f _ s i m a r ，h u r s t ，i t e r a t i v e ，n e t w o r kc o n t m l i i 独创性声明 y 8 7 9 8 9 1 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或证书而使用过的 材料。与我一起工作的同志对本研究所做的任何贡献已 在论文中作了明确的说明并表示了谢意。 本人签名：芗7 j 哼 1 = 二f 剃：堕年三月止h 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学计算机与信息技 术学院所有。未经许可，任何单位和个人不得拷贝。版 权所有，违者必究。 本人签名： 垄楚箜 日期：旦年三月监日 绪论 第1 章绪论 1 1 网络业务量研究的意义和研究现状 随着宽带网络服务需求( 如多媒体、视频业务等) 的激增，高速 网络传输技术成为目前网络研究的热点。要想对网络业务拥塞控 制、信息监测、带宽分配及网络性能评价等问题进行进一步的研 究，建立一个能准确描述网络业务( t r a “i c ) 的模型是就是首先要 解决的问题之一。 多年来，网络流量特性的研究一直使用p o i s s o n 模型，即包的 到达过程是无记记的，包的到达间隔服从指数分布。随着研究的 深入逐渐引入了各种推广的p o i s s o n 过程和其它的随机模型，这些 模型均认为，若s 足够大，当前时间t 的业务量和t s 时刻的业务量 是不相关的，也就是说仅考虑s 较小时业务到达间的相关性，即业 务量是短相关( s h o r t r a n g ed e p e n d e n c e ) 的，这意味着业务量序 列的自相关性随着时间间隔增大呈指数衰减，而研究表明这些模 型表现出的行为与实际网络的测量结果不符， 近年来研究结果表明：实际网络业务普遍存在统计上的自相似 性，而该特性与业务发生的时间地点或信元编码方式无关。其中， 从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 研究工程中心的几个 以太网段的不同位置上收集了数百万个实际传输的数据包。通过 对大量实际业务数据的分析，他们发现：这种聚集的网络业务所表 现的统计自相似性完全不同于传统的业务模型。实际网络业务序 列的自相关函数随间隔增大呈双曲函数衰减，从而是长相关的 北京交通大学硕士学位论文 ( l o n g r a n g ed e p e n d e n c e ) 。自l e l a n d 对b e u c o r e 的局域网的测试 与分析结果发表后 1 】，又有许多针对其他网络的测量如w a n 【2 1 ， v b r 【3 l ，w 耐4 】等，这些结果均表明实际网络业务流具有长相关性。 自此之后，网络流量研究进入了一个新的历史阶段，在此后近1 0 多年的时间内，自相似( s e l f s i m i l a “t y ) 、长相关、重尾分布 ( h e a v y t a i l e d ) 、分形( f r a c t a l ) 以及多重分形( m u l t i f r a c t a l ) 等概念下的流量模型以及其框架下的相关研究一片繁荣。我国相 关学者在这方面也有一些研究进展，这方面的研究也被列入了“网 络与信息安全”重大研究计划课题范围【”。 网络的自相似特性突出的表现为：( 1 ) 突发( b u 墙t i n e s s ) 没有 明确的长度，在不同的时间尺度下表现出相同的突发特性，随着 时间尺度的增大突发不能被平滑掉。而传统模型一般是基于 p o i s s o n 模型的，它的突发特性会随着时间尺度的增加而被平滑掉， 见图1 1 。( 2 ) 业务量的相关性会随着时间间隔的增加而衰减， 但是远比p o i s s 帅模型的指数衰减要慢，这种长记忆性必须在业 务量模型中体现出来。 网络流量的自相似特性将给网络测量和网络设计带来深远的 影响，传统的网络设计、性能分析等都是基于p o i s s o n 模型，而 该模型并不能体现流量的自相似特性。研究表明，流量的自相似 特性对网络有着显著影响，包括排队时延和丢包率激增、网络性 能显著劣化等。因此，研究能准确刻画自相似特性的数学模型及 其相关问题已经成为业务量研究领域的热门课题。 2 绪论 图1 1 自相似业务量与p o i s s o n 业务量 1 2 传统的业务量模型 流量模型是流量预测和性能分析的基础，流量模型的建模应 该尽量考虑以下几个方面： ( 1 ) 真实。眭。流量模型应该尽可能的刻画流量数据的统计特性。 ( 2 ) 理论| 生。模型应该具有明显物理意义，较强的可分析性。 ( 3 ) 简单性。模型应该具有尽量少的参数，而且参数要有直观的意义。 ( 4 ) 通用性。不同种业务可能有不同的流量特性，流量模型要适合尽 可能多的业务种类，或者能用某一个参数来代表业务的种类。 ( 5 ) 易仿真性。模型要易于从计算机上进行仿真。 一般的模型很难保证同时满足上述要求，比如复杂的模型可 以较好的刻画流量特性，但模型参数就会很多，而且这些参数一 般都不容易进行估计；或者说对某一种业务有了较好的模型来刻 画它，当应用于另外一种业务时就会出现较大的误差。所以建立 3 北京交通大学硕士学位论文 模型往往需要在各个条件之间做一个折衷。 传统的业务量模型指的是非自相似的模型，它们与自相似的 长相关性相对，是短相关的。下面我们对常见的几种传统业务量 模型做一个简单的介绍； 1 2 1 更新业务模型 在更新业务模型中【6 】，到达间隔时间随机过程置独立同分布， 其自相关函数对于任意非零滞后都消失为o ，因此无法描述真实业 务量的突发现象。它的两个特例是泊松过程与贝努里过程。贝努 里过程假设到达间隔时间随机过程x ，是一个离散变量，服从几何 分布。根据泊松过程，我们可以得到在指定时间f ，0 内到达个数 为n 的概率为： p ( x o + f ) 一y o ) ) ：，l ：。一z r 生! ! ：e( 1 1 ) x “) 表示t 时涮内累计到达个数，a 为平均到达速率。在泊松 过程中，两个互不相交时间段内到达的随机数之间是互相独立的。 泊松分布具有非常优美的数学特性： ( 1 ) 时间间隔r 。是独立同分布的，服从指数分布 p ( l o 。5 ，而对于一般的短相关过程有圩i o 5 。这一现象 后来被称为h u r s t 现象。 同样在其他领域的研究中也发现了自相似现象的存在，例如在 经济、物理、生物等领域中。具体点说如股市的涨跌中、地震分 布上、自然风景中、海流中、湍流中、泥沙的沉积和树的年轮分 布上也都存在自相似现象，说明自相似现象在自然晃是广泛存在 的。近年来在网络通信量领域的研究也大量发现了自相似现象的 存在。 自相似业务相关概念 2 _ 2 自相似随机过程的定义 自相似性( s e l f s i m i l a r i t y ) 是指系统在某种测度的不同尺度 上表现出相似的特征，它在本质上是系统尺度行为( s c a l i n g b e h a y i o r ) 的一种特例。事实上，自相似( 与单分形等同) 、长程 相关( l r d ) 和多分形都可以在尺度行为的框架内得到统一，只不 过，在网络行为领域，以自相似特征最为显著，影响最大。在不 同的角度，对自相似行为可以有不同的描述手段，如频域内的l ， 噪声、时域内的l r d 分布等等，它们有密切联系而又有细节差别【l o l 。 本文采用基于空域尺度变换观点的自相似定义，并且对自相似和 长相关不加区分。 定义1 【1 1 考查一广义平稳过程以，n = 1 ，2 ，3 ，描述网络 流量时置可以表示第t 个单位时间内到达的网络业务量( 比特 数、包数) 等。记 = e 隅】 ( 2 2 ) 盯2 = i 么r 【五】= e 【( 五一肛) 2 】 ( 2 3 ) 数。 r ) = c d v 隅，置+ t ) = e 【伐一肛) + t 一肛) 】 ( 2 4 ) p ) = r o ，f + t ) ；c b v ( x ，五+ k ) 盯2 = y 他) 盯2 ( 2 5 ) 分别代表随机过程x 。的均值、方差、自相关函数、自相关系 若随机过程e 的统计特性( 如一阶统计指标口和二阶统计指 标仃2 ) 不随时间变化，则称之为“平稳”的。由此可见，自相似 北京交通大学硕士学位论文 过程在本质上是非平稳的，因为其统计指标会随着时间的变化而 不同，对平稳过程而言，p 和仃2 是最重要的统计指标，但对白相 似过程而言，和仃2 的意义不大，需引入新的统计量进行描述。 定义2 【圳对于一个时间序列x = 以，捍。0 ，1 ，2 ) ，首先定 义其小重归并时间序列盖似- 叫，n 一0 1 ，2 ) 是将原时间序列分 成大小为珊、互不重叠的数据块，然后分别计算各块的平均值所得 的序列，即： 1l m 掣；土墨 ( 2 6 ) 朋女翩- 1 1 “ 、 它的女阶自相关系数记为矿北) 。 定义3 【l l l 广义平稳的离散随机过程x 。称为严格自相似的， 如果其卅阶聚集过程矗”与原过程量。有相同的自相关系数结 构，即矿( t ) = p ) ，对所有的m ( = 1 ，2 ，3 ，) 都成立。若m o 。 时此式成立，则称x 。为渐进自相似的。 自相似过程的自相关系数满足： p ) ；三( + 1 ) ”一拍2 h + ( t 一1 ) 2 ”) 口日( 2 h 一1 冲2 ”一2 七，。( 2 7 ) 其中h 为h u r s t 参数或自相似参数，它是描述随机过程自相 似程度的唯一参数。h 有3 个不同物理意义的取值范围，0 5 ( k 1 表示负相关，0 5 日 1 为正相关，月r - o 5 表示没有相关性。实际 网络业务是正相关的，所以h 的取值范围是( o 5 ，1 ) ，h 越大，过 自相似业务相关概念 程自相似程度越高，突发也就越剧烈。 自相似过程的最重要特征是：自相似过程的聚集过程依然有 着较大的突发( b u 硌t i n e s s ) 当m m 时，聚集过程x ：m 的自相关 结构并不退化，传统业务模型则不同，当m 一* ，聚集过程z 1 4 的自相关结构将退化，即矿 ) 一0 ，当k = 1 ，2 ，3 ，。 2 3 自相似的相关性质 2 3 1 长相关( l o n g - r a n g ed e p e n d e n c e ) 长相关性是相对于短相关性( s h o r t r a n g ed e p e n d e n c e ) 的。 在p o i s s o n 或g a u s s 过程中，k 阶自协方差函数一般都至少具有和 指数衰减一样迅速的尾巴，即： y ( 七) 口口，七一，0 口 1 ( 2 8 ) 这种性质成为短程相关性，它说明样本之间的相关特性只在 一定范围内存在，随着k 的增大，相关性减小的很快。 相对短相关而言，长相关的自协方差衰减的就慢多了，它的 自相关系数满足式( 2 7 ) ，k 阶自协方差函数满足式( 2 9 ) ： y ( 七) 口i 七r “，七一o o ，o 口 1( 2 9 ) 图2 1指数衰减与双曲线衰减 北京交通大学硕士学位论文 图2 1 分别是指数分布和双曲线分布的自相关函数与阶数k 的关系图，可以看出，随着k 的增大，它的自相关性迅速衰减； 而双曲线分布的衰减速度要比指数分布的衰减速度慢的多。显然， 满足式( 2 9 ) 的自协方差函数是不可求和的，即r ) = o 。( 或 p ) = o 。) ，正是长相关的含义，这说明随着k 的增大，样本间的 相关性虽然在减小，但是不会像指数衰减那样忽略不计，而是必 须要考虑的。 2 3 2 重尾分布m e a v y - 髓i l e dd i s t r m u 6 0 n ) 长相关表明在时间间隔上相差很远的两个样本的相关性不可 忽略，而造成这种性质的一个重要原因就在于某些元素以不可忽 略的概率出现非常大的值。即我们通常所说的重尾( h e a v y t a i l c d ) 特性。 称随机变量x 满足重尾分布，如果x 的概率分布函数满足： p ( x o 为方差系数，z 。为标 准的分数布朗运动，且其自相似系数满足0 5 h 1 。 由于f 酬有其良好的性质，现已成为统计自相似过程的经典算 法之一。产生分数布朗运动的算法很多，快速算法主要是随机中 1 6 自相似业务相关概念 点置换( r a n d o mm i d p o i n td i s p l a c e m e n t ，r m d ) 方法【切，它通过不 断地分割间隔来产生样本值。每次分割时，利用一个高斯置换来 确定子间隔中点的样本值。通过高斯置换方差的标度变化，可以 产生自相似性。这种方法的优点是计算速度快，而缺点是只能产 生渐进自相似过程。 另一种方法通过对分形高斯噪声的频谱进行快速f o u r i e r 逆变 换获得业务数据，此方法生成的业务源h u r s t 系数具有较好的一致 性，而且业务数据样本的边际分布非常接近高斯分布。而缺点是 多数真实业务源在很短的时间间隔下具有与分形高斯过程不同的 相关结构，此方法无法兼顾真实业务源在不同时间尺度下完整的 相关函数结构 2 4 2 渊m a 模型 丛r i m a ( p ，d ，q ) 模型最初由g 豫g e r 和j o y e n n 【18 】以及 h o s k i n 一1 q 提出。它是d 取分数的a r i m a ( p ，d ，q ) 过程，o d t ) = t 一。，t - ，1 乜 2( 2 - 1 7 ) 即f 和疗均服从p a r c l o 分布，它是一种典型的重尾分布，具 自相似业务相关概念 有有限均值口一e 【x 】 1 ) 阶消失矩，即 f 。，妒。坤；o ，r = o l ”皿一1 ( 2 _ 2 1 ) 且小波系数 ) 是零均值互不相关的随机变量，具有方差 妇r c ? = 口2 2 ”。其中，参数y 满足o tr t2 r 。则z ( f ) 具有功率 谱为： s ，( m ) = 。2 2 1 ”l 且是 ) 是近似l ，或称广义1 ，的。 ( 2 2 2 ) 该模型可以通过选择合适的小波基、合适的系数以及在小波 级数展开中保留足够多项，则其功率谱在理论上可以任意接近幂 律，而功率谱满足幂律这种形式的随机过程是自相似的【捌。 小波模型通过伸缩和平移运算对信号进行多尺度分析，这与 自相似业务的多尺度特征是类似的。在真实业务中，自相似业务 还表现出多重分形的特征，这也是其他数学工具很难解决的难题， 而小波变换分析正是针对这类信号的强有力的工具。 2 0 自相似业务相关概念 2 4 5 基于混沌映射的业务模型 该法充分利用非线性系统的类分形行为。其基本思想是将非 线性系统的不同部分的状态空间与不同的到达分布联系起来， p r u t h i 提出在区间 o ，1 上的“双混合映射”可以产生长相关业 务量。该法从任意开始，序列矗可以由下列方式递归产生： 吒【0 ，d ) ( 2 2 3 ) 【d ，1 ) 五( z ) 2 i r 二i 南，c 2 d 1 一m t 一1 ( 2 2 4 ) ，2 “) = 1 1 一工 矿i i 妒巳 = ( 1 一d ) 1 一“：一1 ( 2 2 5 ) 且o d d ( 2 2 6 ) 当y 。2 1 时为o n 周期，一次产生由个分组或信元，y 。= 0 时为 0 f f 周期。 m ，柳2 分别定义0 f f 和o n 周期分布的拖尾行为，当；珊2 ；1 时，二者皆为几何分布。而3 2 c c2 对应于有限均值与无限方 差，从而得到一长相关过程。p r u t h i 证明，在3 2 c m 。c 2 ，鸭；1 时，所得业务量序列的h u r s t 参数为：h - 眠一4 ) ( 2 卅：一2 ) 。 北京交通大学硕士学位论文 混沌映射法的优点在于其确定性的表达形式便于对系统的排 队性能进行分析。但此法生成的业务量具有一致自相似特性的时 间尺度与门限d 的选取有关，并且，业务源的其他特征参数也不 易提取。 2 5 自相似h u r s t 参数的估计方法 我们已经知道，h u r s t 参数是描述随机过程自相似程度的唯一 参数。当且仅当随机过程的h u f s t 参数落在( 0 5 ，1 ) 之间时，称该随 机过程是自相似的。并且，h u r s t 参数越接近1 ，自相似程度越高， 突发性也就越强。在前面提到的自相似模型当中，h u r s t 参数也都 是模型直接或问接的参数。因此，如何准确、快速的估计h u r s t 参数对于分析随机过程的自相似性、自相似模型的参数估计都有 重要的作用。 下面先对现有的h u r s t 参数估计方法做一介绍，下一章将重点 描述一种h u r s t 参数的迭代估计算法，它与现有的算法相比在估 计速度和估计稳定性上都有明显的改善。 2 5 1 方差时间图 前面提到对于自相似过程的聚集时间序列x ( ，当m 很大时 其方差服从： 肠r 佃) 口堕粤 ( 2 - 2 7 ) 卅 其中自相似参数日( 1 一卢) 2 。对两边取对数，有 l o g f 妇，岱“) 】口l o g 【妇r 晖) 卜卢l o g 胁】 ( 2 2 8 ) 因为l o g 【妇，( 置) 】是独立于埘的常数，如果画出1 0 9 【肠r 扣) 】 自相似业务相关概念 和i o g 陋】的关系图，结果应该是一条斜率为一卢的直线。实际当中 的做法通常是通过产生不同聚集级别肌的聚集过程，并将它的方 差绘制到对数图上，再对所有的点进行线形拟合，求出斜率一口， 再根据公式h 一1 一口2 求出h u r s t 参数的估计值。 这种方法的优点是计算简单，但一般来讲偏差比较大，通常 用于检验一个过程是否是自相似过程，而不直接作为精确估计自 相似程度的标准。 2 5 2 刚s 图 对于在离散时刻取值的随机过程x ( f ) ，x o ) 在时间段上重 整化范围定义为比率r s ： r s ( 2 2 9 ) 其中m ( n ) 是在时间段n 上的样本均值： m ( ) 2 专善- 2 _ 3 0 r s 表达式中的分子是过程变化范围的度量，而分母是样本标 准差。对于一个自相似过程，这一比率在很大时有下列特性： 月s 口( 2 ) 8 ( 2 3 1 ) 两边取对数，有 l o g 【r s 】口h l o g 【2 】( 2 - 3 2 ) 和方差时间图做法一样，对于不同的_ v 值，将r s 与n 2 的 北京交通大学硕士学位论文 关系画到一张对数图上，再对所有的点做线形拟合，得到一条斜 率为日的直线。 2 5 3 周期图法( p e r i o d o g 豫mm e 恤o d ) 前面介绍了都是从时域上估计出参数日的方法，周期图法 则从频域的角度来得到参数日值。周期图定义为 ，= 击黔e 巾i p s ， 在序列存在方差的情况下，f 沏) 代表了序列x 的功率谱密度，因 此如果它具有长程相关性，它就应该在原点处具有训“的形式， 其中d = h o 5 。因此，如果我们使用l o 争l o g 坐标来分析一个序 列的功率谱密度，如果这个序列是自相似的，即长相关的，我们 就可以得到功率谱的对数和频率的对数满足线性的关系，由这个 线性关系的斜率可以得到参数日。 周期图法抛弃了时域中存在的大量无规则的变化，而利用了 频域中功率谱相对稳定的特性，实践证明它是几种绘图分析法中 最准确的一种。同时，它还具有不受方差是否存在所约束的优点。 因此，周期图经常使用在准确估计参数h 的场合中。但是它的实 现方法相对比较复杂。 2 5 4w h i 砌e 估计器法 前面几种方法都没有给出置信区间。如果需要估计的序列或 者过程的形式是已知的，例如它是一个分形布朗运动过程，我们 可以假定它的功率谱密度为s ，h ) ，其中谱密度的形式是已知 自相似业务相关概念 的而h 未知，可证明，我们可以通过使下面的式子最小化来得到 h 的估计值： l ；器珊 ( 2 3 4 ) ，) 表示通过样本估计值得到的功率谱密度，而s 扣，日) 表示 已知的功率谱密度的形式。如果序列长度为，那么上式积分就 可以转化为频域上甜；等，等，2 丌 的离散求和。这种方法的 一个优点是它不仅可以很方便的得到h 的估计值，而且可以据此 计算出置信区间。这是因为这种估计器是渐近正态的，样本方差 表示为： 岫勘e ( 塑掣) 2 d m 】_ l p s s ， 虽然w h i t t l e 估计器法能够比较准确的估计出来参数h 的值， 并且给出置信空问，但是它的一个最明显的缺点就在于它假设序 列是自相似过程。所以一般是先用方差时间图法或者列s 法测试 一个时间序列是自相似的，然后再用w h i t t l e 估值法估计h u r s t 的 精确值。 2 5 5 小波分析法 由于小波分析在分析信号处理和分型参数估计中显示出其多 分辨率时频分析的独特优势，因此，基于小波变换的h u t s t 参数 估计方法可以适应于各个观察尺度。比较有名的一种小波分析估 计法是e m 方法，它可以在加性白噪声下估计信号的分形参数。 e m 方法是一种迭代算法且基于最大似然准则，但要求信号在不 同的尺度下的分形参数具有一致性。另外，还存在一种基于 北京交通大学硕士学位论文 f o u r i e f 变换和小波分解辨识信号分形特征的方法，可以用来检测 业务数据在不同观察尺度下m r s t 参数是否一致，此方法能排除 噪声的干扰，而且不局限于分型高斯噪声或分形布朗运动的检测。 自从1 9 9 8 年a b r y 等人第一次提出基于小波变换的方法估计 h u 斌参数之后【2 4 】，国内外众多研究人员提出了各种各样的小波 分析的估计方法1 2 5 ，拍1 。基于小波的分析方法可以对样本序列在不 同时间尺度下的h u r s t 参数变化做一致性分析。如果一致性较好， 则估计精度较高。若一致性较差，则小波方法能捕捉h u r s t 参数 在不同尺度下变化的特征，即基于小波分析的多重分形分析。而 且它可以在较少估计样本的情况下得到精确的估计值，基于这些 优点，小波分析的方法一直是研究人员的重点。本论文在第三章 将提出一种快速h u f s t 参数估计算法，它在网络流量的自相似特 性明显于多重分形特性时，比小波方法有着明显的优势。 自相似 岫指数的快速迭代估计算法 第3 章自相似h u r s t 指数的快速迭代估计算法 第2 章我们叙述了现有的h u r s t 指数的估计方法，在他们当中， 时域分析法一般具有较快的估计速度，但是糖度较差。以小波分 析为代表的频域分析法具有较高的估计精度，但是估计速度比较 慢。本章提出一种基于自相似过程自相关结构的h u r s t 指数估计 算法，它是一种时域的分析方法，通过和小波估计方法比较，该 方法有精度高、估计置信区b j 小、估计速度快等特点。在对估计 稳定性，估计速度要求比较高的应用，比如基于在线h u r s t 指数 估计的网络控制和性能分析等方面有着突出的贡献。 f 面首先介绍分形高斯噪声数据( f g n ) 的产生算法，因为 f g n 数据是严格白相似的，所以在后面我们都利用f g n 数据来 对估计方法进行验证评价。用m a t l a b 产生了h u i s t 值分别为0 5 ， o - 6 ，0 7 ，o7 5 ，o 8 ，0 1 8 5 ，0 9 ，o ，9 5 等分形高斯噪声数据，每 个h u r s t 值产乍1 0 0 组数据，用来防【 偶然性带来的误差，估计 算法的稳定性。第二节对该算法进行详细的描述和数学证明，第 三节将该算法应用于分形高斯噪声( f g n ) 数据和真实网络流量数 据，并将估计性能与小波估计方法做了全面的比较。 3 1 分形高斯噪声数据 分形高斯噪声是分形布朗运动的增量过程，它是严格的自相 似过程，它具有严格自相似过程的自相关结构： 1 p ( 七) * 妄( ( 七+ 1 ) “一2 七”+ ( 七一1 ) “) ( 3 1 ) 要产生特定h 值的f g n 序列的过程如下： 要产生特定h 值的f g n 序列的过程如下： 北京交通大学硕士学位论文 l ，根据公式( 3 1 ) 我们可以算出f g n 序列的k 阶自相关 系数以( k = 1 ，2 n 一1 ) ，n 代表序列样本数。 2 因为自相关矩阵是对称的t o e p l i t z 矩阵，所以在 m a t l a b 中用t o e p l i t z 命令可以生成自相关系数为 以 的自相关矩阵r 。 3 x = m v n r n d ( z e r o s ( 1 ，n ) ，r ，l ) 命令用于生成均值为o ，自 相关矩阵为r 的随机序列，为减小随机性带来的误差， 对每一个h u r s t 值，产生l 个这样的随机序列，实验中 利用l 个序列估计值的均值作为最终估计的结果。这样 x 就是一个l 行，x 列的矩阵。 实验中我们取n = 4 0 0 0 ，l = 1 0 0 ，产生了h u r s t 值分别为0 5 ， 0 ，6 ，o 7 ，o 7 5 ，o 8 ，0 8 5 ，o 9 ，0 9 5 八组数据，每组数据 1 0 0 个( 实现) 随机序列。图3 一l 为生成的h u r s t 值为o 8 5 的一次实现，可以看出它是典型的自相似过程。 05 0 01 0 0 01 锄砌踟3 0 0 03 5 0 0 4 0 0 0 自相似h l l r s t 指数的快速迭代估计算法 3 2 算法介绍 图3 1h l l f s t 指数为0 8 5 的分数噪声数据 网络流量序列置是自相似的，其中墨表示在第f 个时间周期 内网络的业务量( 早节数、包数量等) ，则其自相关函数见应该 满足公式 p ) ；去( + 1 ) ”一驰2 ”+ 一1 ) 2 “) 口日( 2 h 一毗2 “2 ( 3 2 ) 对该式进行变换有 p k ；h q h q k 拍_ 等成= ( 2 h 2 一日) 七2 肌2 辛凤七2 2 日+ 日= 2 2 ( 3 - 3 ) 穹= ( 风七2 2 仃+ 日) o 5 由上式可以得到日的迭代计算公式： q + l = ( 以足2 。2 啊+ e ) o 5七一 ( 3 4 ) 对于给定的样本序列置，x ：并。，令 应= i 2 寺善置， 九= 击喜( 置咧司 1 ， 以及反：拿 后；o ，1 ， y o 分别代表样本均值，样本协方差和样本自相关函划明。 在式( 3 - 4 ) 中利用样本自相关函数a 代替风，有h u r s t 参数 2 日 北京交通大学硕士学位论文 的迭代估计公式： 毫+ 。= ( a 豇2 。2 鱼+ 毫) o 5 七一( 3 _ 5 ) 对于长相关过程，设初值矾；o 5 。这样，我们就可以根据随 机的k 阶样本自相关系数容易的估计出该过程的自相关程度。 公式( 3 5 ) 中七取任意值都可以得出h u r s t 的估计值，现在 分析七取何值时会有较好的估计性能。用第一节中的8 组数据做 实验，我们分别分析了k 取1 ，3 ，5 ，1 0 时的h u 瑙t 估计值，估 计结果如表3 1 ： 表3 1 女取不同值时的估计精度 h七= 1七；3七= 5七= 1 0 0 50 5 00 4 70 4 5o 4 1 0 60 6 20 60 5 90 5 8 0 70 7 20 6 9o 6 90 6 3 0 7 50 7 60 7 50 7 40 7 l 0 80 8 10 7 90 7 80 7 5 o 8 50 8 50 8 4o 8 30 7 7 0 9 o 8 8o 8 7o 8 60 8 2 o 9 5 o 9 20 9 0 0 9 0 0 8 5 公式( 3 5 ) 成立的条件是七无穷大，理论上讲应该是七值越 大，估计精度越高。然而从表3 1 我们看到，七取1 时h u r s t 估计 值精度最高，偏置最小，而且等于1 时公式能够进一步简化， 大大减少运算量。相反，后取较大的值时不仅计算复杂( 要估计 序列的样本自相关系数，还要进行指数运算和乘法运算) ，迭代结 果也并不理想，我们分析导致这种情况的主要原因可能是：对于 固定长度的序列，随着七的增大，a 代替见所产生的误差越来越 大，这种误差对日估计值影响越来越明强。 自相似h u f s t 指数的快速迭代估计算法 鉴于以上分析结果，我们在公式( 3 - 5 ) 中取七= 1 ，得到简化 的迭代估计公式： 宣+ ，= ( a + 宣) o 5 ( 3 6 ) 下面对简化的迭代公式的迭代收敛性作简单的证明，首先引 入迭代收敛性定理。 定理1 【冽：假定函数妒( z ) 满足下列两项条件： 1 对任意x 【口，6 】有： 口e 妒o ) 6 2 存在正数l o 9 时估计值偏低。而研究表明，大量 的网络流量的自相似指数在【o 7 5 ，o 9 】之间，因此适合作为网络 流量h u r s t 指数的估计方法。另外，该算法对于所有的日值，都 有着比小波方法更小的置信区间，这说明该估计方法在保证精度 的条件下有着相当高的稳定性。 图3 2 的描述更为直观，对于每一个h 值，我们画出了本文 方法( 右) 和小波方法( 左) 的估计值的分布情况，图中每一个 样本点代表一次估计值，中间的红线代表样本均值，上下两条蓝 线代表置信区间的上下限。 ：圃：摹面 柏 叩1 0 即即1 nn 自相似h u 嘣指数的快速迭代估计算法 t 国r 国 h = 0 6 z 国z 圈 帕劬 劬1 帕1 加 n n h = 0 7 帕1 j ，；o 7 5 国z 日= 08 日= 0 8 5 。坛云赢 。【 2 0 4 0f 柏l 巨彝z 赫嗣 川w即 1 柏l 北京交通大学硕士学位论文 h = u y 图3 - 2 两种方法h u 哑估计值的分布 从计算速度上来看，对上述4 0 0 0 个样本点的序列，取估计误 差e o 0 0 0 5 ，最多只需要进行6 次迭代就可以完成估值。在对 上述每组1 0 0 个序列数据进行h u r s t 估值时，迭代算法平均估计 一次花费0 0 0 5 秒，而利用小波方法需要0 2 4 5 秒，比小波方法快 了将近5 0 倍，可以看出，该算法在执行速度方面有着很大的优势。 3 3 2 应用于真实网络数据 我们也将该方法在真实网络数据上作了实验，选取b e l l 实验 室1 9 8 9 年测得的数据b c 0 c t 8 9 、b d o c t 8 9 e x t 、b c p a u 9 8 9 以及 9 5 年测得的t c p 流量数据d e c p k i j 印作为原始数据。这四组数 据是网上公开的该领域的经典数据，几乎所有的该领域的新的理 论、方法都会在此组数据上做实验。它们都包括一百万个样本点， 代表不同时间间隔内的数据包的大小。 首先将上述四组数据分别处理到l s 、5 s 和1 0 s 的时间尺度上， 这样做出于两个目的：( 1 ) 增加实验数据；( 2 ) 分析估计方法在 同一组数据不同的时间尺度下的估计结果，这也应该作为判断 h u r s t 指数估计方法的另外一个指标，因为自相似过程在不同的时 间尺度下h u r s t 值相同，所以如果某个估计方法在不同尺度序列 上波动小，说明该方法稳定。利用本文算法和小波方法对这四组 数据值进行估计，实验结果见表3 3 。 从表3 3 可以看出，本文算法在真实的网络数据上的估计值与 小波方法的估计值接近，而且本算法在相同流量不同时间尺度下 的估计值相差很小，而小波方法的估计值则相差较大，这说明该 自相似m r s t 指数的快速迭代估计算法 方法不易受时间尺度变化影响，正好对应了自相似过程在不同时 间尺度下统计特性不变的性质。 表3 - 3 两种方法对真实数据的估计值 流量数据尺度样本数迭代法估计值小波方法估计值 1 s1 2 2 7 9 80 9 10 9 0 b c o c 惦9 e x t5 s2 4 5 6 00 9 20 9 2 1 0 s1 2 2 8 00 9 20 9 5 1 s1 7 6 00 9 10 8 0 b c - o c 嵋95 s3 5 20 9 50 8 7 1 0 s1 7 60 9 5o 9 6 1 s3 1 4 30 8 40 8 2 b c - p a u 9 8 9 5 s6 2 90 8 50 8 5 1 0 s 3 1 50 8 60 8 8 1 s3 6 0 00 8 50 8 3 d e c - p 呲p 5 s7 2 00 8 80 8 7 1 0 s3 6 0o 8 6o 8 9 3 4 在线估计h u r s t 指数 在实际网络运行过程中，网络的控制模块需要实时掌握网络的 业务流量特性，因此需要参数估计单元实时地对网络特性进行估 计，这就是网络流量参数的在线估计。对于自相似网络流量，最 重要的就是如何在线估计h u r s t 参数。 在线估计h u r s t 指数是指随着时间的推移，根据最新一段时 间的网络业务量不断估计h u r s t 指数，在线估计h u r s t 指数对于 实时了解网络流量特性以及采取基于流量特性进行的网络控制， 网络异常检测等方面有着重要意义。 对于在线估计算法的要求主要有这样两个方面：首先，在线算 法能够将新得到的数据进行单独处理后和前面己有的运算结果结 合起来得到目标量的估计值，而不必将以前的所有数据都重新处 北京交通大学硕士学位论文 理一遍。在线估计算法通常采用这样的工作原理：估计模块需要定 义并保存一些状态参量，而目标量的估计值是这些状态参量的函 数。每当得到一个新的数据，就以一定的算法更新状态参量，并 从更新后的状态参量估计出新的目标量的估计值。这样每次得到 一个新的观测值，只需要对状态参量进行处理以后就可以得到目 标量的估计值，而且由于状态参量己经能够充分体现累积的历史 值的作用，系统也不用保存全部己经观测到的历史值。其次，在 线算法应该尽量简单，以便能够在相邻两个数据到达的间隔时间 内完成。这个要求随着数据处理硬件的计算能力以及网络数据传 输速度的提高而变化。硬件处理能力的提高，降低了对算法的实 时性要求，而网络数据传输速率提高使得相邻两个数据到达间隔 缩短，因此要求在线估计的算法尽量简单。 由此可见，进行实时估计的好处在于：一方面可以快速得到 参数的估计值，而不必经过长时间的数据采集和处理过程，另一 方面由于不必保存很长时间的历史值而减小了估计模型需要的内 存。 前面提到的h u r s t 参数估计算法都是对于静态数据的，不适合 在线估计h u r s t 指数。我们发现迭代估计算法的迭代特性特别适 合在线估计h u r s t 参数，下面针对在线估计的特点，我们对