Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Quasireversibility
Property of some queues

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 and further developed by Frank Kelly. 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.

A network of queues, such that each individual queue when considered in isolation is quasireversible, always has a product form stationary distribution. 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.

We don't have any images related to Quasireversibility yet.
We don't have any YouTube videos related to Quasireversibility yet.
We don't have any PDF documents related to Quasireversibility yet.
We don't have any Books related to Quasireversibility yet.
We don't have any archived web articles related to Quasireversibility yet.

Definition

A queue with stationary distribution π {\displaystyle \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.7

Partial balance formulation

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

π ( x ) q ′ ( x , x ′ ) = π ( x ′ ) q ( x ′ , x ) {\displaystyle \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 α {\displaystyle \alpha } ), so

α = ∑ x ′ ∈ M x q ( x , x ′ ) = ∑ x ′ ∈ M x q ′ ( x , x ′ ) {\displaystyle \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 x ′ ∈ M x {\displaystyle \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

See also

References

  1. Muntz, R.R. (1972). Poisson departure process and queueing networks (IBM Research Report RC 4145) (Technical report). Yorktown Heights, N.Y.: IBM Thomas J. Watson Research Center. http://domino.research.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/20b9b17a2db64886852574ef005775ce ↩

  2. Kelly, F. P. (1975). "Networks of Queues with Customers of Different Types". Journal of Applied Probability. 12 (3): 542–554. doi:10.2307/3212869. JSTOR 3212869. S2CID 51917794. /wiki/Frank_Kelly_(mathematician) ↩

  3. Kelly, F. P. (1976). "Networks of Queues". Advances in Applied Probability. 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912. S2CID 204177645. /wiki/Frank_Kelly_(mathematician) ↩

  4. Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. p. 288. ISBN 0-201-54419-9. 0-201-54419-9 ↩

  5. Kelly, F.P. (1982). Networks of quasireversible nodes Archived 2007-02-21 at the Wayback Machine. In Applied Probability and Computer Science: The Interface (Ralph L. Disney and Teunis J. Ott, editors.) 1 3-29. Birkhäuser, Boston http://www.statslab.cam.ac.uk/~frank/PAPERS/nqrn.pdf ↩

  6. Chao, X.; Miyazawa, M.; Serfozo, R. F.; Takada, H. (1998). "Markov network processes with product form stationary distributions". Queueing Systems. 28 (4): 377. doi:10.1023/A:1019115626557. S2CID 14471818. /wiki/Doi_(identifier) ↩

  7. Kelly, F.P., Reversibility and Stochastic Networks Archived 2023-01-19 at the Wayback Machine, 1978 pages 66-67 http://www.statslab.cam.ac.uk/~frank/BOOKS/kelly_book.html ↩

  8. Burke, P. J. (1956). "The Output of a Queuing System". Operations Research. 4 (6): 699–704. doi:10.1287/opre.4.6.699. S2CID 55089958. /wiki/Doi_(identifier) ↩

  9. Burke, P. J. (1968). "The Output Process of a Stationary M/M/s Queueing System". The Annals of Mathematical Statistics. 39 (4): 1144–1152. doi:10.1214/aoms/1177698238. https://doi.org/10.1214%2Faoms%2F1177698238 ↩

  10. O'Connell, N.; Yor, M. (December 2001). "Brownian analogues of Burke's theorem". Stochastic Processes and Their Applications. 96 (2): 285–298. doi:10.1016/S0304-4149(01)00119-3. https://doi.org/10.1016%2FS0304-4149%2801%2900119-3 ↩

  11. Kelly, F.P. (1979). Reversibility and Stochastic Networks. New York: Wiley. Archived from the original on 2012-02-05. Retrieved 2011-12-02. /wiki/Frank_Kelly_(mathematician) ↩

  12. Dao-Thi, T. H.; Mairesse, J. (2005). "Zero-Automatic Queues". Formal Techniques for Computer Systems and Business Processes. Lecture Notes in Computer Science. Vol. 3670. p. 64. doi:10.1007/11549970_6. ISBN 978-3-540-28701-8. 978-3-540-28701-8 ↩