Arrival theorem

{{Short description|Theorem of queueing theory about instantaneous behavior at arrival times}}

In queueing theory, a discipline within the mathematical theory of probability, the arrival theorem{{Cite book | first1 = Søren | last1 = Asmussen| doi = 10.1007/0-387-21525-5_4 | chapter = Queueing Networks and Insensitivity | title = Applied Probability and Queues | series = Stochastic Modelling and Applied Probability | volume = 51 | pages = 114–136 | year = 2003 | isbn = 978-0-387-00211-8 }} (also referred to as the random observer property, ROP or job observer property{{cite book|title=Sample-path Analysis of Queueing Systems|url=https://archive.org/details/samplepathanalys00elta|url-access=limited|first=Muhammad|last=El-Taha|publisher=Springer|year=1999|isbn=0-7923-8210-2|page=[https://archive.org/details/samplepathanalys00elta/page/n105 94]}}) states that "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."{{Cite journal | last1 = Van Dijk | first1 = N. M. | title = On the arrival theorem for communication networks | doi = 10.1016/0169-7552(93)90073-D | journal = Computer Networks and ISDN Systems | volume = 25 | issue = 10 | pages = 1135–2013 | year = 1993 | url = https://research.vu.nl/ws/files/73611045/Scanjob%20199100081 }}

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. 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{{Cite journal | last1 = Boucherie | first1 = R. J. | last2 = Van Dijk | first2 = N. M. | doi = 10.1016/S0166-5316(96)00045-4 | title = On the arrivai theorem for product form queueing networks with blocking | journal = Performance Evaluation | volume = 29 | issue = 3 | pages = 155 | year = 1997 }}{{cite journal | last1 = Kingman | first1 = J. F. C. | author-link1 = John Kingman | year = 1969 | title = Markov Population Processes | journal = Journal of Applied Probability | volume = 6 | issue = 1 | pages = 1–18 | publisher = Applied Probability Trust | jstor = 3212273| doi = 10.2307/3212273 }} and networks with a delay protocol.

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. For instance, an incoming job can never see all 'k jobs present at node i, because it itself cannot be among the jobs already present."{{cite book | page = [https://archive.org/details/modellingofcompu0000mitr/page/114 114] | title = Modelling of Computer and Communication Systems | first = Isi | last = Mitrani | publisher = CUP | year = 1987 | isbn = 0521314224 | url = https://archive.org/details/modellingofcompu0000mitr/page/114 }}

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.{{Cite journal | last1 = Wolff | first1 = R. W. | title = Poisson Arrivals See Time Averages | doi = 10.1287/opre.30.2.223 | journal = Operations Research | volume = 30 | issue = 2 | pages = 223–231 | year = 1982 }} 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.{{Cite journal | last1 = Van Doorn | first1 = E. A. | last2 = Regterschot | first2 = G. J. K. | doi = 10.1016/0167-6377(88)90036-3 | title = Conditional PASTA | journal = Operations Research Letters | url = http://doc.utwente.nl/70043/1/Doorn88conditional.pdf| volume = 7 | issue = 5 | pages = 229 | year = 1988 }}

Theorem for Jackson networks

In an open Jackson network with m queues, write $\mathbf{n} = (n_1, n_2, \ldots, n_m)$ for the state of the network. Suppose $\pi(\mathbf{n})$ is the equilibrium probability that the network is in state $\mathbf{n}$ . Then the probability that the network is in state $\mathbf{n}$ immediately before an arrival to any node is also $\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.{{cite book|first1=Peter G.|last1=Harrison|author-link1=Peter G. Harrison|first2=Naresh M.|last2=Patel|title=Performance Modelling of Communication Networks and Computer Architectures|publisher=Addison-Wesley|year=1992|page=[https://archive.org/details/performancemodel0000harr/page/228 228]|isbn=0-201-54419-9|url-access=registration|url=https://archive.org/details/performancemodel0000harr/page/228}} This theorem first published by Sevcik and Mitrani in 1981.

Theorem for Gordon–Newell networks

In a closed Gordon–Newell network with m queues, write ${\mathbf{n} = (n_1, n_2, \ldots, n_m)}$ for the state of the network. For a customer in transit to state $i$ , let ${\alpha_i(\mathbf{n}-\mathbf{e}_i)}$ denote the probability that immediately before arrival the customer 'sees' the state of the system to be

: $\mathbf{n}-\mathbf{e}_i = (n_1,n_2,\ldots,n_i - 1,\ldots,n_m).$

This probability, ${\alpha_i(\mathbf{n}-\mathbf{e}_i)}$ , is the same as the steady state probability for state ${\mathbf{n}-\mathbf{e}_i}$ for a network of the same type with one customer less.{{Cite book | first1 = L. | last1 = Breuer| first2 = Dave | last2 = Baum| doi = 10.1007/1-4020-3631-0_5 | chapter = Markovian Queueing Networks | title = An Introduction to Queueing Theory and Matrix-Analytic Methods | url = https://archive.org/details/introductiontoqu00lbre | url-access = limited | pages = [https://archive.org/details/introductiontoqu00lbre/page/n74 63]–61 | year = 2005 | isbn = 1-4020-3630-2 }} It was published independently by Sevcik and Mitrani,{{Cite journal | last1 = Sevcik | first1 = K. C. | last2 = Mitrani | first2 = I. | doi = 10.1145/322248.322257 | title = The Distribution of Queuing Network States at Input and Output Instants | journal = Journal of the ACM | volume = 28 | issue = 2 | pages = 358 | year = 1981 | doi-access = free }} and Reiser and Lavenberg,{{Cite journal | last1 = Reiser | first1 = M.| last2 = Lavenberg | first2 = S. S. | doi = 10.1145/322186.322195 | title = Mean-Value Analysis of Closed Multichain Queuing Networks | journal = Journal of the ACM| volume = 27 | issue = 2 | pages = 313 | year = 1980 | doi-access = free }} where the result was used to develop mean value analysis.

Notes

Category:Queueing theory

Category:Theorems in probability theory