Chooser option: Difference between revisions
Jump to navigation
Jump to search
en>Lockley m resolve context tag |
en>Cydebot m Robot - Speedily moving category Options to Category:Options (finance) per CFDS. |
||
| Line 1: | Line 1: | ||
In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]], '''quasireversibility''' (sometimes '''QR''') is a property of some queues. The concept was first identified by [[Richard R. Muntz]]<ref>{{cite techreport|last=Muntz|first=R.R.|year=1972|title=Poisson departure process and queueing networks (IBM Research Report RC 4145)|url=http://domino.research.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/20b9b17a2db64886852574ef005775ce|institution=IBM Thomas J. Watson Research Center|location=Yorktown Heights, N.Y.|}}</ref> and further developed by [[Frank Kelly (professor)|Frank Kelly]].<ref>{{cite jstor|3212869}}</ref><ref>{{cite jstor|1425912}}</ref> Quasireversibility differs from reversibility in that a stronger condition is imposed on arrival rates and a weaker condition is applied on probability fluxes. For example, an M/M/1 queue with state-dependent arrival rates and state-dependent service times is reversible, but not quasireversible.<ref>{{cite book|authorlink1=Peter G. Harrison|first1=Peter G.|last1=Harrison|first2=Naresh M.|last2=Patel|title=Performance Modelling of Communication Networks and Computer Architectures|publisher=Addison-Wesley|year=1992|page=288|isbn=0-201-54419-9}}</ref> | |||
A network of queues, such that each individual queue when considered in isolation is quasireversible, always has a [[product form solution|product form]] stationary distribution.<ref>Kelly, F.P. (1982). [http://www.statslab.cam.ac.uk/~frank/PAPERS/nqrn.pdf Networks of quasireversible nodes]. In ''Applied Probability and Computer Science: The Interface'' (Ralph L. Disney and Teunis J. Ott, editors.) '''1''' 3-29. Birkhäuser, Boston</ref> Quasireversibility had been conjectured to be a necessary condition for a product form solution in a queueing network, but this was shown not to be the case. Chao et al. exhibited a product form network where quasireversibility was not satisfied.<ref>{{cite doi|10.1023/A:1019115626557}}</ref> | |||
==Definition== | |||
A queue with stationary distribution <math>\pi</math> is '''quasireversible''' if its state at time ''t'', '''''x'''(t)'' is independent of | |||
* the arrival times for each class of customer subsequent to time ''t'', | |||
* the departure times for each class of customer prior to time ''t'' | |||
for all classes of customer.<ref>Kelly, F.P., [http://www.statslab.cam.ac.uk/~frank/BOOKS/kelly_book.html Reversibility and Stochastic Networks], 1978 pages 66-67</ref> | |||
==Partial balance formulation== | |||
Quasireversibility is equivalent to a particular form of [[partial balance equations|partial balance]]. First, define the reversed rates ''q'('''x''','''x'''')'' by | |||
:<math>\pi(\mathbf x)q'(\mathbf x,\mathbf{x'}) = \pi(\mathbf{x'})q(\mathbf{x'},\mathbf x)</math> | |||
then considering just customers of a particular class, the arrival and departure processes are the same [[Poisson process]] (with parameter <math>\alpha</math>), so | |||
:<math>\alpha = \sum_{\mathbf{x'} \in M_{\mathbf x}} q(\mathbf x,\mathbf{x'}) = \sum_{\mathbf{x'} \in M_{\mathbf x}} q'(\mathbf x,\mathbf{x'})</math> | |||
where ''M<sub>x</sub>'' is a set such that <math>\scriptstyle{\mathbf{x'} \in M_{\mathbf x}}</math> means the state '''x'''' represents a single arrival of the particular class of customer to state '''x'''. | |||
==Examples== | |||
* [[Burke's theorem]] shows that an [[M/M/m]] queueing system is quasireversible.<ref>{{cite doi|10.1287/opre.4.6.699}}</ref><ref>{{cite doi|10.1214/aoms/1177698238}}</ref><ref>{{cite doi|10.1016/S0304-4149(01)00119-3}}</ref> | |||
* Kelly showed that each station of a [[BCMP network]] is quasireversible when viewed in isolation.<ref>{{cite book|last=Kelly|first=F.P.|authorlink=Frank Kelly (mathematician)|year=1979|url=http://www.statslab.cam.ac.uk/~frank/rsn.html|title=Reversibility and Stochastic Networks|publisher=Wiley|location=New York}}</ref> | |||
* G-queues in [[G-network]]s are quasireversible.<ref>{{cite doi|10.1007/11549970_6}}</ref> | |||
==See also== | |||
:*[[Time reversibility]] | |||
==References== | |||
{{Reflist}} | |||
{{Queueing theory}} | |||
[[Category:Queueing theory]] | |||
[[Category:Stochastic processes]] | |||
{{Probability-stub}} | |||
Latest revision as of 09:03, 9 November 2013
In queueing theory, a discipline within the mathematical theory of probability, quasireversibility (sometimes QR) is a property of some queues. The concept was first identified by Richard R. Muntz[1] and further developed by Frank Kelly.[2][3] Quasireversibility differs from reversibility in that a stronger condition is imposed on arrival rates and a weaker condition is applied on probability fluxes. For example, an M/M/1 queue with state-dependent arrival rates and state-dependent service times is reversible, but not quasireversible.[4]
A network of queues, such that each individual queue when considered in isolation is quasireversible, always has a product form stationary distribution.[5] Quasireversibility had been conjectured to be a necessary condition for a product form solution in a queueing network, but this was shown not to be the case. Chao et al. exhibited a product form network where quasireversibility was not satisfied.[6]
Definition
A queue with stationary distribution is quasireversible if its state at time t, x(t) is independent of
- the arrival times for each class of customer subsequent to time t,
- the departure times for each class of customer prior to time t
for all classes of customer.[7]
Partial balance formulation
Quasireversibility is equivalent to a particular form of partial balance. First, define the reversed rates q'(x,x') by
then considering just customers of a particular class, the arrival and departure processes are the same Poisson process (with parameter ), so
where Mx is a set such that means the state x' represents a single arrival of the particular class of customer to state x.
Examples
- Burke's theorem shows that an M/M/m queueing system is quasireversible.[8][9][10]
- Kelly showed that each station of a BCMP network is quasireversible when viewed in isolation.[11]
- G-queues in G-networks are quasireversible.[12]
See also
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
- ↑ Template:Cite techreport
- ↑ Template:Cite jstor
- ↑ Template:Cite jstor
- ↑ 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - ↑ Kelly, F.P. (1982). Networks of quasireversible nodes. In Applied Probability and Computer Science: The Interface (Ralph L. Disney and Teunis J. Ott, editors.) 1 3-29. Birkhäuser, Boston
- ↑ Template:Cite doi
- ↑ Kelly, F.P., Reversibility and Stochastic Networks, 1978 pages 66-67
- ↑ Template:Cite doi
- ↑ Template:Cite doi
- ↑ Template:Cite doi
- ↑ 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - ↑ Template:Cite doi