Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T22:15:31.497Z Has data issue: false hasContentIssue false
  • English
  • Français

Distribution of the Number of Retransmissions of Bounded Documents

Part of: Stochastic processes Limit theorems

Published online by Cambridge University Press:  22 February 2016

Predrag R. Jelenković  and
Evangelia D. Skiani
Predrag R. Jelenković*
Affiliation:
Columbia University
Evangelia D. Skiani*
Affiliation:
Columbia University
*
∗ Postal address: Department of Electrical Engineering, Columbia University, New York, NY 10027, USA.
∗ Postal address: Department of Electrical Engineering, Columbia University, New York, NY 10027, USA.
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.

Retransmission-based failure recovery represents a primary approach in existing communication networks that guarantees data delivery in the presence of channel failures. Recent work has shown that, when data sizes have infinite support, retransmissions can cause long (-tailed) delays even if all traffic and network characteristics are light-tailed. In this paper we investigate the practically important case of bounded data units 0 ≤ Lb ≤ b under the condition that the hazard functions of the distributions of data sizes and channel statistics are proportional. To this end, we provide an explicit and uniform characterization of the entire body of the retransmission distribution ℙ[Nb > n] in both n and b. Our main discovery is that this distribution can be represented as the product of a power law and gamma distribution. This rigorous approximation clearly demonstrates the coupling of a power law distribution, dominating the main body, and the gamma distribution, determining the exponential tail. Our results are validated via simulation experiments and can be useful for designing retransmission-based systems with the required performance characteristics. From a broader perspective, this study applies to any other system, e.g. computing, where restart mechanisms are employed after a job processing failure.

Keywords

Retransmissionrestartchannel with failuretruncated distributionpower lawgamma distributionheavy-tailed distributionlight-tailed distribution

MSC classification

Primary: 60F99: None of the above, but in this section
Secondary: 60F10: Large deviations 60G99: None of the above, but in this section
Type
Research Article
Information
Advances in Applied Probability , Volume 47 , Issue 2 , June 2015 , pp. 425 - 449
Copyright
© Applied Probability Trust 

References

Abramowitz, M. and Stegun, I. A. (1964). “Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. “U.S. Government Printing Office, Washington, D.C.Google Scholar
Asmussen, S., Lipsky, L. and Thompson, S. (2014). Failure Recovery in Computing and Data Transmission. In Analytic and Stochastic Modelling Techniques and Applications. (Lecture Notes Comput. Sci. 8499). Springer, Berlin, pp. 253–272.Google Scholar
Asmussen, S. et al. (2008). “Asymptotic behavior of total times for Jobs that must start over if a failure occurs.” Math. Operat. Res. 33, 932–944.Google Scholar
Bertsekas, D. P. and Gallager, R. (1992). “Data Networks, 2nd edn. “Prentice Hall, London.Google Scholar
Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). “Regular Variation.” Cambridge University Press.Google Scholar
Fiorini, P. M., Sheahan, R. and Lipsky, L. (2005). “On unreliable computing systems when heavy-tails appear as a result of the recovery procedure.” ACM SIGMETRICS Performance Evaluation Rev. 33, 15–17.Google Scholar
Jelenković, P. R. and Olvera-Cravioto, M. (2012). “Implicit renewal theorem for trees with general weights.” Stoch. Process. Appl. 122, 3209–3238.CrossRefGoogle Scholar
Jelenković, P. R. and Skiani, E. D. (2012). “Uniform approximation of the distribution for the number of retransmissions of bounded documents.“In Proc. 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, ACM, New York, pp. 101–112. June 2012.Google Scholar
Jelenković, P. R. and Skiani, E. D. (2012). “Distribution of the number of retransmissions of bounded documents.” Extended version. Available at http://arxiv.org/abs/1210.8421v1.Google Scholar
Jelenković, P. R. and Tan, J. (2007). “Are end-to-end acknowlegements causing power law delays in large multi-hop networks? In 14th Informs Applied Probability Conference, APS, pp. 9–11.Google Scholar
Jelenković, P. R. and Tan, J. (2007). “Can retransmissions of superexponential documents cause subexponential delays? In Proc. 26th IEEE INFOCOM'07, IEEE, pp. 892–900.Google Scholar
Jelenković, P. R. and Tan, J. (2007). “Is ALOHA causing power law delays? In Managing Traffic Performance in Converged Networks (Lecture Notes Comput. Sci. 4516). Springer, Berlin, pp. 1149–1160.Google Scholar
Jelenković, P. R. and Tan, J. (2008). “Dynamic packet fragmentation for wireless channels with failures.“In Proc. 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, ACM, New York, pp. 73–82.Google Scholar
Jelenković, P. R. and Tan, J. (2009). “Stability of finite population ALOHA with variable packets.” Preprint. Available at http://arxiv.org/abs/0902.4481v2.Google Scholar
Jelenković, P. R. and Tan, J. (2010). “Modulated branching processes, origins of power laws, and queueing duality.” Math. Operat. Res. 35, 807–829.CrossRefGoogle Scholar
Jelenković, P. R. and Tan, J. (2013). “Characterizing heavy-tailed distributions induced by retransmissions.” Adv. Appl. Prob. 45, 106–138. Extended version available at http://arxiv.org/pdf/0709.1138.pdf Google Scholar
Nair, J. et al. (2010). “File fragmentation over an unreliable channel.” In Proc. IEEE INFOCOM'10, IEEE, pp. 965–973.Google Scholar
Ross, S. M. (2002). “A First Course in Probability, 6th edn. “Prentice Hall, Upper Saddle River, NJ.Google Scholar
Sheahan, R., Lipsky, L., Fiorini, P. M. and Asmussen, S. (2006). “On the completion time distribution for tasks that must restart from the beginning if a failure occurs.” ACM SIGMETRICS Performance Evaluation Rev. 34, 24–26.Google Scholar
Tan, J. and Shroff, N. B. (2010). “Transition from heavy to light tails in retransmission durations.“In Proc. IEEE INFOCOM'10, IEEE, pp. 1334–1342.Google Scholar