请输入您要查询的百科知识：

　

词条 Fluid queue
释义

  1. Model description

  2. Stationary distribution

     On/off model 

  3. Busy period

     Example  Loss rate  Mountain process 

  4. Networks of fluid queues

  5. Feedback fluid queues

  6. Second order fluid queues

  7. External links

  8. References

In queueing theory, a discipline within the mathematical theory of probability, a fluid queue (fluid model,[1] fluid flow model[2] or stochastic fluid model[3]) 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,[4] in ruin theory[5] and to model high speed data networks.[6] 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.[7][8][9] 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,[10] a router,[10] the IEEE 802.11 protocol,[11] Asynchronous Transfer Mode (the intended technology for B-ISDN),[12][13] peer-to-peer file sharing,[14] optical burst switching,[15] and has applications in civil engineering when designing dams.[16] The process is closely connected to quasi-birth–death processes, for which efficient solution methods are known.[17][18]

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 (input less output). When the buffer contains fluid, if we write X(t) for the fluid level at time t,[19]

The operator is a continuous time Markov chain and is usually called the environment process, background process[20] or driving process.[6] 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[2] as first shown by Asmussen[24] and can be computed using matrix-analytic methods.[21]

The additive decomposition method is numerically stable and separates the eigenvalues necessary for computation using Schur decomposition.[22][23]

On/off model

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[6]

and average fluid level[29]

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). In earlier literature it is sometimes referred to as the wet period (of the dam).[30] The Laplace–Stieltjes transform of the busy period distribution is known for the fluid queue with infinite buffer[24][25][26] and the expected busy period in the case of a finite buffer and arrivals as instantaneous jumps.[27]

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[26]

which gives the mean busy period[36]

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 busy periods which means that the longer a busy period has lasted the longer it is likely to last.[28]

There are two main approaches to solving for the busy period in general, using either spectral decomposition or an iterative recurrent method.[29]

A quadratically convergent algorithm for computing points of the transform was published by Ahn and Ramaswami.[30]

Example

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.

Loss rate

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.[31]

Mountain process

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.[32][33]

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.[34][35][36][37][38]

Feedback fluid queues

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.[39] The ordered Schur factorization can be used to efficiently compute the stationary distribution of such a model.[40]

Second order fluid queues

Second order fluid queues (sometimes called Markov modulated diffusion processes or fluid queues with Brownian noise[41]) consider a reflected Brownian motion with parameters controlled by a Markov process.[42][43] Two different types of boundary conditions are commonly considered: absorbing and reflecting.[44]

External links

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

References

1. ^{{Cite journal | last1 = Mitra | first1 = D. | authorlink1=Debasis Mitra| title = Stochastic Theory of a Fluid Model of Producers and Consumers Coupled by a Buffer | journal = Advances in Applied Probability | volume = 20 | issue = 3 | pages = 646–676 | doi = 10.2307/1427040 | year = 1988 | pmid = | pmc = | jstor = 1427040 }}
2. ^1 {{Cite journal | last1 = Ahn | first1 = S. | last2 = Ramaswami | first2 = V. | doi = 10.1081/STM-120023564 | title = Fluid Flow Models and Queues—A Connection by Stochastic Coupling | journal = Stochastic Models | volume = 19 | issue = 3 | pages = 325 | year = 2003 | url = http://www.dm.unipi.it/~mam5/RAMASWAMI/fluid/SteadyD.pdf| pmid = | pmc = }}
3. ^{{Cite journal | last1 = Elwalid | first1 = A. I. | last2 = Mitra | first2 = D. | authorlink2=Debasis Mitra| doi = 10.1007/BF01158791 | title = Analysis and design of rate-based congestion control of high speed networks, I: Stochastic fluid models, access regulation | journal = Queueing Systems| volume = 9 | issue = 1–2 | pages = 29–63 | year = 1991 | pmid = | pmc = }}
4. ^{{Cite journal | last1 = Stanford | first1 = David A. | last2 = Latouche | first2 = Guy| last3 = Woolford | first3 = Douglas G. | last4 = Boychuk | first4 = Dennis | last5 = Hunchak | first5 = Alek| title = Erlangized Fluid Queues with Application to Uncontrolled Fire Perimeter | doi = 10.1081/STM-200056242 | journal = Stochastic Models | volume = 21 | issue = 2–3 | pages = 631 | year = 2005 | pmid = | pmc = }}
5. ^{{Cite journal | last1 = Remiche | first1 = M. A. | title = Compliance of the Token-Bucket Model with Markovian Traffic | doi = 10.1081/STM-200057884 | journal = Stochastic Models | volume = 21 | issue = 2–3 | pages = 615–630 | year = 2005 | pmid = | pmc = }}
6. ^1 2 {{cite book|chapter=Fluid models for single buffer systems|last=Kulkarni|first=Vidyadhar G.|title=Frontiers in Queueing: Models and Applications in Science and Engineering|year=1997|pages=321–338|chapter-url=http://www.unc.edu/~vkulkarn/papers/fluid.pdf|isbn=978-0-8493-8076-1}}
7. ^{{cite journal|first=P. A. P.|last=Moran|authorlink=Pat Moran (statistician)|year=1954|title=A probability theory of dams and storage systems|journal=Aust. J. Appl. Sci.|volume=5|pages=116–124}}
8. ^{{Cite journal | last1 = Phatarfod | first1 = R. M. | title = Application of Methods in Sequential Analysis to Dam Theory | doi = 10.1214/aoms/1177703892 | journal = The Annals of Mathematical Statistics | volume = 34 | issue = 4 | pages = 1588–1592 | year = 1963 | pmid = | pmc = }}
9. ^{{Cite journal | last1 = Gani | first1 = J. | last2 = Prabhu | first2 = N. U. | authorlink2 = N. U. Prabhu| doi = 10.1038/182039a0 | title = Continuous Time Treatment of a Storage Problem | journal = Nature| volume = 182 | issue = 4627 | pages = 39 | year = 1958 | pmid = | pmc = | bibcode = 1958Natur.182...39G}}
10. ^{{Cite book | last1 = Hohn | first1 = N. | last2 = Veitch | first2 = D. | last3 = Papagiannaki | first3 = K. | last4 = Diot | first4 = C. | chapter = Bridging router performance and queuing theory | doi = 10.1145/1005686.1005728 | title = Proceedings of the joint international conference on Measurement and modeling of computer systems - SIGMETRICS 2004/PERFORMANCE 2004 | pages = 355 | year = 2004 | isbn = 978-1581138733 | pmid = | pmc = | citeseerx = 10.1.1.1.3208 }}
11. ^{{Cite journal | last1 = Arunachalam | first1 = V. | last2 = Gupta | first2 = V. | last3 = Dharmaraja | first3 = S. | doi = 10.1016/j.camwa.2010.08.039 | title = A fluid queue modulated by two independent birth–death processes | journal = Computers & Mathematics with Applications | volume = 60 | issue = 8 | pages = 2433–2444| year = 2010 | pmid = | pmc = }}
12. ^{{Cite journal | last1 = Norros | first1 = I. | last2 = Roberts | first2 = J. W. | last3 = Simonian | first3 = A. | last4 = Virtamo | first4 = J. T. | title = The superposition of variable bit rate sources in an ATM multiplexer | doi = 10.1109/49.76636 | journal = IEEE Journal on Selected Areas in Communications | volume = 9 | issue = 3 | pages = 378 | year = 1991 | pmid = | pmc = }}
13. ^{{Cite journal | last1 = Rasmussen | first1 = C. | last2 = Sorensen | first2 = J. H. | last3 = Kvols | first3 = K. S. | last4 = Jacobsen | first4 = S. B. | title = Source-independent call acceptance procedures in ATM networks | doi = 10.1109/49.76633 | journal = IEEE Journal on Selected Areas in Communications| volume = 9 | issue = 3 | pages = 351 | year = 1991 | pmid = | pmc = }}
14. ^{{Cite journal | last1 = Gaeta | first1 = R. | last2 = Gribaudo | first2 = M. | last3 = Manini | first3 = D. | last4 = Sereno | first4 = M. | title = Analysis of resource transfers in peer-to-peer file sharing applications using fluid models | doi = 10.1016/j.peva.2005.01.001 | journal = Performance Evaluation| volume = 63 | issue = 3 | pages = 149 | year = 2006 | pmid = | pmc = | citeseerx = 10.1.1.102.3905 }}
15. ^{{Cite book | last1 = Yazici | first1 = M. A. | last2 = Akar | first2 = N. | doi = 10.1109/ITC.2013.6662952 | chapter = Analysis of continuous feedback Markov fluid queues and its applications to modeling Optical Burst Switching | title = Proceedings of the 2013 25th International Teletraffic Congress (ITC) | pages = 1–8| year = 2013 | isbn = 978-0-9836283-7-8 | pmid = | pmc = | title-link = International Teletraffic Congress }}
16. ^{{Cite journal | last1 = Gani | first1 = J. | title = Recent Advances in Storage and Flooding Theory | journal = Advances in Applied Probability | volume = 1 | issue = 1 | pages = 90–110 | doi = 10.2307/1426410 | jstor = 1426410| year = 1969 | pmid = | pmc = }}
17. ^{{cite journal | last =Ramaswami | first = V.| title= Matrix analytic methods for stochastic fluid flows | journal = Teletraffic Engineering in a Competitive World (Proceedings of the 16th International Teletraffic Congress) | editor-last1 =Smith |editor-first1=D. |editor-last2= Hey | editor-first2= P | publisher = Elsevier Science B.V.}}
18. ^{{Cite journal | last1 = Govorun | first1 = M. | last2 = Latouche | first2 = G. | last3 = Remiche | first3 = M. A. | title = Stability for Fluid Queues: Characteristic Inequalities | doi = 10.1080/15326349.2013.750533 | journal = Stochastic Models| volume = 29 | pages = 64–88 | year = 2013 | pmid = | pmc = }}
19. ^{{Cite journal | last1 = Rogers | first1 = L. C. G. | authorlink1 = 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 | pmid = | pmc = | jstor = 3215314 }}
20. ^{{Cite journal | last1 = Scheinhardt | first1 = W. | last2 = Van Foreest | first2 = N. | last3 = Mandjes | first3 = M. | authorlink3 = 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 | pmid = | pmc = }}
21. ^1 {{cite journal|title=Stochastic Theory of a Data-Handling System with Multiple Sources|first=D.|last=Anick|first2=D.|last2=Mitra|authorlink2=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}}
22. ^{{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| pmid = | pmc = }}
23. ^{{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| pmid = | pmc = }}
24. ^{{Cite journal | last1 = Boxma | first1 = O. J. | authorlink1=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 | pmid = | pmc = }}
25. ^{{Cite journal | last1 = Field | first1 = A. J. | last2 = Harrison | first2 = P. G. | authorlink2 = 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 | pmid = | pmc = }}
26. ^1 {{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| pmid = | pmc = }}
27. ^1 {{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 | pmid = | pmc = }}
28. ^{{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 | pmid = | url = http://www.unc.edu/~vkulkarn/papers/smpbnd.pdf| pmc = }}
29. ^{{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 | url = http://www.rac.es/ficheros/doc/00702.pdf}}
30. ^{{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| pmid = | pmc = }}
31. ^{{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 | pmid = | pmc = }}
32. ^{{Cite journal | last1 = Boxma | first1 = O. J. | authorlink1 = 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 | year = 1999 | pmid = | pmc = }}
33. ^{{Cite journal | last1 = Boxma | first1 = O. J. | authorlink1 = 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 | pmid = | pmc = }}
34. ^1 {{Cite journal | last1 = Field | first1 = A. | last2 = Harrison | first2 = P. |authorlink2=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 | pmid = | pmc = | url = http://aesop.doc.ic.ac.uk/pubs/fluidsPERF07/}}
35. ^1 {{Cite journal | last1 = Kroese | first1 = D. P. | 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 | pmid = | pmc = }}
36. ^{{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 | pmid = | pmc = }}
37. ^{{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 | pmid = | pmc = }}
38. ^{{Cite journal | last1 = Debicki | 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 | year = 2007 | pmid = | pmc = | arxiv = math/0512119}}
39. ^{{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 | pmid = | pmc = | url = http://doc.utwente.nl/80266/}}
40. ^{{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 | pmid = | pmc = }}
41. ^{{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 | pmid = | pmc = | arxiv = 1003.4107}}
42. ^1 {{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 | pmid = | pmc = }}
43. ^{{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 | pmid = | pmc = }}
44. ^{{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 | pmid = | pmc = | citeseerx = 10.1.1.484.6192 }}
{{Queueing theory}}{{Stochastic processes}}

1 : Queueing theory
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/11/10 23:23:44