Fluid queue

In probability theory, 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 and model high speed data networks.^[1]

The model was first introduced by Pat Moran in 1954.^[2][3][4] Fluid queues allow arrivals to be continuous rather than discrete, as in models like the M/M/1 and M/G/1 queues.

Model description

A fluid queue can be viewed as a large tank of capacity B 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 r_i for the net fluid arrival rate in this state (input less output). When the buffer contains fluid, if we write X(t) for the fluid level at time t,^[5]

$\frac{\mathrm{d}X(t)}{\mathrm{d}t} = \begin{cases} r_i & \text{ if } X(t)>0 \\ \max(r_i,0) & \text{ if } X(t)=0.\end{cases}$

The operator is a continuous time Markov chain and is usually called the environment process, background process^[6] or driving process.^[1] As the process X represents the level of fluid in the buffer it can only take non-negative values.

Applications

Fluid queues have been used to model router performance^[7] and has applications in civil engineering when designing dams.^[8]

Stationary distribution

The stationary distribution can be computed using matrix-analytic methods.^[9] For a simple system where service a constant rate μ and arrival fluctuate between rates λ and 0 (in states 1 and 2 respectively) according to a continuous time Markov chain with generator matrix

$Q = \begin{pmatrix}-\alpha & \alpha \\ \beta & -\beta \end{pmatrix}$

the stationary distribution is given as^[1]

$F(x,1) = \frac{\beta}{\alpha+\beta}\left(1-e^{\left(\frac{\beta}{\mu}-\frac{\alpha}{\lambda-\mu}\right) x}\right)$

$F(x,2) = \frac{\alpha}{\alpha+\beta}-\frac{\beta\left(\lambda-\mu\right)}{\alpha+\beta}e^{\left(\frac{\beta}{\mu}-\frac{\alpha}{\lambda-\mu}\right) x}.$

Busy period

The busy period is the period of time measured from the instant that fluid first arrives in the buffer (X(t) becomes non-zero) until the buffer is again empty (X(t) returns to zero). The Laplace–Stieltjes transform of the busy period distribution is known for the fluid queue with infinite buffer^[10][11][12] and the expected busy period in the case of a finite buffer.^[13]

For an infinite buffer with constant service rate μ and arrivals at rates λ and 0, modulated by a continuous time Markov chain with parameters

$Q=\begin{pmatrix}-\alpha & \alpha \\ \beta &-\beta \end{pmatrix}$

write W*(s) for the Laplace–Stieltjes transform of the busy period distribution, then^[12]

$W^\ast(s) = \frac{\beta \lambda + s \lambda - \beta \mu + \alpha \mu - \sqrt{4\beta \alpha \mu(\mu-\lambda) + (s \lambda + \beta(\lambda-\mu)+\alpha \mu)^2}}{2 \beta (\lambda - \mu)}$

which gives the mean busy period

$\mathbb E(W) = \frac{\lambda}{\alpha \mu + \beta \mu - \beta \lambda}.$

Networks of fluid queues

The stationary distribution of two tandem fluid queues has been computed and shown not to exhibit a product form stationary distribution in nontrivial cases.^{[14][15][16][17]}

References

1. ^ ^{a b c} Kulkarni, Vidyadhar G. (1997). "Fluid models for single buffer systems". Frontiers in Queueing: Models and Applications in Science and Engineering. pp. 321–338. ISBN 0849380766. http://www.unc.edu/~vkulkarn/papers/fluid.pdf. 
2. ^ Moran, P. A. P. (1954). "A probability theory of dams and storage systems". Aust. J. Appl. Sci. 5: 116–124. 
3. ^ Phatarfod, R. M. (1963). "Application of Methods in Sequential Analysis to Dam Theory". The Annals of Mathematical Statistics 34 (4): 1588. doi:10.1214/aoms/1177703892.  edit
4. ^ Gani, J.; Prabhu, N. U. (1958). "Continuous Time Treatment of a Storage Problem". Nature 182 (4627): 39. doi:10.1038/182039a0.  edit
5. ^ Rogers, L. C. G.; Shi, Z. (1994). "Computing the Invariant Law of a Fluid Model". Journal of Applied Probability 31 (4): 885–896. doi:10.2307/3215314.  edit
6. ^ Scheinhardt, W.; Van Foreest, N.; Mandjes, M. (2005). "Continuous feedback fluid queues". Operations Research Letters 33 (6): 551. doi:10.1016/j.orl.2004.11.008.  edit
7. ^ Hohn, N.; Veitch, D.; Papagiannaki, K.; Diot, C. (2004). "Bridging router performance and queuing theory". Proceedings of the joint international conference on Measurement and modeling of computer systems - SIGMETRICS 2004/PERFORMANCE 2004. pp. 355. doi:10.1145/1005686.1005728. ISBN 1581138733.  edit
8. ^ Gani, J. (1969). "Recent Advances in Storage and Flooding Theory". Advances in Applied Probability 1 (1): 90–110. doi:10.2307/1426410. JSTOR 1426410.  edit
9. ^ Anick, D.; Mitra, D.; Sondhi, M. M. (1982). "Stochastic Theory of a Data-Handling System with Multiple Sources". The Bell System Technical Journal 61 (8). http://www.alcatel-lucent.com/bstj/vol61-1982/articles/bstj61-8-1871.pdf. 
10. ^ Boxma, O. J.; Dumas, V. (1998). "The busy period in the fluid queue". ACM SIGMETRICS Performance Evaluation Review 26: 100. doi:10.1145/277858.277881.  edit
11. ^ Field, A. J.; Harrison, P. G. (2010). "Busy periods in fluid queues with multiple emptying input states". Journal of Applied Probability 47 (2): 474. doi:10.1239/jap/1276784904.  edit
12. ^ ^{a b} Asmussen, S. R. (1994). "Busy period analysis, rare events and transient behavior in fluid flow models". Journal of Applied Mathematics and Stochastic Analysis 7 (3): 269–299. doi:10.1155/S1048953394000262.  edit
13. ^ Lee, E. (2000). "The expected wet period of finite dam with exponential inputs". Stochastic Processes and their Applications 90: 175–180. doi:10.1016/S0304-4149(00)00034-X.  edit
14. ^ Field, A.; Harrison, P. (2007). "An approximate compositional approach to the analysis of fluid queue networks". Performance Evaluation 64 (9–12): 1137. doi:10.1016/j.peva.2007.06.025.  edit
15. ^ Kroese, D. P.; Scheinhardt, W. R. W. (2001). Queueing Systems 37: 99. doi:10.1023/A:1011044217695.  edit
16. ^ Kella, O. (1996). "Stability and nonproduct form of stochastic fluid networks with Lévy inputs". The Annals of Applied Probability 6: 186. doi:10.1214/aoap/1034968070.  edit
17. ^ Kella, O. (2000). "Non-product form of two-dimensional fluid networks with dependent Lévy inputs". Journal of Applied Probability 37 (4): 1117. doi:10.1239/jap/1014843090.  edit