基于FARIMA-GARCH模型的网络业务预测算法

doi:10.3969/j.issn.1000-436x.2013.03.004

摘要/Abstract

摘要：

针对网络流量的波动性与自相似特性为其精确预测提出的挑战，提出了一种基于FARIMA-GARCH模型的预测算法。该算法首先利用分段双向CUSUM检测算法对流量序列的均值进行有效检测，并在此基础上将序列零均值化；然后采用限定搜索法对分数差分阶数进行精确估计；在获得模型参数后，使用FARIMA-GARCH模型对网络流量进行预测。仿真实验表明，限定搜索法能够获得比传统算法更高的估计精度。随后采用真实网络流量验证了预测算法的性能，在保持与FARIMA 预测算法等价的时间复杂度下，其均方根和相对均方根误差与RBF神经网络预测算法相当，而高于FARIMA预测算法。同时，预测算法对突发流量的跟踪和预测性能明显优于对比算法，且有更好的区间估计性能。

关键词: FARIMA, GARCH, CUSUM, 流量预测

Abstract:

The volatility and self-similarity features of network traffic poses great cha lenge to network traffic prediction. For this purpose, a novel network traffic prediction scheme based on FARIMA-GARCH model was formulated. A novel method was used to get a zero-mean traffic series by a piecewise two-way CUSUM detection algorithm. Then the fraction difference order was evaluated with precision by the presented bounded search method. After obtaining the model para-meters, the prediction algorithm was conducted by using FARIMA-GARCH model. Compared with the traditional me-thod, the limited search method reduces the evaluated error despite a slight computational cost. Then simulation was car-ried out to verify the accuracy of proposed algorithm with real network traffic. The proposed prediction method keeps the same time complexity with the FARIMA model prediction method, and the simulation result shows that the root mean-square error and relative root mean-square error, which closely resemble the RBF prediction method, is less than FARIMA model prediction method. And the interval estimation and volatility prediction performance is excellent.

Key words: FARIMA, GARCH, CUSUM, traffic prediction

杨双懋,郭伟,唐伟. 基于FARIMA-GARCH模型的网络业务预测算法[J]. 通信学报, 2013, 34(3): 23-31.

Shuang-mao YANG,Wei GUO,Wei TANG. Network traffic prediction based on FARIMA-GARCH model[J]. Journal on Communications, 2013, 34(3): 23-31.

图/表 15

图1

图2

图3

图4

图5

表1

表2

表3

表4

表5

表6

表7

表8

图6

图7

参考文献 35

[1]	PAXSONV , FLOYDS . Wide-area traffic: the failure of poisson mod-eling[J]. IEEE/ACM Transactions on Networking, 1995,3(3): 226-244.
[2]	LELANDW E , WILLINGERW , TAQQUM S , et al. On the self-similar nature of ethernet traffic[J]. Computer Communication Review, 1995,25(1): 203-213.
[3]	LELANDW E , WILLINGERW , TAQQUM S , et al. On the self-similar nature of ethernet traffic(extended version)[J]. IEEE/ ACM Transactions on Networking, 1994,2(1): 1-15.
[4]	WILLINGERW . Self-similarity in wide-area network traffic[A]. Lasers and Electro-Optics Society Annual Meeting[C]. San Francisco, USA, 1997. 462-463.
[5]	HAMILTONJ D . Time-Series Analysis[M]. New Jersey: Princeton University Press, 1994.
[6]	王西锋，高岭，张晓孪 . 基于小波技术的网络流量分析和预测[J]. 计算机应用与软件， 2008,25(8): 70-72. WANGX F , GAOL , ZHANGX L . A network traffic analysis and forecast based on wavelet technology[J]. Computer Applications and Software, 2008,25(8): 70-72.
[7]	白翔字, 叶新铭, 蒋海 . 基于小波变换与自回归模型的网络流量预测[J]. 计算机科学， 2007,34(7): 47-49. BAIX Y , YEX M , JIANGH . Network traffic predicting based on wavelet transform and autoregressive model[J]. Computer Science, 2007,34(7): 47-49.
[8]	陈晓天, 刘静娴 . 改进的基于小波变换和 FARIMA模型的网络流量预测算法[J]. 电子学报， 2011,32(4): 153-157. CHENX T , LIUJ X . Network traffic prediction based on wavelet transformation and FARIIMA[J]. Journal on Communications, 2011,32(4): 153-157.
[9]	TARRAFA , HABIBW , AHMEDA . ATM multimedia traffic predic-tion using neural networks[A]. Global Data Networking Proceed-ings[C]. Cairo, Egypt, 1993. 77-84.
[10]	WANGF , XIAH B . Network traffic prediction based on grey neural network integrated model[A]. International Conference Computer Science and Software Engineering[C]. Wuhan, China, 2008. 915-918.
[11]	JUNL , LIT , LIX . Network traffic prediction algorith and its prac-tical application in real network[A]. IFIP International Conference on Network and Parallel Computing Workshops[C]. Liaoning, China, 2007. 512-517.
[12]	ARDHANS , SATSRIS , CHUTCHAVONGV , et al. Improved model for traffic fluctuation prediction by neural network[A]. International Conference on Control, Automation and Systems[C]. Seou Korea, 2007. 122-125.
[13]	ZHUL , QINL , XUEK , et al. A novel BP neural network model for traffic prediction of next generation network[A]. Fift International Conference on Natural Computation[C]. Tianjin, China, 2009. 32-38.
[14]	LIX Y . Prediction of traffic flow base on neural network[A]. Intelli-gent Computation Technology and Automation[C]. Changsha, China, 2009. 374-377.
[15]	王俊松, 高志伟 . 基于 RBF神经网络的网络流量建模及预测[J]. 计算机工程与应用， 2008,44(13): 6-11. WANGJ S , GAOZ W . Network traffic modeling and prediction based on RBF neural network[J]. Computer Engineering and Applications, 2008,44(13): 6-11.
[16]	WENY , YANGD Y , ZHAOY L . Traffic flow prediction based on wavelet transform and radial basis function network[A]. International Conference on Logistics Systems and Intelligent Manage nt[C]. Harbin, China, 2010. 969-972.
[17]	邹伯贤, 刘强 . 基于ARMA模型的网络流量预测[J]. 计算机研究与发展， 2002,39(12): 1645-1652. ZOUB X , LIUQ . Arma-based traffic prediction and overload detec-tion of network[J]. Journal of Computer Research and Development, 2002,39(12): 1645-1652.
[18]	舒炎泰, 王雷, 张连芳等. 基于FARIMA模型的 Internet网络业务预报[J]. 计算机学报， 2001,24(1): 46-54. SHUY T , WANGL , ZHANGL F , et al. Internet traffic modeling and prediction using FARIMA models[J]. Chinese Journal of Computers, 2001,24(1): 46-54.
[19]	冯慧芳 . IEEE 802.11无线局域网业务流特性研究及预报[D]. 天津: 天津大学， 2006. FENGH F . Traffic Characterization and Prediction in IEEE 802.11 WLANs[D]. Tianjin: Tianjin University, 2006.
	吕金虎 . 混沌时间序列分析及其应用[M]. 武汉: 武汉大学出版社， 2002. LVJ H . Chaos Time Series Analysis and Application[M]. Wuhan: Wu-han University Press, 2002.
[21]	杨双懋, 郭伟, 唐伟 . 认知无线网络中基于时间序列预测的冲突分解算法. 通信学报， 2011,32(11): 51-58. YANGS M , GUOW , TANGW . A collision resolution algorithm based on time-series forecasting for cognitive wireless networks[J]. Journal on Communications, 2011,32(11): 51-58.
[22]	WILFREDOP . Long-Memory Time Series : Theory and Methods[M]. Hoboken: John Wiley ＆ Sons, 2007.
[23]	ZHANGH F , SHUY T , YANGO . Estimation of hurst parameter by variance time plots[A]. IEEE Pacific Rim Conference on Communica-tions, Computers and Signal Processing[C]. Victoria, Canada, 1997. 883-886.
[24]	CLEGGR G . A practical guide to measuring the hurst parameter[J]. International Journal of Simulation: Systems,Science and Technology, 2006,7(2): 3-14.
[25]	LAUW C , ERRAMILLIA , WANGJ L , et al. Self-similar traffic parameter estimation: a semi-parametric periodogram-based algo-rithm[A]. IEEE Global Telecommunications Conference[C]. Singa-pore, 1995. 2225-2231.
[26]	ABRYP , VEITCHD . Wavelet analysis of long range dependent traf-fic[J]. IEEE Transactions on Information Theory, 1998,44(1): 2-15.
[27]	洪飞, 吴志美 . 基于小波的Hurst指数自适应估计方法[J]. 软件学报， 2005,16(9): 1685-1689. HONGF , WUZ M . Adaptive hurst index estimator based on wave-let[J]. Journal of Software, 2005,16(9): 1685-1689.
[28]	WILLIAMR , LESO , MARCOR , et al. Estimators for long range dependence: an empirical study[J]. Electronic Journal of Statistics, 2009. 1-16.
[29]	陈彦辉, 谢维信 . 随机分形信号参数的分数差分估计[J]. 电子与信息学报， 2001,23(1): 9-15. CHENY H , XIEW X . Fractional difference estimation for the para-meters of random fractal signal[J]. Journal of Electronics and Informa-tion Technology, 2001,23(1): 9-15.
[30]	BROCKWELLP J , DAVISR A . Time Series:Theory and Methods[M]. New York: Springer, 1987.
[31]	GARCH模型与应用简介[EB/OL]. .GARCH model application profile[EB/OL]. .
[32]	AKAIKEH . A new look at the statistical model identification[J]. IEEE Transactions on Automatic Control, 1974,19(6): 716-723.
[33]	SHIBATAR . Selection of the order of an autoregressive model by Akaike's information criterion[J]. Biometrika, 1976,63(1): 117-126.
[34]	HOSKINGJ R M . Modeling persistence in hydrological time series using fractional differencing[J]. Water Resources Research, 1984,20(12): 1898-1908.
[35]	Sigcomm 2004 trace dataset[EB/OL]. . 2011.

H	方差法	R/S分析法	A-V小波法	自适应法	限定搜索法
0.55	0.548 5(0.56s)	0.499 7(56.66s)	0.547 0(0.16s)	0.550 2(0.27s)	0.549 4(4.25s)
0.60	0.572 0(0.48s)	0.544 1(58.88s)	0.590 4(0.10s)	0.594 1(0.25s)	0.600 5(5.17s)
0.70	0.708 0(0.52s)	0.693 2(57.17s)	0.689 3(0.07s)	0.694 6(0.25s)	0.699 9(4.74s)
0.80	0.720 2(0.53s)	0.757 9(57.77s)	0.790 2(0.11s)	0.794 2(0.20s)	0.799 6(4.72s)
0.85	0.839 9(0.53s)	0.856 3(58.03s)	0.864 6(0.09s)	0.854 3(0.20s)	0.849 5(5.25s)
0.90	0.858 7(0.52s)	0.914 6(56.75s)	0.926 8(0.11s)	0.913 1(0.26s)	0.900 3(5.66s)
0.95	0.885 9(0.49s)	0.923 5(57.36s)	0.931 9(0.09s)	0.943 3(0.234s)	0.950 8(4.23s)

业务流名称	H指数	均值	方差
sig04_ver01(10ms)	0.649 2	0.665 1	2.183 4
sig04_ver01(100ms)	0.831 5	6.648 9	31.069 0
sig04_ver02(10ms)	0.717 2	2.034 6	10.545 8
sig04_ver02(100ms)	0.837 5	20.325 2	206.875 7
sig04_ver03(10ms)	0.758 5	1.681 0	8.545 8
sig04_ver03(100ms)	0.853 9	16.806 7	187.432 3

预测算法及其评价指标	单步预测	5步预测	15步预测	25步预测
RMSE(FARIMA)	1.628 6	5.314 2	7.704 5	9.476 0
RMSE(RBF)	1.998 8	1.980 6	1.958	2.999 6
RMSE(FARIMA-GARCH)	1.568 5	1.874 9	2.757 3	3.302 7
RRMSE(FARIMA)	1.101 3	3.565 7	5.479 1	6.536 1
RRMSE(RBF)	1.062 32	1.573 8	1.804	2.106 3
RRMSE(FARIMA-GARCH)	1.026	2.646 8	4.337 4	5.272 5
IFA(FARIMA)	95.51%	73.90%	55.92%	48.30%
IFA(FARIMA-GARCH)	96.61%	90.59%	80.92%	75.23%

预测算法及其评价指标	单步预测	5步预测	15步预测	25步预测
RMSE(FARIMA)	1.791 1	2.630 8	2.865 7	2.879 3
RMSE(RBF)	2.357 5	2.365 7	2.349 8	2.315 8
RMSE(FARIMA-GARCH)	1.702 4	1.753 6	1.960 8	2.285 1
RRMSE(FARIMA)	1.472 8	2.525 7	2.857 5	2.879 6
RRMSE(RBF)	1.031 1	1.119 4	1.306 8	1.295 7
RRMSE(FARIMA-GARCH)	1.114 7	1.400 0	1.697 2	2.569 8
IFA(FARIMA)	95.22%	91.96%	89.93%	84.13%
IFA(FARIMA-GARCH)	97.96%	96.44%	95.73%	95.52%

预测算法及其评价指标	单步预测	5步预测	15步预测	25步预测
RMSE(FARIMA)	3.606 4	5.355 3	8.852 6	9.157 4
RMSE(RBF)	5.057 7	5.033 6	4.901 7	4.858 5
RMSE(FARIMA-GARCH)	3.399 4	4.124 1	4.276 9	4.438 0
RRMSE(FARIMA)	1.664 3	4.207 4	7.152 2	7.839 3
RRMSE(RBF)	1.301 0	1.480 1	1.874 8	1.915 3
RRMSE(FARIMA-GARCH)	0.941 1	2.148 2	2.256 5	2.821 9
IFA(FARIMA)	85.73%	67.93%	55.08%	52.56%
IFA(FARIMA-GARCH)	92.53%	91.18%	90.01%	87.15%