Retransmissions represent a primary failure recovery mech- anism on all layers of communication network architecture. Similarly, fair sharing, e.g. processor sharing (PS), is a widely accepted approach to resource allocation among mul- tiple users. Recent work has shown that retransmissions in failure-prone, e.g. wireless ad hoc, networks can cause heavy tails and long delays. In this paper, we discover a new phe- nomenon showing that PS-based scheduling induces com- plete instability in the presence of retransmissions, regard- less of how low the traffic load may be. This phenomenon occurs even when the job sizes are bounded/fragmented, e.g. deterministic. Our analytical results are further validated via simulation experiments. Moreover, our work demon- strates that scheduling one job at a time, such as first-come- first-serve, achieves stability and should be preferred in these systems.

Retransmission-based failure recovery represents a primary approach in existing communication networks, on all protocol layers, that guarantees data delivery in the presence of channel failures. Contrary to the traditional belief that the number of retransmissions is geometrically distributed, a new phenomenon was discovered recently, which shows that retransmissions can cause long (-tailed) delays and instabilities even if all traffic and network characteristics are light-tailed, e.g., exponential or Gaussian. Since the preceding finding holds under the assumption that data sizes have infinite support, in this paper we investigate the practically important case of bounded data units 0≤ Lb≤ b. To this end, we provide an explicit and uniform characterization of the entire body of the retransmission distribution Pr[Nb > n] in both n and b. This rigorous approximation clearly demonstrates the previously observed transition from power law distributions in the main body to exponential tails. The accuracy of our approximation is validated with a number of simulation experiments. Furthermore, the results highlight the importance of wisely determining the size of data units in order to accommodate the performance needs in retransmission-based systems. From a broader perspective, this study applies to any other system, e.g., computing, where restart mechanisms are employed after a job processing failure.

It was shown recently [7-9], under quite general conditions, that retransmission-based protocols may result in power-law delays and possibly zero throughput even if the distribution of packets (data units) is very concentrated, e.g., exponential or Gaussian. This phenomenon occurs irrespective of whether the cause of retransmissions is due to channel failures in the data link layer [7] or collisions in ALOHA-type protocols in the MAC layer [9]. These theoretical findings are in agreement with empirical measurements in [18], showing that the utilization of the 802.11 protocol is only 40%, basically due to retransmissions.

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 Aiand unavailable Ui, respectively. During each period of time that the channel becomes available, say Ai, we attempt to transmit the data unit. If L les Ai, the transmission was considered successful; otherwise, we wait for the next period Ai+iwhen 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 A1are 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[A1> 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 A1may be. In particular, both L and A1can decay faster than any exponential, which we term superexponential. For example, if L and A1are Gaussian with variances sigma2Land sigma2A, respectively, then N and T have power law distributions with exponent alpha = sigma2A/sigma2L; note that, if sigma2A2L, 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.

The Shortest Remaining Processing Time (SRPT) scheduling disciplineis optimal and its superior performance, compared with the policies that do not use the knowledge of job sizes, can be quantified using mean-value analysis as well as our new a symptotic distribution allimits for the relatively smaller heavy-tailed jobs. However, the main difficulty in implementing SRPT in large practical systems, e.g., Web servers, is that its complexity grows with the number of jobs in the queue. Hence, in order to lower the complexity, it is natural to approximate SRPT by grouping the arrivals into a fixed (small) number of classes containing jobs of approximately equal size and then serve the classes of smaller jobs with higher priorities. In this paper, we design a novel adaptive grouping mechanism based on relative size comparison of a newly arriving job to the preceding m arrivals. Specifically, if the newly arriving job is smallerthan k and larger than m-k of the previous m jobs, it isrouted into class k. The excellent performance of this mechanism,even for a small number of classes m+1, is demonstrated using both the asymptotic queueing analysis under heavy tails and extensive simulations. We also discuss refinements of the comparison grouping mechanism that improve the accuracy of job classification at the expense of a small additional complexity.

Abstract—This paper investigates the existence of scalable protocols that can achieve the capacity limit of per source-destination pair in a large wireless network of nodes when the buffer space of each node does not grow with the size of the network. It is shown that there is no end-to-end protocol capable of carrying out the limiting throughput of with nodes that have constant buffer space. In other words, this limit is achievable only with devices whose buffers grow with the size of the network. On the other hand, the paper establishes that there exists a protocol which realizes a slightly smaller throughput of log when devices have constant buffer space. Furthermore, it is shown that the required buffer space can be very small, capable of storing just a few packets. This is particularly important for wireless sensor networks where devices have limited resources. Finally, from a mathematical perspective, the paper furthers our understanding of the difficult problem of analyzing large queueing networks with finite buffers for which, in general, no explicit solutions are available. Index Terms—Ad hoc wireless networks, finite-buffer queueing networks, large-scale networks, local cooperation, scaling laws, wireless sensor networks. I.

We investigate a widely popular least-recently-used (LRU) cache replacement algorithm with semiMarkov modulated requests. SemiMarkov processes provide the flexibility for modeling strong statistical correlation, including the broadly reported long-range dependence in the World Wide Web page request patterns. When the frequency of requesting a page n is equal to the generalized Zipf's law c/n/sup /spl alpha//, /spl alpha/ > 1, our main result shows that the cache fault probability is asymptotically, for large cache sizes, the same as in the corresponding LRU system with i.i.d. requests. This appears to be the first explicit average case analysis of LRU caching with statistically dependent request sequences. The surprising insensitivity of LRU caching performance demonstrates its robustness to changes in document popularity. Furthermore, we show that the derived asymptotic result and simulation experiments are in excellent agreement, even for relatively small cache sizes. The potential of using our results in predicting the behavior of Web caches is tested using actual, strongly correlated, proxy server access traces.

We investigate the distribution of the waiting time V in an M/G/1 processor sharing queue with traffic intensity /spl rho/x] = P[B > (1 - /spl rho/)x](1 + o(1)) Furthermore, we demonstrate that the preceding relationship does not hold if the job distribution has a lighter tail than e/sup -/spl radic/x/. This result provides a new tool for analyzing network congestion points with moderately heavy-tailed characteristics, e.g. log normal distributions, that have been recently empirically discovered in Web traffic. The accuracy of our approximation is confirmed with simulation experiments.

Consider a network multiplexer with a finite buffer fed by a superposition of independent heterogeneous on-off sources. An on-off source consists of a sequence of alternating independent activity and silence periods. During its activity period a source produces fluid with constant rate. For this system, under the assumption that the residual activity periods are intermediately regularly varying, we derive explicit and asymptotically exact formulas for approximating the stationary overflow probability and loss rate. The derived asymptotic formulas, in addition to their analytical tractability, exhibit excellent quantitative accuracy, which is illustrated by a number of simulation experiments. We demonstrate through examples how these results can be used for efficient computation of capacity regions for network switching elements. Furthermore, the results provide important insight into qualitative tradeoffs between the overflow probability, offered traffic load, available capacity, and buffer space. Overall, they provide a new set of tools for designing and provisioning of networks with heavy-tailed traffic streams.

Consider two M/G/1 queues that are coupled in the following way. Whenever both queues are non-empty, each server serves its own queue at unit speed. However, if server 2 has no work in its own queue, then it assists server 1, resulting in an increased service speed r/sub 1//sup *//spl ges/1 in the first queue. This kind of coupling is related to generalized processor sharing. We assume that the service request distributions at both queues are regularly varying at infinity of index -v/sub 1/ and -v/sub 2/, namely, they are heavy-tailed. Under this assumption, we present a detailed analysis of the tail behaviour of the workload distribution at each queue. If the guaranteed unit speed of server 1 is already sufficient to handle its offered traffic, then the workload distribution at the first queue is shown to be regularly varying at infinity of index 1-v/sub 1/. But if it is not sufficient, then the workload distribution at the first queue is shown to be regularly varying at infinity of index 1-min(v/sub 1/,v/sub 2/). In particular, traffic at server 1 is then no longer protected from worse-behaved (heavier-tailed) traffic at server 2.

We analyze the asymptotic behavior of long-tailed traffic sources under the generalized processor sharing (GPS) discipline. GPS-based scheduling algorithms, such as weighted fair queueing, have emerged as an important mechanism for achieving differentiated quality-of-service in integrated-services networks. Under certain conditions, we prove that in an asymptotic sense an individual source with long-tailed traffic characteristics is effectively served at a constant rate, which may be interpreted as the maximum feasible average rate for that source to be stable. Thus, asymptotically, the source is only affected by the traffic characteristics of the other sources through their average rate. In particular, the source is essentially immune from excessive activity of sources with 'heavier'-tailed traffic characteristics. This suggests that GPS-based scheduling algorithms provide an effective mechanism for extracting high multiplexing gains, while protecting individual connections.

This paper investigates the asymptotic behavior of a single server queue with truncated heavy-tailed arrival sequences. We have discovered and explicitly asymptotically characterized a unique asymptotic behavior of the queue length distribution. Informally, this distribution on the log scale resembles a stair-wave function that has steep drops at specific buffer sizes. This has important design implications suggesting that negligible increases of the buffer size in certain buffer regions can decrease the overflow probabilities by order of magnitudes. A problem of this type arises quite frequently in practice when the arrival process distribution has a bounded support and inside that support it is nicely matched with a heavy-tailed distribution (e.g. Pareto). However, the primary interest in this scenario is in its possible application to controlling heavy-tailed traffic flows. More precisely, one can imagine a network control procedure in which short network flows are separated from long ones. If the distribution of flows is heavy-tailed this procedure will yield a truncated heavy-tailed distribution for the short network flows. Intuitively, it can be expected that with short flows one can obtain much better multiplexing gains than with the original ones (before the separation). Indeed, the analysis confirms this expectation.

Hidden Markov processes such as the Gilbert-Elliott (1960) channel have an infinite dependency structure. Therefore, entropy and channel capacity calculations require knowledge of the infinite past. In practice, such calculations are often approximated with a finite past. It is commonly assumed that the approximations require an unbounded amount of the past as the memory in the underlying Markov chain increases. We show that this is not necessarily true. We derive an exponentially decreasing upper bound on the accuracy of the finite-past approximation that is much tighter than existing upper hounds when the Markov chain mixes well. We also derive an exponentially decreasing upper bound that applies when the Markov chain does not mix at all. Our methods are demonstrated on the Gilbert-Elliott channel, where we prove that a prescribed finite-past accuracy is quickly reached, independently of the Markovian memory. We conclude that the past can be used either to learn the channel state when the memory is high, or wait until the states mix when the memory is low. Implications fur computing and achieving capacity on the Gilbert-Elliott channel are discussed.

In this paper we have considered several queueing systems with finite buffers and long-tailed arrivals. For these queueing systems we have derived explicit asymptotic formulas for approximating loss rates. The accuracy of the suggested approximate formulas is demonstrated on various numerical and simulation experiments. Overall, we expect that these approximate expressions, both for reasons of their explicit nature and accuracy, will be useful tools in designing modern communication networks that will be able to efficiently carry non-traditional long-tailed ("bursty") traffic.

Consider an aggregate arrival process A/sup N/ obtained by multiplexing N on-off sources with exponential off periods of rate /spl lambda/ and subexponential on periods /spl tau//sup on/. For this process its activity period I/sup N/ satisfies P[I/sup N/>t]/spl sim/(1+/spl lambda/E/spl tau//sup on/)/sup N-1/P[/spl tau//sup on/>t] as t/spl rarr//spl infin/ for all sufficiently small /spl lambda/. When N goes to infinity, with /spl lambda/N/spl rarr//spl Lambda/, A/sup N/ approaches an M/G//spl infin/ type process, for which the activity period I/sup /spl infin//, or equivalently a busy period of an M/G//spl infin/ queue with subexponential service requirement /spl tau//sup on/, satisfies P[I/sup /spl infin//>t]/spl sim/e/sup /spl Lambda/Er(on)/P[/spl tau//sup on/>t] as t/spl rarr//spl infin/. For a simple subexponential on-off fluid flow queue we establish a precise asymptotic relation between the Palm queue distribution and the time average queue distribution. Further, a queueing system in which one on-off source, whose on period belongs to a subclass of subexponential distributions, is multiplexed with independent exponential sources with aggregate expected rate Ee/sub t/, is shown to be asymptotically equivalent to the same queueing system with the exponential arrival processes being replaced by their total mean value Ee/sub t/. For a fluid queue with the limiting M/G//spl infin/ arrivals we obtain a tight asymptotic lower bound for large buffer probabilities. Based on this bound, we suggest a computationally efficient approximation for the case of finitely many subexponential on-off sources. The accuracy of this approximation is verified with extensive simulation experiments.

Guided by the empirical observation that real-time MPEG video streams exhibit both multiple time scale and subexponential characteristics, we construct a video model that captures both of these characteristics and is amenable to queueing analysis. We investigate two fundamental approaches for extracting the model parameters: using sample path and second-order statistics-based methods. The model exhibits the following two canonical queueing behaviors. When strict stability conditions are satisfied, i.e., the conditional mean of each scene is smaller than the capacity of the server, precise modeling of the interscene dynamics (long-term dependency) is not essential for the accurate prediction of small to moderately large queue sizes. In this case, the queue length distribution is determined using quasistationary (perturbation theory) analysis. When weak stability conditions are satisfied, i.e., the conditional mean of at least one scene type is greater than the capacity of the server, the dominant effect for building a large queue size is the subexponential (long-tailed) scene length distribution. In this case, precise modeling of intrascene statistics is of secondary importance for predicting the large queueing behavior. A fluid model, whose arrival process is obtained from the video data by replacing scene statistics with their means, is shown to asymptotically converge to the exact queue distribution. Using the transition scenario of moving from one stability region to the other by a change in the value of the server capacity, we synthesize recent queueing theoretic advances and ad hoc results in video modeling, and unify a broad range of seemingly contradictory experimental observations found in the literature. As a word of caution for the widespread usage of second-order statistics modeling methods, we construct two processes with the same second-order statistics that produce distinctly different queueing behaviors.

For an ATM multiplexer we develop a recursive asymptotic expansion method for approximating the queue length distribution and investigate the radius of convergence of the queue asymptotic expansion series. The analysis focuses on "small" to "moderate" buffer sizes under the conditions of strictly stable multiple time scale arrivals. For a class of examples we analytically determine the radius of convergence using methods of linear operator theory. We also give general sufficient conditions under which the radius converges to zero; this shows roughly what situations have to be avoided for the proposed method to work well. We combine the asymptotic expansion method with the EB approximation, and give an approximation procedure for the buffer probabilities for all buffer ranges. The procedure is tested on extensive numerical examples. We suggest this procedure for efficient admission control in ATM networks.