Queueing theory without limits: transient and asymptotic analysis

October 17-19, 2007

EURANDOM, Eindhoven, The Netherlands

ABSTRACTS

Søren Asmussen (Aarhus University, Denmark)

Some applications of phase-type distributions to transient analysis

The classical applications of phase-type (PH) distributions dealt typically with steady-state problems such as finding the stationary distribution of a queueing system. More recently, also transient problems have been approached using PH distributions; the main tools have been based on transforms.
The present talk presents some examples of a more probabilistic flavour, covering M/PH/1 transient analysis, first passage problems for queues with Levy netput process, some related examples from finance, and fluid rewards,

Rene Bekker (Vrije Universiteit Amsterdam)

A fluid model for a relay node in an ad-hoc network: The Case of Heavy-Tailed input

Relay nodes in an ad-hoc network can be modelled as fluid queues, in which the available service capacity is shared by the input and output.
In this paper such a relay node is considered; jobs arrive according to a Poisson process and bring along a random amount of work. The total transmission capacity is fairly shared, meaning that, when n jobs are present, each job transmits traffic into the queue at rate 1/(n+1) while the queue is drained at the same rate of 1/(n+1). Where previous studies mainly concentrated on the case of exponentially distributed job sizes, the present paper analyzes the case of regularly varying jobs.
The focus lies on the tail asymptotics of the sojourn time S. Using sample-path arguments, it is proven that P(S>x) behaves roughly as the residual job size, i.e., if the job sizes are regularly varying of index -m, the tail of S is regularly varying of index 1-m. The tail asymptotics of other performance metrics, such as the workload in the queue, the flow transfer time and the queueing delay, are also addressed.

James Cruise (Cambridge, UK)

Large and Moderate Deviations for Small buffers

We consider a large and moderate deviations limits for a small buffer queueing system fed by many independent identical flows where traffic is modeled as a point process. We show that single server queue and associated sample paths behave as if fed by marked Poisson traffic in a large deviations limit and Brownian traffic in the moderate deviations limit. The timescale of events of interest tends to zero, so we study the log moment generating function as time tends to zero. The associated rate function depends only on the mean arrival rate and the moment generating function of the arrivals.

Krzysztof Debicki (Wroclaw University, Poland)

Gaussian queues: the analysis of the asymptotic constant

Ton Dieker (IBM Research in New York)

Time-dependent behavior of Jackson series networks and determinants

This talk is partly based on joint work with Jon Warren (University of Warwick, UK).

Product forms for Jackson networks consistute a cornerstone of queueing theory. To obtain product forms, it is essential to consider the system in steady state. This leaves an important question unanswered: how does the system behave before it reaches steady state? This talk focuses on this question for special Jackson networks: queues in series. I will show that, in an attempt to study their time-dependent behavior, determinants arise on several occasions.

Ken Duffy (National University of Ireland)

Logarithmic asymptotics for the supremum of a stochastic process.

The supremum of a stochastic process arises as an object of natural interest in many branches of applied probability. In queueing theory, this is due to theorem of Loynes from 1962 where the supremum arises as the stationary distribution of the waiting time in the stationary solution of Lindley's recursion for the single server queue.

In this talk we describe an asymptotic result for the logarithm of the likelihood that the supremum of a stochastic process is large.
The theorem is proved under a few large-deviation-like assumptions.
In a departure from many large deviation results in the queueing literature, the scaled cumulant generating function is not used as a tool in the proof, which helps broaden the result's range of applicability.

This talk is based on a paper written with John T. Lewis and Wayne Sullivan, and includes an example based on some recent joint work with Artem Sapozhnikov.

Michael Drmota (TU Vienna, Austria)

Asymptotic theory of enumeration and applications to Markov chain models

The purpose of this talk is to present analytic methods for determining the asymptotic behaviour of the coefficents of power series that can be applied to homogeneous discrete quasi death and birth processes. It turns that there are in principle only three types for the asymptotic behaviour. The process either converges to the stationary distribution or it can be approximated in terms of a reflected Brownian motion or by a Brownian motion. In terms of Markov chains these cases correspond to positive recurrence, to null recurrence, and to non recurrence. The same results hold for the continuous case, too.

B. Van Houdt (Universiteit Antwerpen)

Quasi-Birth-Death Markov chains with marked time epochs

In this talk we present a framework to assess transient performance measures by generalizing the theory of the quasi Birth-and-Death (QBD) processes to QBDs with marked time epochs (QBD^m).

The distinction with the classical QBD process is that certain time epochs get marked according to a specific set of Markovian rules. Our interest lies in obtaining the system state at the n-th marked time epoch. To obtain this measure, we transform the transient problem, via a discrete Erlangization, into a steady state problem of a reset Markov chain. A fast algorithm, with limited memory usage, based on solving a single quadratic matrix equation, a set of Sylvester matrix equations and fast Fourier transforms is discussed.

We also explain how this approach avoids the need to redo all the computations when changing the initial state, i.e., the state at time 0.

Sir John Kingman (former director Isaac Newton Institute, UK)

Fifty years of heavy traffic

Because queueing theory originated in the practical field of teletraffic engineering, there was always a concern with approximating complex formulae by simple rules of thumb. Moreover, the use of complex variable techniques by Felix Pollaczek, from 1930 onwards, made it clear that waiting time distributions typically had exponential tails. But it was only in the 1950s and 1960s that the existence and usefulness of approximations, robust to assumptions about arrival and service distributions, became apparent. This talk will set the historical context of these developments, will summarise the lines of research that have since evolved, and will attempt to draw some lessons for future progress in usable queueing theory.

Marc Lelarge (ENS, France)

Logarithmic asymptotics for the maximum of a transient process

We derive bounds for the logarithmic asymptotics for the maximum of a transient process in term of its scaled moment generating function. When the process is an independent subadditive or superadditive process, natural conditions are given for the agreement of these bounds. Then we show how our results apply to processes arising in the analysis of communication networks, insurance or bio-informatics. We also apply our results to functional of branching processes.

Johan van Leeuwaarden (Eindhoven University of Technology/EURANDOM)

Gaussian asymptotics for Erlang B and C

We present new asymptotic expansions and bounds for the Poisson distribution that lead to similar results for the Erlang B and C formula. The obtained bounds seem to be the sharpest obtained in the literature thus far. We also show how our framework can be used to settle a conjecture of Ramanujan.

This is joint work with Guido Janssen and Bert Zwart.

Lasse Leskelä (Eindhoven University of Technology)

Coupling techniques for queueing systems

This talk introduces stochastic binary relations that extend the notion of stochastic order into a relation between probability measures over two arbitrary state spaces. The main result is an extension of Massey's stochastic comparison theorem that characterizes when two Markov jump processes can be coupled to preserve a given binary relation. These methods are applied to derive upper and lower bounds for the time-dependent distributions of Markovian queueing systems.

Andreas Löpker (EURANDOM)

Analysis of a multiplicative growth collapse model

We investigate a piecewise deterministic Markov process that increases linearly in time and experiences downward jumps at Poisson times. More specifically, the current value of the process at a jump time is multiplied by a random number between zero and one. We present a transient analysis of this process, the main result being a formula for the Laplace transform of the transient moments. Explicit results for the integer and fractional moments are given. We further present results on the first hitting time of the process, including power series representations for the mean and the Laplace transform and an analysis of the asymptotic behavior as the reached level tends to infinity.

William Massey (Princeton University, USA)

Dynamical Queueing Systems

A common assumption made for Markovian queueing models is that the underlying stochastic process is a time-homogeneous Markov chain. The resulting stationary behavior of these chains (when it exists) is equivalent to its limiting or steady state behavior. Hence the distant, future behavior of this chain describes its own present day behavior, when initiated in the distant past. So instead of studying of its short run, transient behavior through the analysis of differential equations, we can study its long run steady state behavior through a simpler analysis of linear equations.

Unfortunately, many communication systems and services generate Markov chain queueing models that are not time-homogeneous. We now have systems governed in the future by rates that have not yet happened in the present. Hence the classical steady state analysis no longer gives us useful insight into the evolution of such queueing models. This means that a new type of analysis is needed to create a time-inhomogeneous, time-varying, or more simply, a dynamical queueing theory.

Poisson processes play a major role in constructing many important, fundamental queueing models through random time changes, reflection mappings, stochastic integrals and other sample path constructions. Hence we can analyze these queueing models by using techniques such as random measures and strong approximations. A key method of asymptotic analysis that we use is called uniform acceleration, where we scale the rates of the underlying Markov chain instead of time. Uniform acceleration gives us a dynamic analogue to steady state analysis. Moreover, it forms a rigorous basis for obtaining fluid and diffusion approximations of the original queueing model as limit theorems, where the limits are characterized by dynamical systems. Finally, through the use of these fluid models, we can apply the variational calculus techniques of classical mechanics to develop a near optimal design and control of these dynamical queueing systems.

Mariana Olvera (Columbia University, USA)

Model Robustness of Tail Distributions

We analyze the robustness of approximations for the tail distribution of the sum of iid random variables when the extreme tail of the summands is unknown. Similar results for the tail distribution of the steady-state waiting time in the G/G/1 queue are also presented under the assumption that the distribution of the interarrival times is fully known but the tail distribution of the processing times is unknown beyond a certain point.

Zbigniew Palmowski (University of Wrocław)

Overflow probabilities in a two-node parallel queue.

We analyze a two-node parallel queue with the Levy-type input. We first derive an explicit expression for the joint distribution function of the workloads of the first and second queue, which allows us to calculate their exact large-buffer asymptotics. We also analyze input intensity being renewal compound process and concentrate on the Poisson compound process.

Andrew Richards (Heriot-Watt, UK)

Asymptotics of Dependent Subexponential Sums and the Principle of the Big Jump

The asymptotic tail-behaviour of sums of independent subexponential random variables is well understood, one of the main characteristics being the Principle of the Single Big Jump. We study the case of dependent subexponential random variables, for both deterministic and random sums, by considering conditional independence structures on the random variables, and asking for sufficient conditions for the results of the theory with independent random variables still to hold. We examine some examples where our conditions are not met, and see how the behaviour of the sum differs then from the independent case.

Gennady Samorodnitsky (Cornell University, USA)

Long range dependence

The lectures will focus on the notion of long range dependence and its importance. We will discuss the different point of views on long range dependence (including second order theory, fractional models, connections with self-similarity and large deviations), and most important models possessing long memory.

Seva Shneer (EURANDOM)

Tail asymptotics for the busy period of an M/G/1 queue

We study the exact asymptotics for the tail distribution of the busy period of an M/G/1 queue. We focus on the case when the tails of the service times are “moderately heavy”. The results obtained may be generalised to find the exact asymptotics for the tail distribution of the first time a Levy process or a random walk crosses a fixed negative level. This is a joint work with Denis Denisov.

Werner Scheinhardt (TU Twente)

Shot noise fluid queues with a time-dependent arrival process.

We consider a shot noise model, in which a fluid reservoir receives quantities of fluid (with some general probability distribution) that arrive according to a Poisson process. Moreover, the reservoir is continuously drained at a rate that is proportional to the current content of the reservoir. We are interested in the time-dependent behavior of the content of the reservoir, where we also allow the arrival rate of the Poisson process to depend on time. We derive the Kolmogorov forward (partial differential) equation for the Laplace-Stieltjes transform of the content at time t, and solve it. Interestingly, the model may be seen as the limiting case of a certain sequence of infinite-server queues with batch arrivals. We show why this fact holds, and how it enables us to find the solution also from the (known) generating function of the number of jobs in the infinite-server queue.

Joint work with R.J. Boucherie and W.F. de Graaf.

Jian Tan (Columbia University, USA)

Characterizing Heavy-Tailed Distributions Induced by Retransmissions