Jump to content

Product-form solution

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Monkbot (talk | contribs) at 21:21, 28 January 2014 (→Sojourn time distributions: Fix CS1 deprecated date parameter errors). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In probability theory, a product-form solution is a particularly efficient form of solution for determining some metric of a system with distinct sub-components, where the metric for the collection of components can be written as a product of the metric across the different components. Using capital Pi notation a product-form solution has algebraic form

where B is some constant. Solutions of this form are of interest as they are computationally inexpensive to evaluate for large values of n. Such solutions in queueing networks are important for finding performance metrics in models of multiprogrammed and time-shared computer systems.

Equilibrium distributions

The first product-form solutions were found for equilibrium distributions of Markov chains. Trivially, models composed of two or more independent sub-components exhibit a product-form solution by the definition of independence. Initially the term was used in queueing networks where the sub-components would be individual queues. For example, Jackson's theorem gives the joint equilibrium distribution of an open queueing network as the product of the equilibrium distributions of the individual queues.[1] After numerous extensions, chiefly the BCMP network it was thought local balance was a requirement for a product-form solution.[2][3] Gelenbe's G-network model showed this to not be the case.[4] Product-form solutions are sometimes described as "stations are independent in equilibrium".[5] Product form solutions also exist in networks of bulk queues.[6]

J.M. Harrison and R.J. Williams note that "virtually all of the models that have been successfully analyzed in classical queueing network theory are models having a so-called product-form stationary distribution"[5] More recently, product-form solutions have been published for Markov process algebras (e.g. RCAT in PEPA[7][8]) and stochastic petri nets.[9][10] Martin Feinberg's deficiency zero theorem gives a sufficient condition for chemical reaction networks to exhibit a product-form stationary distribution.[11]

Sojourn time distributions

The term product form has also been used to refer to the sojourn time distribution in a cyclic queueing system, where the time spent by jobs at M nodes is given as the product of time spent at each node.[12] In 1957 Reich showed the result for two M/M/1 queues in tandem,[13] later extending this to n M/M/1 queues in tandem[14] and it has been shown to apply to overtake–free paths in Jackson networks.[15] Walrand and Varaiya suggest that non-overtaking (where customers cannot overtake other customers by taking a different route through the network) may be a necessary condition for the result to hold.[15] Mitrani offers exact solutions to some simple networks with overtaking, showing that none of these exhibit product-form sojourn time distributions.[16]

For closed networks, Chow showed a result to hold for two service nodes,[17] which was later generalised to a cycle of queues[18] and to overtake–free paths in Gordon–Newell networks.[19][20]

Extensions

  • Approximate product-form solutions are computed assuming independent marginal distributions, which can give a good approximation to the stationary distribution under some conditions.[21][22]
  • Semi-product-form solutions are solutions where a distribution can be written as a product where terms have a limited functional dependency on the global state space, which can be approximated.[23]
  • Quasi-product-form solutions are either
    • solutions which are not the product of marginal densities, but the marginal densities describe the distribution in a product-type manner[24] or
    • approximate form for transient probability distributions which allows transient moments to be approximated.[25]

References

  1. ^ Jackson, James R. (1963). "Jobshop-like queueing systems". Management Science. 10 (1): 131–142. doi:10.1287/mnsc.10.1.131.
  2. ^ Boucherie, Richard J.; van Dijk, N. M. (1994). "Local balance in queueing networks with positive and negative customers". Annals of Operations Research. 48: 463–492. doi:10.1007/BF02033315.
  3. ^ Chandy, K. Mani; Howard, J. H., Jr; Towsley, D. F. (1977). "Product form and local balance in queueing networks". Journal of the ACM. 24: 250–263. doi:10.1145/322003.322009.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  4. ^ Gelenbe, Erol (1993). "G-Networks with triggered customer movement". Journal of Applied Probability. 30 (3): 742–748. doi:10.2307/3214781.
  5. ^ a b Harrison, J. M.; Williams, R. J. (1992). "Brownian models of feedforward queueing networks: quasireversibility and product-form solutions". Annals of Applied Probability. 2 (2): 263–293. doi:10.1214/aoap/1177005704.
  6. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/BF02411466, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/BF02411466 instead.
  7. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/S0166-5316(99)00005-X, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/S0166-5316(99)00005-X instead.
  8. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/S0304-3975(02)00375-4, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/S0304-3975(02)00375-4 instead.
  9. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/j.peva.2012.06.003, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/j.peva.2012.06.003 instead.
  10. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/978-3-642-02424-5_8, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/978-3-642-02424-5_8 instead.
  11. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/s11538-010-9517-4, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/s11538-010-9517-4 instead.
  12. ^ Boxma, O. J.; Kelly, F. P.; Konheim, A. G. (January 1984). "The Product Form for Sojourn Time Distributions in Cyclic Exponential Queues". Journal of the ACM. 31 (1). doi:10.1145/2422.322419.
  13. ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:2237237, please use {{cite journal}} with |jstor=2237237 instead.
  14. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1214/aoms/1177704275, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1214/aoms/1177704275 instead.
  15. ^ a b Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:1426753, please use {{cite journal}} with |jstor=1426753 instead.
  16. ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:2345774, please use {{cite journal}} with |jstor=2345774 instead.
  17. ^ Chow, We-Min (April 1980). "The Cycle Time Distribution of Exponential Cyclic Queues". Journal of the ACM. 27 (2). doi:10.1145/322186.322193.
  18. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/322358.322369, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/322358.322369 instead.
  19. ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:1426680, please use {{cite journal}} with |jstor=1426680 instead.
  20. ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:1426623, please use {{cite journal}} with |jstor=1426623 instead.
  21. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0166-5316(93)90017-O, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0166-5316(93)90017-O instead.
  22. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0166-5316(92)90019-D, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0166-5316(92)90019-D instead.
  23. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/978-3-642-15784-4_14, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/978-3-642-15784-4_14 instead.
  24. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1287/moor.1070.0259, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1287/moor.1070.0259 instead.
  25. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/978-3-642-39408-9_3, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/978-3-642-39408-9_3 instead.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Product-form_solution&oldid=592855887"