关于时间序列预测在流媒体服务中应用的研究
|
摘要
流媒体系统常常因为同时实时处理大量用户服务,而耗费大量的资源和能源,譬如网络带宽和电力。不管是为了节省本身系统开支还是世界能源危机,为流媒体系统开发节省带宽资源和服务器能源的方案越来越有必要;而在进一步开发具体方案之前,对带宽需求和服务器用户量的预测成了首要解决的问题。因此,本论文提出解决两个课题:
1)课题一:如何基于视频迹文件的数据来预测视频服务对于网络带宽的需求;
2)课题二:如何基于视频服务器上的日志文件数据来预测服务器未来用户量的变化。
为了解决这两个课题,本文基于时间序列建模和预报的理论和方法,对每个方案各提出了一个预测方案。这两个预测方案都用到了我们提出的一个ARMA模型拟合算法,并且在使用这个算法之前,都对样本数据进行了分析绘图、趋势项和季节项分离、平稳化和零均值化等可逆预处理过程;而在算法之后,都基于算法的拟合平稳过程进行了预报,并且基于这些预报结果对未来数据进行了预测。
课题二的预测方案相对简单,没有脱离时间序列分析法的一般步骤;而课题一的预测方案在运行算法前,提出了一个比较特殊和有效的可逆初变换,并且一步步依靠实验改进了该变换,最后提出了一个多步动态预测机制。我们针对两个课题都设计了多个实验,实验结果表明我们的预测方案有效而精度较高,能够捕捉到历史数据的变化特征和趋势。特别是课题一的预测方案相对于其他相关工作,不需要基于平稳性假设和不需要区分对待I、P和B,因此结果更精确而实现复杂度更低。
The streaming media system usually costs lots of resource like network bandwidth and energy like electricity, because of hosting a large number of instantaneous users. No matter to cut the system budget itself or for the world energy crisis, it is more and more necessary to seek solutions to optimize resource or energy efficiency. However, the expected schemes would have to be developed based on predictions of future bandwidth requirement and sever workload of the whole system. Therefore, this paper proposes and solves two topics as follows:
1) Topic 1: How to predict the network bandwidth requirement based on video traces?
2) Topic 2: How to predict the future connection number based on its log data?
To address these two problems, this paper proposes one prediction scheme for each topic based on the modeling and forecast of Time Series. Each prediction schemes uses an ARMA fitting algorithm designed by us. And each time, the sample series is analyzed, plot, processed to be stationary without trend or seasonal components, and subtracted by its mean before running the algorithm. These operations are all reversible. In addition, after running the algorithm, each scheme predicts the future values based on the forecasts from the gained stationary model of the algorithm.
Topic 2 is relatively simpler, and can be processed and solved according to the normal steps of Time Series Analysis. But topic 1 is harder, and a special, effective and reversible initial transformation is needed before the fitting algorithm, which improves step by step as the experiments proceed. At last, we get a multi-step dynamic prediction mechanism. We design several experiments for each prediction and the results show that our schemes are effective with a high accuracy, and could capture the characteristics and variation of history data. Especially, compared with related work, the scheme for Topic 1 needs no stationary assumption and doesn’t have to separate the I, P and B frames, and thus achieves higher accuracy with a lower implementation complexity.
1)课题一:如何基于视频迹文件的数据来预测视频服务对于网络带宽的需求;
2)课题二:如何基于视频服务器上的日志文件数据来预测服务器未来用户量的变化。
为了解决这两个课题,本文基于时间序列建模和预报的理论和方法,对每个方案各提出了一个预测方案。这两个预测方案都用到了我们提出的一个ARMA模型拟合算法,并且在使用这个算法之前,都对样本数据进行了分析绘图、趋势项和季节项分离、平稳化和零均值化等可逆预处理过程;而在算法之后,都基于算法的拟合平稳过程进行了预报,并且基于这些预报结果对未来数据进行了预测。
课题二的预测方案相对简单,没有脱离时间序列分析法的一般步骤;而课题一的预测方案在运行算法前,提出了一个比较特殊和有效的可逆初变换,并且一步步依靠实验改进了该变换,最后提出了一个多步动态预测机制。我们针对两个课题都设计了多个实验,实验结果表明我们的预测方案有效而精度较高,能够捕捉到历史数据的变化特征和趋势。特别是课题一的预测方案相对于其他相关工作,不需要基于平稳性假设和不需要区分对待I、P和B,因此结果更精确而实现复杂度更低。
The streaming media system usually costs lots of resource like network bandwidth and energy like electricity, because of hosting a large number of instantaneous users. No matter to cut the system budget itself or for the world energy crisis, it is more and more necessary to seek solutions to optimize resource or energy efficiency. However, the expected schemes would have to be developed based on predictions of future bandwidth requirement and sever workload of the whole system. Therefore, this paper proposes and solves two topics as follows:
1) Topic 1: How to predict the network bandwidth requirement based on video traces?
2) Topic 2: How to predict the future connection number based on its log data?
To address these two problems, this paper proposes one prediction scheme for each topic based on the modeling and forecast of Time Series. Each prediction schemes uses an ARMA fitting algorithm designed by us. And each time, the sample series is analyzed, plot, processed to be stationary without trend or seasonal components, and subtracted by its mean before running the algorithm. These operations are all reversible. In addition, after running the algorithm, each scheme predicts the future values based on the forecasts from the gained stationary model of the algorithm.
Topic 2 is relatively simpler, and can be processed and solved according to the normal steps of Time Series Analysis. But topic 1 is harder, and a special, effective and reversible initial transformation is needed before the fitting algorithm, which improves step by step as the experiments proceed. At last, we get a multi-step dynamic prediction mechanism. We design several experiments for each prediction and the results show that our schemes are effective with a high accuracy, and could capture the characteristics and variation of history data. Especially, compared with related work, the scheme for Topic 1 needs no stationary assumption and doesn’t have to separate the I, P and B frames, and thus achieves higher accuracy with a lower implementation complexity.
引文
1Patrick Seeling, Martin Reisslein, Beshan Kulapala,“Network Performance Evaluation Using Frame Size and Quality Traces of Single-Layer and Two-Layer Video: A Tutorial,”IEEE Communications Surveys and Tutorials, Vol. 6, No. 2, Pages 58-78, Third Quarter 2004.
2Martin Reisslein, Jeremy Lassetter, Sampath Ratnam, Osama Lotfallah, Frank H.P. Fitzek, Sethuraman Panchanathan.“Traffic and Quality Characterization of Scalable Encoded Video: A Large-Scale Trace-Based Study, Part 1: Overview and Definitions,”Arizona State University, Dept. of Electrical Engineering, Technical Report, Dec 2003.
3Martin Reisslein, Jeremy Lassetter, Sampath Ratnam, Osama Lotfallah, Frank H.P. Fitzek, Sethuraman Panchanathan,“Traffic and Quality Characterization of Scalable Encoded Video: A Large-Scale Trace-Based Study, Part 2: Statistical Analysis of Single-Layer Encoded Video,”Arizona State University, Dept. of Electrical Engineering, Technical Report, Dec 2003.
4Patrick Seeling, Frank H.P. Fitzek, Martin Reisslein,“Video Traces for Network Performance Evaluation,”ISBN: 978-1-4020-5565-2, springer 2007.
5Peter J.Brockwell, Richard A.Davis,“Time Series: Theory and Methods”,2nd ed., ISBN 7-04-008701-4, springer 2001.
6A. Adas, A. Mukhejee,“On resource management and QoS guarantees for long range dependent traffic,”in IEEE INFOCOM, Apr.
7S. Li, L. Hwang,“Queue response to input correlation functions: Discrete spectral analysis,”IEEE Trans. Networking, vol. 1.
8P. Pancha, M. Zarki,“Bandwidth requirements of variable bit rate MPEG source in ATM networks,”IEEE INFOCOM, pp.902-909, Mar. 1993.
9N. Nomura, T. Fujii, N. Ohta,“Basic characteristics of variable rate video coding in ATM environment,”IEEE J. Select. Areas Commun., vol. 7, pp. 752-760, June 1989.
10R. Grunenfelder et al.,“Characterisation of video codecs as autoregressvie moving average process and related queuing system performance,”IEEE J. Select. Areas Commun., vol. 9, pp. 284-293, Apr.1991.
11B. Maglaris et al.,“Performance models of statistical multiplexing in packet video communications,”IEEE Trans. Commun., vol. 36, pp.834-843, July 1988.
12B. Maglaris, G. Karlsson, P. Sen, D. Anastassiou, J. Robbins,“Performance analysis of statistical multiplexing for packet video sources,”Proc. GLOBECOM.87, paper 47.8, Nov. 1987.
13G.Jianbao, I.Rubin,“Multifractal analysis and modeling of VBR video traffic,”Electronics Letters, vol.36, no.3, pp.278-279, Feb. 2000.
14R. Lehnert,“Definitions of terms and parameters and traffic model for the evaluation of switching blocks,”RACE 1022, PKI,-123-0006-CD-CC, Apr. 1989.
15P. Kuehn,”Traffic model for TG (D + E) investigations,”RACE 1022, UST-123-0001-CD-CC, Apr. 1988.
16J. P. Cosmas, A. Odinma-Okafor,“The characterization of video codecs as geometrically modulated deterministic processes,”RACE 1022, QMC-123-0022-CD-CC, Sept. 1989.
17J. P. Cosmas, A. Odinma-Okafor,“The correlations of a conditional replenishment video codec and GMDO source models,”RACE 1022, QMC-123-0023-CD-CC, Nov. 1989.
18R. Jain, S. A. Routhier,“Packet trains-Measurements and a new model for computer network traffic,”IEEE J. Select. Areas Commun., vol. SAC-4, no. 6, pp. 986-995, Sept. 1986.
19W. Xu, A. G. Qureshi,“Adaptive Linear Prediction of MPEG Video Traffic,”Signal Processing and Its Applications 1999, Volume 1, 22-25, Page(s):67 - 70, Aug. 1999.
20Yongfang Wang, Songyu Yu, Xiaokang Yang, Daowen Zou, Zhijun Fang,“H1 Optimal Model for VBR Video Traffic Prediction,”IEEE Transactions on consumer Electronics, Volume 52, Issue 3, Aug. 2006, Page(s):1078- 1083.
21Huabing Liu, Guoqiang Mao,“Prediction Algorithms for Real-Time Variable-Bit-Rate Video,”2005 Asia-Pacific Conference on Communications, 5-5 Oct. 2005, Page(s):664-668.
22S. Chong, S . Li, J. Ghosh,“Predictive dynamic bandwidth allocation for efficient transport of real-time VBR video ATM,”IEEE J. Select. Areas Commun., vol. 13, Jan. 1995.
23A. Adas,“Using adaptive linear prediction to support realtime VBR video under RCBR network service model,”IEEE Trans. Networking, vol. 6, pp. 635-644, Oct. 1998.
24P. Chang, J. Hu,“Optimal nonlinear adaptive prediction and modelling of MPEG video in ATM networks using pipelined recurrent neural networks,”J. Select. Areas Commun., vol.15, pp. 1087-1 100, August 1997.
25H.Zhao, N.Ansari, Y.Q.Shi,“A fast nonlinear adaptive algorithm for video traffic prediction,”Proc. of international conference on information technology: coding and computing (ITCC2002), Las Vegas, pp.54-58, Apr 2002.
26Z. Fang, Y. Zhou, D. Zou,“Kalman optimized model for MPEG-4 VBR sources,”IEEE Transactions on Consumer Electronics, vol.50, no.2, pp.688-690, May 2004.
27A. Qureshi, R. Weber, H. Balakrishnan, J. Guttag, B. Maggs,“Cutting the Electric Bill for Internet-Scale Systems,”ACM SIGCOMM Conference, (August 2009).
28Gong Chen , Wenbo He , Jie Liu , Suman Nath , Leonidas Rigas , Lin Xiao , Feng Zhao,“Energy-aware server provisioning and load dispatching for connection-intensive internet services”, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.337-350, April 16-18, 2008, San Francisco, California.
29Jeffrey S. Chase , Darrell C. Anderson , Prachi N. Thakar , Amin M. Vahdat , Ronald P. Doyle,“Managing energy and server resources in hosting centers”, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada.
30Yiyu Chen , Amitayu Das , Wubi Qin , Anand Sivasubramaniam , Qian Wang , Natarajan Gautam,“Managing server energy and operational costs in hosting centers”, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada.
31Anshul Gandhi , Mor Harchol-Balter , Rajarshi Das , Charles Lefurgy,“Optimal power allocation in server farms”, Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems, June 15-19, 2009, Seattle, WA, USA.
32Ricardo Bianchini, Ram Rajamony,“Power and Energy Management for Server Systems”, Computer, v.37 n.11, p.68-74, November 2004.
33Report to Congress on Server and Data Center Energy Efficiency Public Law 109-431, U.S. Environmental Protection Agency ENERGY STAR Program, August 2, 2007.
34Jiang-chuan Liu,“Streaming Media Caching”, US: Springer, 2005.
2Martin Reisslein, Jeremy Lassetter, Sampath Ratnam, Osama Lotfallah, Frank H.P. Fitzek, Sethuraman Panchanathan.“Traffic and Quality Characterization of Scalable Encoded Video: A Large-Scale Trace-Based Study, Part 1: Overview and Definitions,”Arizona State University, Dept. of Electrical Engineering, Technical Report, Dec 2003.
3Martin Reisslein, Jeremy Lassetter, Sampath Ratnam, Osama Lotfallah, Frank H.P. Fitzek, Sethuraman Panchanathan,“Traffic and Quality Characterization of Scalable Encoded Video: A Large-Scale Trace-Based Study, Part 2: Statistical Analysis of Single-Layer Encoded Video,”Arizona State University, Dept. of Electrical Engineering, Technical Report, Dec 2003.
4Patrick Seeling, Frank H.P. Fitzek, Martin Reisslein,“Video Traces for Network Performance Evaluation,”ISBN: 978-1-4020-5565-2, springer 2007.
5Peter J.Brockwell, Richard A.Davis,“Time Series: Theory and Methods”,2nd ed., ISBN 7-04-008701-4, springer 2001.
6A. Adas, A. Mukhejee,“On resource management and QoS guarantees for long range dependent traffic,”in IEEE INFOCOM, Apr.
7S. Li, L. Hwang,“Queue response to input correlation functions: Discrete spectral analysis,”IEEE Trans. Networking, vol. 1.
8P. Pancha, M. Zarki,“Bandwidth requirements of variable bit rate MPEG source in ATM networks,”IEEE INFOCOM, pp.902-909, Mar. 1993.
9N. Nomura, T. Fujii, N. Ohta,“Basic characteristics of variable rate video coding in ATM environment,”IEEE J. Select. Areas Commun., vol. 7, pp. 752-760, June 1989.
10R. Grunenfelder et al.,“Characterisation of video codecs as autoregressvie moving average process and related queuing system performance,”IEEE J. Select. Areas Commun., vol. 9, pp. 284-293, Apr.1991.
11B. Maglaris et al.,“Performance models of statistical multiplexing in packet video communications,”IEEE Trans. Commun., vol. 36, pp.834-843, July 1988.
12B. Maglaris, G. Karlsson, P. Sen, D. Anastassiou, J. Robbins,“Performance analysis of statistical multiplexing for packet video sources,”Proc. GLOBECOM.87, paper 47.8, Nov. 1987.
13G.Jianbao, I.Rubin,“Multifractal analysis and modeling of VBR video traffic,”Electronics Letters, vol.36, no.3, pp.278-279, Feb. 2000.
14R. Lehnert,“Definitions of terms and parameters and traffic model for the evaluation of switching blocks,”RACE 1022, PKI,-123-0006-CD-CC, Apr. 1989.
15P. Kuehn,”Traffic model for TG (D + E) investigations,”RACE 1022, UST-123-0001-CD-CC, Apr. 1988.
16J. P. Cosmas, A. Odinma-Okafor,“The characterization of video codecs as geometrically modulated deterministic processes,”RACE 1022, QMC-123-0022-CD-CC, Sept. 1989.
17J. P. Cosmas, A. Odinma-Okafor,“The correlations of a conditional replenishment video codec and GMDO source models,”RACE 1022, QMC-123-0023-CD-CC, Nov. 1989.
18R. Jain, S. A. Routhier,“Packet trains-Measurements and a new model for computer network traffic,”IEEE J. Select. Areas Commun., vol. SAC-4, no. 6, pp. 986-995, Sept. 1986.
19W. Xu, A. G. Qureshi,“Adaptive Linear Prediction of MPEG Video Traffic,”Signal Processing and Its Applications 1999, Volume 1, 22-25, Page(s):67 - 70, Aug. 1999.
20Yongfang Wang, Songyu Yu, Xiaokang Yang, Daowen Zou, Zhijun Fang,“H1 Optimal Model for VBR Video Traffic Prediction,”IEEE Transactions on consumer Electronics, Volume 52, Issue 3, Aug. 2006, Page(s):1078- 1083.
21Huabing Liu, Guoqiang Mao,“Prediction Algorithms for Real-Time Variable-Bit-Rate Video,”2005 Asia-Pacific Conference on Communications, 5-5 Oct. 2005, Page(s):664-668.
22S. Chong, S . Li, J. Ghosh,“Predictive dynamic bandwidth allocation for efficient transport of real-time VBR video ATM,”IEEE J. Select. Areas Commun., vol. 13, Jan. 1995.
23A. Adas,“Using adaptive linear prediction to support realtime VBR video under RCBR network service model,”IEEE Trans. Networking, vol. 6, pp. 635-644, Oct. 1998.
24P. Chang, J. Hu,“Optimal nonlinear adaptive prediction and modelling of MPEG video in ATM networks using pipelined recurrent neural networks,”J. Select. Areas Commun., vol.15, pp. 1087-1 100, August 1997.
25H.Zhao, N.Ansari, Y.Q.Shi,“A fast nonlinear adaptive algorithm for video traffic prediction,”Proc. of international conference on information technology: coding and computing (ITCC2002), Las Vegas, pp.54-58, Apr 2002.
26Z. Fang, Y. Zhou, D. Zou,“Kalman optimized model for MPEG-4 VBR sources,”IEEE Transactions on Consumer Electronics, vol.50, no.2, pp.688-690, May 2004.
27A. Qureshi, R. Weber, H. Balakrishnan, J. Guttag, B. Maggs,“Cutting the Electric Bill for Internet-Scale Systems,”ACM SIGCOMM Conference, (August 2009).
28Gong Chen , Wenbo He , Jie Liu , Suman Nath , Leonidas Rigas , Lin Xiao , Feng Zhao,“Energy-aware server provisioning and load dispatching for connection-intensive internet services”, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.337-350, April 16-18, 2008, San Francisco, California.
29Jeffrey S. Chase , Darrell C. Anderson , Prachi N. Thakar , Amin M. Vahdat , Ronald P. Doyle,“Managing energy and server resources in hosting centers”, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada.
30Yiyu Chen , Amitayu Das , Wubi Qin , Anand Sivasubramaniam , Qian Wang , Natarajan Gautam,“Managing server energy and operational costs in hosting centers”, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada.
31Anshul Gandhi , Mor Harchol-Balter , Rajarshi Das , Charles Lefurgy,“Optimal power allocation in server farms”, Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems, June 15-19, 2009, Seattle, WA, USA.
32Ricardo Bianchini, Ram Rajamony,“Power and Energy Management for Server Systems”, Computer, v.37 n.11, p.68-74, November 2004.
33Report to Congress on Server and Data Center Energy Efficiency Public Law 109-431, U.S. Environmental Protection Agency ENERGY STAR Program, August 2, 2007.
34Jiang-chuan Liu,“Streaming Media Caching”, US: Springer, 2005.