Announcement of a workshop on

QUEUES, FLUID QUEUES AND EXTREMES

EURANDOM, Eindhoven, The Netherlands,
March 13 -14, 2006

ABSTRACTS

I. Adan (Eindhoven University of Technology, Netherlands)

Analysis of a Simple Markovian Re-Entrant Line with Infinite Supply of Work under the LBFS Policy

We consider a two machine 3 step re-entrant line, with an infinite supply of work. The service discipline is last buffer first served. Processing times are independent exponentially distributed. We analyze this system, obtaining steady state behavior and sample path properties.

S. Borst (CWI, Netherlands)
Joint work with Nidhi Hegde and Alexandre Proutiere

Wireless data network with intra- and inter-cell mobility

The performance of wireless data systems has been thoroughly studied in the context of a single base station. In this talk we examine networks with several interacting base stations, and specifically investigate the capacity impact of intra- and inter-cell mobility. We consider a dynamic setting where users come and go over time as governed by random finite-size data transfers, and explicitly allow for users to roam around over the course of their service. It may be shown that mobility tends to increase the capacity, not only in case of globally optimal scheduling, but also when each of the base stations operates according to a fair sharing policy. We further demonstrate that the capacity region for globally optimal scheduling is in general strictly larger than the stability region for a fair sharing discipline. However, if the users distribute themselves so as to maximize their individual throughputs, thus enabling some implicit coordination, then a fair sharing policy is in fact guaranteed to achieve stability whenever a globally optimal strategy is able to do so.

B. D'Auria (EURANDOM, Netherlands)

Small scale analysis of data traffic models

We review two infinite source Poisson input models for data traffic that are able to catch the main characteristics of the real traffic traces, i.e. burstiness, long range dependence and heavy tails. Main ingredients for the models are the hypotheses of randomness for the file sizes, the rates of transmissions and the transmission durations that
are all supposed to be heavy-tailed. For both models we look at the small scale behaviour and we show that one of them converges marginally to a normal random variable while the second one preserves in the limit the heaviness of the tails.

presentation

T. Dieker (CWI, Netherlands)

Fluid systems with Markov-additive input, an approach based on extremes

In view of the results on quasi-product forms for Levy-driven fluid systems from the talk of Tomasz Rolski, it is natural to look for analogues in the presence of a 'modulating' (Markovian) background process. In my talk, I'll discuss how the Laplace transform of the steady-state buffer-content vector can be found for a special tandem fluid system; I'll show that a matrix quasi-product form appears. It turns out that the main difficulty is not that we are interested in a fluid network, but that a deeper understanding of the single fluid queue is required. Exploiting the connection with extremes, we need to study the maximum of a continuous-time Markov-additive process with one-sided jumps, jointly with the epoch at which the maximum is `attained'. This is the aim of the talk. The results offer interesting insights into the connections between the approaches developed so far, including matrix-analytic techniques, martingale methods, the rate-conservation approach, and the occupation-measure method.

R. Egorova (CWI, Netherlands)

Tail behavior of conditional sojourn times in processor-sharing queues

The tail asymptote for the sojourn time distribution in the M/M/1 PS queue is known to be of complicated form, seems difficult to extend to more general PS queues, and is not precise enough to serve as approximation. Motivated by this, we investigate the asymptotic behavior of the sojourn time distribution for a request of given length in the M/G/1 PS queue. In particular, we prove that the sojourn time asymptotics are of purely exponential type for a queue with general service time distribution in two special cases: (i) when the traffic load is sufficiently high and (ii) when the size of the request of the tagged customer is sufficiently small. We next turn our attention to the M/M/1 PS queue. Using the branching process technique we derive exponential asymptotics for all values of the load and the job size. We obtain an equation for the asymptotic decay rate and an explicit (though complicated) expression for the asymptotic constant. We show that the exponential asymptote is an accurate approximation of the conditional sojourn time distribution for moderate values of x. Finally, we analyze the behavior of the decay rate depending on the request length and compare it with decay rates for an M/M/1 system with different service discipline such as FCFS, LCFS and SRPT.

presentation

V. Kulkarni (Univeristy of North Carolina, USA)

Fluid Models with Jumps: Applications to Production and Inventory Systems

We consider a single buffer fluid system where the instantaneous input and output rates from the buffer are determined by the current state of a finite state stochastic process called the environment. When the fluid level hits zero, it instantaneously jumps to a positive level, which depends on the state of the environment at the time the buffer reaches zero. At the point of the jump, the state of the environment also undergoes an instantaneous transition. Between two consecutive jumps the environment process is a continuous time Markov chain. We develop methods of computing the limiting distribution of the bivariate process (buffer level, environment state).

We then proceed to apply this theory to a single stage production system by viewing the fluid level as the inventory level and the upward jumps as the external orders. We show that when there are no lead times, the holding and stock out costs are linear, and there is a positive ordering cost, the well known deterministic Economic Order Quantity formula continues to hold with an intuitive modification. We extend the results when the lead times are non-negative random variables.

presentation

J. van Leeuwaarden (EURANDOM, Netherlands)
Joint work with A.J.E.M. Janssen.

Moments of the maximum of the Gaussian random walk

We consider the Gaussian random walk (one-dimensional random walk with normally distributed increments) with negative drift, and in particular the moments of its maximum M.

We derive explicit expressions for all moments of M in terms of Taylor series about "drift=0" with coefficients that involve the Riemann zeta function. We build upon the work of Chang and Peres (1997) on P(M=0) and Bateman's formulas on Lerch's transcendent. Our result for E(M) extends Kingman's (1965) first order approximation for a drift close to zero.

The key idea in obtaining the Taylor series for the k-th moment is to differentiate its Spitzer-type expression (involving the Gaussian distribution) k+1 times, rewrite the resulting expression in terms of Lerch's transcendent, and integrate k+1 times. The major issue then is to determine the k+1 integration constants, for which we invoke Euler-Maclaurin summation, among other things.

We further present sharp bounds on P(M=0) and the first two moments of M. The bounds on P(M=0) complement Siegmund's diffusion correction for the Gaussian family. We also show how our results might find important applications, particularly for queues in heavy traffic and for the equidistant sampling of Brownian motion. Indeed, M shows up in a range of applications, such as sequentially testing for the drift of a Brownian motion, corrected diffusion approximations, simulation of Brownian motion, option pricing, thermodynamics of a polymer chain, and quality & efficiency driven regimes for large-scale service systems (e.g. call centers).

presentation

M. Mandjes (CWI / University of Amsterdam, Netherlands)
Joint work with Hans van den Berg and Frank Roijers.

Fluid models for ad hoc networks

In this talk I consider a fluid queue with coupled input and output. Flows arrive according to a Poisson process, and when $n$ flows are present, each of them transmits traffic into the queue at a rate $\CC/(n+1)$, where the remaining $\CC/(n+1)$ is used to serve the queue. We assume exponentially distributed flow sizes, so that the queue under consideration can be regarded as a system with Markov fluid input. The rationale behind studying this queue lies in ad hoc networks: bottleneck links have roughly this type of sharing policy.

We consider four performance metrics: (i)~the stationary workload of the queue, (ii)~the queueing delay, i.e., the delay of a `packet' (a fluid particle) that arrives at the queue at an arbitrary point in time, (iii)~the flow transfer delay, i.e., the time elapsed between arrival of a flow and the epoch that all its traffic has been put into the queue, and (iv)~the sojourn time, i.e., the flow transfer time increased by the time it takes before the last fluid particle of the flow is served. For each of these random variables we compute the Laplace transform. The corresponding tail probabilities decay exponentially, as is shown by a large-deviations analysis.

presentation

I. Norros (University of Helsinki, Finland)
Joint work with M. Mandjes, P. Mannersalo, M. van Uitert

Queueing theory meets optimization and control: subtleties of the minimum norm problem encountered by Gaussian queues

Made / updated on 24-02-2009
Maintained by Lucienne Coolen.