...the transient workload distribution, which are applied to obtain conditional limit theorem for the most probable time to overflow.

The results are strongly inspired by the large-deviations idea that overflow is typically due to some minimal combination of extremely long concurrent sessions causing positive drift. The typical configuration of long sessions is identified through a simple integer program, paving the way for the exact computation of the asymptotic workload behavior. The calculations provide crucial insight in the typical overflow scenario.

Key words: fluid queues; heavy-tailed input; infinite-server queue; large deviations; transient analysis; workload distribution

MSC2000 subject classification: Primary: 60K25; secondary: 60F10, 68M20, 90B18, 90B22

OR/MS subject classification: Primary: queues/limit theorems; secondary: probability/stochastic model applications; queues/transient results

History: Received April 1, 2001; revised October 14, 2002, January 31, 2004, and October 31, 2004.

**********

1. Introduction. Fluid models have found widespread use as a versatile approach for analyzing burst-scale traffic behavior in high-speed communication networks. The canonical model comprises a superposition of on-off sources, independently alternating between activity phases (bursts) and silence periods. When active, each source generates traffic at some constant rate.

An alternative yet closely related model is that of M/G/[infinity] input, where sessions arrive as a Poisson process, and remain in the system for a randomly distributed period of time. While in the system, each session generates traffic at some constant rate. Note that the number of active sessions behaves as the number of customers in an M/G/[infinity] system, hence the term M/G/[infinity] input. An M/G/[infinity] input process can also be viewed as the limit of the superposition of on-off sources when the number of sources grows large, and the fraction of on-time gets correspondingly small as shown in Jelenkovic and Lazar [11].

As is typically the case for fluid queues, the distribution of the activity periods strongly influences the workload behavior in an M/G/[infinity] model. In particular, there is a sharp dichotomy in the qualitative workload behavior, depending on whether the activity periods have light-tailed or heavy-tailed characteristics, It turns out that for light-tailed (exponentially bounded) activity periods, the tail distribution of the workload generally exhibits exponential decay as well; see Parulekar and Makowski [21]. These results fall in the realm of logarithmic asymptotics for general single-server queues with light-tailed arrival processes as in Duffield and O'Connell [7] and Glynn and Whitt [9].

The past few years have witnessed a surging interest in fluid models with heavy-tailed activity periods. Extensive measurements in high-speed communication networks indicate that bursty traffic behavior can extend over a wide range of time scales, manifesting itself in long-range dependence and self-similarity; see Leland et al. [14] and Paxson and Floyd [22]. The occurrence of these phenomena is commonly attributed to extreme variability and heavy-tailed characteristics in the underlying activity patterns (connection times, file sizes, scene lengths); see Beran et al. [2], Crovella and Bestavros [5], and Willinger et al. [27]. Fluid models with heavy-tailed activity periods provide a natural paradigm for capturing these characteristics; see in particular Likhanov et al. [17] for the case of M/G/[infinity] input. We refer to Boxma and Dumas [4] for a survey paper; see also the recent publications Park and Willinger [20] and Sigman [26].

Fluid queues with heavy-tailed M/G/[infinity] input have been extensively studied in several earlier papers. Likhanov [15] and Liu et al. [18] obtain asymptotic lower and upper bounds for the workload distribution. Under a certain peak rate condition, the bounds are shown to be tight (up to a constant factor) for Pareto-distributed session lengths, thus yielding the exact decay rate. The peak rate condition essentially implies that just a single long session is enough to cause overflow. Under roughly similar assumptions, Boxma [3], Jelenkovic and Lazar [12], and Resnick and Samorodnitsky [25] also determine the corresponding pre-factor, resulting in the exact workload asymptotics. Duffield [6] obtains logarithmic "many sources" asymptotics (as opposed to "large-buffer" asymptotics) for a regime where the arrival rate, service rate, and buffer size are scaled up in proportion; see also Mandjes [19].

Recently, several authors have considered heterogeneous heavy-tailed M/G/[infinity] input, where sessions belong to one of several classes with distinct characteristics (arrival rates, session lengths, peak rates). Likhanov and Mazumdar [16] obtain asymptotic lower and upper bounds for the workload distribution, which are shown to be tight up to a constant factor. Under a similar peak rate condition as described above, the bounds coincide, yielding the exact asymptotics. Remarkably enough, the bounds in Likhanov and Mazumdar [16] are asymptotically exact for finite buffers as well.

As mentioned above, the M/G/[infinity] model is closely related to the classical model with a fixed set of on-off sources. The similarity manifests itself in the qualitative way that overflow occurs for heavy-tailed input, and is also reflected in the tall asymptotics of the workload. For example, the results in Dumas and Simonian [8] and Jelenkovic and Momcilovic [13] for a fixed set of on-off sources are reminiscent of the results in Likhanov and Mazumdar [16] for M/G/[infinity] input. Also, the M/G/[infinity] asymptotics in Boxma [3], Jelenkovic and Lazar [12], and Resnick and Samorodnitsky [25] for the special case where a single long session can cause overflow are accompanied (in Boxma [3] and Jelenkovic and Lazar [12]) by conceptual counterparts for a scenario where a single regularly varying on-off source is multiplexed with several light-tailed sources.

Despite the above conceptual similarity between the two models, there are also some key differences. A striking difference arises for example in situations where the input consists of a mixture of traffic classes with light-tailed and heavy-tailed characteristics. In that case, the workload asymptotics in the M/G/[infinity] model will always be heavy-tailed as long as at least one the traffic classes is heavy-tailed, since the number of flows is not bounded. In contrast, with a fixed set of on-off sources, the workload asymptotics may either be heavy-tailed or light-tailed, depending on the value of the aggregate peak rate of the heavy-tailed flows plus the mean rate of the light-tailed flows relative to the service rate; see Dumas and Simonian [8].

As mentioned above, the exact workload asymptotics for the M/G/[infinity] model with infinite buffers have been obtained only under the restrictive condition that a single long session is sufficient to cause positive drift. In the present paper, we derive the exact asymptotics in general situations where a combination of several long sessions could be involved in causing overflow. Besides the practical relevance, these scenarios are also theoretically challenging, because the combinatorial structure of the overlap of the various sessions significantly adds to the complexity. The analysis unifies and generalizes the results in Likhanov and Mazumdar [16] and Resnick and Samorodnitsky [25] and complements the exact tail asymptotics for a fixed set of on-off sources that were recently obtained in Zwart et al. [29].

While some of the high-level concepts concerning the 'typical configuration' are similar to those in Zwart et al. [29], there are also major differences due to the dynamic population of flows. In particular, while the Poisson structure is mathematically convenient, the dynamic population of flows in the M/G/[infinity] model entails some substantial complications as well: (i) unbounded versus bounded peak rates, which requires additional effort in deriving upper bounds; (ii) there does not exist a notion of a "reduced-load equivalence," which causes some subtleties in isolating the typical configuration. In addition, the analysis sheds some new light on the relationship between the M/G/[infinity] model and the case of a fixed set of on-off sources, because it reveals some interesting distinctions that do not arise in case of a single-session overflow scenario. Specifically, in the case of a fixed set of on-off sources, the average rate and the probability of the remaining sources starting long activity periods decrease as the typical configuration assembles prior to the path to overflow. In the M/G/[infinity] model, the average rate and the intensity of further long activity periods being initiated remain constant throughout. As a result, there is a fundamental difference between the two models, which is somewhat obscured in case of a single-session overflow scenario.

As a further contribution of the present paper, the analysis provides several results for the transient workload asymptotics. It is shown that the optimal configuration of long sessions critically depends on the time parameter. In particular, we establish asymptotically tight upper and lower bounds. The bounds yield the exact asymptotics if a certain additional assumption is satisfied. As an application, we obtain a conditional limit theorem that provides crucial information on the most probable time to overflow in the steady-state case. This result complements a conditional limit theorem of Asmussen and Kluppelberg [1] for random walks. In fact, our steady-state results also follow from our transient results: In [section] 5, we formally show that limits can be interchanged.

The remainder of the paper is organized as follows. In [section] 2, we present a detailed model description and state an important preliminary result. Next, we provide some intuitive arguments and summarize the main results of the paper in [section] 3. The arguments are grounded on the large-deviations idea that overflow is typically due to some minimal combination of extremely long concurrent sessions causing positive drift. The typical configuration of long sessions is identified through a simple integer linear program, which corresponds to the set optimization problem defined in Likhanov and Mazumdar [16].

The subsequent sections are devoted to the detailed proofs. In particular, in [section] 4, we extend the probabilistic arguments developed in Resnick and Samorodnitsky [25], enabling the exact calculation of the asymptotic workload behavior. In addition, the computations provide fundamental insight in the typical overflow scenario.

As mentioned above, the analysis focuses on the transient behavior, from which the steady-state asymptotics easily follow after showing in [section] 5 that overflow occurs in linear time. In [section] 6, we combine the transient and steady-state asymptotics to obtain the limiting distribution of the most probable time to overflow.

2. Model description and preliminaries. In this section, we present a detailed model description, discuss some useful concepts, and state an important auxiliary result.

We first introduce some notational conventions that we use throughout the paper. For any two real functions f(*) and g(*), we write f(x) ~ g(x) to indicate [lim.sub.x [right arrow] [infinity]] f(x)/g(x) = 1, or equivalently, f(x) = g(x)(1 + o(1)) as x [right arrow] [infinity]. Also, we use f(x) [??] g(x) to denote lim [sup.sub.x [right arrow] [infinity]] f(x)/g(x) < 1. Similarly, f(x) [??] g(x) denotes lim [inf.sub.x [right arrow] [infinity]] f(x)/g(x) [greater than or equal to] 1. For any two random variables [??] and [??], we write [??] [??] [??] to indicate that [??] and [??] are equal in distribution. We denote by [??] = {0, 1, ...} the set of nonnegative integers. The class of functions which are regularly varying of index -[alpha] is denoted by [[??].sub.[alpha]].

2.1. Basic input and workload processes. We consider a fluid queue of unit capacity fed by K heterogeneous M/G/[infinity] input processes. Class-k sessions arrive as a Poisson process of rate [[lambda].sub.k] and remain in the system for a random period [[??].sub.k] having distribution [B.sub.k] (*) with mean [[beta].sub.k], k = 1, ..., K. We assume that [B.sub.k](*) is regularly varying of index -[[nu].sub.k] < -1 (this assumption may be relaxed somewhat; see Remark 3.1 below), so that [B.sub.k] < [infinity]. While in the system, each class-k session generates traffic at constant rate...

NOTE: All illustrations and photos have been removed from this article.



More articles from Mathematics of Operations Research
The number of solutions sufficient for solving a family of problems., November 01, 2005
Convergence to second-order stationary points of a primal-dual algorit..., November 01, 2005
Efficient algorithms for separated continuous linear programs: the mul..., November 01, 2005
Boundedness theorems for the relaxation method., November 01, 2005
Characterizations of the strong basic constraint qualifications., November 01, 2005

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.