Quasireversibility Explained
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
\pi(x)q'(x,x')=\pi(x')q(x',x)
then considering just customers of a particular class, the arrival and departure processes are the same Poisson process (with parameter
), so
\alpha=
q(x,x')=
q'(x,x')
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
See also
Notes and References
- Muntz. R.R.. 1972. Poisson departure process and queueing networks (IBM Research Report RC 4145). IBM Thomas J. Watson Research Center. Yorktown Heights, N.Y..
- Kelly . F. P. . Frank Kelly (mathematician). Networks of Queues with Customers of Different Types . Journal of Applied Probability . 12 . 3 . 542–554 . 10.2307/3212869 . 3212869. 1975 . 51917794 .
- Kelly . F. P. . Frank Kelly (mathematician). Networks of Queues . Advances in Applied Probability . 8 . 2 . 416–432 . 10.2307/1425912 . 1425912. 1976 . 204177645 .
- Book: Peter G. Harrison. Peter G.. Harrison. Naresh M.. Patel. Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. 1992. 288. 0-201-54419-9. registration.
- 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
- Chao . X. . Miyazawa . M. . Serfozo . R. F. . Takada . H. . Queueing Systems . 28 . 4 . 377 . 10.1023/A:1019115626557 . 1998 . Markov network processes with product form stationary distributions. 14471818 .
- Kelly, F.P., Reversibility and Stochastic Networks, 1978 pages 66-67
- Burke . P. J. . The Output of a Queuing System . 10.1287/opre.4.6.699 . Operations Research . 4 . 6 . 699–704 . 1956 . 55089958 .
- Burke . P. J. . The Output Process of a Stationary M/M/s Queueing System . 10.1214/aoms/1177698238 . The Annals of Mathematical Statistics . 39 . 4 . 1144–1152 . 1968 . free .
- O'Connell . N. . Yor . M. . Brownian analogues of Burke's theorem . 10.1016/S0304-4149(01)00119-3 . Stochastic Processes and Their Applications . 96 . 2 . 285–298 . December 2001 . free .
- Book: Kelly, F.P.. Frank Kelly (mathematician). 1979. Reversibility and Stochastic Networks. Wiley. New York. 2011-12-02. 2012-02-05. https://web.archive.org/web/20120205024930/http://www.statslab.cam.ac.uk/~frank/rsn.html. live.
- Book: Dao-Thi . T. H. . Mairesse . J. . Zero-Automatic Queues . 10.1007/11549970_6 . Formal Techniques for Computer Systems and Business Processes . Lecture Notes in Computer Science . 3670 . 64 . 2005 . 978-3-540-28701-8 .