Quasireversibility

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{{cite tech report|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.}} and further developed by Frank Kelly.{{Cite journal | last1 = Kelly | first1 = F. P. | author-link1 = Frank Kelly (mathematician)| title = Networks of Queues with Customers of Different Types | journal = Journal of Applied Probability | volume = 12 | issue = 3 | pages = 542–554 | doi = 10.2307/3212869 | jstor = 3212869| year = 1975 | s2cid = 51917794 }}{{Cite journal | last1 = Kelly | first1 = F. P. | author-link1 = Frank Kelly (mathematician)| title = Networks of Queues | journal = Advances in Applied Probability | volume = 8 | issue = 2 | pages = 416–432 | doi = 10.2307/1425912 | jstor = 1425912| year = 1976 | s2cid = 204177645 }} 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.{{cite book|author-link1=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=[https://archive.org/details/performancemodel0000harr/page/288 288]|isbn=0-201-54419-9|url-access=registration|url=https://archive.org/details/performancemodel0000harr/page/288}}

A network of queues, such that each individual queue when considered in isolation is quasireversible, always has a product form stationary distribution.Kelly, F.P. (1982). [http://www.statslab.cam.ac.uk/~frank/PAPERS/nqrn.pdf Networks of quasireversible nodes] {{Webarchive|url=https://web.archive.org/web/20070221074029/http://www.statslab.cam.ac.uk/~frank/PAPERS/nqrn.pdf |date=2007-02-21 }}. In Applied Probability and Computer Science: The Interface (Ralph L. Disney and Teunis J. Ott, editors.) 1 3-29. Birkhäuser, Boston 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.{{Cite journal | last1 = Chao | first1 = X. | last2 = Miyazawa | first2 = M. | last3 = Serfozo | first3 = R. F. | last4 = Takada | first4 = H. | journal = Queueing Systems | volume = 28 | issue = 4 | pages = 377 | doi = 10.1023/A:1019115626557 | year = 1998 |title=Markov network processes with product form stationary distributions| s2cid = 14471818 }}

Definition

A queue with stationary distribution \pi 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.Kelly, F.P., [http://www.statslab.cam.ac.uk/~frank/BOOKS/kelly_book.html Reversibility and Stochastic Networks] {{Webarchive|url=https://web.archive.org/web/20230119031733/http://www.statslab.cam.ac.uk/~frank/BOOKS/kelly_book.html |date=2023-01-19 }}, 1978 pages 66-67

Partial balance formulation

Quasireversibility is equivalent to a particular form of partial balance. First, define the reversed rates q'(x,x') by

:\pi(\mathbf x)q'(\mathbf x,\mathbf{x'}) = \pi(\mathbf{x'})q(\mathbf{x'},\mathbf x)

then considering just customers of a particular class, the arrival and departure processes are the same Poisson process (with parameter \alpha), so

:\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'})

where Mx is a set such that \scriptstyle{\mathbf{x'} \in M_{\mathbf x}} 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.{{Cite journal | last1 = Burke | first1 = P. J. | title = The Output of a Queuing System | doi = 10.1287/opre.4.6.699 | journal = Operations Research | volume = 4 | issue = 6 | pages = 699–704 | year = 1956 | s2cid = 55089958 }}{{Cite journal | last1 = Burke | first1 = P. J. | title = The Output Process of a Stationary M/M/s Queueing System | doi = 10.1214/aoms/1177698238 | journal = The Annals of Mathematical Statistics | volume = 39 | issue = 4 | pages = 1144–1152 | year = 1968 | doi-access = free }}{{Cite journal | last1 = O'Connell | first1 = N. | last2 = Yor | first2 = M. | title = Brownian analogues of Burke's theorem | doi = 10.1016/S0304-4149(01)00119-3 | journal = Stochastic Processes and Their Applications | volume = 96 | issue = 2 | pages = 285–298 | date=December 2001 | doi-access = free }}
  • Kelly showed that each station of a BCMP network is quasireversible when viewed in isolation.{{cite book|last=Kelly|first=F.P.|author-link=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|access-date=2011-12-02|archive-date=2012-02-05|archive-url=https://web.archive.org/web/20120205024930/http://www.statslab.cam.ac.uk/~frank/rsn.html|url-status=live}}
  • G-queues in G-networks are quasireversible.{{Cite book | last1 = Dao-Thi | first1 = T. H. | last2 = Mairesse | first2 = J. | chapter = Zero-Automatic Queues | doi = 10.1007/11549970_6 | title = Formal Techniques for Computer Systems and Business Processes | series = Lecture Notes in Computer Science | volume = 3670 | pages = 64 | year = 2005 | isbn = 978-3-540-28701-8 }}

See also

References

{{Reflist}}

{{Queueing theory}}

Category:Queueing theory