Self-similarity through high-variability: statistical analysis of ethernet LAN traffic at the source level

ABSTRACT

A number of recent empirical studies of traffic measurements from a variety of working packet networks have convincingly demonstrated that actual network traffic is self-similar or long-range dependent in nature (i.e., bursty over a wide range of time scales) - in sharp contrast to commonly made traffic modeling assumptions. In this paper, we provide a plausible physical explanation for the occurrence of self-similarity in high-speed network traffic. Our explanation is based on convergence results for processes that exhibit high variability (i.e., infinite variance) and is supported by detailed statistical analyses of real-time traffic measurements from Ethernet LAN's at the level of individual sources.Our key mathematical result states that the superposition of many ON/OFF sources (also known as packet trains) whose ON-periods and OFF-periods exhibit the Noah Effect (i.e., have high variability or infinite variance) produces aggregate network traffic that features 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). An extensive statistical analysis of two sets of high time-resolution traffic measurements from two Ethernet LAN's (involving a few hundred active source-destination pairs) confirms that the data at the level of individual sources or source-destination pairs are consistent with the Noah Effect. We also discuss implications of this simple physical explanation for the presence of self-similar traffic patterns in modern high-speed network traffic for (i) parsimonious traffic modeling (ii) efficient synthetic generation of realistic traffic patterns, and (iii) relevant network performance and protocol analysis.

REFERENCES

• 1: Tim Berners-Lee , Robert Cailliau , Ari Luotonen , Henrik Frystyk Nielsen , Arthur Secret, The World-Wide Web, Communications of the ACM, v.37 n.8, p.76-82, Aug. 1994 [doi>10.1145/179606.179671]
• 2: F. Brichet, J Roberts, A. Simonian, and D. Veitch. Heavy traffic analysis of a fluid queue fed by on/off sources with long-range dependence. Preprint, 1995.
• 3: F. Danzig, S Jam,n, R. C~ceres, D. Mitzel and D. Estrin. An Empirical Workload Model for Driving Wide-Area TCP/IP Network Simulations. Internetwork~ng: Research and Experience, Vol. 3, pp. 1-26, 1992.
• 4: N.G. Duffield. Economies of scale in queues with sources having power-law large deviation scalings. Preprint, 1994.
• 5: N G. Duffield and N O'Connell. Large deviations and overflow probabilities for the general single-server queue, with applications. Prec. Cambridge Phil. Soc,~ 1995 (to appear).
• 6: Anwar I. Elwalid , Debasis Mitra, Effective bandwidth of general Markovian traffic sources and admission control of high speed networks, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.329-343, June 1993 [doi>10.1109/90.234855]
• 7: A. Erramilli, O. Narayan, and W. Willinger. Experimental queueing analysis with long-range dependent traffic. Preprint, 1994.
• 8: Riccardo Gusella, A characterization of the variability of packet arrival processes in workstation networks, University of California at Berkeley, Berkeley, CA, 1992
• 9: R. Gusella. A measurement study of diskless workstation traffic on an Ethernet. IEEE Transactions on Comraun~cations, Vol. 38, pp. 1557-1568, 1990.
• 10: R. Gusella. Characterizing the variability of arrival processes with indexes of dispersion. IEEE Journal on Selected Areas tn Cornmunzcat, ons, Vol. 9, pp. 203-211, 1991.
• 11: B. M. Hill. A simple general approach to reference about the tail of a distribution The Annals of Stat,stzcs, Vol. 3, pp 1163- 1174, 1975.
• 12: R. Jain and S. A. Routhier. Packet trains: Measurements and a new model for Computer network traffic. IEEE Journal on Selected Areas in Coraraunicattons, Vol. 4, pp 986-995, 1986.
• 13: S. M. Klivansky, A. Mukherjee, and C. Song. On Long-Range Dependence in NSFNET Traffic. Preprint, 1994.
• 14: M. F. Kratz and S. I. Resnick. The QQ-Estimator and Heavy Tails. Preprint, 1995.
• 15: W E Leland , T J Ott, UNIX process behavior and load balancing among loosely-coupled computers, Proc. of the international seminar on Teletraffic analysis and computer performance evaluation, p.191-208, December 1986, Amsterdam, The Netherlands
• 16: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic, Conference proceedings on Communications architectures, protocols and applications, p.183-193, September 13-17, 1993, San Francisco, California, United States
• 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: Hans Eriksson, MBONE: the multicast backbone, Communications of the ACM, v.37 n.8, p.54-60, Aug. 1994 [doi>10.1145/179606.179627]
• 19: B.B. Mandelbrot. Long-run linearity, locally Gaussian processes, H-spectra and infinite variances. Internatzonal Economic Remew, Vol. 10, pp. 82-113, 1969.
• 20: B. B. Mandelbrot. The Fractat Geometry of Nature. Freeman, New York, 1983.
• 21: K. Meier-Hellstern, P. E. Wirth, Y.-L. Yah, and D. A. Hoefiin. Traffic models for ISDN data users: Office Automation application. In A. Jensen and V. B. Iversen, editors, Teletraffic and Datatraj~c m a Pemod of Change, Proc of ITC13, Copenhagen, pp. 167-172, Amsterdam, 1991, Elsevier Science Publishers B. V.
• 22: I. Norros. A storage model with self-similar input. Queueing Systems, Vol. 16, pp. 387-396, 1994.
• 23: V. Paxson. Growth Trends in Wide-Area TCP Connections IEEE Network, Vol. 8, pp. 8-17, 1994.
• 24: Vern Paxson , Sally Floyd, Wide-area traffic: the failure of Poisson modeling, Proceedings of the conference on Communications architectures, protocols and applications, p.257-268, August 31-September 02, 1994, London, United Kingdom
• 25: P. Pruthi and A. Erramilli. Heavy-tailed on/off source behavior and self-similar traffic. Prec. IEEE ICC'95, Seattle, June 1995.
• 26: S. I. Resnick and C. Starcia. Smoothing the Hill Estimator Preprint, 1995.
• 27: G. Samorodnitsky and M. S. Taqqu. Stable Non-Gausszan Processes: Stochasttc Models with Infinite Variance. Chapman and Hall, New York, London, 1994.
• 28: D. F. Swayne, D. Cook, and A. Buja. XGobi: Interactive Dynamic Graphics in the X Window System with a Link to S. 1991 Proceedings of the Section on Stat~sttcal Graphzcs, pp. 1-8, 1991.
• 29: M. S. Taqqu and j. Levy. Using renewal processes to generate long-range depm~dence and high variability. In E. Eberlem ~nd M. S. Taqqu, editors, Dependence in Probab~hty and Stat,stzcs, pp. 73-89, Boston, 1986. Birkhiiuser.
• 30: J W. Tukey and P. A Tukey Strips displaying empirical distributions: I. Textured Dot Strips. Bellcore Technzcal Memorandum, 1990.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: Ethernet

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Design, Measurement, Performance