Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-27T19:21:30.309Z Has data issue: false hasContentIssue false
  • English
  • Français

The influence of dependence on data network models

Part of: Special processes Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Bernardo D'Auria  and
Sidney I. Resnick
Bernardo D'Auria*
Affiliation:
EURANDOM
Sidney I. Resnick*
Affiliation:
Cornell University
*
∗ Current address: Departamento Estadística, Universidad Carlos III de Madrid, Avda. de la Universidad, 30, 28911 Leganés, Madrid, Spain.
∗∗ Postal address: School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Consider an infinite-source marked Poisson process to model end user inputs to a data network. At Poisson times, connections are initated. The connection is characterized by a triple (F, L, R) denoting the total quantity of transmitted data in a connection, the length or duration of the connection, and the transmission rate; the three quantities are related by F = LR. How critical is the dependence structure of the mark for network characteristics such as burstiness, distribution tails of cumulative input, and long-range dependence properties of traffic measured in consecutive time slots? In a previous publication (D'Auria and Resnick (2006)) we assumed that F and R were independent. Here we assume that L and R are independent. The change in dependence assumptions means that the model properties change dramatically: tails of cumulative input per time slot are dramatically heavier, traffic cannot be approximated by a Gaussian distribution, and the decay of dependence cannot be measured in the traditional way using correlation functions. Different network applications are likely to have different mark dependence structure. We argue that the present independence assumption on L and R is likely to be appropriate for network applications such as streaming media or peer-to-peer networks. Our conclusion is that it is desirable to separate network traffic by application and to model each application with its own appropriate dependence structure.

Keywords

Bursty trafficM/G/∞ input modelinfinite-source Poisson modelnetwork modelinglimit distributionLévy processGaussian limit

MSC classification

Primary: 90B15: Network models, stochastic 60K30: Applications (congestion, allocation, storage, traffic, etc.)
Secondary: 90B22: Queues and service 90B18: Communication networks
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 40 , Issue 1 , March 2008 , pp. 60 - 94
Copyright
Copyright © Applied Probability Trust 2008 

References

Arlitt, M. and Williamson, C. L. (1996). Web server workload characterization: the search for invariants (extended version). In Proc. ACM SIGMETRICS Conf. (Philadelphia, PA), ACM, New York, pp. 126–137.Google Scholar
Ben Azzouna, N., Clérot, F., Fricker, C. and Guillemin, F. (2004). A flow-based approach to modeling ADSL traffic on an IP backbone link. Ann. Telecommun., 59, 1260–1299.Google Scholar
Bingham, N. H., Goldie, C. M., and Teugels, J. L. (1987). Regular Variation. Cambridge University Press.Google Scholar
Breiman, L. (1965). On some limit theorems similar to the arc-sin law. Theory Prob. Appl. 10, 323–331.Google Scholar
Cline, D. B. H. (1983). Estimation and linear prediction for regression, autoregression and ARMA with infinite variance data. , Colorado State University.Google Scholar
Crovella, M. and Bestavros, A. (1996). Self-similarity in world wide web traffic: evidence and possible causes. In Proc. ACM SIGMETRICS Conf. (Philadelphia, PA), ACM, New York, pp. 160–169.Google Scholar
Crovella, M. and Bestavros, A. (1997). Self-similarity in world wide web traffic: evidence and possible causes. IEEE/ACM Trans. Networking 5, 835–846.Google Scholar
D'Auria, B. and Resnick, S. I. (2006). Data network models of burstiness. Adv. Appl. Prob. 38, 373–404.Google Scholar
Davis, R. A., and Resnick, S. I. (1986). Limit theory for the sample covariance and correlation functions of moving averages. Ann. Statist. 14, 533–558.Google Scholar
De Haan, L. (1970). On Regular Variation and Its Application to the Weak Convergence of Sample Extremes. Mathematisch Centrum, Amsterdam.Google Scholar
Duffy, D. E., McIntosh, A. A., Rosenstein, M. and Willinger, W. (1993). Analyzing telecommunications traffic data from working common channel signaling subnetworks. In Computing Science and Statistics Interface (Proc. 25th Symp. Interface; San Diego, CA), eds Tarter, M. E. and Lock, M. D., Interface, Fairfx Station, VA, pp. 156–165.Google Scholar
Embrechts, P. and Goldie, C. M. (1980). On closure and factorization properties of subexponential and related distributions. J. Austral. Math. Soc. Ser. A 29, 243–256.CrossRefGoogle Scholar
Guerin, C. A. et al. (2003). Empirical testing of the infinite source Poisson data traffic model. Stoch. Models, 19, 151–200.Google Scholar
Heath, D., Resnick, S. I. and Samorodnitsky, G. (1998). Heavy tails and long range dependence in on/off processes and associated fluid models. Math. Operat. Res. 23, 145–165.Google Scholar
Heffernan, J. E. and Resnick, S. I. (2005). Hidden regular variation and the rank transform. Adv. Appl. Prob. 37, 393–414.Google Scholar
Hernández-Campos, F. et al. (2005). Extremal dependence: internet traffic applications. Stoch. Models 21, 1–35.CrossRefGoogle Scholar
Heyde, C. C. and Yang, Y. (1997). On defining long-range dependence. J. Appl. Prob. 34, 939–944.Google Scholar
Heyman, D. and Lakshman, T. V. (1996). What are the implications of long-range dependence for VBR-video traffic engineering? IEEE/ACM Trans. Networking 4, 301–317.Google Scholar
Kaj, I. and Taqqu, M. S. (2008). Convergence to fractional Brownian motion and to the Telecom process: the integral representation approach. To appear in Brazilian Prob. School, 10th Anniversary Volume, eds Vares, M.E. and Sidoravicius, V. Google Scholar
Kallenberg, O. (1983). Random Measures, 3rd edn. Akademie-Verlag, Berlin.Google Scholar
Konstantopoulos, T. and Lin, S. J. (1998). Macroscopic models for long-range dependent network traffic. Queueing Systems 28, 215–243.Google Scholar
Leland, W. E., Taqqu, M. S., Willinger, W. and Wilson, D.V. (1993). Statistical analysis of high time-resolution ethernet LAN traffic measurements. In Proc. 25th Symp. Interface Statist. Comput. Sci., Interface Foundation of North America, Virginia, pp. 146–155.Google Scholar
Leland, W. E., Taqqu, M. S., Willinger, W. and Wilson, D.V. (1994). On the self-similar nature of ethernet traffic (extended version). IEEE/ACM Trans. Networking 2, 1–15.Google Scholar
Levy, J. and Taqqu, M. (2000). Renewal reward processes with heavy-tailed interrenewal times and heavy-tailed rewards. Bernoulli 6, 23–44.Google Scholar
Loève, M. (1978). Probability Theory (Graduate Texts Math. 46), Vol. II, 4th edn. Springer, New York.Google Scholar
Maulik, K. and Resnick, S. I. (2003). The self-similar and multifractal nature of a network traffic model. Stoch. Models 19, 549–577.Google Scholar
Maulik, K., Resnick, S. I. and Rootzén, H. (2003). Asymptotic independence and a network traffic model. J. Appl. Prob. 39, 671–699.Google Scholar
Mikosch, T., Resnick, S. I., Rootzén, H. and Stegeman, A. W. (2002). Is network traffic approximated by stable Lévy motion or fractional Brownian motion? Ann. Appl. Prob. 12, 23–68.Google Scholar
Neveu, J. (1977). Processus ponctuels. In École d'Été de Probabilités de Saint-Flour, VI—1976 (Lecture Notes Math. 598), Springer, Berlin, pp. 249–445.Google Scholar
Pandurangan, G., Raghavan, P. and Upfal, E. (2001). Building low-diameter P2P networks. In Proc. 42nd IEEE Symp. Foundations Comput. Sci. (Las Vegas, NV), IEEE, Los Alamitos, CA, pp. 492–499.Google Scholar
Park, K. and Willinger, W. (2000). Self-similar network traffic: an overview. In Self-Similar Network Traffic and Performance Evaluation, eds Park, K. and Willinger, W., John Wiley, New York, pp. 1–38.Google Scholar
Pratt, J. W. (1960). On interchanging limits and integrals. Ann. Math. Statist. 31, 74–77.Google Scholar
Resnick, S. I. (1987). Extreme Values, Regular Variation and Point Processes. Springer, New York.Google Scholar
Resnick, S. I. (1992). Adventures in Stochastic Processes. Birkhäuser, Boston, MA.Google Scholar
Resnick, S. I. (1999). A Probability Path. Birkhäuser, Boston, MA.Google Scholar
Resnick, S. I. (2003). Modeling data networks. In SemStat: Seminaire Europeen de Statistique, Extreme Values in Finance, Telecommunications, and the Environment, eds Finkenstadt, B. and Rootzén, H., Chapman & Hall, London, pp. 287–372.Google Scholar
Resnick, S. I. (2004a). On the foundations of multivariate heavy tail analysis. In Stochastic Methods and Their Applications (J. Appl. Prob. Spec. Vol. 41A), eds Gani, J. and Seneta, E., Applied Probability Trust, Sheffield, pp. 191–212.Google Scholar
Resnick, S. I. (2004b). The extremal dependence measure and asymptotic independence. Stoch. Models 20, 205–227.Google Scholar
Resnick, S. I. (2007). Heavy Tail Phenomena: Probabilistic and Statistical Modeling. Springer, New York.Google Scholar
Resnick, S. I. and Rootzén, H. (2000). Self-similar communication models and very heavy tails. Ann. Appl. Prob. 10, 753–778.Google Scholar
Riedi, R. H. and Willinger, W. (2000). Toward an improved understanding of network traffic dynamics. In Self-Similar Network Traffic and Performance Evaluation, John Wiley, New York, pp. 507–530.Google Scholar
Samorodnitsky, G. (2002). Long range dependence, heavy tails and rare events. Lecture Note MPS-LN 2002-12, Centre for Mathematical Physics and Stochastics, Department of Mathematical Sciences, University of Aarhus. Available at http://www.maphysto.dk/cgi-bin/gp.cgi?publ=412.Google Scholar
Samorodnitsky, G. and Taqqu, M. (1994). Stable Non-Gaussian Random Processes. Stochastic Models with Infinite Variance. Chapman & Hall, New York.Google Scholar
Sarvotham, S., Riedi, R. and Baraniuk, R. (2005). Network and user driven on-off source model for network traffic. Comput. Networks 48, 335–350 Google Scholar
Seneta, E. (1976). Regularly Varying Functions (Lecture Notes Math. 508), Springer, New York.Google Scholar
Tanenbaum, A. (1996). Computer Networks, 3rd edn. Prentice Hall PTR, Upper Saddle River, NJ.Google Scholar
Taqqu, M. S., Willinger, W. and Sherman, R. (1997). Proof of a fundamental result in self-similar traffic modeling. Comput. Commun. Rev. 27, 5–23.Google Scholar
Willinger, W. (1998). Data network traffic: heavy tails are here to stay. Presentation at Extremes – Risk and Safety, Nordic School of Public Health, Gothenberg, Sweden, August 1998.Google Scholar
Willinger, W. and Paxson, V. (1998). Where mathematics meets the Internet. Notices Amer. Math. Soc. 45, 961–970.Google Scholar
Willinger, W., Paxson, V. and Taqqu, M. S. (1998). Self-similarity and heavy tails: structural modeling of network traffic. In A Practical Guide to Heavy Tails. Statistical Techniques and Applications, eds Adler, R. J. et al. Birkhäuser, Boston, MA, pp. 27–53.Google Scholar
Willinger, W., Taqqu, M. S., Leland, M. and Wilson, D. (1995). Self-similarity in high-speed packet traffic: analysis and modelling of ethernet traffic measurements. Statist. Sci. 10, 67–85.Google Scholar
Willinger, W., Taqqu, M. S., Leland, M. and Wilson, D. (1997). Self-similarity through high variability: statistical analysis of ethernet LAN traffic at the source level (extended version). IEEE/ACM Trans. Networking 5, 71–96.Google Scholar