Search

We study the transient and limiting behavior of a queue with a Pólya arrival process. The Pólya process is interesting because it exhibits path-dependent behavior, e.g. it satisfies a non-ergodic law of large numbers: the average number of arrivals over time [0, t] converges almost surely to a nondegenerate limit as $t \rightarrow \infty$. We establish a heavy-traffic diffusion limit for the $\sum_{i=1}^{n} P_i/GI/1$ queue, with arrivals occurring exogenously according to the superposition of n independent and identically distributed Pólya point processes. That limit yields a tractable approximation for the transient queue-length distribution, because the limiting net input process is a Gaussian Markov process with stationary increments. We also provide insight into the long-run performance of queues with path-dependent arrival processes. We show how Little’s law can be stated in this context, and we provide conditions under which there is stability for a queue with a Pólya arrival process.

We introduce open stochastic fluid networks that can be regarded as continuous analogues or fluid limits of open networks of infinite-server queues. Random exogenous input may come to any of the queues. At each queue, a c.d.f.-valued stochastic process governs the proportion of the input processed by a given time after arrival. The routeing may be deterministic (a specified sequence of successive queue visits) or proportional, i.e. a stochastic transition matrix may govern the proportion of the output routed from one queue to another. This stochastic fluid network with deterministic c.d.f.s governing processing at the queues arises as the limit of normalized networks of infinite-server queues with batch arrival processes where the batch sizes grow. In this limit, one can think of each particle having an evolution through the network, depending on its time and place of arrival, but otherwise independent of all other particles. A key property associated with this independence is the linearity: the workload associated with a superposition of inputs, each possibly having its own pattern of flow through the network, is simply the sum of the component workloads. As with infinite-server queueing models, the tractability makes the linear stochastic fluid network a natural candidate for approximations.

We consider the standard single-server queue with unlimited waiting space and the first-in first-out service discipline, but without any explicit independence conditions on the interarrival and service times. We find conditions for the steady-state waiting-time distribution to have asymptotics of the form x –1 log P(W > x) → –θ ∗as x → ∞for θ ∗ > 0. We require only stationarity of the basic sequence of service times minus interarrival times and a Gärtner–Ellis condition for the cumulant generating function of the associated partial sums, i.e. n –1 log E exp (θSn ) → ψ (θ) as n → ∞, plus regularity conditions on the decay rate function ψ. The asymptotic decay rate θ is the root of the equation ψ (θ) = 0. This result in turn implies a corresponding asymptotic result for the steady-state workload in a queue with general non-decreasing input. This asymptotic result covers the case of multiple independent sources, so that it provides additional theoretical support for a concept of effective bandwidths for admission control in multiclass queues based on asymptotic decay rates.

We apply the general theory of stochastic integration to identify a martingale associated with a Lévy process modified by the addition of a secondary process of bounded variation on every finite interval. This martingale can be applied to queues and related stochastic storage models driven by a Lévy process. For example, we have applied this martingale to derive the (non-product-form) steady-state distribution of a two-node tandem storage network with Lévy input and deterministic linear fluid flow out of the nodes.

Variability orderings indicate that one probability distribution is more spread out or dispersed than another. Here variability orderings are considered that are preserved under conditioning on a common subset. One density f on the real line is said to be less than or equal to another, g, in uniform conditional variability order (UCVO) if the ratio f(x)/g(x) is unimodal with the model yielding a supremum, but f and g are not stochastically ordered. Since the unimodality is preserved under scalar multiplication, the associated conditional densities are ordered either by UCVO or by ordinary stochastic order. If f and g have equal means, then UCVO implies the standard variability ordering determined by the expectation of all convex functions. The UCVO property often can be easily checked by seeing if f(x)/g(x) is log-concave. This is illustrated in a comparison of open and closed queueing network models.

In 1969 H. and D. Stoyan showed that the stationary waiting-time distribution in a GI/G/1 queue increases in the ordering determined by the expected value of all non-decreasing convex functions when the interarrival-time and service-time distributions become more variable, as expressed in the ordering determined by the expected value of all convex functions. Ross (1978) and Wolff (1977) showed by counterexample that this conclusion does not extend to all GI/G/s queues. Here it is shown that this conclusion does hold for all GI/G/s queues for several other measures of congestion which coincide with the waiting time in single-server systems. One such alternate measure of congestion is the clearing time, the time required after the arrival epoch of the nth customer for the system to serve all customers in the system at that time, excluding the nth customer. The stochastic comparisons also imply an ordering for the expected waiting times in M/G/s queues.

One probability measure is less than or equal to another in the sense of UCSO (uniform conditional stochastic order) if a standard form of stochastic order holds for each pair of conditional probability measures obtained by conditioning on appropriate subsets. UCSO can be applied to the comparison of lifetime distributions or the comparison of decisions under uncertainty when there may be reductions in the set of possible outcomes. When densities or probability mass functions exist on the real line, then the main version of UCSO is shown to be equivalent to the MLR (monotone likelihood ratio) property. UCSO is shown to be preserved by some standard probability operations and not by others.

Karlin and Rinott (1980) introduced and investigated concepts of multivariate total positivity (TP2) and multivariate monotone likelihood ratio (MLR) for probability measures on Rn These TP and MLR concepts are intimately related to supermodularity as discussed in Topkis (1968), (1978) and the FKG inequality of Fortuin, Kasteleyn and Ginibre (1971). This note points out connections between these concepts and uniform conditional stochastic order (ucso) as defined in Whitt (1980). ucso holds for two probability distributions if there is ordinary stochastic order for the corresponding conditional probability distributions obtained by conditioning on subsets from a specified class. The appropriate subsets to condition on for ucso appear to be the sublattices of Rn . Then MLR implies ucso, with the two orderings being equivalent when at least one of the probability measures is TP2.

In 1969 H. and D. Stoyan showed that the stationary waiting-time distribution in a GI/G/1 queue increases in the ordering determined by the expected value of all non-decreasing convex functions when the interarrival-time and service-time distributions become more variable, as expressed in the ordering determined by the expected value of all convex functions. Ross (1978) and Wolff (1977) showed by counterexample that this conclusion does not extend to all GI/G/s queues. Here it is shown that this conclusion does hold for all GI/G/s queues for several other measures of congestion which coincide with the waiting time in single-server systems. One such alternate measure of congestion is the clearing time, the time required after the arrival epoch of the nth customer for the system to serve all customers in the system at that time, excluding the nth customer. The stochastic comparisons also imply an ordering for the expected waiting times in M/G/s queues.

This paper describes the operator mapping a renewal-interval distribution into its associated stationary-excess distribution. This operator is monotone for some kinds of stochastic order, but not for the usual stochastic order determined by the expected value of all non-decreasing functions. Conditions for a renewal-interval distribution to be larger or smaller than its associated stationary-excess distribution for several kinds of stochastic order are determined in terms of familiar notions of ageing. Convergence results are also obtained for successive iterates of the operator, which supplement Harkness and Shantaram (1969), (1972) and van Beek and Braat (1973).

A bound on the rate of convergence and sufficient conditions for the convergence of moments are obtained for the sequence of waiting times in the GI/G/1 queue when the traffic intensity is at the critical value ρ = 1.

To obtain a limit with independent components in the superposition ofm-dimensional point processes, a condition corresponding to asymptotic independence must be included. When this condition is relaxed, convergence to limits with dependent components is possible. In either case, convergence of finite distributions alone implies tightness and thus weak convergence in the function spaceD[0, ∞) × … ×D[0, ∞).

To obtain a limit with independent components in the superposition of m-dimensional point processes, a condition corresponding to asymptotic independence must be included. When this condition is relaxed, convergence to limits with dependent components is possible. In either case, convergence of finite distributions alone implies tightness and thus weak convergence in the function space D[0, ∞) × … × D[0, ∞).

We shall consider a single-server queue with r priority classes of customers and a preemptive-resume discipline. In this system customers are served in order of their priority while customers of the same priority are served in order of their arrival. Higher priority customers, immediately upon arrival, replace lower priority customers at the server, while customers displaced in this way return to the server before any other customers of the same priority receive service. When a displaced customer returns to the server, his remaining service time is the uncompleted portion of his original service time (cf. Jaiswal (1968)).

Let D = D[0, ∞) be the space of all real-valued right-continuous functions on [0, ∞) with limits from the left. For any stochastic process X in D, let the associated supremum process be S(X), wherefor any x ∊ D. It is easy to verify that S: D → D is continuous in any of Skorohod's (1956) topologies extended from D[0,1] to D[0, ∞) (cf. Stone (1963) and Whitt (1970a, c)). Hence, weak convergence Xn ⇒ X in D implies weak convergence S(Xn) ⇒ S(X) in D by virtue of the continuous mapping theorem (cf. Theorem 5.1 of Billingsley (1968)).

We verify and extend a conjecture of Purdue (1981) concerning the stochastic monotonicity of absorption times in a class of compartmental urn models. We also describe the effect of increased variability in the reinforcement sizes. Finally, we investigate variability in the content process for large populations. In many applications, compartmental models substantially under-represent the variability observed in the data, so that there has been considerable interest in modifying the model to increase the variability. We show that the squared coefficient of variation of the content is not asymptotically negligible when both the size and the variability of the reinforcements are of the same order as the initial population.