An overview of long-range dependent network traffic engineering and analysis: characteristics, simulation, modelling and control

ABSTRACT

This paper surveys techniques for the recognition and treatment of self-similar network or internetwork traffic. Various researchers have reported traffic measurements that demonstrate considerable burstiness on a range of time scales with properties of self-similarity. Rapid technological development has widened the scope of network and Internet applications and, in turn, increased traffic volume. The exponential growth of the number of servers, as well as the number of users, causes Internet performance to be problematic as a result of the significant impact that long-range dependent traffic has on buffer requirements. Consequently, accurate and reliable measurement, analysis and control of Internet traffic are vital. The most significant techniques for performance evaluation include theoretical analysis, simulation, and empirical study based on measurement. In this research, we discuss existing and recent developments in performance evaluation and control tools used in network traffic engineering.

References

1. Kolmogorov, A. N., The local structure of turbulence in incompressible viscous fluid for very large Reynolds numbers, C. R. Acad. Sci. URSS (N. S.), Vol. 30, 1941, pp. 301--305. {Translation in Turbulence (S. K. Friedlander and L. Topper, eds.) 151--155. (1961). Interscience, New York}.
2. Mandelbrot B. B., Self-similar error clusters in communications systems and the concept of conditional stationarity. IEEE Transactions on Communications Technology, 1965, COM-13, pp. 71--90.
3. Mandelbrot B. B. and Van Ness J. W., Fractional Brownian motions, fractional noises and applications. SIAM Review: 10, 1968, pp. 422--437.
4. Mandelbrot B. B. and Wallis J. R., M & James R. WALLIS, Some long-run properties of geophysical records. Water Resources Research: 5, 1969, pp. 321--340.
5. Mandelbrot B. B. and James R. WALLIS, Noah, Joseph and operational hydrology. Water Resources Research: 4, 1968, pp. 909--918.
6. Will E. Leland, Murad S. Taqqu, Walter Willinger, Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Trans. Networking, Vol. 2, No. 1, February 1994, pp. 1--15.
7. Willinger, W., Paxson, V. and Taqqu, M. S., Self-Similarity and Heavy-tails: Structural Modeling of Network Traffic, A Practical Guide to Heavy Tails, 1998, Birkhauser, Boston.
8. Jena Ajit K. and Popescu Adrian. Traffic engineering for Internet applications, SPIE proceedings series, Internet Performance and Control of Network Systems II, Robert D. van der Mei; Frank Huebner-Szabo de Bucs; Eds., Vol. 4523, 2001, pp. 67--78.
9. Philippe Owezarski, Nicolas Larrieu, Measurement Based Approach of Congestion Control for enforcing a robust QoS in the Internet, Report LAAS No. 04722, International Conference on Internet Surveillance and Protection (ICISP'06), Cap Esterel (France), 27--29 August 2006.
10. Hurst H. E., Long-term storage capacity of reservoirs, Transactions of the American Society of Civil Engineers, 1951, vol.116, pp 770--808.
11. Ton Dieker, Simulation of Fractional Brownian Motion, Masters Thesis, Department of Mathematical Sciences, University of Twente, The Netherlands, 2004.
12. T. Higuchi, Approach to an irregular time series on the basis of the fractal theory, Physica D, 1988, vol.31, pp. 277--283.
13. P. Abry, P. Flandrin, M. S. Taqqu and D. Veitch, Wavelets for the Analysis, Estimation, and Synthesis of Scaling Data, K. Park and W. Willinger (editors), Self-Similar Network Traffic and Performance Evaluation. John Wiley & Sons, New York, 2000, pp. 39--88.
14. Kihong Park, Gitae Kim, Mark Crovella, On the relationship between file sizes, transport protocols, and self-similar network traffic, Fourth International Conference on Network Protocols (ICNP'96). 1996, pp. 171--180.
15. Vern Paxson and Sally Floyd, Wide-Area Traffic: The Failure of Poisson Modeling, IEEE/ACM Transactions on Networking, June 1995, Vol. 3 No. 3, pp. 226--244.
16. Ashok Erramilli, Onuttom Narayan, and Walter Willinger, Experimental Queueing Analysis with Long-range Dependent Packet Traffic, IEEE/ACM Transactions on Networking, April 1996, Vol. 4, No. 2, pp. 209--223.
17. O. Rose, Estimation of the Hurst Parameter of Long-Range Dependent Time Series, Report No. 137, February 1996, Institute of Computer Science, University of Wurzburg.
18. E. Willekens and J. Teugels, Asymptotic expansions for waiting time probabilities in an M/G/1 queue with longtailed service time, Queueing Systems 10, 1992, pp. 295--312.
19. An Ge, Franco Callegati, and Lakshman S. Tamil, On Optical Burst Switching and Self-Similar Traffic, IEEE Communications Letters, March 2000, Vol. 4, No. 3, pp. 98--100.
20. R. J. Gibbens, Traffic characterisation and effective bandwidths for broadband network traces, Stochastic Networks, Theory and Applications, 1996, pp. 169--179, Oxford Science Pub.
21. Amit Aggarwal, Stefan Savage and Thomas Anderson, Understanding the Performance of TCP Pacing. Proc. of the IEEE INFOCOM 2000 Conference on Computer Communications, March 2000, pp. 1157 -- 1165.
22. K. Park, G. Kim, and M. Crovella, On the effect of self-similarity on network performance, In Proceedings of the SPIE International Conference on Performance and Control of Network System, November 1997, pp 296--310.
23. A. Veres, Zs. Kenesi, S. Molnár, G. Vattay, TCP's Role in the Propagation of Self-Similarity in the Internet, Computer Communications, Special issue on Performance Evaluation of IP Networks and Services, Vol. 26, Issue 8, May 2003, pp. 899--913.
24. J. H. B. Deane, C. Smythe, and D. J. Jefferies. Self-similarity in a deterministic model of data transfer, International Journal of Electronics, 80(5), 1996, pp. 677--691.
25. Brocklebank J. and D. Dickey. SAS System for Forecasting Time Series. SAS Institute Inc. Cary NC. 1986.
26. Walter Willinger, Vern Paxson, and Murad Taqqu, Self-similarity and Heavy Tails: Structural Modeling of Network Traffic, Adler, R., Feldman, R., and Taqqu, M. S., (editors), In A Practical Guide to Heavy Tails: Statistical Techniques and Applications, Birkhauser, 1998.
27. Cox D., Long-Range Dependence: a Review. H. A. David and H. T. David (eds.), In Statistics: An Appraisal, Iowa State Statistical Library, The Iowa State University Press, 1984, pp.55--74.
28. Duffy D. E., McIntosh A. A., Rosenstein M., Willinger, W., Statistical analysis of CCSN/SS7 traffic data from working CCS subnetworks, IEEE JSAC, Vol. 12, No. 3, April 1994, pp. 544--551.
29. Ashok Erramilli, Onuttom Narayan, Walter Willinger, Experimental queueing analysis with long-range dependent packet traffic, IEEE/ACM Transactions on Networking, Vol. 4, No. 2, April 1996, pp. 209 -- 223.
30. V. Bolotin, J. Coombs-Reyes, D. Heyman, Y. Levy and D. Liu, IP Traffic Characterization for Planning and Control, Teletraffic Sci. and Eng., vol. 3a, Proc. 16th Int'l. Teletraffic Congress, P. Key and D. Smith, Eds., June 1999, pp. 425--436.
31. http://www-dirt.cs.unc.edu/unc02_ts/, visited on January 2005.
32. Fei Xue and Lj. Trajkovic, Performance analysis of a wavelet-based Hurst parameter estimator for self-similar traffic, Proc. SPECTS '2000, Vancouver, BC, Canada, July 2000, pp. 294--298.
33. UNC Network Data Analysis Study Group, University of North Carolina, http://www-dirt.cs.unc.edu/net_lrd/, visited on December 2002.
34. Stilian Stoev, Murad Taqqu, Cheolwoo Park and J. S. Marron, Strengths and Limitations of the Wavelet Spectrum Method in the Analysis of Internet Traffic, SAMSI, Technical Report #2004-8, March 26, 2004.
35. N. Cackov, Wavelet-based estimation of long-range dependence in video and network traffic traces, MSc thesis, School of Engineering Science, Simon Fraser University, 2005.
36. Clegg Richard G., A practical guide to measuring the Hurst parameter, International Journal of Simulation: Systems, Science & Technology, 7(2), 2006, pp. 3--14.
37. Sonechkin D. M., Astafyeva N. M., Datsenko N. M., Ivachtchenko N. N. and Jakubiak, B., Multiscale Oscillations of the Global Climate System as Revealed by Wavelet Transform of Observational Data Time Series, Theoretical and Applied Climatology, Volume 64, Issue 1/2, 1999, pp. 131--142.
38. M. S. Taqqu, V. Teverovsky, and W. Willinger, Estimators for long-range dependence: an empirical study, Fractals, 3, 1995, pp. 785--798.
39. Trang D. D., SÁNDOR M., On the Effects of Non-Stationarity in Long-Range Dependence Tests, Periodica Pol. Elec. Eng., Vol. 43, No. 4, 1999, pp. 227--250.
40. Marwan Krunz: On the Limitations of the Variance-time Test for Inference of Long-range Dependence, INFOCOM 2001, pp.1254--1260
41. Thomas Karagiannis, Michalis Faloutsos and Rudolf Riedi, Long-Range Dependence: Now you see it, now you don't! Global Internet Symposium (in IEEE GLOBECOM), Taipei, Taiwan, November 17--21, 2002.
42. S. Molnár, A. Vidács, On Modeling and Shaping Self-Similar ATM Traffic, 15th International Teletraffic Congress, Washington, DC, USA, June 23--27, 1997.
43. Karim M. Rezaul and Grout, V., Exploring the Reliability and Robustness of HEAF(2) for Quantifying the Intensity of Long-Range Dependent Network Traffic, International Journal of Computer Science and Network Security, Vol. 7, No. 2, February 2007, pp221--229.
44. Karim M. Rezaul, Algirdas Pakštas, Robert Gilchrist, Thomas M. Chen, HEAF: A Novel Estimator for Long-Range Dependent Self-similar Network Traffic, Y. Koucheryavy, J. Harju, and V. B. Iversen (Eds.): Next Generation Teletraffic and Wired/Wireless Advanced Networking (NEW2AN), May 29 - June 2, 2006, LNCS 4003, pp. 34 -- 45.
45. Karim M. Rezaul, Algirdas Pakštas, Robert Gilchrist, Investigation of the Properties of the HEAF Estimator Using Simulation Experiments and MPEG-encoded Video Traces, 10th IEEE International Conference on Intelligent Engineering Systems (INES 2006), London, UK, June 26--28, 2006, pp. 276--281.
46. V. Paxson and S. Floyd., Wide Area Traffic: The Failure of Poisson Modeling, IEEE/ACM Transactions on Networking, June 1995, pp.236--244.
47. Mark E. Crovella and Lester Lipsky, Long-Lasting Transient Conditions in Simulations with Heavy-Tailed Workloads, In Proceedings of the 1997 Winter Simulation Conference, 1997. pp.1005--1012.
48. Mark E. Crovella and Azer Bestavros, Explaining World Wide Web Traffic Self-Similarity, October 12, 1995, Boston University, Technical Report TR-95-015.
49. Karim M. Rezaul. & Grout, V. A Comparison of Methods for Estimating the Tail Index of Heavy-tailed Internet Traffic, Proceedings of the second International Joint e-Conference on Computer, Information, and Systems Sciences, and Engineering (CISSE 2006). December 4 -- 14, 2006
50. Karim M. Rezaul and Algirdas Pakštas, Web Traffic Analysis Based on EDF Statistics, 7th Annual PostGraduate Symposium on the Convergence of Telecommunications, Networking and Broadcasting (PGnet 2006), Liverpool, UK, June 26--27, 2006, pp. 340--345.
51. Karim M. Rezaul and Grout, V. CoLoRaDe: A Novel Algorithm for Controlling Long-Range Dependent Network Traffic, Proceedings of the Sixth International Conference on Networking (ICN 2007), Martinique, French Caribbean, 22--28 April 2007.
52. Amit Aggarwal, Stefan Savage and Thomas Anderson, Understanding the Performance of TCP Pacing. Proc. of the IEEE INFOCOM 2000 Conference on Computer Communications, March 2000, pp. 1157 -- 1165.
53. K. Park, G. Kim, and M. Crovella, On the effect of self-similarity on network performance, In Proceedings of the SPIE International Conference on Performance and Control of Network System, November 1997, pp 296--310.
54. Karim M. Rezaul and Grout, V. BPTraSha: A Novel Algorithm for Shaping Bursty Nature of Internet Traffic, Proceedings of the 3rd IARIA/IEEE Advanced International Conference on Telecommunications (AICT 2007), May 13--19 2007, Mauritius.
55. R. Riedi, M. S. Crouse, V. Ribero, and R. G. Baraniuk, A Multifractal Wavelet Model with Application to Network Traffic, IEEE Trans. Info. Theory, Special Issue on Multiscale signal analysis and its application, Vol. 45, April 1999, pp992--1018.
56. Jens Feder, Fractals, Plenum NY and London, 1988.
57. G. E. P. Box and G. M. Jenkins, Time Series Analysis: Forecasting and Control, 2nd ed. San Francisco, CA: Holden Day, 1976.
58. C. W. J. Granger and R. Joyeux, An introduction to long-memory time series models and fractional differencing, Journal of Time Series Analysis, vol. 1, pp. 15--29, 1980.
59. J. R. M. Hosking, Fractional differencing, Biometrika, vol. 68, pp. 156--176. 1981
60. D. Veitch, P. Flandrin, P. Abry, R. Riedi, R. Baraniuk. The Multiscale Nature of Network Traffic: Discovery, Analysis, and Modelling, IEEE Signal Processing Magazine, pp 28--46, Vol. 19, No. 3, May, 2002.
61. Gao J. and Rubin I., Multiplicative Multifractal Modeling of Long-range dependent Network Traffic, International Journal of Communication Systems, 2001, Vol. 14, pp 783--801.
62. Steven Bradley Lowen and Malvin Carl Teich, Fractal-Based Point Processes, Wiley, 2005
63. Parulekar M., Makowski M. A., M|G|Infinity Input Processes: A Versatile Class of Models for Network Traffic, In Proc. IEEE INFOCOM, Kobe, Japan, pp419--426, April 1997.
64. M. Krunz and A. M. Makowski. Modeling Video Traffic Using M/G/Infinity Input Processes: A Compromise between Markovian and LRD Models. In IEEE Journal on Selected Areas in Communications, 16(5): 733--748, June 1998.
65. Marwan Krunz, Armand M. Makowski, A Source Model for VBR Video Traffic Based On M/G/infinity Input Processes. INFOCOM 1998, pp1441--1448.
66. D. R. Cox and V. Isham, Point Processes, Chapman and Hall, New York, 1980.

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• Computing methodologies

  • Modeling and simulation

• General and reference

  • Cross-computing tools and techniques

    • Measurement

    • Performance

• Networks

  • Network protocols

  • Network services

    • Network monitoring