product-form solution

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

: $\text{P}(x_1,x_2,x_3,\ldots,x_n) = B \prod_{i=1}^n \text{P}(x_i)$

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.{{Cite journal | first = James R. | last = Jackson | author-link = James R. Jackson | title = Jobshop-like queueing systems | year = 1963 | pages = 131–142 | volume = 10 | issue = 1 | doi = 10.1287/mnsc.10.1.131 | journal = Management Science }} After numerous extensions, chiefly the BCMP network it was thought local balance was a requirement for a product-form solution.{{Cite journal | first1 = Richard J. | last1 = Boucherie | first2 = N. M. | last2 = van Dijk | title = Local balance in queueing networks with positive and negative customers | doi = 10.1007/BF02033315 | journal = Annals of Operations Research | year = 1994 | pages = 463–492 | volume = 48 | issue = 5 | hdl = 1871/12327 | s2cid = 15599820 | url = https://research.vu.nl/en/publications/f31f9223-e306-4c35-943f-922cda73cd93 | hdl-access = free }}{{Cite journal | first1 = K. Mani | last1 = Chandy | author-link = K. Mani Chandy | first2 = J. H. Jr | last2 = Howard | first3 = D. F. | last3 = Towsley | title = Product form and local balance in queueing networks | doi = 10.1145/322003.322009 | journal = Journal of the ACM | year = 1977 | pages = 250–263 | volume = 24 | issue = 2 | s2cid = 6218474 | doi-access = free }}

Gelenbe's G-network model was the first to show that this is not the case. Motivated by the need to model biological neurons which have a point-process like spiking behaviour, he introduced the precursor of G-Networks, calling it the random neural network.{{cite journal | doi = 10.1162/neco.1989.1.4.502 | title = Random Neural Networks with Negative and Positive Signals and Product Form Solution | first = Erol | last = Gelenbe | author-link = Erol Gelenbe | journal = Neural Computation | volume = 1 | issue = 4 | year = 1989 | pages = 502–510 | s2cid = 207737442 }} By introducing "negative customers" which can destroy or eliminate other customers, he generalised the family of product form networks.{{cite journal | doi = 10.2307/3214499 | title = Product-form queueing networks with negative and positive customers | first = Erol | last = Gelenbe | author-link = Erol Gelenbe | journal = Journal of Applied Probability | volume = 28 | issue = 3 | year = 1991 | pages = 656–663 | jstor = 3214499 | url = https://vestifm.belnauka.by/jour/article/view/351 }} Then this was further extended in several steps, first by Gelenbe's "triggers" which are customers which have the power of moving other customers from some queue to another.{{cite journal | doi = 10.2307/3214781 | title = G-networks with triggered customer movement | first = Erol | last = Gelenbe | author-link = Erol Gelenbe | journal = Journal of Applied Probability | volume = 30 | issue = 3 | year = 1993 | pages = 742–748 | jstor = 3214781 }} Another new form of customer that also led to product form was Gelenbe's "batch removal".{{cite journal | doi = 10.1017/S0269964800002953 | title = G-Networks with triggered customer movement | first = Erol | last = Gelenbe | author-link = Erol Gelenbe | journal = Probability in the Engineering and Informational Sciences | volume = 7 | issue = 3 | year = 1993 | pages = 335–342 }} This was further extended by Erol Gelenbe and Jean-Michel Fourneau with customer types called "resets" which can model the repair of failures: when a queue hits the empty state, representing (for instance) a failure, the queue length can jump back or be "reset" to its steady-state distribution by an arriving reset customer, representing a repair. All these previous types of customers in G-Networks can exist in the same network, including with multiple classes, and they all together still result in the product form solution, taking us far beyond the reversible networks that had been considered before.{{cite journal | doi = 10.1016/S0166-5316(02)00127-X | title = G-Networks with resets | first1 = Erol | last1 = Gelenbe | first2 = Jean-Michel | last2 = Fourneau | author-link = Erol Gelenbe | journal = Performance Evaluation | volume = 49 | issue = 1 | year = 2002 | pages = 179–191 }}

Product-form solutions are sometimes described as "stations are independent in equilibrium".{{cite journal | doi = 10.1214/aoap/1177005704 | title = Brownian models of feedforward queueing networks: quasireversibility and product-form solutions | first1 = J. M. | last1 = Harrison | author-link = J. Michael Harrison | first2 = R. J. | last2 = Williams | journal = Annals of Applied Probability | volume = 2 | issue = 2 | year = 1992 | pages = 263–293 | citeseerx = 10.1.1.56.1572 }} Product form solutions also exist in networks of bulk queues.{{Cite journal | last1 = Henderson | first1 = W. | last2 = Taylor | first2 = P. G. | doi = 10.1007/BF02411466 | title = Product form in networks of queues with batch arrivals and batch services | journal = Queueing Systems| volume = 6 | pages = 71–87 | year = 1990 | s2cid = 30949152 }}

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" More recently, product-form solutions have been published for Markov process algebras (e.g. RCAT in PEPA{{Cite journal | last1 = Hillston | first1 = J. | author-link = Jane Hillston| last2 = Thomas | first2 = N. | doi = 10.1016/S0166-5316(99)00005-X | title = Product form solution for a class of PEPA models | journal = Performance Evaluation | volume = 35 | issue = 3–4 | pages = 171–192 | year = 1999 | url = https://www.pure.ed.ac.uk/ws/files/16206787/Product_form_solution_for_a_class_of_PEPA_models.pdf | hdl = 20.500.11820/13c57018-5854-4f34-a4c9-833262a71b7c | hdl-access = free }}{{Cite journal | last1 = Harrison | first1 = P. G. | author-link = Peter G. Harrison | title = Turning back time in Markovian process algebra | doi = 10.1016/S0304-3975(02)00375-4 | url = http://pubs.doc.ic.ac.uk/rcat/ | journal = Theoretical Computer Science | volume = 290 | issue = 3 | pages = 1947–2013 | year = 2003 | access-date = 2015-08-29 | archive-url = https://web.archive.org/web/20061015010731/http://pubs.doc.ic.ac.uk/rcat/ | archive-date = 2006-10-15 | doi-access = free }}) and stochastic petri nets.{{Cite journal | last1 = Marin | first1 = A. | last2 = Balsamo | first2 = S. | last3 = Harrison | first3 = P. G. | author-link3 = Peter G. Harrison| doi = 10.1016/j.peva.2012.06.003 | title = Analysis of stochastic Petri nets with signals | journal = Performance Evaluation | year = 2012 | volume=69 | issue = 11 | pages=551–572| hdl = 10044/1/14180 | hdl-access = free }}{{Cite book | last1 = Mairesse | first1 = J. | last2 = Nguyen | first2 = H. T. | chapter = Deficiency Zero Petri Nets and Product Form | doi = 10.1007/978-3-642-02424-5_8 | title = Applications and Theory of Petri Nets | series = Lecture Notes in Computer Science | volume = 5606 | page = 103 | year = 2009 | isbn = 978-3-642-02423-8 | citeseerx = 10.1.1.745.1585 }} Martin Feinberg's deficiency zero theorem gives a sufficient condition for chemical reaction networks to exhibit a product-form stationary distribution.{{Cite journal | last1 = Anderson | first1 = D. F. | last2 = Craciun | first2 = G. | last3 = Kurtz | first3 = T. G. | doi = 10.1007/s11538-010-9517-4 | title = Product-Form Stationary Distributions for Deficiency Zero Chemical Reaction Networks | journal = Bulletin of Mathematical Biology | volume = 72 | issue = 8 | pages = 1947–1970 | year = 2010 | pmid = 20306147| arxiv = 0803.3042 | s2cid = 2204856 }}

The work by Gelenbe also shows that product form G-Networks can be used to model spiking random neural networks, and furthermore that such networks can be used to approximate bounded and continuous real-valued functions.{{cite journal | doi = 10.1162/neco.1993.5.1.154 | title = Learning in the recurrent random neural network | first = Erol | last = Gelenbe | author-link = Erol Gelenbe | journal = Neural Computation | volume = 5 | issue = 1 | year = 1993 | pages = 154–164 | s2cid = 38667978 }}{{cite journal | doi = 10.1109/72.737488 | pmid = 18252498 | title = Function approximation with the random neural network | first1 = Erol | last1 = Gelenbe | first2 = Zhi-Hong | last2 = Mao | first3 = Yan-Da | last3 = Li | author-link = Erol Gelenbe | journal = IEEE Transactions on Neural Networks | volume = 10 | issue = 1 | year = 1991 | pages = 3–9 | citeseerx = 10.1.1.46.7710 }}

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.{{cite journal|title=The Product Form for Sojourn Time Distributions in Cyclic Exponential Queues|journal=Journal of the ACM|first1=O. J.|last1=Boxma|author-link1=Onno J. Boxma|first2=F. P.|last2=Kelly|author-link2=Frank Kelly (mathematician)|first3=A. G.|last3=Konheim|volume=31|issue=1|date=January 1984|doi=10.1145/2422.322419|pages=128–133|s2cid=6770615|doi-access=free}} In 1957 Reich showed the result for two M/M/1 queues in tandem,{{Cite journal | last1 = Reich | first1 = Edgar| title = Waiting Times when Queues are in Tandem | journal = The Annals of Mathematical Statistics | volume = 28 | issue = 3 | pages = 768–773 | doi = 10.1214/aoms/1177706889 | year = 1957 | doi-access = free }} later extending this to n M/M/1 queues in tandem{{Cite journal | last1 = Reich | first1 = E.| doi = 10.1214/aoms/1177704275 | title = Note on Queues in Tandem | journal = The Annals of Mathematical Statistics | volume = 34 | pages = 338–341 | year = 1963 | doi-access = free }} and it has been shown to apply to overtake–free paths in Jackson networks. 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.{{Cite journal | last1 = Walrand | first1 = J. | author-link1 = Jean Walrand| last2 = Varaiya | first2 = P. | title = Sojourn Times and the Overtaking Condition in Jacksonian Networks | journal = Advances in Applied Probability| volume = 12 | issue = 4 | pages = 1000–1018 | doi = 10.2307/1426753 | jstor = 1426753| year = 1980 }} Mitrani offers exact solutions to some simple networks with overtaking, showing that none of these exhibit product-form sojourn time distributions.{{Cite journal | last1 = Mitrani | first1 = I. | title = Response Time Problems in Communication Networks | journal = Journal of the Royal Statistical Society. Series B (Methodological)| volume = 47 | issue = 3 | pages = 396–406 | jstor = 2345774| year = 1985 | doi = 10.1111/j.2517-6161.1985.tb01368.x }}

For closed networks, Chow showed a result to hold for two service nodes,{{cite journal|title=The Cycle Time Distribution of Exponential Cyclic Queues|journal=Journal of the ACM|first=We-Min|last=Chow|volume=27|issue=2|date=April 1980|doi=10.1145/322186.322193|pages=281–286|s2cid=14084475|doi-access=free}} which was later generalised to a cycle of queues{{Cite journal | last1 = Schassberger | first1 = R. | last2 = Daduna | first2 = H. | doi = 10.1145/322358.322369 | title = The Time for a Round Trip in a Cycle of Exponential Queues | journal = Journal of the ACM | volume = 30 | pages = 146–150 | year = 1983 | s2cid = 33401212 | doi-access = free }} and to overtake–free paths in Gordon–Newell networks.{{Cite journal | last1 = Daduna | first1 = H. | title = Passage Times for Overtake-Free Paths in Gordon-Newell Networks | journal = Advances in Applied Probability | volume = 14 | issue = 3 | pages = 672–686 | doi = 10.2307/1426680 | year = 1982 | jstor = 1426680 }}{{Cite journal | last1 = Kelly | first1 = F. P. | author-link= Frank Kelly (mathematician)| last2 = Pollett | first2 = P. K. | title = Sojourn Times in Closed Queueing Networks | journal = Advances in Applied Probability | volume = 15 | issue = 3 | pages = 638–656 | doi = 10.2307/1426623 | year = 1983 | jstor = 1426623 }}

Extensions

Approximate product-form solutions are computed assuming independent marginal distributions, which can give a good approximation to the stationary distribution under some conditions.{{Cite journal | last1 = Baynat | first1 = B. | last2 = Dallery | first2 = Y. | doi = 10.1016/0166-5316(93)90017-O | title = A unified view of product-form approximation techniques for general closed queueing networks | journal = Performance Evaluation | volume = 18 | issue = 3 | pages = 205–224 | year = 1993 }}{{Cite journal | last1 = Dallery | first1 = Y. | last2 = Cao | first2 = X. R. | doi = 10.1016/0166-5316(92)90019-D | title = Operational analysis of stochastic closed queueing networks | journal = Performance Evaluation | volume = 14 | pages = 43–61 | year = 1992 }}
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.{{Cite book | last1 = Thomas | first1 = Nigel| last2 = Harrison | first2 = Peter G. | author-link2 = Peter G. Harrison| chapter = State-Dependent Rates and Semi-Product-Form via the Reversed Process | doi = 10.1007/978-3-642-15784-4_14 | title = Computer Performance Engineering | series = Lecture Notes in Computer Science | volume = 6342 | page = 207 | year = 2010 | isbn = 978-3-642-15783-7 }}
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{{Cite journal

| last1 = Dębicki | first1 = K.

| last2 = Dieker | first2 = A. B.

| last3 = Rolski | first3 = T.

| doi = 10.1287/moor.1070.0259

| title = Quasi-Product Forms for Levy-Driven Fluid Networks

| journal = Mathematics of Operations Research

| volume = 32

| issue = 3

| pages = 629–647

| year = 2007

| arxiv = math/0512119

| s2cid = 16150704}} or

approximate form for transient probability distributions which allows transient moments to be approximated.{{Cite book | last1 = Angius | first1 = A. | last2 = Horváth | first2 = A. S. | last3 = Wolf | first3 = V. | doi = 10.1007/978-3-642-39408-9_3 | chapter = Approximate Transient Analysis of Queuing Networks by Quasi Product Forms | title = Analytical and Stochastic Modeling Techniques and Applications | series = Lecture Notes in Computer Science | volume = 7984 | page = 22 | year = 2013 | isbn = 978-3-642-39407-2 }}

References

Category:Queueing theory