Proof of a fundamental result in self-similar traffic modeling

ABSTRACT

We state and prove the following key mathematical result in self-similar traffic modeling: the superposition of many ON/OFF sources (also known as packet trains) with strictly alternating ON- and OFF-periods and whose ON-periods or OFF-periods exhibit the Noah Effect (i.e., have high variability or infinite variance) can produce aggregate network traffic that exhibits the Joseph Effect (i.e., is self-similar or long-range dependent). There is, moreover, a simple relation between the parameters describing the intensities of the Noah Effect (high variability) and the Joseph Effect (self-similarity). This provides a simple physical explanation for the presence of self-similar traffic patterns in modern high-speed network traffic that is consistent with traffic measurements at the source level. We illustrate how this mathematical result can be combined with modern high-performance computing capabilities to yield a simple and efficient linear-time algorithm for generating self-similar traffic traces.We also show how to obtain in the limit a Lévy stable motion, that is, a process with stationary and independent increments but with infinite variance marginals. While we have presently no empirical evidence that such a limit is consistent with measured network traffic, the result might prove relevant for some future networking scenarios.

REFERENCES

• 1: [1] P. Billingsley. Convergence of Probability Measures J. Wiley & Sons, Inc., New York, 1968.
• 2: [2] N. H. Bingham, C. M. Goldie, and J. L. Teugels. Regular Variation. Cambridge University Press, 1987.
• 3: [3] K. L. Chung. A Course in Probability Theory. Academic Press, New York, 2nd edition, 1974.
• 4: [4] D. R. Cox. Renewal Theory. Methuen & Co., London, 1967. Science Paperback Edition.
• 5: [5] W. Feller. An Introduction to Probability Theory and its Applications, volume 2. Wiley, New York, 2nd edition, 1971.
• 6: [6] D. Heath, S. Resnick and G. Samorodnitsky. Heavy Tails and Long-Range Dependence in On/Off Processes and Associated Fluid Models. Preprint, School of ORIE, Cornell University, Ithaca, NY, 1996.
• 7: [7] I. A. Ibragimov and Yu. V. Linnik. Independent and stationary sequences of random variables. Wolters-Nordhoff, The Netherlands, 1971.
• 8: [8] R. Jain and S. A. Routhier. Packet Trains: Measurements and a New Model for Computer Network Traffic. IEEE Journal on Selected Areas in Communications, Vol. 4, pp. 986-995, 1986.
• 9: [9] S. Karlin and H. M. Taylor. A First Course in Stochastic Processes. Academic Press, New York, second edition, 1975.
• 10: [10] T. Konstantopoulos and S-J Lin. High variability versus long-range dependence for network performance. Preprint, 1996.
• 11: [11] K. R. Krishnan. The Hurst Parameter of non-Markovian On-Off Traffic Sources. Preprint, 1995.
• 12: [12] W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson. On the Self-Similar Nature of Ethernet Traffic. ACM/SIGCOMM Computer Communications Review, Vol. 23, pp. 183-193, 1993. Proceedings of the ACM/SIGCOMM'93, San Francisco, September 1993.
• 13: 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]
• 14: [14] S. B. Lowen and M. C. Teich. Fractal Renewal Processes Generate 1/f Noise. Physical Review E, 47: 992-1001, 1993.
• 15: [15] B. B. Mandelbrot. Long-Run Linearity, Locally Gaussian Processes, H-Spectra and Infinite Variances. International Economic Review, Vol. 10, pp. 82-113, 1969.
• 16: [16] G. Samorodnitsky and M. S. Taqqu. Stable Non-Gaussian Processes: Stochastic Models with Infinite Variance. Chapman and Hall, New York, London, 1994.
• 17: [17] A. V. Skorohod. Limit theorems for stochastic processes with independent increments. Theory of Probability and Its Applications, 2: 138-171, 1957.
• 18: [18] M. S. Taqqu. Weak Convergence to Fractional Brownian Motion and to the Rosenblatt Process. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 31: 287-302, 1975.
• 19: [19] M. S. Taqqu and J. Levy. Using Renewal Processes to Generate Long-Range Dependence and High Variability. In E. Eberlein and M. S. Taqqu, editors, Dependence in Probability and Statistics, pp. 73-89, Boston, 1986. Birkhäuser.
• 20: [20] J. L. Teugels. Renewal Theorems when the First or the Second Moment is Infinite. The Annals of Mathematical Statistics, 39, pp. 1210-1219, 1968.
• 21: [21] W. Willinger, M. S. Taqqu, R. Sherman, and D. V. Wilson. Self-similarity through High-Variability: Statistical Analysis of Ethernet LAN Traffic at the Source Level. Computer Communications Review, 25, pp. 100-113, 1995. Proceedings of the ACM/SIGCOMM'95, Cambridge, MA, August 1995.
• 22: 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Theory, Verification