Fluid queue
In queueing theory, a discipline within the mathematical theory of probability, a fluid queue is a mathematical model used to describe the fluid level in a reservoir subject to randomly determined periods of filling and emptying. The term dam theory was used in earlier literature for these models. The model has been used to approximate discrete models, model the spread of wildfires, in ruin theory and to model high speed data networks. The model applies the leaky bucket algorithm to a stochastic source.
The model was first introduced by Pat Moran in 1954 where a discrete-time model was considered. Fluid queues allow arrivals to be continuous rather than discrete, as in models like the M/M/1 and M/G/1 queues.
Fluid queues have been used to model the performance of a network switch, a router, the IEEE 802.11 protocol, Asynchronous Transfer Mode, peer-to-peer file sharing, optical burst switching, and has applications in civil engineering when designing dams. The process is closely connected to quasi-birth–death processes, for which efficient solution methods are known.
Model description
A fluid queue can be viewed as a large tank, typically assumed to be of infinite capacity, connected to a series of pipes that pour fluid in to the tank and a series of pumps which remove fluid from the tank. An operator controls the pipes and pumps controlling the rate at which fluid pours in to the buffer and the rate at which fluid leaves. When the operator puts the system in to state i we write ri for the net fluid arrival rate in this state. When the buffer contains fluid, if we write X for the fluid level at time t,The operator is a continuous time Markov chain and is usually called the environment process, background process or driving process. As the process X represents the level of fluid in the buffer it can only take non-negative values.
The model is a particular type of piecewise deterministic Markov process and can also be viewed as a Markov reward model with boundary conditions.
Stationary distribution
The stationary distribution is a phase-type distribution as first shown by Asmussen and can be computed using matrix-analytic methods.The additive decomposition method is numerically stable and separates the eigenvalues necessary for computation using Schur decomposition.
On/off model
For a simple system where service has a constant rate μ and arrival fluctuate between rates λ and 0 according to a continuous time Markov chain with generator matrixthe stationary distribution can be computed explicitly and is given by
and average fluid level
Busy period
The busy period is the period of time measured from the instant that fluid first arrives in the buffer until the buffer is again empty. In earlier literature it is sometimes referred to as the wet period. The Laplace–Stieltjes transform of the busy period distribution is known for the fluid queue with infinite buffer and the expected busy period in the case of a finite buffer and arrivals as instantaneous jumps.For an infinite buffer with constant service rate μ and arrivals at rates λ and 0, modulated by a continuous time Markov chain with parameters
write W* for the Laplace–Stieltjes transform of the busy period distribution, then
which gives the mean busy period
In this case, of a single on/off source, the busy period distribution is known to be a decreasing failure rate function which means that the longer a busy period has lasted the longer it is likely to last.
There are two main approaches to solving for the busy period in general, using either spectral decomposition or an iterative recurrent method.
A quadratically convergent algorithm for computing points of the transform was published by Ahn and Ramaswami.