Arrival theorem

Arrival theorem In queueing theory, a discipline within the mathematical theory of probability, the arrival theorem[1] (also referred to as the random observer property, ROP or job observer property[2]) afferma che "upon arrival at a station, a job observes the system as if in steady state at an arbitrary instant for the system without that job."[3] The arrival theorem always holds in open product-form networks with unbounded queues at each node, but it also holds in more general networks. A necessary and sufficient condition for the arrival theorem to be satisfied in product-form networks is given in terms of Palm probabilities in Boucherie & Dijk, 1997.[4] A similar result also holds in some closed networks. Examples of product-form networks where the arrival theorem does not hold include reversible Kingman networks[4][5] and networks with a delay protocol.[3] Mitrani offers the intuition that "The state of node i as seen by an incoming job has a different distribution from the state seen by a random observer. Per esempio, an incoming job can never see all 'k jobs present at node i, because it itself cannot be among the jobs already present."[6] Contenuti 1 Theorem for arrivals governed by a Poisson process 2 Theorem for Jackson networks 3 Theorem for Gordon–Newell networks 4 Notes Theorem for arrivals governed by a Poisson process For Poisson processes the property is often referred to as the PASTA property (Poisson Arrivals See Time Averages) and states that the probability of the state as seen by an outside random observer is the same as the probability of the state seen by an arriving customer.[7] The property also holds for the case of a doubly stochastic Poisson process where the rate parameter is allowed to vary depending on the state.[8] Theorem for Jackson networks In an open Jackson network with m queues, write {textstyle mathbf {n} =(n_{1},n_{2},ldot ,n_{m})} for the state of the network. Supponiamo {textstyle pi (mathbf {n} )} is the equilibrium probability that the network is in state {textstyle mathbf {n} } . Then the probability that the network is in state {textstyle mathbf {n} } immediately before an arrival to any node is also {textstyle pi (mathbf {n} )} .

Note that this theorem does not follow from Jackson's theorem, where the steady state in continuous time is considered. Here we are concerned with particular points in time, namely arrival times.[9] This theorem first published by Sevcik and Mitrani in 1981.[10] Theorem for Gordon–Newell networks In a closed Gordon–Newell network with m queues, write {stile di visualizzazione {mathbf {n} =(n_{1},n_{2},ldot ,n_{m})}} for the state of the network. For a customer in transit to state {stile di visualizzazione i} , permettere {stile di visualizzazione {alfa _{io}(mathbf {n} -mathbf {e} _{io})}} denote the probability that immediately before arrival the customer 'sees' the state of the system to be {displaystyle mathbf {n} -mathbf {e} _{io}=(n_{1},n_{2},ldot ,n_{io}-1,ldot ,n_{m}).} This probability, {stile di visualizzazione {alfa _{io}(mathbf {n} -mathbf {e} _{io})}} , is the same as the steady state probability for state {stile di visualizzazione {mathbf {n} -mathbf {e} _{io}}} for a network of the same type with one customer less.[11] It was published independently by Sevcik and Mitrani,[10] and Reiser and Lavenberg,[12] where the result was used to develop mean value analysis.

Notes ^ Asmussen, Søren (2003). "Queueing Networks and Insensitivity". Applied Probability and Queues. Stochastic Modelling and Applied Probability. vol. 51. pp. 114–136. doi:10.1007/0-387-21525-5_4. ISBN 978-0-387-00211-8. ^ El-Taha, Muhammad (1999). Sample-path Analysis of Queueing Systems. Springer. p. 94. ISBN 0-7923-8210-2. ^ Salta su: a b Van Dijk, N. M. (1993). "On the arrival theorem for communication networks". Computer Networks and ISDN Systems. 25 (10): 1135–2013. doi:10.1016/0169-7552(93)90073-D. ^ Salta su: a b Boucherie, R. J.; Van Dijk, N. M. (1997). "On the arrivai theorem for product form queueing networks with blocking". Performance Evaluation. 29 (3): 155. doi:10.1016/S0166-5316(96)00045-4. ^ Kingman, J. F. C. (1969). "Markov Population Processes". Journal of Applied Probability. Applied Probability Trust. 6 (1): 1–18. doi:10.2307/3212273. JSTOR 3212273. ^ Mitrani, Isi (1987). Modelling of Computer and Communication Systems. CUP. p. 114. ISBN 0521314224. ^ Wolff, R. w. (1982). "Poisson Arrivals See Time Averages". Operations Research. 30 (2): 223–231. doi:10.1287/opre.30.2.223. ^ Van Doorn, e. UN.; Regterschot, G. J. K. (1988). "Conditional PASTA" (PDF). Operations Research Letters. 7 (5): 229. doi:10.1016/0167-6377(88)90036-3. ^ Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. p. 228. ISBN 0-201-54419-9. ^ Salta su: a b Sevcik, K. C.; Mitrani, io. (1981). "The Distribution of Queuing Network States at Input and Output Instants". Giornale dell'ACM. 28 (2): 358. doi:10.1145/322248.322257. ^ Breuer, l.; Baum, Dave (2005). "Markovian Queueing Networks". An Introduction to Queueing Theory and Matrix-Analytic Methods. pp. 63–61. doi:10.1007/1-4020-3631-0_5. ISBN 1-4020-3630-2. ^ Reiser, M.; Lavenberg, S. S. (1980). "Mean-Value Analysis of Closed Multichain Queuing Networks". Giornale dell'ACM. 27 (2): 313. doi:10.1145/322186.322195. 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: Queueing theoryProbability theorems