Arrival theorem: Difference between revisions

Edit links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
→‎Theorem for Gordon–Newell networks: use template for reference
use template for ref
Line 1: Line 1:
In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]], the '''arrival theorem'''<ref>{{cite book|title=Applied Probability and Queues|first=Søren|last=Asmussen|publisher=Springer|year=2003|isbn=0-387-00211-1|page=134}}</ref> (also referred to as the '''random observer property''', '''ROP''' or '''job observer property'''<ref>{{cite book|title=Sample-path Analysis of Queueing Systems|first=Muhammad|last=El-Taha|publisher=Springer|year=1999|isbn=0-7923-8210-2|page=94}}</ref>) 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."<ref name="dijk">{{cite doi|10.1016/0169-7552(93)90073-D}}</ref>
In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]], the '''arrival theorem'''<ref>{{cite doi|10.1007/0-387-21525-5_4}}</ref> (also referred to as the '''random observer property''', '''ROP''' or '''job observer property'''<ref>{{cite book|title=Sample-path Analysis of Queueing Systems|first=Muhammad|last=El-Taha|publisher=Springer|year=1999|isbn=0-7923-8210-2|page=94}}</ref>) 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."<ref name="dijk">{{cite doi|10.1016/0169-7552(93)90073-D}}</ref>


The arrival theorem always holds in open [[product-form solution|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.<ref name=boucherie-dijk /> 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<ref name=boucherie-dijk>{{cite doi|10.1016/S0166-5316(96)00045-4}}</ref><ref>{{cite jstor|3212273}}</ref> and networks with a delay protocol.<ref name="dijk" />
The arrival theorem always holds in open [[product-form solution|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.<ref name=boucherie-dijk /> 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<ref name=boucherie-dijk>{{cite doi|10.1016/S0166-5316(96)00045-4}}</ref><ref>{{cite jstor|3212273}}</ref> and networks with a delay protocol.<ref name="dijk" />

Revision as of 20:42, 18 March 2013

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 intution 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]

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 for the state of the network. Suppose is the equilibrium probability that the network is in state . Then the probability that the network is in state immediately before an arrival to any node is also .

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 for the state of the network. For a customer in transit to state i, let denote the probability that immediately before arrival the customer 'sees' the state of the system to be

This probability, , is the same as the steady state probability for state 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

  1. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/0-387-21525-5_4, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/0-387-21525-5_4 instead.
  2. ^ El-Taha, Muhammad (1999). Sample-path Analysis of Queueing Systems. Springer. p. 94. ISBN 0-7923-8210-2.
  3. ^ a b Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0169-7552(93)90073-D, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0169-7552(93)90073-D instead.
  4. ^ a b Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/S0166-5316(96)00045-4, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/S0166-5316(96)00045-4 instead.
  5. ^ Attention: This template ({{cite jstor}}) is deprecated. To cite the publication identified by jstor:3212273, please use {{cite journal}} with |jstor=3212273 instead.
  6. ^ Mitrani, Isi (1987). Modelling of Computer and Communication Systems. CUP. p. 114. ISBN 0521314224.
  7. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1287/opre.30.2.223, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1287/opre.30.2.223 instead.
  8. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1016/0167-6377(88)90036-3, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1016/0167-6377(88)90036-3 instead.
  9. ^ Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. p. 228. ISBN 0-201-54419-9.
  10. ^ a b Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/322248.322257, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/322248.322257 instead.
  11. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1007/1-4020-3631-0_5, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1007/1-4020-3631-0_5 instead.
  12. ^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/322186.322195, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/322186.322195 instead.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Arrival_theorem&oldid=545269918"