Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
Line 1:
In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]], '''Buzen's algorithm''' (or '''convolution algorithm''') is an algorithm for calculating the [[normalization constant]] G(''N'') in the [[Gordon–Newell theorem]]. This method was first proposed by [[Jeffrey P. Buzen]] in his 1971 PhD dissertation<ref name=":0">{{Cite book |last=Buzen, J.P. |url=http://archive.org/details/DTIC_AD0731575 |title=DTIC AD0731575: Queueing Network Models of Multiprogramming |date=1971-08-01 |language=english}}</ref> and subsequently published in a refereed journal in 1973.<ref name="buzen-1973">{{Cite journal | last1 = Buzen | first1 = J. P. | author-link = Jeffrey P. Buzen | title = Computational algorithms for closed queueing networks with exponential servers | doi = 10.1145/362342.362345 | url = http://www-unix.ecs.umass.edu/~krishna/ece673/buzen.pdf | journal = Communications of the ACM | volume = 16 | issue = 9 | pages = 527–531 | year = 1973 | s2cid = 10702 | access-date = 2006-04-15 | archive-date = 2016-05-13 | archive-url = https://web.archive.org/web/20160513192804/http://www-unix.ecs.umass.edu/~krishna/ece673/buzen.pdf | url-status = dead }}</ref> Computing G(''N'') is required to compute the stationary [[probability distribution]] of a closed queueing network.<ref name="gn">{{Cite journal | last1 = Gordon | first1 = W. J. | last2 = Newell | first2 = G. F. | author-link2 = Gordon F. Newell| doi = 10.1287/opre.15.2.254 | jstor = 168557| title = Closed Queuing Systems with Exponential Servers | journal = [[Operations Research (journal)|Operations Research]]| volume = 15 | issue = 2 | pages = 254 | year = 1967 }}</ref>
Performing a naïve computation of the normalizing constant requires enumeration of all states. For a closed network with ''N'' circulating customers and ''M'' service facilities, G(''N'') is the sum of <math>\tbinom{N+M-1}{M-1}</math> individual terms, with each term consisting of ''M'' factors raised to powers whose sum is ''N''. Buzen's algorithm computes G(''N'') using only ''NM'' multiplications and ''NM'' additions. This dramatic improvement opened the door to applying the Gordon-Newell theorem to models of real world computer systems as well as flexible manufacturing systems and other cases where bottlenecks and queues can form within networks of inter-connected service facilities.<ref name=":1">{{cite journal |last1=Denning |first1=Peter J. |date=24 August 2016 |title=Rethinking Randomness: An interview with Jeff Buzen, Part I |url=https://dl.acm.org/doi/10.1145/2986329 |journal=Ubiquity |volume=2016 |issue=August |pages=1:1–1:17 |doi=10.1145/2986329|doi-access=free }}</ref> The values of G(1), G(2) ... G(''N'' -1), which can be used to calculate other important quantities of interest, are computed as by-products of the algorithm.
Line 69:
<math>\mathbb E(n_i) = \sum_{k=1}^N X_i^k \frac{G(N-k)}{G(N)}.</math>
These characterizations of quantities of interest in terms of the G(''n'') are also due to Buzen.<ref name="buzen-1973"
==Implementation==
| |||