自相似网络业务的一个FARIMA模型

1、 自相似网络业务的一个FARIMA模型* 本文为国家自然科学基金资助项目（批准号69672031） 刘嘉焜 薛飞 王镭 张连芳 舒炎泰 （天津大学） 摘 要近来发现，高速网络业务具有自相似及长相关特性。分数噪声可描述该类业务，但它仅表现长相关特性。本文给出利用FARIMA（自回归分数整合滑动平均）模型拟合自相似网络业务的一整套方法。该模型同时刻画了实际业务的长相关与短相关特性。通过对实测数据的实验，证明了模型的优效性。关键词：自相似性 长相关 网络业务模型 自回归分数整合滑动平均1. 概述 随着宽带网络服务需求（如多媒体、视频业务等）的激增，高速网络传输技术（如ATM等）成为目前网络研究的热点

2、。研究人员围绕高速网络的业务拥塞控制、信息监测、带宽分配及网络性能评价等课题开展了大量工作，其中建立一个能准确描述网络业务（traffic）的模型是所有这些研究工作的基础。最初研究ATM网络时，常假设业务到达为Poisson过程。随着研究的深入逐渐引入了各种推广的Poisson过程和其它的随机模型，如Markov调制Poisson过程1，fluid-flow模型2、TES（Transform-Expand-Sample）模型3、packet-train模型4、批到达Markov过程5等等。这些模型的共同特点是所描述的业务序列具有短相关性（short range dependence），即业务序

3、列的自相关函数随序列间隔增大呈指数衰减趋势。当时间标度增加时，统计上单位时间内得到的数据包数将趋于白噪声，所以这些模型所表示的业务流在不同的时间标度下具有不同的特性。但是近年来研究结果表明：实际网络业务普遍存在统计上的自相似性，该特性与业务发生的时间地点或信元编码方式无关。其中，从1989年到1992年间，Leland和Wilson6等人使用具有很高时间分辨率的以太网监视设备在 BellCore Morristown 研究工程中心的几个以太网段的不同位置上收集了数百万个实际传输的数据包。通过对大量实际业务数据的分析，他们发现：这种聚集的网络业务所表现的统计自相似性完全不同于传统的业务模型。实际

4、网络业务序列的自相关函数随间隔增大呈双曲函数衰减，从而是长相关的（long range dependence）。Basu和Mukherjee等曾利用ARIMA模型，对贝尔实验室的自相似业务数据进行了分析7。他们假设业务过程是非平稳的，由于ARIMA模型不能描述网络业务内在的长相关性，因此该模型对自相似业务的描述能力是有限的。该研究证明了利用时间序列分析方法研究网络业务是可行的。为研究长相关的物理过程，Mandelbrot等将布朗运动推广到分数布朗运动FBM。分数差分噪声FARIMA(0,d,0)是FBM的离散情形8。FBM或FARIMA(0,d,0)适合于描述长相关过程，但由于FBM或FARI

5、MA(0,d,0)过程仅有三个参数，它们不能很好地表示实际中不可忽略的短相关结构9,10。本文将长相关特性的时间序列分析方法引入到自相似业务建模分析中，给出了利用FARIMA模型对自相似业务进行研究的方法，对模型辨识、参数估计及生成方法进行了系统的研究，利用“后向预报”技术对序列进行分形反滤波，在模型辩识、参数估计中利用粗、精估计结合的方法建立模型，并开发实现了更为有效的算法。最后，通过对实测数据的实验，定义了MSE统计量，证明了模型的优效性。2. FARIMA 模型FARIMA(p,d,q)过程扩展了FBM或FARIMA(0,d,0)的描述能力，弥补了它们在描述能力上的不足11。从定义不难看

6、出，FARIMA(p,d,q)模型是由分数差分噪声FARIMA(0,d,0)为激励的ARMA模型。该模型在利用参数d描述观测样本中的长相关结构时，利用p+q+ 1个参数来刻画样本中的短相关结构。定义2.1 随机过程称为服从(-0.5,0.5)的FARIMA()模型，如果是平稳（零均值）的，且满足差分方程 ， (2.1)其中为白噪声序列,和分别是p阶和阶多项式，,这里B是延迟算子，即 。显然，是(-0.5,0.5)的FARIMA()过程当且仅当是一个ARMA()过程。如果对，有，那么满足和 ，因此，可看成由FARIMA(0,d,0)驱动的ARMA(p,q)过程。定理2.2 设是(-0.5,0.5

7、)的FARIMA()过程，且(2.1)式中多项式与无公共根，则 (1) 如果，则(2.1)式有唯一的平稳解，形如 ， (2.2) 其中 ； (2) 具有物理可实现的单边滑动平均表示的充分必要条件是； (3) 可逆的充分必要条件是；(4) 如果具有物理可实现的单边滑动平均表示且可逆，则对，其自相关函数和谱密度有 ， (2.3)其中为常数； , ()。 (2.4) 因此，在极限状态下，FARIMA()过程的自相关函数和谱密度函数有同FARIMA (0,d,0)类似的结构。即当时，FARIMA(p,d,q)是长相关的。定理2.3 12 当时，FARIMA(p,d,q)过程是渐进二阶自相似过程，且其H

8、urst参数H=d+1/2。 不难看出，的FARIMA(0,d,0)和FARIMA()过程可以描述自相似业务所具有的长相关特性。3. 网流的FARIMA建模与传统ARMA过程相比，FARIMA模型的结构辨识和参数估计要困难和复杂得多。当数据同时呈现长短相关时，它们的行为将很难区分，使得模型选择变得困难。在利用似然函数估计自协方差时，精确似然估计方法遇到了计算上的问题。而其它“半参数（semi-parametric）”技术导致明显的有限样本偏置和较大的样本方差13。相对于FARIMA建模中的困难，传统的ARMA模型已经建立了一套成熟的理论和方法14。如前所述，分数差分噪声FARIMA(0,d,0

9、)被定义为高斯白噪声的-d阶分数差分，这一运算又被称为分形滤波。利用FARIMA(p,d,q)模型时，在获取参数d（等价地，Hurst参数H）的有效估计后，可以通过分形反滤波来消弱数据中的长期间相关结构，以达到增强短相关结构的目的。这是因为当我们将传递函数为的分形反滤波器作用于动态数据时，所得到的过程将是一个ARMA过程。基于上述讨论，我们可把FARIMA(p,d,q)分离成“分数差分”和“ARMA”两部分，而实现这种分离的关键是分数差分算子（即分形反滤波）的实现。 通过以上讨论，我们提出以下FARIMA的模型建立步骤：(1) 动态数据的预处理；(2) 动态数据的长相关结构分析；(3) 动态数

10、据的分形反滤波；(4) ARMA的结构辨识与模型检测；(5) FARIMA的参数估计与评估。3.1 分数差分算子的实现在对动态数据进行零均值化之后，得到。我们可以在FARIMA(p,d,q)模型p、q均未知的情况下，利用Hurst参数的有关分析方法，如聚集过程的方差分析法(variance-time)、基于周期图(Periodogram)的频域分析法、R/S分析法等得到动态数据Hurst参数的近似估计H，由关系d=H-0.5得到d的近似估计6。这就完成了步骤（1），（2）。作用于序列的分数差分算子Ñd的精确形式为： （3.1）其中。对于d<1/2，(3.1)式均方收敛，因此算子

11、Ñd是一个完备的定义。从(3.1)式可看出，分数差分的计算过程需要用到首个观测点之前的数据W0，W-1，W-2，而且其表达形式为无穷求和，因此在实际应用中必须采取近似形式方能计算。我们的具体策略为只当时，用均值0来替代Wt ，这里M的选择应足够大以使得这种替代合理。从而得到算子： 。 (3.2)为了实现(3.2)中定义的差分算子，我们采用“后向预报”技术估计非观测样本Wt ，的值。假设我们已知过程 (3.3) 的一个样本，现在我们需要估计观测点之前的数据w0，w-1，w-2，w-n。可以证明由式(3.3)所给出的wt的概率结构与中所描述的一样，这里F为前置算子即。因此，w-n和序列w

12、1，w2，wt之间的概率关系，等同于wt+n+1和序列w1，w2，wt之间的概率关系。所以，为了估计首个观测点之前n+1步的数据，我们可以首先考虑观测序列结束之后n+1步数据的最优预报和估计，然后将这个过程运用于wt的反转序列。我们称这种技术为“后向预报”。为了实现后向预报，需要建立一个能基本反映序列变化的模型。我们采用高阶AR模型来描述实际的数据序列，在我们的实验中就采用AR(8)模型来建立所需的辅助模型。在得到辅助长自回归模型后，我们可以利用后向预报技术，利用式(3.2)定义的算子对序列进行分形反滤波，消弱数据中的长相关结构，得到序列。根据式(3.2)，我们在Sun SPARC20工作站上

13、利用C语言实现了分数差分算子，用于采样数据的分形反滤波。为了考察分形反滤波的实际效果，我们选取某随机数种子值和不同的差分阶数d，利用定义生成分数差分噪音FARIMA(0,d,0)序列，每个序列的样本个数为20000个。利用生成的分数差分算子进行分形反滤波，对各序列进行Hurst参数估计，得到表1。表1 FARIMA(0,d,0)序列的分形反滤波效果 目标参数dFARIMA(0,d,0)序列特性分形反滤波后序列的特性0.10.6260.1260.5110.0110.20.7270.2270.5250.0250.30.8250.3250.5360.036从表1分形反滤波后数据可以看出，分形反滤波达

14、到了预期效果。3.2 FARIMA的结构辨识ARMA模型的结构辨识与模型检测我们知道，经分形反滤波后所得到的序列是一个ARMA模型，因此FARIMA结构辨识的等价问题就是序列的ARMA分析与定阶。我们采用 ARMA模型参数的近似极大似然估计14 。应用于辨识ARMA模型阶数,我们采用最小信息准则或最小AIC(Akaike Information Criterion)准则，和BIC准则15。我们在0,1,2,3,4,5中选择p、q，在35种有效组合中，综合利用AIC和BIC准则选择使准则函数最小的p、q组合。对每个p、q组合的分析利用ARMA的极大似然估计方法。我们在统计软件S-plus的基础上

15、，利用S语言编制了通过近似极大似然估计和定阶准则进行模型辨识的程序，使用 BellCore Morristown 研究中心的实际业务数据pAug.TL进行了实验。3.3 模型的统计检验与诊断 时间序列建模的统计检验对于保证模型的应用效果具有重要的意义。通过模型的统计检验，可以对得到的候选模型进行评估。序列被估计为ARMA(p,q)模型后 ， 应为白噪声序列。因此，我们可以利用模型ARMA(p, q)，从序列的一段样本求得模型残量的一段样本值。这时我们便可以对命题“是白噪声序列”进行统计检验14。我们利用以下的模型检验与诊断方法：1 标准化模型残量序列图；2 模型残量的自相关函数检验；3 por

16、tmanteau检验。 因篇幅所限仅给出ARMA(1,0)模型诊断（图1）。该图有标准化残差图、残差自相关函数图及portmanteau检验图。需要说明的是portmanteau检验，图中的虚线表示显著性水平0.05，分析点代表在当前自由度（即横坐标取值）下，检验值所对应的显著性水平；若分析点在该虚线之下，则表示分析点所对应的显著性水平小于0.05，表示拟合情况较好；否则，就认为拟合不理想。 图1 ARMA(1,0)模型诊断图3.4 FARIMA模型的参数估计近似极大似然方法完成FARIMA(p,d,q)的模型辨识后，我们就可以利用FARIMA模型的最大似然方法对p+q+1个未知参数进行估计，

17、从而得到我们所需要的模型。设是FARIMA(p,d,q)过程，关于的条件分布是正态分布，、可以用Durbin-Levinson算法求得14。利用极大似然方法作参数估计时，似然函数的计算量相当大。由于我们所研究的序列是一个样本数较大的序列(N=2,000)，我们利用一种近似极大似然方法来实现FARIMA的参数估计。该算法设计的基本出发点是仅利用FARIMA(0,d,0)过程的偏相关系数来计算上述的条件均值和条件方差，而不用FARIMA(p,d,q)过程的偏相关系数，这是因为FARIMA(p,d,q)过程的偏相关系数相当复杂。这样即可得到全部估计17。 我们在利用AIC、BIC准则判定最优模型的同

18、时，也考察差分系数d的合理性。若经近似极大似然方法估计所得的d与前面所述的d的近似估计相差甚远，或并不处于区间(0,0.5)内，我们则认为该模型是不准确的。4. 性能分析我们对同一序列分别建立FGN、AR、ARIMA和FARIMA四种不同的模型。如前所述，FGN模型有三个参数：均值、方差和Hurst参数；ARIMA模型是美国Georgia理工学院的研究小组所采用的时间序列模型7；而AR模型是用传统方法给出的AR(8)自回归模型（这里不详述了）。网络自相似业务的基本特性可用其自相关函数来反映。我们定义自相关函数均方误差量MSE(Mean Squared Errors)如下： (4.1)其中MSE

19、(m)表示模型m的自相关函数均方误差量，ACFmi表示模型m的第i阶自相关函数，ACFSi表示样本序列的第i阶自相关函数。该统计量反映了模型对序列自相关函数的描述效果，值越小，效果越好。表2 各模型的MSE统计量模型MSE统计量FARIMA(1,d,1)0.0006031FGN0.0398209AR(8)0.0026151ARIMA(10,1,0)0.0011448从表2中MSE统计量来看，FARIMA的描述效果仍被证明是最有效的，ARIMA次之，FGN的效果最差。为了比较FARIMA与其它模型在描述能力的优劣，我们给出：FGN模型为： mean=3.8995，Var= 7.357078，H=

20、0.80；AR模型为AR(8)；ARIMA(10,1,0)：参数() =（-0.47360296,-0.48794950,-0.39297214, -0.28920862, -0.20433070, -0.23897851, -0.17016975, -0.10837808, -0.06937427,-0.03941886），=5.24312。利用仿真技术，分别产生四种模型的样本，并与原始序列进行比较。图2图5是各模型与原始序列自相关函数的比较。可以看出，在间隔较小（lag<15）时，FGN模型的自相关函数与原始序列的自相关函数有一定差异，而其它模型则较为准确地描述了这种短相关特性。考察

21、模型对长相关特性的描述效果，当间隔较大(lag>40)时，FGN和AR模型对长期间相关特性的描述误差较大，而FARIMA和ARIMA要好得多，而FARIMA对长期间相关特性的描述偏大，ARIMA则偏小，显然这与模型自身的特性有关：前者是把原序列看成平稳的长相关序列来处理，而后者把原序列看成是非平稳的短相关序列。 图2 FARIMA模型与样本数据自相关函数的比较 图4 AR模型与样本数据自相关函数的比较图3 FGN模型与样本数据自相关函数的比较 图5 ARIMA模型与样本数据自相关函数的比较 比较四个模型FGN、AR(8)、 ARIMA(10,1,0)、FARIMA(1,d,1)可以发现，

22、FGN模型适于描述长相关特性，模型参数较少，但描述能力有限；AR和ARIMA模型用较多的参数描述了样本中复杂的相关特性，但模型较为复杂。FARIMA过程引入分数差分阶数d这一个参数就有效地描述了样本中的长相关特性，从而使得模型变得很简洁。另外，通过将FARIMA(p,d,q)分离成“分数差分噪音”和“ARMA(p,q)”两个组成部分，利用分数差分阶数d反映了样本中的长相关特性，而ARMA(p,q)中p+q+1个参数描述了样本中的短相关特性，故模型本身还具有一定的物理意义，使得我们在利用该模型进行深入研究时可以有效地考察长、短相关特性的不同作用。这是AR、ARIMA模型所不具备的。5. 结论本文

23、讨论了FARIMA(p,d,q)模型的概念和特性，发现时该模型可以描述自相似业务的长相关特性。并比较了FARIMA()模型与其它模型的描述能力，提出了一种基于FARIMA过程进行自相似业务建模分析的方法,系统地将具有长相关特性的时间序列分析方法应用在网络业务的数据分析与建模中。通过对样本数据进行分形反滤波，利用传统的ARMA建模分析和统计检验技术解决了业务建模中的模型辩识问题。我们利用一种近似极大似然估计方法实现了业务建模中的参数估计。通过将所建的FARIMA模型同其它业务模型相比较，证实了FARIMA模型的优效性。参考文献1H.Heffes and D.M. Lucantoni. “A Ma

24、rkov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance” IEEE Journal on Selected Areas in communications,4:856-868,19862D.Anick, et al., “Stochastic theory of a data-handling system with multiple sources” Bell System Technical Journal,61:

25、1871-1894,19823B.Melamed “An overview of TES processes and modeling methodology” In L.Donatielo and R.Nelson, eidtors, Models and techniques for Performance Evaluation of computer and communications system, pp 359-393. Springer-Verlag, New York,19934 R.Jain and S.A.Routhier, ”Packet trains: Measurem

26、ents and a new model for computer network traffic” IEEE Journal on Selected Areas in Communications, 4:986-995,19865D.M.Lucantoni “The BMAP/G/1 queue” In L.Donatielo and R.Nelson ,eidtors, Models and techniques for Performance Evaluation of computer and communications system, pp 335-358. Springer-Ve

27、rlag, New York,19936W.E. Leland, M.S.Taqqu, W. Willinger and D.V. Wilson, "On the self-similar nature of Ethernet traffic", In Proceedings of the ACM/SIGCOMM'93, San Francisco, CA, 183-193,1993.7S.Basu, A. Mukherjee “Time series models for Internet Traffic”, In: Proceedings of IEEE INF

28、OCOM96 pp 611-620,19968 J.R.M.Hosking, “Fractional differencing,” Biometrika, 68: 165-176, 1981.9I. Norros, “On the use of Fractional Brownian Motion in the theory of connectionless networks,” , IEEE Journal on Selected Areas in Commununication, 1995, 13(6):953-96210N.Duffield, “Economies of scale i

29、n long and short buffers of large multiplexers” in: Proceedings of 12th IEE UK Teletraffic Symposium, Windsor, 15-17 March 1995, 11 C.W.J.Granger and R.Joyeux, “An introduction to long-memory time series models and fractional differencing”, Journal of .Time Series Analysis. 1: 159-29, 1980.12 W.Lela

30、nd, et al., “On the self-similar nature of Ethernet traffic (extended version),” IEEE/ACM Transactions on Networking ,1994, 2(1):1-1513C.Agiakloglou, P.Newbold and M.Whohar, “Bias in an estimator of the fractional difference parameter”, Journal of Time Series Analysis, 14: 235-46, 199314Brockwell, P.J.and Davis, R.A., Time Series: Theory and Methods, 2nd edition, New York, Springer verlag, 1991.15H.Akaike, “Time series analysis and control through parametric models” ,Applied Time Series Analysis,