Product-form solution

Last updated

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

Contents

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 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. [4] By introducing "negative customers" which can destroy or eliminate other customers, he generalised the family of product form networks. [5] 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. [6] Another new form of customer that also led to product form was Gelenbe's "batch removal". [7] 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. [8]

Product-form solutions are sometimes described as "stations are independent in equilibrium". [9] Product form solutions also exist in networks of bulk queues. [10]

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" [9] More recently, product-form solutions have been published for Markov process algebras (e.g. RCAT in PEPA [11] [12] ) and stochastic petri nets. [13] [14] Martin Feinberg's deficiency zero theorem gives a sufficient condition for chemical reaction networks to exhibit a product-form stationary distribution. [15]

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. [16] [17]

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. [18] In 1957 Reich showed the result for two M/M/1 queues in tandem, [19] later extending this to n M/M/1 queues in tandem [20] and it has been shown to apply to overtake–free paths in Jackson networks. [21] 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. [21] Mitrani offers exact solutions to some simple networks with overtaking, showing that none of these exhibit product-form sojourn time distributions. [22]

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

Extensions

Related Research Articles

<span class="mw-page-title-main">Queueing theory</span> Mathematical study of waiting lines, or queues

Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide a service.

In queueing theory, a discipline within the mathematical theory of probability, a Jackson network is a class of queueing network where the equilibrium distribution is particularly simple to compute as the network has a product-form solution. It was the first significant development in the theory of networks of queues, and generalising and applying the ideas of the theorem to search for similar product-form solutions in other networks has been the subject of much research, including ideas used in the development of the Internet. The networks were first identified by James R. Jackson and his paper was re-printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’

A phase-type distribution is a probability distribution constructed by a convolution or mixture of exponential distributions. It results from a system of one or more inter-related Poisson processes occurring in sequence, or phases. The sequence in which each of the phases occurs may itself be a stochastic process. The distribution can be represented by a random variable describing the time until absorption of a Markov process with one absorbing state. Each of the states of the Markov process represents one of the phases.

<span class="mw-page-title-main">Erol Gelenbe</span>

Sami Erol Gelenbe, a Turkish and French computer scientist, electronic engineer and applied mathematician, pioneered the field of Computer System and Network Performance. Currently Professor in the Institute of Theoretical and Applied Informatics of the Polish Academy of Sciences, he is also an Associate Researcher in the I3S Laboratory and Abraham de Moivre Laboratory. Fellow of several National Academies, he Chairs the Informatics Section of Academia Europaea since 2023. His previous Professorial Chairs include the University of Liège (1974-1979), University Paris-Saclay (1979-1986), University Paris Descartes (1986-2005), NJIT (1991-93), ECE Chair at Duke University (1993-1998), University Chair Professor and Director of EECS, University of Central Florida (1998-2003), and Dennis Gabor Professor and Head of Intelligent Systems and Networks, Imperial College (2003-2019).

The random neural network (RNN) is a mathematical representation of an interconnected network of neurons or cells which exchange spiking signals. It was invented by Erol Gelenbe and is linked to the G-network model of queueing networks as well as to Gene Regulatory Network models. Each cell state is represented by an integer whose value rises when the cell receives an excitatory spike and drops when it receives an inhibitory spike. The spikes can originate outside the network itself, or they can come from other cells in the networks. Cells whose internal excitatory state has a positive value are allowed to send out spikes of either kind to other cells in the network according to specific cell-dependent spiking rates. The model has a mathematical solution in steady-state which provides the joint probability distribution of the network in terms of the individual probabilities that each cell is excited and able to send out spikes. Computing this solution is based on solving a set of non-linear algebraic equations whose parameters are related to the spiking rates of individual cells and their connectivity to other cells, as well as the arrival rates of spikes from outside the network. The RNN is a recurrent model, i.e. a neural network that is allowed to have complex feedback loops.

In queueing theory, a discipline within the mathematical theory of probability, a G-network is an open network of G-queues first introduced by Erol Gelenbe as a model for queueing systems with specific control functions, such as traffic re-routing or traffic destruction, as well as a model for neural networks. A G-queue is a network of queues with several types of novel and useful customers:

<span class="mw-page-title-main">M/M/1 queue</span> Queue with Markov (Poisson) arrival process, exponential service time distribution and one server

In queueing theory, a discipline within the mathematical theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an exponential distribution. The model name is written in Kendall's notation. The model is the most elementary of queueing models and an attractive object of study as closed-form expressions can be obtained for many metrics of interest in this model. An extension of this model with more than one server is the M/M/c queue.

In queueing theory, a discipline within the mathematical theory of probability, a BCMP network is a class of queueing network for which a product-form equilibrium distribution exists. It is named after the authors of the paper where the network was first described: Baskett, Chandy, Muntz, and Palacios. The theorem is a significant extension to a Jackson network allowing virtually arbitrary customer routing and service time distributions, subject to particular service disciplines.

Peter George Harrison is an Emeritus Professor of Computing Science at Imperial College London known for the reversed compound agent theorem, which gives conditions for a stochastic network to have a product-form solution.

In queueing theory, a discipline within the mathematical theory of probability, the arrival theorem states that "upon arrival at a station, a job observes the system as if in steady state at an arbitrary instant for the system without that job."

In queueing theory, a discipline within the mathematical theory of probability, quasireversibility 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.

In probability theory, a balance equation is an equation that describes the probability flux associated with a Markov chain in and out of states or set of states.

<span class="mw-page-title-main">Fork–join queue</span> Type of queue

In queueing theory, a discipline within the mathematical theory of probability, a fork–join queue is a queue where incoming jobs are split on arrival for service by numerous servers and joined before departure. The model is often used for parallel computations or systems where products need to be obtained simultaneously from different suppliers. The key quantity of interest in this model is usually the time taken to service a complete job. The model has been described as a "key model for the performance analysis of parallel and distributed systems." Few analytical results exist for fork–join queues, but various approximations are known.

In queueing theory, a discipline within the mathematical theory of probability, mean value analysis (MVA) is a recursive technique for computing expected queue lengths, waiting time at queueing nodes and throughput in equilibrium for a closed separable system of queues. The first approximate techniques were published independently by Schweitzer and Bard, followed later by an exact version by Lavenberg and Reiser published in 1980.

In queueing theory, a discipline within the mathematical theory of probability, the M/M/c queue is a multi-server queueing model. In Kendall's notation it describes a system where arrivals form a single queue and are governed by a Poisson process, there are c servers, and job service times are exponentially distributed. It is a generalisation of the M/M/1 queue which considers only a single server. The model with infinitely many servers is the M/M/∞ queue.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/1 queue is a queue model where arrivals are Markovian, service times have a General distribution and there is a single server. The model name is written in Kendall's notation, and is an extension of the M/M/1 queue, where service times must be exponentially distributed. The classic application of the M/G/1 queue is to model performance of a fixed head hard disk.

In queueing theory, a discipline within the mathematical theory of probability, a fluid queue is a mathematical model used to describe the fluid level in a reservoir subject to randomly determined periods of filling and emptying. The term dam theory was used in earlier literature for these models. The model has been used to approximate discrete models, model the spread of wildfires, in ruin theory and to model high speed data networks. The model applies the leaky bucket algorithm to a stochastic source.

In queueing theory, a discipline within the mathematical theory of probability, an M/G/k queue is a queue model where arrivals are Markovian, service times have a General distribution and there are k servers. The model name is written in Kendall's notation, and is an extension of the M/M/c queue, where service times must be exponentially distributed and of the M/G/1 queue with a single server. Most performance metrics for this queueing system are not known and remain an open problem.

In probability theory, reflected Brownian motion is a Wiener process in a space with reflecting boundaries. In the physical literature, this process describes diffusion in a confined space and it is often called confined Brownian motion. For example it can describe the motion of hard spheres in water confined between two walls.

In queueing theory, a discipline within the mathematical theory of probability, a Kelly network is a general multiclass queueing network. In the network each node is quasireversible and the network has a product-form stationary distribution, much like the single-class Jackson network.

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 (5): 463–492. doi:10.1007/BF02033315. hdl: 1871/12327 . S2CID   15599820.
  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 (2): 250–263. doi: 10.1145/322003.322009 . S2CID   6218474.
  4. ↑ Gelenbe, Erol (1989). "Random Neural Networks with Negative and Positive Signals and Product Form Solution". Neural Computation. 1 (4): 502–510. doi:10.1162/neco.1989.1.4.502. S2CID   207737442.
  5. ↑ Gelenbe, Erol (1991). "Product-form queueing networks with negative and positive customers". Journal of Applied Probability. 28 (3): 656–663. doi:10.2307/3214499. JSTOR   3214499.
  6. ↑ Gelenbe, Erol (1993). "G-networks with triggered customer movement". Journal of Applied Probability. 30 (3): 742–748. doi:10.2307/3214781. JSTOR   3214781.
  7. ↑ Gelenbe, Erol (1993). "G-Networks with triggered customer movement". Probability in the Engineering and Informational Sciences. 7 (3): 335–342. doi:10.1017/S0269964800002953.
  8. ↑ Gelenbe, Erol; Fourneau, Jean-Michel (2002). "G-Networks with resets". Performance Evaluation. 49 (1): 179–191. doi:10.1016/S0166-5316(02)00127-X.
  9. 1 2 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. CiteSeerX   10.1.1.56.1572 . doi:10.1214/aoap/1177005704.
  10. ↑ Henderson, W.; Taylor, P. G. (1990). "Product form in networks of queues with batch arrivals and batch services". Queueing Systems . 6: 71–87. doi:10.1007/BF02411466. S2CID   30949152.
  11. ↑ Hillston, J.; Thomas, N. (1999). "Product form solution for a class of PEPA models" (PDF). Performance Evaluation. 35 (3–4): 171–192. doi:10.1016/S0166-5316(99)00005-X. hdl: 20.500.11820/13c57018-5854-4f34-a4c9-833262a71b7c .
  12. ↑ Harrison, P. G. (2003). "Turning back time in Markovian process algebra". Theoretical Computer Science. 290 (3): 1947–2013. doi: 10.1016/S0304-3975(02)00375-4 . Archived from the original on 2006-10-15. Retrieved 2015-08-29.
  13. ↑ Marin, A.; Balsamo, S.; Harrison, P. G. (2012). "Analysis of stochastic Petri nets with signals". Performance Evaluation. 69 (11): 551–572. doi:10.1016/j.peva.2012.06.003. hdl: 10044/1/14180 .
  14. ↑ Mairesse, J.; Nguyen, H. T. (2009). "Deficiency Zero Petri Nets and Product Form". Applications and Theory of Petri Nets. Lecture Notes in Computer Science. Vol. 5606. p. 103. CiteSeerX   10.1.1.745.1585 . doi:10.1007/978-3-642-02424-5_8. ISBN   978-3-642-02423-8.
  15. ↑ Anderson, D. F.; Craciun, G.; Kurtz, T. G. (2010). "Product-Form Stationary Distributions for Deficiency Zero Chemical Reaction Networks". Bulletin of Mathematical Biology. 72 (8): 1947–1970. arXiv: 0803.3042 . doi:10.1007/s11538-010-9517-4. PMID   20306147. S2CID   2204856.
  16. ↑ Gelenbe, Erol (1993). "Learning in the recurrent random neural network". Neural Computation. 5 (1): 154–164. doi:10.1162/neco.1993.5.1.154. S2CID   38667978.
  17. ↑ Gelenbe, Erol; Mao, Zhi-Hong; Li, Yan-Da (1991). "Function approximation with the random neural network". IEEE Transactions on Neural Networks. 10 (1): 3–9. CiteSeerX   10.1.1.46.7710 . doi:10.1109/72.737488. PMID   18252498.
  18. ↑ 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): 128–133. doi: 10.1145/2422.322419 . S2CID   6770615.
  19. ↑ Reich, Edgar (1957). "Waiting Times when Queues are in Tandem". The Annals of Mathematical Statistics. 28 (3): 768–773. doi: 10.1214/aoms/1177706889 .
  20. ↑ Reich, E. (1963). "Note on Queues in Tandem". The Annals of Mathematical Statistics. 34: 338–341. doi: 10.1214/aoms/1177704275 .
  21. 1 2 Walrand, J.; Varaiya, P. (1980). "Sojourn Times and the Overtaking Condition in Jacksonian Networks". Advances in Applied Probability. 12 (4): 1000–1018. doi:10.2307/1426753. JSTOR   1426753.
  22. ↑ Mitrani, I. (1985). "Response Time Problems in Communication Networks". Journal of the Royal Statistical Society. Series B (Methodological). 47 (3): 396–406. doi:10.1111/j.2517-6161.1985.tb01368.x. JSTOR   2345774.
  23. ↑ Chow, We-Min (April 1980). "The Cycle Time Distribution of Exponential Cyclic Queues". Journal of the ACM . 27 (2): 281–286. doi: 10.1145/322186.322193 . S2CID   14084475.
  24. ↑ Schassberger, R.; Daduna, H. (1983). "The Time for a Round Trip in a Cycle of Exponential Queues". Journal of the ACM. 30: 146–150. doi: 10.1145/322358.322369 . S2CID   33401212.
  25. ↑ Daduna, H. (1982). "Passage Times for Overtake-Free Paths in Gordon-Newell Networks". Advances in Applied Probability. 14 (3): 672–686. doi:10.2307/1426680. JSTOR   1426680.
  26. ↑ Kelly, F. P.; Pollett, P. K. (1983). "Sojourn Times in Closed Queueing Networks". Advances in Applied Probability. 15 (3): 638–656. doi:10.2307/1426623. JSTOR   1426623.
  27. ↑ Baynat, B.; Dallery, Y. (1993). "A unified view of product-form approximation techniques for general closed queueing networks". Performance Evaluation. 18 (3): 205–224. doi:10.1016/0166-5316(93)90017-O.
  28. ↑ Dallery, Y.; Cao, X. R. (1992). "Operational analysis of stochastic closed queueing networks". Performance Evaluation. 14: 43–61. doi:10.1016/0166-5316(92)90019-D.
  29. ↑ Thomas, Nigel; Harrison, Peter G. (2010). "State-Dependent Rates and Semi-Product-Form via the Reversed Process". Computer Performance Engineering. Lecture Notes in Computer Science. Vol. 6342. p. 207. doi:10.1007/978-3-642-15784-4_14. ISBN   978-3-642-15783-7.
  30. ↑ Dębicki, K.; Dieker, A. B.; Rolski, T. (2007). "Quasi-Product Forms for Levy-Driven Fluid Networks". Mathematics of Operations Research . 32 (3): 629–647. arXiv: math/0512119 . doi:10.1287/moor.1070.0259. S2CID   16150704.
  31. ↑ Angius, A.; Horváth, A. S.; Wolf, V. (2013). "Approximate Transient Analysis of Queuing Networks by Quasi Product Forms". Analytical and Stochastic Modeling Techniques and Applications. Lecture Notes in Computer Science. Vol. 7984. p. 22. doi:10.1007/978-3-642-39408-9_3. ISBN   978-3-642-39407-2.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.