Characterizing Heavy-Tailed Distributions Induced by Retransmissions

Abstract

Consider a generic data unit of random sizeLthat needs to be transmitted over a channel of unit capacity. The channel availability dynamic is modeled as an independent and identically distributed sequence {A,Ai}i≥1that is independent ofL. During each period of time that the channel becomes available, sayAi, we attempt to transmit the data unit. IfL<Ai, the transmission is considered successful; otherwise, we wait for the next available periodAi+1and attempt to retransmit the data from the beginning. We investigate the asymptotic properties of the number of retransmissionsNand the total transmission timeTuntil the data is successfully transmitted. In the context of studying the completion times in systems with failures where jobs restart from the beginning, it was first recognized by Fiorini, Sheahan and Lipsky (2005) and Sheahan, Lipsky, Fiorini and Asmussen (2006) that this model results in power-law and, in general, heavy-tailed delays. The main objective of this paper is to uncover the detailed structure of this class of heavy-tailed distributions induced by retransmissions. More precisely, we study how the functional relationship ℙ[L>x]-1≈ Φ (ℙ[A>x]-1) impacts the distributions ofNandT; the approximation ‘≈’ will be appropriately defined in the paper based on the context. Depending on the growth rate of Φ(·), we discover several criticality points that separate classes of different functional behaviors of the distribution ofN. For example, we show that if log(Φ(n)) is slowly varying then log(1/ℙ[N>n]) is essentially slowly varying as well. Interestingly, if log(Φ(n)) grows slower than e√(logn)then we have the asymptotic equivalence log(ℙ[N>n]) ≈ - log(Φ(n)). However, if log(Φ(n)) grows faster than e√(logn), this asymptotic equivalence does not hold and admits a different functional form. Similarly, different types of distributional behavior are shown for moderately heavy tails (Weibull distributions) where log(ℙ[N>n]) ≈ -(log Φ(n))1/(β+1), assuming that log Φ(n) ≈ nβ, as well as the nearly exponential ones of the form log(ℙ[N>n]) ≈ -n/(logn)1/γ, γ>0, when Φ(·) grows faster than two exponential scales log log (Φ(n)) ≈nγ.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 34 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.