Buzen's algorithm: Difference between revisions

Revision as of 06:56, 9 June 2023

Revision as of 17:44, 9 June 2023

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=Defense Technical Information Center |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 }}</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 jobs and ''M'' service centers, 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 total sum is ''N''. Buzen's algorithm computes G(''N'') using a total of ''NM'' multiplications and ''NM'' additions. This is a highly significant improvement<ref>{{cite journal |last1=Denning |first1=Peter J. |title=Rethinking Randomness: An interview with Jeff Buzen, Part I |journal=Ubiquity |date=24 August 2016 |volume=2016 |issue=August |pages=1:1–1:17 |doi=10.1145/2986329 |url=https://dl.acm.org/doi/10.1145/2986329}}</ref> that opened the door to applying the Gordon-Newell theorem to models of realistic size.<ref name="buzen-1973" /> In addition, the values of G(1), G(2) ... G(''N''-1), which can be used to express other important quantities of interest,<ref name=":0" /> are computed as by-products of the algorithm.

==Problem setup==

Consider a closed queueing network with ''M'' service facilities and ''N'' circulating customers. Assume that the service time for a customer at theservice facility ''i''th facility is given by an [[exponentially distributed]] random variable with parameter ''μ''_''i'' and that, after completing service at theservice facility ''i''th facility, a customer will proceed next to theservice facility ''j''th facility with probability ''p''_''ij''.<ref name="gn" />

It follows from the [[Gordon–Newell theorem]] that the equilibrium distribution of this model is

Line 25:

The individual terms that must be added together to compute G(''N'') all have the following form: <math> \left( X_1 \right)^{n_1}</math><math> \left( X_2 \right)^{n_2}</math><math> \left( X_3 \right)^{n_3}</math> .... <math> \left( X_M \right)^{n_M}</math>. Note that this set of terms can be partitioned into two groups. The first group comprises all terms for which the exponent of <math> \left( X_M \right)</math> is greater than or equal to 1.  This implies that <math> \left( X_M \right)</math>¹ can be factored out of each of these terms.  

After factoring out <math> \left( X_M \right)</math>, a surprising result emerges: the sum of the modified terms in the first group are nowidentical exactlyto equalthe terms used to compute the normalizing constant for the same network with one customer removed.  Thus, the sum of the terms in the first group can be written as “''X''_''M'' times G(''N'' -1)”.

Next consider the second group.  The exponent of ''X''_''M'' for every term in this group is zero.  In effect, service facility ''M'' disappears from all terms in this group (since it reduces in every case to a factor of 1). This leaves the total number of customers at the remaining ''M'' -1 service facilities equal to ''N''.

Line 42:

g(n,m) = X_m g(n-1,m) + g(n,m-1).  

The thought process that led to the discovery of this recurrence relation is discussed in the final sections of a 2016 interview. Buzen’s algorithm is simply the iterative application of this this fundamental recurrence relation, along with the following boundary conditions.

The thought process that led to the discovery of this recurrence relation is discussed in the final sections of a 2016 interview. Buzen’s algorithm is simply the iterative application of this this fundamental recurrence relation, along with the following boundary conditions.

g(0,m) = 1 for m = 1, 2, …''M''