Importance sampling for non-Markovian tandem queues using subsolutions

Queueing Systems - In this paper, we use importance sampling simulation to estimate the probability that the number of customers in a d-node GI|GI|1 tandem queue reaches some high level N in a busy...     

A feedback fluid queue with two congestion control thresholds

Feedback fluid queues play an important role in modeling congestion control mechanisms for packet networks. In this paper we present and analyze a fluid queue with a feedback-based traffic rate adaptation scheme which uses two thresholds. The higher threshold B ₁ is used to signal the beginning of congestion while the lower threshold B ₂ signals the end of congestion. These two parameters together allow to make the trade-off between maximizing throughput performance and minimizing delay. The difference between the two thresholds helps to control the amount of feedback signals sent to the traffic source. In our model the input source can behave like either of two Markov fluid processes. The first applies as long as the upper threshold B ₁ has not been hit from below. As soon as that happens, the traffic source adapts and switches to the second process, until B ₂ (smaller than B ₁) is hit from above. We analyze the model by setting up the Kolmogorov forward equations, then solving the corresponding balance equations using a spectral expansion, and finally identifying sufficient constraints to solve for the unknowns in the solution. In particular, our analysis yields expressions for the stationary distribution of the buffer occupancy, the buffer delay distribution, and the throughput.     

Alternative proof and interpretations for a recent state-dependent importance sampling scheme

Recently, a state-dependent change of measure for simulating overflows in the two-node tandem queue was proposed by Dupuis et al. (Ann. Appl. Probab. 17(4):1306–1346, 2007), together with a proof of its asymptotic optimality. In the present paper, we present an alternative, shorter and simpler proof. As a side result, we obtain interpretations for several of the quantities involved in the change of measure in terms of likelihood ratios. Part of this research has been funded by the Dutch BSIK/BRICKS project; part of this research was done while the first author was visiting INRIA/IRISA, Rennes, France.     

On a generic class of two-node queueing systems

This paper analyzes a generic class of two-node queueing systems. A first queue is fed by an on–off Markov fluid source; the input of a second queue is a function of the state of the Markov fluid source as well, but now also of the first queue being empty or not. This model covers the classical two-node tandem queue and the two-class priority queue as special cases. Relying predominantly on probabilistic argumentation, the steady-state buffer content of both queues is determined (in terms of its Laplace transform). Interpreting the buffer content of the second queue in terms of busy periods of the first queue, the (exact) tail asymptotics of the distribution of the second queue are found. Two regimes can be distinguished: a first in which the state of the first queue (that is, being empty or not) hardly plays a role, and a second in which it explicitly does. This dichotomy can be understood by using large-deviations heuristics. This work has been carried out partly in the Dutch BSIK/BRICKS project.     

Analysis of a single-server queue interacting with a fluid reservoir

We consider a single-server queueing system with Poisson arrivals in which the speed of the server depends on whether an associated fluid reservoir is empty or not. Conversely, the rate of change of the content of the reservoir is determined by the state of the queueing system, since the reservoir fills during idle periods and depletes during busy periods of the server. Our interest focuses on the stationary joint distribution of the number of customers in the system and the content of the fluid reservoir, from which various performance measures such as the steady-state sojourn time distribution of a customer may be obtained. We study two variants of the system. For the first, in which the fluid reservoir is infinitely large, we present an exact analysis. The variant in which the fluid reservoir is finite is analysed approximatively through a discretization technique. The system may serve as a mathematical model for a traffic regulation mechanism - a two-level traffic shaper - at the edge of an ATM network, regulating a very bursty source. We present some numerical results showing the effect of the mechanism. This revised version was published online in June 2006 with corrections to the Cover Date.     

Joint Distributions for Interacting Fluid Queues

Motivated by recent traffic control models in ATM systems, we analyse three closely related systems of fluid queues, each consisting of two consecutive reservoirs, in which the first reservoir is fed by a two-state (on and off) Markov source. The first system is an ordinary two-node fluid tandem queue. Hence the output of the first reservoir forms the input to the second one. The second system is dual to the first one, in the sense that the second reservoir accumulates fluid when the first reservoir is empty, and releases fluid otherwise. In these models both reservoirs have infinite capacities. The third model is similar to the second one, however the second reservoir is now finite. Furthermore, a feedback mechanism is active, such that the rates at which the first reservoir fills or depletes depend on the state (empty or nonempty) of the second reservoir.The models are analysed by means of Markov processes and regenerative processes in combination with truncation, level crossing and other techniques. The extensive calculations were facilitated by the use of computer algebra. This approach leads to closed-form solutions to the steady-state joint distribution of the content of the two reservoirs in each of the models.     

Continuous feedback fluid queues

We investigate a fluid queue with feedback from the (finite) buffer to the background process. The latter behaves as a continuous-time Markov chain, but the generator (and traffic rates) depend continuously on the current buffer level. We derive the Kolmogorov equations, and, for two-state background processes, the explicit stationary distribution.