Buzen's algorithm: Difference between revisions

Revision as of 17:28, 11 May 2020

Revision as of 23:44, 9 December 2020

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 1973.<ref name="buzen-1973">{{Cite journal | last1 = Buzen | first1 = J. P. | authorlinkauthor-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 | year = 1973 | pmid = | pmc = }}</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. | authorlink2author-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 | pmid = | pmc = }}</ref>

Performing a naïve computation of the normalising constant requires enumeration of all states. For a system with ''N'' jobs and ''M'' states there are <math>\tbinom{N+M-1}{M-1}</math> states. Buzen's algorithm "computes G(1), G(2), ..., G(''N'') using a total of ''NM'' multiplications and ''NM'' additions." This is a significant improvement and allows for computations to be performed with much larger networks.<ref name="buzen-1973" />