IP packet generation: statistical models for TCP start times based on connection-rate superposition

ABSTRACT

TCP start times for HTTP are nonstationary. The nonstationarity occurs because the start times on a link, a point process, are a superposition of source traffic point processes, and the statistics of superposition changes as the number of superposed processes changes. The start time rate is a measure of the number of traffic sources. The univariate distribution of the inter-arrival times is approximately Weibull, and as the rate increases, the Weibull shape parameter goes to 1, an exponential distribution. The autocorrelation of the log inter-arrival times is described by a simple, two-parameter process: white noise plus a long-range persistent time series. As the rate increases, the variance of the persistent series tends to zero, so the log times tend to white noise. A parsimonious statistical model for log inter-arrivals accounts for the autocorrelation, the Weibull distribution, and the nonstationarity in the two with the rate. The model, whose purpose is to provide stochastic input to a network simulator, has the desirable property that the superposition point process is generated as a single stream. The parameters of the model are functions of the rate, so to generate start times, only the rate is specified. As the rate increases, the model tends to a Poisson process. These results arise from theoretical and empirical study based on the concept of connection-rate superposition. The theory is the mathematics of superposed point processes, and the empiricism is an analysis of 23 million TCP connections organized into 10704 blocks of approximately 15 minutes each.

REFERENCES

• 1: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 2: R. A. Becker, W. S. CleveIand, and M. J. Shyu. The Design and Control of Trellis Display. Journal o.f Computational and Statistical Graphics, 5:123-155, 1996.
• 3: John M. Chambers , J. M. Chambers, Programming with Data: A Guide to the S Language, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 4: William S. Cleveland, Visualizing Data, Hobart Press, 1993
• 5: W. S. Cleveland and S. J. Devlin. Locally-Weighted Regression: An Approach to Regression Analysis by Local Fitting. Journal of the American Statistical Association, 83: 596-610, 1988.
• 6: W. S. Cleveland, C. L. Mallows, and J. E. McRae. ATS Methods: Nonparametric Regression for Nongaussian Data. Journal of the American Statistical Association, 88:821-835, 1993.
• 7: D. R. Cox. Renewal Theory. Chapman and Hall, 1962.
• 8: S. Deng. Empirical model of www document axrivals at access link. In Proceedings of ICC/SUPERCOMM, 1996.
• 9: 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]
• 10: A. Feldmann , A. C. Gilbert , W. Willinger , T. G. Kurtz, The changing nature of network traffic: scaling phenomena, ACM SIGCOMM Computer Communication Review, v.28 n.2, p.5-29, Apr. 1998 [doi>10.1145/279345.279346]
• 11: A. Feldmann. Characteristics of TCP Connection Arrivals. Technical report, AT&T Labs Research, 1998.
• 12: H. Fowler and W. Leland. Local Area Network traffic Characteristics, with Implications for Broadband Network Congestion Maaaagement. IEEE Journal on Selected Areas in Communications, 9:1139-1145~ 1991.
• 13: J. Geweke and S. Porter-Hudak. The Estimation and Application of Long Memory Time Series Models. Journal of Time Series Analysis, 4:221-238, 1983.
• 14: J, R. M. Hosking. Fractional Differencing. Biometrika, 68:165-176, 1981.
• 15: N. L. Johnson and S. Kotz. Distributions in Statistics: Continuous Univariate Distributions. Houghton Mifflin Company, Boston, 1971}.
• 16: 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]
• 17: W. Leland and D. Wilson. High Time-Resolution Measurement and Analysis of LAN Traffic: Implications for LAN Interconnection. In Proceedings of IEEE Infocom, 1991.
• 18: Bruce A. Mah, An Empirical Model of HTTP Network Traffic, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.592, April 09-11, 1997
• 19: S. McCanne and S. Floyd. NS (Network Simulator). http: //www-nrg.ee.lbl.gov/ns/, 1998.
• 20: S. McCanne and S. Floyd. UCB/LBNL Network Simulator - ns (version 2). http://wwwmash.cs.berkeley.edu/ns/, 1998.
• 21: J. Mogul. Network Behavior of a Busy Web Server. Technical Report 95/5, DEC Western Research Lab, 1995.
• 22: Kihong Park , Gitae Kim , Mark Crovella, On the relationship between file sizes, transport protocols, and self-similar network traffic, Proceedings of the 1996 International Conference on Network Protocols (ICNP '96), p.171, October 29-November 01, 1996
• 23: K. Park, G. Kirn, and M. Crovella. On the effect of traffic self-similarity on network performance. In Proc. SPIE Intl. Conf. Perf. and Control of Network Systems, 1997.
• 24: 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]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks
      C.2.2 Network Protocols

          Nouns: TCP/IP

  G. Mathematics of Computing

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Experimentation, Measurement, Performance, Standardization, Theory