Can Retransmissions of Superexponential Documents Cause Subexponential Delays?

Consider a generic data unit of random size L that needs to be transmitted over a channel of unit capacity. The channel dynamics is modeled as an on-off process {(Ai, E/j)}iles1 with alternating independent periods when channel is available A_i and unavailable U_i, respectively. During each period of time that the channel becomes available, say A_i, we attempt to transmit the data unit. If L les A_i, the transmission was considered successful; otherwise, we wait for the next period A_i+i when the channel is available and attempt to retransmit the data from the beginning. We study the asymptotic properties of the total transmission time T and number of retransmissions N until the data is successfully transmitted. In recent studies it was proved that the waiting time T follows a power law when the distributions of L and A₁ are of an exponential type, e.g., Gamma distribution. In this paper, we show that the distributions of N and T follow power laws with exponent alpha as long as logP[L > x] apalphalogP[A₁ > x] for large x. Hence, it may appear surprising that we obtain power law distributions irrespective of how heavy or light the distributions of L and A₁ may be. In particular, both L and A₁ can decay faster than any exponential, which we term superexponential. For example, if L and A₁ are Gaussian with variances sigma² _L and sigma² _A, respectively, then N and T have power law distributions with exponent alpha = sigma² _A/sigma² _L; note that, if sigma² _A<sigma² _L, the transmission time has an infinite mean and, thus, the system is unstable. The preceding model, as recognized in (Fiorini et al., 2005), describes a variety of situations where failures require jobs to restart from the beginning. Here, we identify that this model also provides a new mechanism for explaining the frequently observed power law phenomenon in data networks. Specifically, we argue that it may imply the power laws on both the application as well as the data link layer, where variable-sized documents and (IP) packets are transmitted, respectively. We discuss the engineering ramifications of our observations, especially in the context of wireless ad hoc and sensor networks where channel failures are frequent. Furthermore, our results provide an easily computable benchmark for measuring the matching between the data and channel characteristics that permits/prevents satisfactory transmission.