Vern Paxson
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.
- {AV97} P. Abry and D. Veitch, "Wavelet Analysis of Long Range Dependent Traffic," to appear in IEEE Transactions on Information Theory, 1997. Google Scholar
Digital Library
- {B86} J. Beran, "Estimation, Testing and Prediction for Self-Similar and Related Processes", Ph.D. dissertation, ETH, Zürich, 1986.Google Scholar
- {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.Google Scholar
- {B92b} J. Beran, "Statistical Methods for Data with Long-Range Dependence", with discussion, Statistical Science, 7(4), pp. 404-427, 1992.Google ScholarCross Ref
- {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.Google ScholarCross Ref
- {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.Google Scholar
- {DS86} R. B. D'Agostino and M. A. Stephens, editors, Goodness-of-Fit Techniques, Marcel Dekker, Inc., 1986. Google ScholarDigital Library
- {ENW96} A. Erramilli, O. Narayan, and W. Willinger, "Experimental Queueing Analysis with Long-Range Dependent Packet Traffic," IEEE/ACM Transactions on Networking, 4(2), pp. 209-223, Apr. 1996. Google ScholarDigital Library
- {F66} W. Feller, An Introduction to Probability Theory and Its Applications, Volume II, John Wiley and Sons, 1966.Google Scholar
- {F92} P. Flandrin, "Wavelet Analysis and Synthesis of Fractional Brownian Motion" IEEE Transactions on Information Theory, 38(2), pp. 910-917, March 1992.Google ScholarDigital Library
- {FM94} V. Frost and B. Melamed, "Traffic Modeling for Telecommunications Networks", IEEE Communications Magazine, 32(3), pp. 70-80, March, 1994.Google ScholarDigital Library
- {G93} M. Garrett, "Contributions Toward Real-Time Services on Packet Switched Networks", Ph.D. thesis, Columbia University, CU/CTR/TR 340-93- 20, 1993. Google ScholarDigital Library
- {GW94} M. Garrett and W. Willinger, "Analysis, Modeling and Generation of Self-Similar VBR Video Traffic", Proceedings of SIGCOMM '94, September, 1994. Google ScholarDigital Library
- {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.Google ScholarDigital Library
- {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.Google ScholarDigital Library
- {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.Google Scholar
- {LTWW94} W. Leland, M. Taqqu, W. Willinger, and D. Wilson, "On the Self-Similar Nature of Ethernet Traffic (Extended Version)", IEEE/ACM Transactions on Networking, 2(1), pp. 1-15, February 1994. Google ScholarDigital Library
- {P94} V. Paxson, "Empirically-Derived Analytic Models of Wide-Area TCP Connections," IEEE/ACM Transactions on Networking, 2(4), pp. 316-336, August 1994. Google ScholarDigital Library
- {PF95} V. Paxson and S. Floyd, "Wide-Area Traffic: The Failure of Poisson Modeling" IEEE/ACM Transactions on Networking, 3(3), pp. 226-244, June 1995. Google ScholarDigital Library
- {P97} V. Paxson, "End-to-End Internet Packet Dynamics," Proceedings of SIGCOMM '97, Cannes, France, September 1997. Google ScholarDigital Library
- {RP94} S. Rambaldi and O. Pinazza, "An accurate fractional Brownian motion generator," Physica A, 208(1), pp. 21-30, July 1, 1994.Google ScholarCross Ref
- {ST94} G. Samorodnitsky and M. Taqqu, Stable Non-Gaussian Random Processes, Chapman & Hall, 1994.Google Scholar
- {S92} S. Schiff, "Resolving time-series structure with a controlled wavelet transform," Optical Engineering, 31(11), pp. 2492-2495, November 1992.Google ScholarCross Ref
- {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.Google ScholarCross Ref
- {TTW95} M. Taqqu, V. Teverovsky, and W. Willinger, "Estimators for Long-Range Dependence: An Empirical Study" Fractals, 3(4), pp. 785-798, 1995.Google ScholarCross Ref
- {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.Google ScholarCross Ref
- {WTSW97} W. Willinger, M. Taqqu, R. Sherman, and D. Wilson, "Self-Similarity Through High-Variability: Statistical Analysis of Ethernet LAN Traffic at the Source Level" IEEE/ACM Transactions on Networking , 5(1), pp. 71-86, January 1997. Google ScholarDigital Library
Index Terms
- Fast, approximate synthesis of fractional Gaussian noise for generating self-similar network traffic
Recommendations
Synthesis of fractional gaussian noise using linear approximation for generating self-similar network traffic
The present paper focuses on self-similar network traffic generation. Network traffic modeling studies the generation of synthetic sequences. The generated sequences must have similar features to the measured traffic. Exact methods for generating self-...
The influence of self-similar traffic on telecommunication network queuing
CompSysTech '09: Proceedings of the International Conference on Computer Systems and Technologies and Workshop for PhD Students in ComputingThe self-similar network traffic influence on the telecommunication queuing systems with infinite and finite buffer sizes in terms of the average queuing size and buffer overflow probability is investigated in this paper. The obtained results show that ...
Comments