Transition from Heavy to Light Tails in Retransmission Durations
Authors:
- 1 March 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-9
Abstract
Retransmissions serve as the basic building block that communication protocols use to achieve reliable data transfer. Until recently, the number of retransmissions were thought to follow a light tailed (in particular, a geometric) distribution. However, recent work seems to suggest that when the distribution of the packets have infinite support, retransmission-based protocols may result in heavy tailed delays and even possibly zero throughput. While this result is true even when the distribution of packet sizes are light-tailed, it requires the assumption that the packet sizes have infinite support. However, in reality, packet sizes are often bounded by the Maximum Transmission Unit (MTU), and thus the aforementioned result merits a deeper investigation. To that end, in this paper, we allow the distribution of the packet size L to have finite support. This packet is sent over an on-off channel {(Ai,Ui)} with alternating available Ai and unavailable Ui periods. If L ? Ai, the transmission fails and we wait for the next period Ai + 1 to retransmit the packet. The transmission duration is thus measured from the first attempt to a point when a channel available period larger than L. Under mild conditions, we show that the transmission duration distribution exhibits a transition from a power law main body to an exponential tail with Weibull type distributions between the two. The time scale to observe the power law main body is roughly equal to the average transmission duration of the longest packet. Both the power law main body and the exponential tail could dominate the overall performance. For example, the power law main body, if significant, may cause the channel throughput to be very close to zero. On the other hand, the exponential tail, if more evident, may imply that the system operates in a benign environment. These theoretical findings provide an understanding on why some empirical measurements suggest heavy tails and light tails for others (e.g., wireless networks). We use these results to further highlight the engineering implications from distributions with power law main bodies and light tails by analyzing two cases: (1) The throughput of on-off channels with retransmissions, where we show that even when packet sizes have small means and bounded support the variability in their sizes can greatly impact system performance. (2) The distribution of the number of jobs in an M/M/? queue with server failures. Here we show that retransmissions can cause long-range dependence and quantify the impact of the maximum job sizes on the long-range dependence.Keywords
This publication has 10 references indexed in Scilit:
- Asymptotic Behavior of Total Times for Jobs That Must Start Over if a Failure OccursMathematics of Operations Research, 2008
- Power law and exponential decay of inter contact times between mobile devices2007
- Is ALOHA Causing Power Law Delays?2007
- Asymptotic Delay Analysis for Cross-Layer Delay-Based Routing in Ad Hoc NetworksAdvances in Multimedia, 2007
- Can Retransmissions of Superexponential Documents Cause Subexponential Delays?2007
- Self-similarity and long range dependence on the internet: a second look at the evidence, origins and implicationsComputer Networks, 2005
- Measurement-based characterization of 802.11 in a hotspot setting2005
- M|G|∞ input processes: a versatile class of models for network traffic2002
- On the self-similar nature of Ethernet trafficACM SIGCOMM Computer Communication Review, 1995
- Regular Variation1987