Suvarna Garge (Editor)

Quasireversibility

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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.

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.

    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 )

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

    α = ∑ x ′ ∈ M x q ( x , x ′ ) = ∑ x ′ ∈ M x q ′ ( x , x ′ )

    where Mx is a set such that x ′ ∈ M 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.
  • Kelly showed that each station of a BCMP network is quasireversible when viewed in isolation.
  • G-queues in G-networks are quasireversible.

    • References

    Quasireversibility Wikipedia
    (Text) CC BY-SA