Quasireversibility

In probability theory, specifically queueing theory, 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]

Contents

Definition

A queue with stationary distribution \pi is quasireversible if its state at time t, x(t) is independent of

for all classes of customer.[6]

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

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.  edit
  3. ^ Kelly, F. P. (1976). "Networks of Queues". Advances in Applied Probability 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912.  edit
  4. ^ Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. p. 288. ISBN 0201544199. 
  5. ^ 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
  6. ^ Kelly, F.P., Reversibility and Stochastic Networks, 1978 pages 66-67
  7. ^ Burke, P.J. (1956). "The output of a queueing system". Oper. Res. 4 (6): 699–704. doi:10.1287/opre.4.6.699. 
  8. ^ Burke, P.J. (1968). "The output of a stationary M/M/s queueing system". Ann. Math. Statist 39 (4): 1144–1152. doi:10.1214/aoms/1177698238. 
  9. ^ O'Connell, N. (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.  edit
  10. ^ Kelly, F.P. (1979). Reversibility and Stochastic Networks. New York: Wiley. http://www.statslab.cam.ac.uk/~frank/rsn.html.