Theorem of queueing theory about instantaneous behavior at arrival times
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]) 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."[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. 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."[6]
^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.
^ abVan 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.
^ abBoucherie, 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. 6 (1). Applied Probability Trust: 1–18. doi:10.2307/3212273. JSTOR 3212273.
^Mitrani, Isi (1987). Modelling of Computer and Communication Systems. CUP. p. 114. ISBN 0521314224.
probability, the arrivaltheorem (also referred to as the random observer property, ROP or job observer property) states that "upon arrival at a station,...
1145/322186.322195. S2CID 8694947. Van Dijk, N. M. (1993). "On the arrivaltheorem for communication networks". Computer Networks and ISDN Systems. 25...
version by Lavenberg and Reiser published in 1980. It is based on the arrivaltheorem, which states that when one customer in an M-customer closed system...
of networks of queues, and generalising and applying the ideas of the theorem to search for similar product-form solutions in other networks has been...
1007/0-387-21525-5_8. ISBN 978-0-387-00211-8. Ramaswami, V. (1990). "A duality theorem for the matrix paradigms in queueing theory". Communications in Statistics...
theory of probability, a Markovian arrival process (MAP or MArP) is a mathematical model for the time between job arrivals to a system. The simplest such...
distribution Arithmetic mean Armitage–Doll multistage model of carcinogenesis Arrivaltheorem Artificial neural network Ascertainment bias ASReml – software Association...
Wn + 1 = max(0,Wn + Un) where Tn is the time between the nth and (n+1)th arrivals, Sn is the service time of the nth customer, and Un = Sn − Tn Wn is the...
traffic equations are equations that describe the mean arrival rate of traffic, allowing the arrival rates at individual nodes to be determined. Mitrani...