fluid queue

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 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,{{Cite journal | last1 = Rogers | first1 = L. C. G. | author-link1 = Chris Rogers (mathematician)| last2 = Shi | first2 = Z. | title = Computing the Invariant Law of a Fluid Model | journal = Journal of Applied Probability | volume = 31 | issue = 4 | pages = 885–896 | doi = 10.2307/3215314 | year = 1994 | jstor = 3215314 }}

:

The operator is a continuous time Markov chain and is usually called the environment process, background process{{Cite journal | last1 = Scheinhardt | first1 = W. | last2 = Van Foreest | first2 = N. | last3 = Mandjes | first3 = M. | author-link3 = Michel Mandjes| doi = 10.1016/j.orl.2004.11.008 | title = Continuous feedback fluid queues | journal = Operations Research Letters | volume = 33 | issue = 6 | pages = 551 | year = 2005 | url = https://ir.cwi.nl/pub/10967 }} 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.

The stationary distribution is a phase-type distribution as first shown by Asmussen and can be computed using matrix-analytic methods.{{cite journal|title=Stochastic Theory of a Data-Handling System with Multiple Sources|first1=D.|last1=Anick|first2=D.|last2=Mitra|author-link2=Debasis Mitra|first3=M. M.|last3=Sondhi|journal=The Bell System Technical Journal|volume=61|year=1982|url=http://www3.alcatel-lucent.com/bstj/vol61-1982/articles/bstj61-8-1871.pdf|issue=8|pages=1871–1894|doi=10.1002/j.1538-7305.1982.tb03089.x|s2cid=16836549}}

The additive decomposition method is numerically stable and separates the eigenvalues necessary for computation using Schur decomposition.{{Cite journal | last1 = Akar | first1 = N. | last2 = Sohraby | first2 = K. | doi = 10.1239/jap/1082999086 | title = Infinite- and finite-buffer Markov fluid queues: A unified analysis | journal = Journal of Applied Probability | volume = 41 | issue = 2 | pages = 557 | year = 2004 | jstor = 3216036| url = http://www.ee.bilkent.edu.tr/~akar/papers/akar_sohraby_jap04.pdf| hdl = 11693/24279 | hdl-access = free }}{{Cite book | last1 = Telek | first1 = M. S. | last2 = Vécsei | first2 = M. S. | chapter = Analysis of Fluid Queues in Saturation with Additive Decomposition | doi = 10.1007/978-3-642-35980-4_19 | title = Modern Probabilistic Methods for Analysis of Telecommunication Networks | series = Communications in Computer and Information Science | volume = 356 | pages = 167 | year = 2013 | isbn = 978-3-642-35979-8 | chapter-url = http://webspn.hit.bme.hu/~telek/cikkek/tele13a.pdf}}

For a simple system where service has 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

:

the stationary distribution can be computed explicitly and is given by

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

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

and average fluid level

:$\backslash frac\{(\backslash lambda-\backslash mu)\backslash beta\}\{(\backslash mu(\backslash alpha+\backslash beta)-\backslash beta\backslash lambda)(\backslash alpha+\backslash beta)\}(\backslash mu,\backslash lambda-\backslash mu).$

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). In earlier literature it is sometimes referred to as the wet period (of the dam). The Laplace–Stieltjes transform of the busy period distribution is known for the fluid queue with infinite buffer{{Cite journal | last1 = Boxma | first1 = O. J. | author-link1=Onno J. Boxma| last2 = Dumas | first2 = V. | doi = 10.1145/277858.277881 | title = The busy period in the fluid queue | journal = ACM SIGMETRICS Performance Evaluation Review | volume = 26 | pages = 100–110 | year = 1998 }}{{Cite journal | last1 = Field | first1 = A. J. | last2 = Harrison | first2 = P. G. | author-link2 = Peter G. Harrison| doi = 10.1239/jap/1276784904 | title = Busy periods in fluid queues with multiple emptying input states | journal = Journal of Applied Probability | volume = 47 | issue = 2 | pages = 474 | year = 2010 | doi-access = free }}{{Cite journal | last1 = Asmussen | first1 = S. R. | title = Busy period analysis, rare events and transient behavior in fluid flow models | doi = 10.1155/S1048953394000262 | journal = Journal of Applied Mathematics and Stochastic Analysis | volume = 7 | issue = 3 | pages = 269–299 | year = 1994 | url = http://downloads.hindawi.com/journals/ijsa/1994/365297.pdf| doi-access = free }} and the expected busy period in the case of a finite buffer and arrivals as instantaneous jumps.{{Cite journal | last1 = Lee | first1 = Eui Yong| last2 = Kinateder | first2 = Kimberly K. J.| doi = 10.1016/S0304-4149(00)00034-X | title = The expected wet period of finite dam with exponential inputs | journal = Stochastic Processes and Their Applications | volume = 90 | pages = 175–180 | year = 2000 | url = https://corescholar.libraries.wright.edu/math/5| doi-access = free }}

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*(s) for the Laplace–Stieltjes transform of the busy period distribution, then

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

which gives the mean busy period

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

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.{{Cite journal | last1 = Gautam | first1 = N. | last2 = Kulkarni | first2 = V. G. | last3 = Palmowski | first3 = Z. | last4 = Rolski | first4 = T. | title = Bounds for Fluid Models Driven by Semi-Markov Inputs | doi = 10.1017/S026996489913403X | journal = Probability in the Engineering and Informational Sciences | volume = 13 | issue = 4 | pages = 429 | year = 1999 | url = http://www.unc.edu/~vkulkarn/papers/smpbnd.pdf}}

There are two main approaches to solving for the busy period in general, using either spectral decomposition or an iterative recurrent method.{{Cite journal | last1 = Badescu | first1 = Andrei L. | last2 =Landriault | first2 = David | year = 2009 | title = Applications of fluid flow matrix analytic methods in ruin theory —a review | journal = RACSAM - Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales. Serie A. Matematicas | volume = 103 | issue = 2 | pages = 353–372 | doi = 10.1007/BF03191912 | s2cid = 53498442 | url = http://www.rac.es/ficheros/doc/00702.pdf}}

A quadratically convergent algorithm for computing points of the transform was published by Ahn and Ramaswami.{{Cite journal | last1 = Ahn | first1 = S. | last2 = Ramaswami | first2 = V. | doi = 10.1239/jap/1118777186 | title = Efficient algorithms for transient analysis of stochastic fluid flow models | journal = Journal of Applied Probability | volume = 42 | issue = 2 | pages = 531 | year = 2005 | url = http://www.dm.unipi.it/~mam5/RAMASWAMI/fluid/Falgorithm.pdf| doi-access = free }}

For example, if a fluid queue with service rate μ = 2 is fed by an on/off source with parameters α = 2, β = 1 and λ =  3 then the fluid queue has busy period with mean 1 and variance 5/3.

In a finite buffer the rate at which fluid is lost (rejected from the system due to a full buffer) can be computed using Laplace-Stieltjes transforms.{{Cite journal | last1 = O'Reilly | first1 = M. G. M. | last2 = Palmowski | first2 = Z. | title = Loss rates for stochastic fluid models | doi = 10.1016/j.peva.2013.05.005 | journal = Performance Evaluation | volume = 70 | issue = 9 | pages = 593 | year = 2013 }}

The term mountain process has been coined to describe the maximum buffer content process value achieved during a busy period and can be computed using results from a G/M/1 queue.{{Cite journal | last1 = Boxma | first1 = O. J. | author-link1 = Onno Boxma| last2 = Perry | first2 = D. | last3 = Van Der Duyn Schouten | first3 = F. A. | title = Fluid Queues and Mountain Processes | doi = 10.1017/S0269964899134028 | journal = Probability in the Engineering and Informational Sciences | volume = 13 | issue = 4 | pages = 407–427 | year = 1999 | url = https://research.tue.nl/nl/publications/fluid-queues-and-mountain-processes(fc0a1918-05c7-437d-bfa3-5b818e4aa593).html }}{{Cite journal | last1 = Boxma | first1 = O. J. | author-link1 = Onno Boxma| last2 = Perry | first2 = D. | doi = 10.1080/03610910902936232 | title = On the Cycle Maximum of Mountains, Dams and Queues | journal = Communications in Statistics - Theory and Methods | volume = 38 | issue = 16–17 | pages = 2706 | year = 2009 | s2cid = 9973624 }}

The stationary distribution of two tandem fluid queues has been computed and shown not to exhibit a product form stationary distribution in nontrivial cases.{{Cite journal | last1 = Field | first1 = A. | last2 = Harrison | first2 = P. |author-link2=Peter G. Harrison| doi = 10.1016/j.peva.2007.06.025 | title = An approximate compositional approach to the analysis of fluid queue networks | journal = Performance Evaluation| volume = 64 | issue = 9–12 | pages = 1137 | year = 2007 | url = http://aesop.doc.ic.ac.uk/pubs/fluidsPERF07/| url-access = subscription }}{{Cite journal | last1 = Kroese | first1 = D. P. |author-link1=Dirk Kroese | last2 = Scheinhardt | first2 = W. R. W. | journal = Queueing Systems | title = Joint Distributions for Interacting Fluid Queues| volume = 37 | pages = 99–139 | year = 2001 | doi = 10.1023/A:1011044217695 | s2cid = 3482641 }}{{Cite journal | last1 = Kella | first1 = O. | doi = 10.1214/aoap/1034968070 | title = Stability and nonproduct form of stochastic fluid networks with Lévy inputs | journal = The Annals of Applied Probability | volume = 6 | pages = 186–199 | year = 1996 | doi-access = free }}{{Cite journal | last1 = Kella | first1 = O. | title = Non-product form of two-dimensional fluid networks with dependent Lévy inputs | doi = 10.1239/jap/1014843090 | journal = Journal of Applied Probability | volume = 37 | issue = 4 | pages = 1117–1122 | year = 2000 }}{{cite journal

| last1=Dębicki | first1=K.

| last2=Dieker | first2=A. B.

| last3=Rolski | first3=T.

| doi=10.1287/moor.1070.0259

| title=Quasi-Product Forms for Levy-Driven Fluid Networks

| journal=Mathematics of Operations Research

| volume=32

| issue=3

| pages=629

| date=2007

| arxiv=math/0512119

| s2cid=16150704}}

A feedback fluid queue is a model where the model parameters (transition rate matrix and drift vector) are allowed to some extent to depend on the buffer content. Typically the buffer content is partitioned and the parameters depend on which partition the buffer content process is in.{{Cite journal | last1 = Malhotra | first1 = R. | last2 = Mandjes | first2 = M. R. H. | last3 = Scheinhardt | first3 = W. R. W. | last4 = Berg | first4 = J. L. | title = A feedback fluid queue with two congestion control thresholds | doi = 10.1007/s00186-008-0235-8 | journal = Mathematical Methods of Operations Research | volume = 70 | pages = 149–169 | year = 2008 | url = http://doc.utwente.nl/80266/| doi-access = free }} The ordered Schur factorization can be used to efficiently compute the stationary distribution of such a model.{{Cite journal | last1 = Kankaya | first1 = H. E. | last2 = Akar | first2 = N. | doi = 10.1080/15326340802232285 | title = Solving Multi-Regime Feedback Fluid Queues | journal = Stochastic Models| volume = 24 | issue = 3 | pages = 425 | year = 2008 | hdl = 11693/23071 | s2cid = 53363967 | hdl-access = free }}

Second order fluid queues (sometimes called Markov modulated diffusion processes or fluid queues with Brownian noise{{Cite journal | last1 = Ivanovs | first1 = J. | title = Markov-modulated Brownian motion with two reflecting barriers | doi = 10.1239/jap/1294170517 | journal = Journal of Applied Probability | volume = 47 | issue = 4 | pages = 1034–1047 | year = 2010 | arxiv = 1003.4107| s2cid = 19329962 }}) consider a reflected Brownian motion with parameters controlled by a Markov process.{{Cite journal | last1 = Asmussen | first1 = Søren| doi = 10.1080/15326349508807330 | title = Stationary distributions for fluid flow models with or without brownian noise | journal = Communications in Statistics. Stochastic Models| volume = 11 | pages = 21–49 | year = 1995 }}{{Cite journal | last1 = Karandikar | first1 = R. L. | last2 = Kulkarni | first2 = V. G. | doi = 10.1287/opre.43.1.77 | title = Second-Order Fluid Flow Models: Reflected Brownian Motion in a Random Environment | journal = Operations Research| volume = 43 | pages = 77–88 | year = 1995 }} Two different types of boundary conditions are commonly considered: absorbing and reflecting.{{Cite journal | last1 = Gribaudo | first1 = M. | last2 = Manini | first2 = D. | last3 = Sericola | first3 = B. | last4 = Telek | first4 = M. | title = Second order fluid models with general boundary behaviour | doi = 10.1007/s10479-007-0297-7 | journal = Annals of Operations Research| volume = 160 | pages = 69–82 | year = 2007 | citeseerx = 10.1.1.484.6192 | s2cid = 1735120 }}

• [https://github.com/ghorvath78/butools BuTools], a MATLAB, Python and Mathematica implementation of some of the above results.
• [http://www.ee.bilkent.edu.tr/~pevatools/fq.htm PevaTools], MATLAB code for multi-regime models
• [https://www.youtube.com/watch?v=3vmU9R_rSVA Fluid flow models tutorial] by V. Ramaswami at MAM8

{{Reflist}}

{{Queueing theory}}

{{Stochastic processes}}

Category:Queueing theory