...Gromoll [9] and Puha and Williams [15]. An important distinction between critical and strictly supercritical fluid models is that the total mass for a solution that starts from zero grows with time for the, but it is identically equal to zero for the former. For strictly supercritical fluid models, this paper contains descriptions of each of the following: the distribution of the mass as it builds up from zero, the set of stationary solutions, and the limiting behavior of an arbitrary solution as time tends to infinity. In addition, a fluid limit result is proved that justifies strictly supercritical fluid models as first order approximations to overloaded processor sharing queues.

Key words: overloaded processor sharing queue; supercritical fluid models; measure-valued process; invariant shape; order preservation; continuity in initial conditions; renewal equations MSC2000 subject classification: Primary: 60K25; secondary: 68M20, 90B22 OR/MS subject classification: Primary: queues-approximations, queues-limit theorems, queues-transient results; secondary: probability-stochastic model applications

1. Introduction. The main aim of this paper is to study strictly supercritical fluid models which arise as functional law of large numbers approximations for overloaded GI/GI/1 processor sharing queues. An analogous study of critical fluid models associated with heavily loaded processor sharing queues is contained in Gromoll et al. [9] and Puha and Williams [15], and the investigation undertaken here is a natural progression from that work. The introduction of Gromoll et al. [9] contains a brief summary of the processor sharing literature, and we refer the reader to that paper for a list of references. The queueing model setup used here is similar to that in Gromoll et al. [9]. In particular, we use a measure-valued state descriptor in order to capture information about residual service times. Measure-valued state descriptors have been successfully used for other stochastic networks models; see, e.g., Doytchinov et al. [3], Grishechkin [7], and Gromoll [8]. In formulating the strictly supercritical fluid models, we take formal limits of sequences of measure-valued stochastic processes, corresponding to sequences of overloaded processor sharing queues, under law of large numbers scaling. Solutions of the strictly supercritical fluid models are functions of time that take values in the set of finite, nonnegative Borel measures on the nonnegative real numbers and that satisfy certain properties. There is an important distinction between the critical fluid models (associated with sequences of heavily loaded processor sharing queues) and the strictly supercritical fluid models. Namely, the total mass for a fluid model solution with zero initial measure grows with time for the latter, but it is identically equal to zero for the former. In analyzing the strictly supercritical fluid models, we describe the distribution of mass as it builds up from zero. The same analysis produces some new results for critical fluid models, which we include here as well. Thus, we consider supercritical fluid models in this paper. These include both the critical and the strictly supercritical cases. However, the main emphasis is on the latter.

For the strictly supercritical fluid models, we prove four results. We give conditions for existence and uniqueness of fluid model solutions (cf. Theorem 3.1). We explicitly identify the fluid model solutions having a zero initial condition (cf. Theorem 3.2). We identify the fluid model solutions for which the shape does not change with time, the so-called stationary fluid model solutions (cf. Theorem 3.6). Finally, we investigate the asymptotic behavior of fluid model solutions as time tends to infinity. Indeed, under mild conditions, we prove a limit theorem that identifies the asymptotic shape (cf. Theorem 3.5). There are two key elements in the proofs of these theorems. The first is an order preservation property for fluid model solutions (cf. Theorem 4.2), and the second is a continuity property (cf. Theorem 4.3). Both properties are valid not only for strictly supercritical fluid models, but also for critical fluid models. As a consequence, we are able to extend the work in Gromoll et al. [9] to prove a result that holds for both critical and strictly supercritical fluid models (cf. Theorem 3.3). This result states that the mapping from initial conditions in a certain domain to the associated fluid model solutions is continuous.

In order to justify the strictly supercritical fluid models as first-order approximations to overloaded processor sharing queues, we prove a fluid limit result. For this, we consider a sequence of measure-valued stochastic processes corresponding to a sequence of overloaded processor sharing queues. The fluid limit result states that, under mild conditions, the fluid scaled measure-valued stochastic processes converge in distribution to a limit which is almost surely a fluid model solution (cf. Theorem 3.7). This result concerns a sequence of stochastic processes that converges in distribution to a limiting stochastic process. However, since the limit process is almost surely a fluid model solution, it is only stochastic through the initial condition.

In [10], Jean-Marie and Robert prove a law of large numbers type of result that is consistent with our fluid limit result. They study the asymptotic behavior as time tends to infinity of a single overloaded processor sharing queue that has exactly one job in the system at time zero. They prove that, under mild conditions, the state at time t divided by t converges almost surely as t tends to infinity to what we would call the state of the fluid model solution at time one when the initial measure is the zero measure (cf. Jean-Marie and Robert [10, Proposition 4] and the last paragraph of [section] 3.3.2 here).

Fluid approximations for the queue length processes of processor sharing queues are proposed in Chen et al. [2]. As was noted in the introduction of Gromoll et al. [9], the justification given in [2] for those fluid approximations is valid, provided that all limit points are deterministic. Our approach provides a proof that this assumption is valid for the overloaded processor sharing queue under the mild conditions identified here (cf. Theorem 3.7). In the strictly supercritical setting, the authors of Chen et al. [2] show that their fluid approximations for the queue length processes are asymptotically linear as time tends to infinity, and they determine the limiting linear rates of increase (cf. [2, Proposition 6] and the last paragraph in [section] 3.2.7 here). Our Theorem 3.5 is a generalized version of [2, Proposition 6] that also specifies the asymptotic shape (as time goes to infinity) of the fluid approximation to the measure-valued process that captures the behavior of the residual service times.

In [13], our fluid limit result is used by Mandjes and Zwart who analyze the asymptotic behavior of the tail probability for the sojourn time of a tagged job in a strictly subcritical GI/GI/1/PS queue in steady state. The main Mandjes and Zwart result [13, Theorem 3.1] concerns the sojourn time under a light-tailed (but not too light) service time distribution (cf. [13, Assumptions 3.1 and 3.2]). In the proof of Mandjes and Zwart [13, Theorem 3.1], the tail probability for the sojourn time in a strictly subcritical queue is related to the tail probability for the sojourn time in a strictly supercritical queue (cf. [13, Equation (3.7)]), and then the strictly supercritical tail probability in [13, Equation (3.7)] is analyzed to obtain a desired lower bound. The analysis of the strictly supercritical tail probability in [13, Equation (3.7)] in part relies on [13, Lemma 3.1], the proof of which uses our fluid limit result.

The paper is organized in the following manner. Section 2 describes the basic setup. Specifically, [section] 2.1 establishes the notation that is used throughout the paper, and [section] 2.2 describes the dynamics for a processor sharing queue and the associated measure-valued state descriptor. Section 3 contains a discussion of the fluid models. The definitions of fluid model solutions for both the critical and strictly supercritical models are contained in [section] 3.1. Section 3.2 contains the statements of the main results proved in the paper concerning solutions of the supercritical fluid models (Theorems 3.1, 3.2, 3.5, and 3.6 for strictly supercritical data, and Theorem 3.3 for supercritical data). Section 3.3 contains the statement of the fluid limit result (Theorem 3.7). Sections 4 and 5 are devoted to the proofs of the theorems stated in [section] 3. Some of the theorems can be proved in a very similar manner to those in Gromoll et al. [9], particularly for the case of nonzero initial measures. For these instances, we have chosen to omit the complete proof in favor of referencing the similar proof in Gromoll et al. [9] and explaining how to adapt it. This allows us to focus on the new tools and results such as the order preservation property (Lemma 4.2 in [section] 4.3), the proof of uniqueness for Theorem 3.2, the proof of continuity at the zero initial measure for Theorem 3.3, and establishing tightness for the fluid limit result.

2. Preliminaries and queueing model. In this section, we outline some necessary background. In [section] 2.1, we introduce the basic notation that is used throughout the paper. In [section] 2.2, we describe the processor sharing queueing model. Readers who are familiar with the setup in Gromoll et al. [9] will find this to be rather redundant, since it is largely taken verbatim from that paper. We repeat it here for completeness because the processor sharing queueing model needs to be precisely defined in order to state the fluid limit result.

2.1. Notation. Let [??] denote the set of natural numbers, let [??] denote the set of real numbers, and let [??] denote the set of nonnegative real numbers. For a, b [member of] [??], we write a [disjunction] b for the maximum of a and b, a [conjunction] b for the minimum of a and b, [a.sup.+] = a [disjunction] and [a.sup.-] = a [disjunction] for the positive and negative parts of a respectively, [??]a[??] for the largest integer less than or equal to a, and [??]a[??] for the smallest integer greater than or equal to a. For a Borel-measurable function g: [[??].sub.+] [right arrow] [??], define the positive and negative parts of g by [g.sup.+] (x) = g(x) [disjunction] and [g.sup.-](x) = (-g(x)) [disjunction] for all x [member of] [[??].sub.+]. For such a function g, let [[parallel]g[parallel].sub.[infinity]] = [sup.sub.x[member of] [[??].sub.+]] [absolute value of g(x)], [[parallel]g[parallell].sub.K] = [sup.sub.x[member of][0.K]] [absolute value of g(x)] for each K [greater than or equal to] 0, and [[paralle]g[parallel].sub.[L.sup.1]] = [[integral].sup.[infinity].sub.0] [absolut value of g(x)] dx, where we allow these quantities to take the value +[infinity].

For a set B [subset] [[??].sub.+], we denote the indicator function for the set B by [1.sub.B]. We also define the real-valued functions [chi] and [phi] on [[??].sub.+] as follows: [chi](x) = x for x [member of] [[??].sub.+], and [phi](x) = 1/x for x [member of] (0, [infinity]) and [phi](0) = 0. For a topological space A, denote by C(A) the set of continuous, real-valued functions defined on A. Similarly, [C.sub.b](A) denotes the set of continuous, bounded, real-valued functions defined on A. In addition, for an interval I [subset] [??], [C.sup.1] (I) is the set of once continuously differentiable, real-valued functions defined on I, and [C.sup.1.sub.b](I) is the set of functions in [C.sup.1](I) that together with their first derivatives are bounded on I. For g [member of] [C.sup.l] (I), we write g'(x) = (d/dx)g(x), for all x [member of] I.

Let [[??].sub.F] be the set of finite, nonnegative Borel measures on [[??].sub.+]. Consider [zeta] [member of] [[??].sub.F] and a Borel-measurable function g: [[??].sub.+] [right arrow] [??] which is integrable with respect to [zeta]. We define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Our equations will involve expressions of the form [[integral].sub.[[alpha].[infinity]) g(x - a) [zeta](dx), for a [greater than or equal to] 0. To ease notation throughout, we write this as [right arrow] as n [right arrow] [infinity] for all g [member of] [[??].sub.b]([[??].sub.+]), in which case we write [[zeta].sub.n] [??] [zeta] as n [right arrow] [infinity]. With this topology, [[??].sub.F] is a Polish space (cf. Prohorov [14]). A family {[[infinity].sub.t], t [member of] (0, [infinity])} [subset] [[??].sub.F] converges to [zeta] [member of] [[??].sub.F] if and only if for each sequence {[t.sub.n] [member of] [??} [subset]] (0, [infinity]) such that [t.sub.n] [right arrow] [infinity] as n [right arrow] [infinity] we have [[zeta].sub.[t.sub.n] [??] [zeta] as n [right arrow] [infinity]. We denote the zero measure in [[??].sub.F] by [??] and the measure in [[??].sub.F] that puts one unit of mass at the point x [member of] [[??].sub.+] [[delta].sub.x].

We will use "[??]" to denote convergence in distribution of random elements of a metric space. Following Billingsley [1], we will use [??] and [??] respectively to denote the probability measure and expectation operator associated with whatever space the relevant random element is defined on. All stochastic processes used in this paper will be assumed to have paths that are right continuous with finite left limits (r.c.l.1.). For a Polish space [??], we denote by D([0, [infinity]), [??]) the space of r.c.l.l, functions from [0, [infinity]) into [??], and we endow this space with the usual Skorohod [J.sub.1]-topology (cf. Ethier and Kurtz [5]). The subspace of continuous functions from [0, [infinity]) into [??] will be denoted by C([0, [infinity]), [??]). When restricted to this space, the Skorohod [J.sub.1]-topology is the same as that induced by uniform convergence on compact time intervals.

2.2. The processor sharing queue. Here, we describe our processor sharing queueing system. The primitive stochastic processes and initial condition for our model are introduced in [section] 2.2.1. The system dynamics and performance processes are described in [section] 2.2.2. Here, an important quantity for the processor sharing queue is introduced, namely the cumulative service process. In [section] 2.2.3, we introduce the state descriptor and a dynamic equation associated with its evolution. The state descriptor and the associated dynamic equation play a fundamental role in justifying the strictly supercritical fluid model as a first-order approximation of an overloaded processor sharing queue.

2.2.1. Primitive processes and initial condition. The exogenous arrival process E(*) is a rate [alpha] delayed-renewal process. The arrival rate [alpha] is assumed to be strictly positive and finite. Jump times for E(*) correspond to times at which jobs enter the system. This renewal process is defined from a sequence of interarrival times [{[[u].sub.i]}.sup.[infinity].sub.i=1], where [u.sub.1] denotes the time at which the first job to arrive after time zero enters the system and [[??].sub.i], i [greater than or equal to] 2, denotes the time between the arrival of the ([i] - 1)st and ith jobs to enter the system after time zero. Frequently, we will simply refer to the ith job to enter the system after time zero as the [??]th arrival. Thus, [U.sub.i] = [[summation].sup.i.sub.j=1] [u.sub.j] is the time at which the ith arrival enters the system, which is interpreted as zero if i = 0, and E(t) = sup{i [greater than or equal to] 0: [U.sub.i] [less than or equal to] t} is the number of exogenous arrivals by time t. We assume that the sequence [{[u.sub.i]}.sup.[infinity].sub.i=2] is an i.i.d, sequence of nonnegative random variables with [??][[u.sub.2]] = 1/[alpha]. The random variable [u.sub.1] is associated with an initial delay preceding the first arrival and is assumed to be a strictly positive random variable, independent of {[u.sub.i}].sup.[infinity].sub.i=2], with finite mean, but otherwise may have an arbitrary distribution. We refer to [u.sub.1] as the initial residual interarrival time.

The service process, [{V(i)}.sup.[infinity].sub.i=0, is such that V(i) records the total amount of time required from the server to process the first i arrivals. More precisely, let [{[v.sub.i]}.sup.[infinity].sub.i=1] denote an i.i.d, sequence of strictly positive random variables with common distribution given by a Borel probability measure [nu] on [[??].sub.+]. We interpret [v.sub.i] as the amount of time required from the server to process the ith arrival. The [v.sub.i]s are known as the service times and [nu] is known as the service time distribution. Then, V([i]) = [[summation].sup.i.sub.j=l] [v.sub.j], i [greater than or equal to] O, which is taken to be zero if i = 0. It is assumed that [v.sub.1] > and [??][[v.sub.1] < [infinity]. In terms of [nu], these assumptions are expressed by saying that [nu] does not charge the origin ([nu]({0}) = 0) and ([chi], [nu]) < [infinity]. (Recall that [chi](x) = x for all x [member of] [[??].sub.+].)

The two processes E(*) and V(*) are called the primitive processes, since they provide the primitive stochastic inputs for the model. The processes E(*) and V(*) are not assumed to be independent of one another since our interest is in asymptotic behavior under fluid scaling where only laws of large numbers come into play.

Any job that is present in the system at time zero is called an initial job. The initial condition specifies the number Z(0) of initial jobs and each initial job's respective service requirement. Here, Z(0) is assumed to be a nonnegative, integer-valued random variable with finite mean. The service times for the initial jobs are taken to be the first Z(0) elements of a sequence [{[[??].sub.j]}.sup.[infinity].sub.j=1] of strictly positive random variables, with [[??].sub.j] being the service time requirement of the [??]th initial job, 1 [greater than or equal to] j [greater than or equal to] Z(0). It is assumed that the initial workload has a finite mean, i.e., that [??][[summation].sup.Z(0).sub.j=1] [[??].sub.j]] < [infinity]. The random variables Z(0) and [{[[??].sub.j]}.sup.[infinity].sub.j=1] are neither assumed to be independent of one another nor of the primitive processes.

2.2.2. Performance processes and descriptive equations. In a processor sharing queue, the server, rather than providing service to just one job at a time, works simultaneously on all jobs currently in the system by providing an equal fraction of its attention to each. In particular, at any given time that the system is nonempty, each job in the system is being processed at a rate that is the reciprocal of the number of jobs in the system. When the server has fulfilled a given job's service requirement, the job exits the system. This system is known as a processor sharing queue.

As the processor sharing queue evolves in time, certain r.c.l.1, stochastic processes are used to track important measures of performance for the system, e.g., queue length, workload, and idle time. Let Z(t) denote the queue length at time t, which is the total number of jobs in the system at time t. Also, let W(t) denote the (immediate) workload at time t, which is the total amount of time that the server must work in order to satisfy the remaining service requirement of each job present in the system at time t, ignoring future arrivals. Finally, let Y(t) denote the cumulative amount of time that the server has been idle up to time t. The processes W(*), Y(*), and Z(*) are called performance processes. These processes satisfy a set of descriptive equations, which we now present.

We begin with the familiar equations for the workload W(*) and idle time Y(*) processes, which are valid for any nonidling service discipline, including processor sharing. For t [greater than or equal to] 0,

W(0) = [Z(0).[summation] over (j=1)] [[??].sub.j] (1)

W(t) = W(0) + V(E(t)) - t + Y(t), (2)

Y(t) = sup{[(W(0) + V(E(s)) - s).sup.-]: [less than or equal to] s < t}. (3)

A set of equations satisfied by the queue length process Z(*) under a processor sharing service discipline is the following. For t [greater than or equal to] 0,

Z(t) = Z(0) + E(t) - D(t), (4)

D(t) = [Z(0).summation over (j=1)] 1{[[??].sub.j] [less than or equal to] S (t)} + [E(t).summation over (i=1)]1{[v.sub.i] [less than or equal to] S(t)-S([U.sub.i], (5)

S(t) = [Integral].sup.t.sub.0] [phi](Z(s)) ds. (6)

Recall that [phi](x) = 1/x if x > 0, and [phi](0) = 0. The process D(*) is the departure process, where D(t) represents the total number of jobs that have departed from the system by time t. The process S(*) is known as the cumulative service process, and S(t) represents the cumulative amount of service time allocated per job up to time t.

The cumulative service process S(*) will play a particularly important role in our analysis. We will find it convenient to have notation for the increments of this process. For t, h [greater than or equal to] 0, define the cumulative service per job in [ t, t + h] by

[S.sub.t,(t + h)] = S(t +h) - S (t) [[integral].sup.t+h.sub.t][phi](Z(s))ds. (7)

For t [greater than or equal to] [U.sub.[??]], the [??]th arrival receives an amount of service equal to [[??].sub.i] [disjunction]] [S.sub.[U.sub.[??]], t] by time t. Define the residual service time at time t [greater than or equal to] of the [??]th arrival, [??] [member of]] {1, ..., E(t)}, and of the [??]th initial job, [??] [member of] {1, ..., Z(0)}, by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (8)

respectively. The workload at time t [greater than or equal to] can be rewritten as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (9)

2.2.3. Measure-valued state descriptor. As in Gromoll et al. [9], we use a measure-valued process to keep track of the residual service times. For each t [greater than or equal to] 0, let [mu](t) be the random, finite, Borel measure on [[??].sub.+] = [0, [infinity]) given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (10)

Recall that [[delta].sub.x] is the measure that puts a single unit of mass at x for x [member of] [[??].sub.+]. Thus, the random measure [mu](t) has a unit of mass at the residual service time of each job that is still in the system at time t. The indicator functions in the above definition serve to eliminate jobs with zero residual service times from the description of the system state, since...

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



More articles from Mathematics of Operations Research
Permuted standardized time series for steady-state simulations., May 01, 2006
Evolutionary stability for large populations and backward induction., May 01, 2006
Job shop scheduling with unit processing times., May 01, 2006
The Hamilton apportionment method is between the Adams method and the ..., May 01, 2006
A linearly convergent dual-based gradient projection algorithm for qua..., May 01, 2006

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.