도착 정리

큐잉 이론에서, 확률의 수학적 이론, 도착^[1] 정리(랜덤 옵저버 속성, ROP 또는 작업^[2] 옵저버 속성이라고도 함)는 "정거장에 도착했을 때, 작업은 작업이 ^[3]없는 시스템을 위해 임의의 순간에 안정된 상태에 있는 것처럼 시스템을 관찰한다"고 기술한다.

도달정리는 항상 각 노드에 무제한 큐가 있는 개방형 제품형 네트워크에서 유지되지만 보다 일반적인 네트워크에서도 유지된다.제품 형태 네트워크에서 도착 정리가 충족되기 위한 필요충분조건은 1997년 Boucherie & ^[4]Dijk의 팜 확률 관점에서 제시되었다.일부 폐쇄형 네트워크에서도 같은 결과가 나타납니다.도착 정리가 유지되지 않는 제품 형태 네트워크의 예로는 가역적 킹맨^[4]^[5] 네트워크와 지연 ^[3]프로토콜을 사용하는 네트워크가 있습니다.

Mitrani는 다음과 같은 직관을 제공한다. "착신 작업에서 볼 수 있는 노드 i의 상태는 랜덤 관찰자가 볼 수 있는 상태와 다른 분포를 가진다.예를 들어, 착신 작업은 노드 i에 존재하는 모든 k개의 작업을 볼 수 없습니다.그 자체가 이미 존재하는 ^[6]작업일 수는 없기 때문입니다.

포아송 공정에 의해 제어되는 도착에 대한 정리

포아송 공정의 경우 이 속성을 종종 PASTA 속성(Poisson 도착 시간 평균 참조)이라고 하며 외부 랜덤 관측자가 볼 수 있는 상태의 확률은 ^[7]도착 고객이 볼 수 있는 상태의 확률과 동일함을 나타냅니다.또한 이 속성은 비율 매개변수가 ^[8]상태에 따라 달라질 수 있는 이중 확률적 포아송 프로세스의 경우에도 유지됩니다.

잭슨 네트워크 정리

m개의 큐가 있는 열린 잭슨 네트워크의 경우 네트워크 상태에 대해 n ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ ( ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ , ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ n ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ 2, ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ , ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ m ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ ) { $textstyle \mathbf {n}$ = ( $n_{1}, n_{2},\ldots,n_{m})$ 이라고 ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ 합니다. $(\textstyle \pi(\mathbf {n})$ 을 ${\textstyle \pi (\mathbf {n} )}$ 네트워크가 n $(\$ ${\textstyle \mathbf {n} }$ 일 평형 확률이라고 가정합니다.그 후 네트워크가 n $(\$ ${\textstyle \pi (\mathbf {n} )}$ $\mathbf {n})$ ${\textstyle \mathbf {n} }$ 일 ${\textstyle \mathbf {n} }$ 확률도 $(\textbstyle$ {n})\ $mathbf {n}$ 입니다.

이 정리는 연속 시간에서의 정상 상태를 고려하는 잭슨의 정리와 일치하지 않습니다.여기에서는 특정 시점, 즉 도착 ^[9]시간에 대해 우려하고 있습니다.이 정리는 1981년 ^[10]세빅과 미트라니에 의해 처음 발표되었다.

고든-뉴엘 네트워크에 대한 정리

m개의 큐가 있는 닫힌 Gordon-Newell 네트워크에서는 네트워크 상태에 대해 ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ ( ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ , ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ n ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ 2, ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ … , ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ m ) { $displaystyle$ { $mathbf {n$ } = ( $n$ _ { n _ { 1} , $n_{2}$ , \ $ldots$ , $n_{m}$ ) 라고 ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ 합니다.운송 중인 고객이 i $(\style$ i)를 말하는 경우, ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ i ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ $)$ (\ $displaystyle {n$ }(\ $mathbf {n}$ - $\mathbf {e}$ _ ${i}}})$ 는 ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ 고객이 도착하기 직전에 시스템 상태를 '확인'할 ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ 을 나타냅니다.

({displaystyle \mathbf {n} -\mathbf {e} _{i}=(n_{1},n_{2},\ldots,n_{i}-1,\ldots,n_{m}).}

이 ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ i ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ ( ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ - ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ ) { $displaystyle$ { $n }$ - \ $mathbf { n$ } _ { i ${\mathbf {n} -\mathbf {e} _{i}}$ } ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ } } , , this ${\mathbf {n} -\mathbf {e} _{i}}$ 。고객이 ^[11]1명 적은 같은 유형의 네트워크에 ${\mathbf {n} -\mathbf {e} _{i}}$ ${\mathbf {n} -\mathbf {e} _{i}}$ n - ${\mathbf {n} -\mathbf {e} _{i}}$ { \ $displaystyle$ { $displaystyle$ { n} - \ $mathbf$ { $n }$ _ e } _ { $e$ }그것은 Sevcik과 Mitrani,^[10] 그리고 Reiser와 Lavenberg에 ^[12]의해 독립적으로 발표되었고, 여기에서 결과는 평균값 분석을 개발하는 데 사용되었다.

메모들

^ 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.
^ ^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.
^ ^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. A.; 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.
^ ^a ^b Sevcik, K. C.; Mitrani, I. (1981). "The Distribution of Queuing Network States at Input and Output Instants". Journal of the 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". Journal of the ACM. 27 (2): 313. doi:10.1145/322186.322195.

[1] 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.

[2] El-Taha, Muhammad (1999). Sample-path Analysis of Queueing Systems. Springer. p. 94. ISBN 0-7923-8210-2.

[dijk-3] 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.

[boucherie-dijk-4] 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.

[5] 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.

[6] Mitrani, Isi (1987). Modelling of Computer and Communication Systems. CUP. p. 114. ISBN 0521314224.

[7] Wolff, R. W. (1982). "Poisson Arrivals See Time Averages". Operations Research. 30 (2): 223–231. doi:10.1287/opre.30.2.223.

[8] Van Doorn, E. A.; Regterschot, G. J. K. (1988). "Conditional PASTA" (PDF). Operations Research Letters. 7 (5): 229. doi:10.1016/0167-6377(88)90036-3.

[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.

[sevcik-10] Sevcik, K. C.; Mitrani, I. (1981). "The Distribution of Queuing Network States at Input and Output Instants". Journal of the ACM. 28 (2): 358. doi:10.1145/322248.322257.

[11] 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.

[12] Reiser, M.; Lavenberg, S. S. (1980). "Mean-Value Analysis of Closed Multichain Queuing Networks". Journal of the ACM. 27 (2): 313. doi:10.1145/322186.322195.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v t 큐잉 이론
단일 큐잉 노드	D/M/1 큐 M/D/1 큐 M/D/C 큐 M/M/1 큐 버크의 정리 M/M/c 큐 M/M/오브로드 큐 M/G/1 큐 폴라체크-킨차인 공식 매트릭스 분석법 M/G/k 큐 G/M/1 큐 G/G/1 큐 킹맨 공식 린들리 방정식 포크 결합 큐 벌크 큐
도착 프로세스	포아송 점 과정 마르코프 도착 과정 합리적인 도착 과정
네트워크 큐잉	잭슨 네트워크 트래픽 방정식 고든-뉴엘 정리 평균값 분석 부젠 알고리즘 켈리 네트워크 G네트워크 BCMP 네트워크
서비스 정책	선입선출 라이프 프로세서 공유 라운드 로빈 최단 시간 작업 최단 남은 시간
주요 개념	연속 시간 마르코프 연쇄 켄달 표기법 리틀의 법칙 제품형태솔루션 균형 방정식 준가역성 흐름 등가 서버 방식 도착 정리 분해법 베네시법
한계 정리	유체 한계 평균장 이론 혼잡한 트래픽의 근사치 반사 브라운 운동
내선번호	유체 큐 레이어드 큐잉 네트워크 폴링 시스템 적대 큐잉 네트워크 손실 네트워크 재심 큐
정보 시스템	데이터 버퍼 Erlang(유닛) 얼랑 분포 흐름 제어(데이터) 메시지 큐 네트워크 폭주 네트워크 스케줄러 파이프라인(소프트웨어) 서비스 품질 스케줄링(컴퓨팅) 텔레트래픽 공학
카테고리

Search

도착 정리

네임스페이스

더

목차

포아송 공정에 의해 제어되는 도착에 대한 정리

잭슨 네트워크 정리

고든-뉴엘 네트워크에 대한 정리

메모들