自相似流量模拟的Hurst参数实时计算

张冬梅

摘要： Hurst参数是自相似流量模拟重要参数。本文采用R/ S法对Hurst系数进行实时计算，在此基础上提出通过实际的Hurst系数与理论Hurst系数的比较来衡量模拟流量与理论模型的差别。

Abstract： Hurst parameter is an important parameter of self-similar flow simulation. In this paper， the R/S method is used to calculate the Hurst coefficient in real time. On this basis， this paper proposes to measure the difference between the simulated flow and the theoretical model by comparing the actual Hurst coefficient with the theoretical Hurst coefficient.

关键词： 自相似；Hurst参数；流量模拟

Key words： self-similar；Hurst parameter；flow simulation

中图分类号：TP393.0 文献标识码：A 文章编号：1006-4311（2017）34-0226-02

0 引言

在網络信息及通信技术发展的过程中，网络流量模型一直是研究的重点，二十世纪七八十年代，人们主要采用PSTN模型对网络流量的到达过程进行研究，由泊松模型的基本假定条件可知，伴随时间的延续和数据的累积，累计流量应该趋近平均值，然而取得的结果却与此有很大差异。Leland和Willinger等人收集了Bellcore实验室在1989到1992年之间的各种Ethernet LAN的数据，证明了传统用泊松到达传输来分析流量的假定是不充分的，需要新的信源模型。Berkeley实验室的Vern等，在长期的研究中发现绝大部分的TCP过程，具有时间尺度上的非常明显的自相似性特点，这并不同于泊松过程，主要表现为流量的突发性。因此，对网络流量数据包的到达过程来建立模型时，应当结合自相似的过程进行建立。基于各种测试的统计，他们得到Ethernet的信源是自相似的，并测得自相似的重要参数Hurst的值是0.9。

1 自相似的数学定义

对于自相似过程的研究始于本世纪中叶，对于一个系统来说，其自相似性主要是从不同的时空尺度上来看某种过程或结构的特征都具有相似性。此外，各整体之间，或者是部分与部分之间，也会存在相似性。一般情况下自相似性有比较复杂的表现形式而不是局域放大倍数以后简单地和整体完全重合。自相似性应用领域非常广泛，包括天文学、地理学、电子学、化学以及环境科学等众多领域。自相似性是跨尺度重复性，它可以产生出具有结构和规则的统计热性，这是对自相似性现象的直观描述。

在统计意义上，自相似过程主要表现为尺度不变性的随机过程。基于此，这种过程实际上可以认为是在随机过程的基础上引入了分形。对于随机过程X（t），（-∞

则可以认为该过程是宽自相似。

对于离散的自相似过程，通常采用这个过程的聚合过程来进行定义。

对于一个平稳的时间序列X={X（i），i>0}，取X（m）（K）=1/mX（i）。

如果对于任意m，满足XD=m1-HX（m），则称序列是严格自相似的；如果只有当m→∞时，上面的式子才成立，则称序列是渐进自相似的。

网络自相似性是网络流量特有的属性，网络流量在一个很长时间范围内表现出的结构是自相似的，每一组成分在特征上与整体一致。对于网络上的流量，不管是现在的时间t，还是过去的时间（t-s），同时不管s取何值，在t与t-s时刻的流量，都会具有相关性。

2 自相似的度量及Hurst参数的估算

既然流量是自相似的，如何用数学的定义表述自相似性呢？Hurst能够对时间序列的自相关性进行描述，也能够反映函数的衰减速度。用于对网络业务流量进行表示的序列属于自相似序列，而其中的Hurst参数，其取值在0.5

对于Hurst系数进行测量的方法有多种，主要有方差-时间图法、R/S图法、周期图法； Whittle估计方法、小波分析估计方。

2.1 方差时间曲线法

对于一个自相似过程的到达时间序列Xm，当m取值较大时，其方差服从：Var（Xm）～Var（X）/m？茁

其中Hurst参数H=1-（？茁/2）。

这个式子表述为严格的数学公式是：log[Var（Xm）]～log[Var（X）]*？茁log（m），其中log[Var（X）]是常数，其值与m的大小无关，如果将Var（X）m作为m的函数在对数图上画出来，结果将得到一条斜率为？茁的直线。斜率在0和1之间就意味着具有自相似性，接下来可以直接估计H值。这种方法需要预先获得大量的观测数据，并且需要大量运算。这种算法的另一个缺点是必须把所有数据都准备好以后才能进行估算。该方法的优势在于可以对随机过程的自相似性进判别。如果生产的曲线，是斜率在0与1之间的直线，可以判断其具有自相似性。

2.2 R/S分析法

R/S分析是经典的Hurst参数统计方法，它的算法原理是对于长度为k样本序列{X（k），k=1…n}，划分该序列为d个长度为n的不相交子序列，每一个子序列有样本均值和样本方差S（n），令Wk=[Xi-（n）]，则R/S的统计值为：R（n）/S（n）=[max（0，W（1），W（2），…，W（n）-min（0，W（1），W（2），…，W（n）]/S（n）

求出每个子序列的R/S统计值，再以算术平均值代替数学期望值，求出这些子序列的平均值E[R（n）/S（n）]，当序列是自相似序列时，E[R（n）/S（n）～cnH]，H就是Hurst系数，c为与d无关的常数。如果序列是短相关序列，则当n→∞时， H=0.5。已知序列X，把它分割成以n为大小的互不相交的块，每块中求R（n）/S（n）的值；在对数坐标上选择合适的n的值，求得所有R/S值；在这些数据中拟合一条直线，其斜率就是Hurst参数的值。R/S分析法要能先活动该随机过程的所有的观察值，因此对于H参数的预测并不适合。

2.3 Whittle估计法

Whittle估计法属于定量估计方法的一种，主要是在周期图的基础上进行的，并以周期图的频域为基础进行分析。假设序列X属于高斯随机序列，并且周期图是I（），f（x，H）是X的功率谱密度。根据最大似然，能够使

g（H）=d？棕

取得最大值的H也就是要得到的Hurst系数。作为量化的估计方法，Whittle估计法一方面可以对H参数的值进行定量估计，另一方面也能够对它的方差进行估计。

3 自相似流量模型模拟的Hurst系数的实时计算

网络流量模拟就是构造与真实网络业务相类似的数据包并发送到网络上，从而为网络攻防试验或网络安全产品提供实验环境。如何使网络流量模拟所产生的流量和实际的网络流量相近，是流量模拟所需要考虑的一个重要问题。流量模拟的模型控制是以自相似模型为基础，按照绑定的模型计算单位时间内的发包数量或下一个发包时间来控制流量的产生过程。

在对流量的模型控制中，针对不同的流量模型，采用一系列内置的流量速率过程数据来描述流量模型。流量生成源的实现算法流程如图1所示，首先发送一个数据包，然后根据绑定的自相似模型来读取下一单位时间内的发包数量或下一次发包时间。

由于网络软件及硬件的影响，网络流量模拟所产生的流量与系统设置的理论模型是有一定差别的，差别的衡量用描述网络流量自相似性的重要参数——Hurst系数。网络流量模拟系统采用Hurst系数的实时计算方式对Hurst系数进行计算，通过实际的Hurst系数与理论Hurst系数的比较来衡量模拟流量与理论模型的差别。

当时间序列的样本数目太少时，其它计算Hurst参数的方法误差比较大，而R/S方法计算的结果相对来说更加稳定，为了实时的监测与计算H系数，可以把算法分为两个部分，分别是数据收集与Hurst系数计算。在该算法体系中，对时间序列X进行记录时，使用数组data。

步骤1：在第一个分组到达以后，再开始进行数据的收集，同时进行时间的计数。如果到达第一个分组时，时间记录是tN，在这之后每次到达一个分组以后，对其到达时间与开始计数时间的时间之差？驻t进行记录并且对到达的分组数total_number进行累计，在第n个分组（n>1）到达之后，如果tN+n-tN

步骤2：如果数组data的长度是M，要开始对当前流的Hurst系数进行计算。令时间序列是X，均值是，S（n）为标准差，而部分和是Y（n）=Xi，可以得到

=

？驻k=Y（k）-k，k=1，2，…，n。

由于自相似特性，n→∞，因此：E[]～cnH

C是正常数且与n无关。

以log{E[R/S（n）]}当做纵坐标，同时以logn当做横坐标进行作图，使用OLS进行直线拟合，该直线的斜率即是H。

步骤3：归零时间与数据的计数器，并将Hurst系数值输出，重复步骤1和2至试验终止。

M的选择非常重要，M选择的太大反映不出Hurst系数的变化，M选择的太小，Hurst系数变化过于频繁，无法准确反映其实际的值。在试验中我们选择M在800-1200之间。另外，研究表明，网络流量的自相似程度与流量的负载有关，网络流量呈现自相似程度是在负载15%到70%之间，所以流量模拟环境在负载范围内计算Hurst的值才是有意义的。

4 结论

对如何提高网络流量模拟与真实网络流量模拟的近似度问题，本文采用流量模拟的模型控制，使流量按照绑定的自相似模型产生流量，利用R/S法对Hurst系数的实时计算，从而可以把实际计算出的Hurst值与理论Hurst的值进行比较来衡量流量模拟与理论模型的差距。

参考文献：

[1]W.E.Leland， M.S.Taqqu， W.Willinger， and .V.Wilson. On the Self-Similar Nature of Ethernet Traffic （extend version）. IEEE/ACM Transactions on Networking.

[2]王新.自相似網络流量的建模与预测[D].硕士学位论文，2003，6.

[3]魏恒义，程竹林，刘伟娜，曹雪.基于小波分析的网络流量的随机模拟[J].西安交通大学学报，2003，2（2）：37-38.