Fast, approximate synthesis of fractional Gaussian noise for generating self-similar network traffic

ABSTRACT

Recent network traffic studies argue that network arrival processes are much more faithfully modeled using statistically self-similar processes instead of traditional Poisson processes [LTWW94, PF95]. One difficulty in dealing with self-similar models is how to efficiently synthesize traces (sample paths) corresponding to self-similar traffic. We present a fast Fourier transform method for synthesizing approximate self-similar sample paths for one type of self-similar process, Fractional Gaussian Noise, and assess its performance and validity. We find that the method is as fast or faster than existing methods and appears to generate close approximations to true self-similar sample paths. We also discuss issues in using such synthesized sample paths for simulating network traffic, and how an approximation used by our method can dramatically speed up evaluation of Whittle's estimator for H, the Hurst parameter giving the strength of long-range dependence present in a self-similar time series.

REFERENCES

• 1: [AV97] P. Abry and D. Veitch, "Wavelet Analysis of Long Range Dependent Traffic," to appear in IEEE Transactions on Information Theory, 1997.
• 2: [B86] J. Beran, "Estimation, Testing and Prediction for Self-Similar and Related Processes", Ph.D. dissertation, ETH, Zürich, 1986.
• 3: [B92a] J. Beran, "A Goodness-of-fit Test for Time Series with Long Range Dependence", Journal of the Royal Statistical Society B, 54(3), pp. 749- 760, 1992.
• 4: [B92b] J. Beran, "Statistical Methods for Data with Long-Range Dependence", with discussion, Statistical Science, 7(4), pp. 404-427, 1992.
• 5: [BSTW95] J. Beran, R. Sherman, M. Taqqu, and W. Willinger, "Variable-Bit-Rate Video Traffic and Long-Range Dependence", IEEE Transactions on Communications , 43(2-4), pp. 1566-1579, 1995.
• 6: [C84] D. R. Cox, "Long-Range Dependence: A Review", in Statistics: An Appraisal, Proceedings 50th Anniversary Conference, Iowa State Statistical Library, H. A. David and H. T. David, editors, Iowa State University Press, pp. 55-74, 1984.
• 7: Ralph B D'Agostino , Michael A Stephens, Goodness-of-fit techniques, Marcel Dekker, Inc., New York, NY, 1986
• 8: Ashok Erramilli , Onuttom Narayan , Walter Willinger, Experimental queueing analysis with long-range dependent packet traffic, IEEE/ACM Transactions on Networking (TON), v.4 n.2, p.209-223, April 1996 [doi>10.1109/90.491008]
• 9: [F66] W. Feller, An Introduction to Probability Theory and Its Applications, Volume II, John Wiley and Sons, 1966.
• 10: [F92] P. Flandrin, "Wavelet Analysis and Synthesis of Fractional Brownian Motion" IEEE Transactions on Information Theory, 38(2), pp. 910-917, March 1992.
• 11: [FM94] V. Frost and B. Melamed, "Traffic Modeling for Telecommunications Networks", IEEE Communications Magazine, 32(3), pp. 70-80, March, 1994.
• 12: Mark William Garrett, Contributions toward real-time services on packet switched networks, Columbia University, New York, NY, 1993
• 13: Mark W. Garrett , Walter Willinger, Analysis, modeling and generation of self-similar VBR video traffic, Proceedings of the conference on Communications architectures, protocols and applications, p.269-280, August 31-September 02, 1994, London, United Kingdom
• 14: [KK93] L. Kaplan and C.-C. Kuo, "Fractal Estimation from Noisy Data via Discrete Fractional Gaussian Noise (DFGN) and the Haar Basis," IEEE Transactions on Signal Processing, 41(12), pp. 3554-3562, December 1993.
• 15: [KK94] L. Kaplan and C.-C. Kuo, "Extending Self-Similarity for Fractional Brownian Motion," IEEE Transactions on Signal Processing, 42(12), pp. 3526-3530, December 1994.
• 16: [LEWW95] W.-C. Lau, A. Erramilli, J. Wang, and W. Willinger, "Self-Similar Traffic Generation: The Random Midpoint Displacement Algorithm and Its properties," Proceedings of ICC'95, 1995.
• 17: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 18: Vern Paxson, Empirically derived analytic models of wide-area TCP connections, IEEE/ACM Transactions on Networking (TON), v.2 n.4, p.316-336, Aug. 1994 [doi>10.1109/90.330413]
• 19: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 20: Vern Paxson, End-to-end Internet packet dynamics, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.139-152, September 14-18, 1997, Cannes, France
• 21: [RP94] S. Rambaldi and O. Pinazza, "An accurate fractional Brownian motion generator," Physica A, 208(1), pp. 21-30, July 1, 1994.
• 22: [ST94] G. Samorodnitsky and M. Taqqu, Stable Non-Gaussian Random Processes, Chapman & Hall, 1994.
• 23: [S92] S. Schiff, "Resolving time-series structure with a controlled wavelet transform," Optical Engineering, 31(11), pp. 2492-2495, November 1992.
• 24: [SLN94] M. Stoksik, R. Lane, and D. Nguyen, "Accurate synthesis of fractional Brownian motion using wavelets," Electronics Letters, 30(5), pp. 383-384, 3rd March 1994.
• 25: [TTW95] M. Taqqu, V. Teverovsky, and W. Willinger, "Estimators for Long-Range Dependence: An Empirical Study" Fractals, 3(4), pp. 785-798, 1995.
• 26: [WTLW95] W. Willinger, M. Taqqu, W. Leland, and D. Wilson, "Self-Similarity in High-Speed Packet Traffic: Analysis and Modeling of Ethernet Traffic Measurements" Statistical Science, 10(1), pp 67-85, February 1995.
• 27: Walter Willinger , Murad S. Taqqu , Robert Sherman , Daniel V. Wilson, Self-similarity through high-variability: statistical analysis of Ethernet LAN traffic at the source level, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.71-86, Feb. 1997 [doi>10.1109/90.554723]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Experimentation, Management