Burke's theorem

Burke's theorem In queueing theory, a discipline within the mathematical theory of probability, Burke's theorem (sometimes the Burke's output theorem[1]) is a theorem (stated and demonstrated by Paul J. Burke while working at Bell Telephone Laboratories) asserting that, for the M/M/1 queue, M/M/c queue or M/M/∞ queue in the steady state with arrivals is a Poisson process with rate parameter λ: The departure process is a Poisson process with rate parameter λ. At time t the number of customers in the queue is independent of the departure process prior to time t. Proof Burke first published this theorem along with a proof in 1956.[2] The theorem was anticipated but not proved by O’Brien (1954) and Morse (1955).[3][4][5] A second proof of the theorem follows from a more general result published by Reich.[6] The proof offered by Burke shows that the time intervals between successive departures are independently and exponentially distributed with parameter equal to the arrival rate parameter, from which the result follows.

Trace with departure/arrival instants highlighted in the forward/reversed time process.

An alternative proof is possible by considering the reversed process and noting that the M/M/1 queue is a reversible stochastic process.[7] Consider the figure. By Kolmogorov's criterion for reversibility, any birth-death process is a reversible Markov chain. Note that the arrival instants in the forward Markov chain are the departure instants of the reversed Markov chain. Thus the departure process is a Poisson process of rate λ. Moreover, in the forward process the arrival at time t is independent of the number of customers after t. Thus in the reversed process, the number of customers in the queue is independent of the departure process prior to time t.

This proof could be counter-intuitive, in the sense that the departure process of a birth-death process is independent of the service offered.

Related results and extensions The theorem can be generalised for "only a few cases," but remains valid for M/M/c queues and Geom/Geom/1 queues.[7] It is thought that Burke's theorem does not extend to queues fed by a Markovian arrival processes (MAP) and is conjectured that the output process of an MAP/M/1 queue is an MAP only if the queue is an M/M/1 queue.[8] An analogous theorem for the Brownian queue was proven by J. Michael Harrison.[3][9] References ^ Walrand, J. (1983). "A probabilistic look at networks of quasi-reversible queues". IEEE Transactions on Information Theory. 29 (6): 825–831. doi:10.1109/TIT.1983.1056762. ^ Burke, P. J. (1956). "The Output of a Queuing System". Operations Research. 4 (6): 699–704. doi:10.1287/opre.4.6.699. S2CID 55089958. ^ Jump up to: a b O'Connell, N.; Yor, M. (December 2001). "Brownian analogues of Burke's theorem". Stochastic Processes and Their Applications. 96 (2): 285–298. doi:10.1016/S0304-4149(01)00119-3. ^ O'Brien, G. G. (September 1954). "The Solution of Some Queueing Problems". Journal of the Society for Industrial and Applied Mathematics. 2 (3): 133–142. doi:10.1137/0102010. JSTOR 2098899. ^ Morse, P. M. (August 1955). "Stochastic Properties of Waiting Lines". Journal of the Operations Research Society of America. 3 (3): 255–261. doi:10.1287/opre.3.3.255. JSTOR 166559. ^ Reich, Edgar (1957). "Waiting Times when Queues are in Tandem". The Annals of Mathematical Statistics. 28 (3): 768–773. doi:10.1214/aoms/1177706889. ^ Jump up to: a b Hui, J. Y. (1990). "Queueing for Multi-Stage Packet Networks". Switching and Traffic Theory for Integrated Broadband Networks. The Kluwer International Series in Engineering and Computer Science. Vol. 91. pp. 313–341. doi:10.1007/978-1-4615-3264-4_11. ISBN 978-1-4613-6436-8. ^ Bean, Nigel; Green, David; Taylor, Peter (1998). "The output process of an MMPP/M/1 queue". Journal of Applied Probability. 35 (4): 998. CiteSeerX doi:10.1239/jap/1032438394. ^ Harrison, J. Michael (1985). Brownian Motion and Stochastic Flow Systems (PDF). New York: Wiley. Archived from the original (PDF) on 2012-04-14. Retrieved 2011-12-01. hide vte Queueing theory Single queueing nodes D/M/1 queueM/D/1 queueM/D/c queueM/M/1 queue Burke's theoremM/M/c queueM/M/∞ queueM/G/1 queue Pollaczek–Khinchine formulaMatrix analytic methodM/G/k queueG/M/1 queueG/G/1 queue Kingman's formulaLindley equationFork–join queueBulk queue Arrival processes Poisson point processMarkovian arrival processRational arrival process Queueing networks Jackson network Traffic equationsGordon–Newell theorem Mean value analysisBuzen's algorithmKelly networkG-networkBCMP network Service policies FIFOLIFOProcessor sharingRound-robinShortest job nextShortest remaining time Key concepts Continuous-time Markov chainKendall's notationLittle's lawProduct-form solution Balance equationQuasireversibilityFlow-equivalent server methodArrival theoremDecomposition methodBeneš method Limit theorems Fluid limitMean-field theoryHeavy traffic approximation Reflected Brownian motion Extensions Fluid queueLayered queueing networkPolling systemAdversarial queueing networkLoss networkRetrial queue Information systems Data bufferErlang (unit)Erlang distributionFlow control (data)Message queueNetwork congestionNetwork schedulerPipeline (software)Quality of serviceScheduling (computing)Teletraffic engineering Category Categories: Single queueing nodesProbability theoremsQueueing theory

Si quieres conocer otros artículos parecidos a Burke's theorem puedes visitar la categoría Probability theorems.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.


Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información