The influence of dependence on data network models. (English) Zbl 1157.90349

Summary: 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 of the authors [Adv. Appl. Probab. 38, No. 2, 373–404 (2006; Zbl 1103.90029)] 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.


90B15 Stochastic network models in operations research
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
90B22 Queues and service in operations research
90B18 Communication networks in operations research


Zbl 1103.90029
Full Text: DOI


[1] 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.
[2] 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.
[3] Bingham, N. H., Goldie, C. M., and Teugels, J. L. (1987). Regular Variation . Cambridge University Press. · Zbl 0617.26001
[4] Breiman, L. (1965). On some limit theorems similar to the arc-sin law. Theory Prob. Appl. 10, 323–331. · Zbl 0147.37004
[5] Cline, D. B. H. (1983). Estimation and linear prediction for regression, autoregression and ARMA with infinite variance data. Doctoral Thesis, Colorado State University.
[6] 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.
[7] Crovella, M. and Bestavros, A. (1997). Self-similarity in world wide web traffic: evidence and possible causes. IEEE/ACM Trans. Networking 5, 835–846.
[8] D’Auria, B. and Resnick, S. I. (2006). Data network models of burstiness. Adv. Appl. Prob. 38, 373–404. · Zbl 1103.90029 · doi:10.1239/aap/1151337076
[9] 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. · Zbl 0605.62092 · doi:10.1214/aos/1176349937
[10] De Haan, L. (1970). On Regular Variation and Its Application to the Weak Convergence of Sample Extremes. Mathematisch Centrum, Amsterdam. · Zbl 0226.60039
[11] 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 M. E. Tarter and M. D. Lock, Interface, Fairfx Station, VA, pp. 156–165.
[12] 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. · Zbl 0425.60011
[13] Guerin, C. A. et al. (2003). Empirical testing of the infinite source Poisson data traffic model. Stoch. Models , 19, 151–200. · Zbl 1048.62080 · doi:10.1081/STM-120020386
[14] 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. JSTOR: · Zbl 0981.60092 · doi:10.1287/moor.23.1.145
[15] Heffernan, J. E. and Resnick, S. I. (2005). Hidden regular variation and the rank transform. Adv. Appl. Prob. 37, 393–414. · Zbl 1073.60057 · doi:10.1239/aap/1118858631
[16] Hernández-Campos, F. et al. (2005). Extremal dependence: internet traffic applications. Stoch. Models 21, 1–35. · Zbl 1061.62077 · doi:10.1081/STM-200046446
[17] Heyde, C. C. and Yang, Y. (1997). On defining long-range dependence. J. Appl. Prob. 34, 939–944. JSTOR: · Zbl 0912.60050 · doi:10.2307/3215008
[18] 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.
[19] 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 M.E. Vares and V. Sidoravicius. · Zbl 1154.60020 · doi:10.1007/978-3-7643-8786-0_19
[20] Kallenberg, O. (1983). Random Measures , 3rd edn. Akademie-Verlag, Berlin. · Zbl 0544.60053
[21] Konstantopoulos, T. and Lin, S. J. (1998). Macroscopic models for long-range dependent network traffic. Queueing Systems 28, 215–243. · Zbl 0908.90131 · doi:10.1023/A:1019190821105
[22] 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.
[23] 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.
[24] Levy, J. and Taqqu, M. (2000). Renewal reward processes with heavy-tailed interrenewal times and heavy-tailed rewards. Bernoulli 6, 23–44. · Zbl 0954.60071 · doi:10.2307/3318631
[25] Loève, M. (1978). Probability Theory (Graduate Texts Math. 46 ), Vol. II, 4th edn. Springer, New York.
[26] Maulik, K. and Resnick, S. I. (2003). The self-similar and multifractal nature of a network traffic model. Stoch. Models 19, 549–577. · Zbl 1138.60316 · doi:10.1081/STM-120025404
[27] Maulik, K., Resnick, S. I. and Rootzén, H. (2003). Asymptotic independence and a network traffic model. J. Appl. Prob. 39, 671–699. · Zbl 1090.90017 · doi:10.1239/jap/1037816012
[28] 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. · Zbl 1021.60076 · doi:10.1214/aoap/1015961155
[29] 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. · Zbl 0439.60044 · doi:10.1007/BFb0097494
[30] 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.
[31] Park, K. and Willinger, W. (2000). Self-similar network traffic: an overview. In Self-Similar Network Traffic and Performance Evaluation , eds K. Park and W. Willinger, John Wiley, New York, pp. 1–38.
[32] Pratt, J. W. (1960). On interchanging limits and integrals. Ann. Math. Statist. 31, 74–77. · Zbl 0090.26802 · doi:10.1214/aoms/1177705988
[33] Resnick, S. I. (1987). Extreme Values, Regular Variation and Point Processes . Springer, New York. · Zbl 0633.60001
[34] Resnick, S. I. (1992). Adventures in Stochastic Processes . Birkhäuser, Boston, MA. · Zbl 0762.60002
[35] Resnick, S. I. (1999). A Probability Path . Birkhäuser, Boston, MA. · Zbl 0944.60002
[36] Resnick, S. I. (2003). Modeling data networks. In SemStat: Seminaire Europeen de Statistique, Extreme Values in Finance, Telecommunications, and the Environment , eds B. Finkenstadt and H. Rootzén, Chapman & Hall, London, pp. 287–372.
[37] 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 J. Gani and E. Seneta, Applied Probability Trust, Sheffield, pp. 191–212. · Zbl 1049.62056 · doi:10.1239/jap/1082552199
[38] Resnick, S. I. (2004b). The extremal dependence measure and asymptotic independence. Stoch. Models 20, 205–227. · Zbl 1054.62063 · doi:10.1081/STM-120034129
[39] Resnick, S. I. (2007). Heavy Tail Phenomena: Probabilistic and Statistical Modeling . Springer, New York. · Zbl 1152.62029
[40] Resnick, S. I. and Rootzén, H. (2000). Self-similar communication models and very heavy tails. Ann. Appl. Prob. 10, 753–778. · Zbl 1083.60521 · doi:10.1214/aoap/1019487509
[41] 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.
[42] 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.
[43] Samorodnitsky, G. and Taqqu, M. (1994). Stable Non-Gaussian Random Processes. Stochastic Models with Infinite Variance . Chapman & Hall, New York. · Zbl 0925.60027
[44] Sarvotham, S., Riedi, R. and Baraniuk, R. (2005). Network and user driven on-off source model for network traffic. Comput. Networks 48, 335–350
[45] Seneta, E. (1976). Regularly Varying Functions (Lecture Notes Math. 508 ), Springer, New York. · Zbl 0324.26002 · doi:10.1007/BFb0079658
[46] Tanenbaum, A. (1996). Computer Networks , 3rd edn. Prentice Hall PTR, Upper Saddle River, NJ. · Zbl 0825.68147
[47] 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.
[48] 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.
[49] Willinger, W. and Paxson, V. (1998). Where mathematics meets the Internet. Notices Amer. Math. Soc. 45, 961–970. · Zbl 0973.00523
[50] 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 R. J. Adler \et Birkhäuser, Boston, MA, pp. 27–53. · Zbl 0926.90014
[51] 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. · Zbl 1148.90310 · doi:10.1214/ss/1177010131
[52] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.