Buzen's algorithm

In queueing theory, a discipline within the mathematical 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[1] and subsequently published in a refereed journal in 1973.[2] Computing G(N) is required to compute the stationary probability distribution of a closed queueing network.[3]

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 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.[4] 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.

  1. ^ Buzen, J.P. (1971-08-01). DTIC AD0731575: Queueing Network Models of Multiprogramming.
  2. ^ Buzen, J. P. (1973). "Computational algorithms for closed queueing networks with exponential servers" (PDF). Communications of the ACM. 16 (9): 527–531. doi:10.1145/362342.362345. S2CID 10702. Archived from the original (PDF) on 2016-05-13. Retrieved 2006-04-15.
  3. ^ Gordon, W. J.; Newell, G. F. (1967). "Closed Queuing Systems with Exponential Servers". Operations Research. 15 (2): 254. doi:10.1287/opre.15.2.254. JSTOR 168557.
  4. ^ Denning, Peter J. (24 August 2016). "Rethinking Randomness: An interview with Jeff Buzen, Part I". Ubiquity. 2016 (August): 1:1–1:17. doi:10.1145/2986329.