마르코프 도착 과정

Markovian arrival process

큐잉 이론에서 마르코프 도착 과정(MAP 또는 MARP[1])은 확률의 수학적 이론 내의 학문이다.이러한 가장 간단한 공정은 각 도착 사이의 시간이 기하급수적으로 [2][3]분포되는 포아송 공정입니다.

그 과정은 1979년에 [2][4]뉴트럴스에 의해 처음 제안되었다.

정의.

마르코프 도착 프로세스는 D의 요소0 숨겨진 천이를 나타내고 D의 관측 가능한 천이의 요소1 나타내는 2개의 행렬0 D1 D에 의해 정의된다.아래의 블록 행렬 Q는 연속 시간 마르코프 [5]사슬에 대한 전이율 행렬이다.

가장 간단한 예제는 포아송 공정으로, 가능0 전환이 하나만 있는 경우 D = -disc 및 D1 = θ이며, 관측 가능하고 속도 θ에서 발생합니다.Q가 유효한 전이율 매트릭스인 경우 D에는i 다음 제약사항이 적용됩니다.

특수한 경우

마르코프 변조 포아송 과정

m 포아송 프로세스가 기본 연속 시간 마르코프 [6]체인에 의해 전환되는 마르코프 변조 포아송 프로세스 또는 MMPP.각각의 m 포아송 프로세스가 속도 θi 가지며 변조 연속 시간 마르코프 행렬 R이 m × m 전이 속도 행렬 R을 가지면 MAP 표현은 다음과 같다.

단계형 갱신 프로세스

위상 유형 갱신 프로세스는 마르코프 도착 프로세스이며, 도착 간 위상 유형 분산 체류이다.를 들어 도착 프로세스에 시간 분포 PH ){\{alpha } {{ {{{\ {1}})가 있는 경우 도착 프로세스 생성기는 매트릭스를 가집니다.

배치 마르코프 도착 과정

배치 마르코프 도착 과정(BMAP)은 한 [7]번에 두 개 이상의 도착을 허용함으로써 마르코프 도착 과정을 일반화한다.[8] 동종 케이스는 비율 매트릭스를 가지고 있습니다.

k(\ k Dk(\에서 천이가 발생할 때마다 발생합니다. 다음과 같이 포아송 프로세스의 비율인 _의 요소를 가집니다.

그리고.

피팅

MAP은 기대 최대화 [9]알고리즘을 사용하여 장착할 수 있습니다.

소프트웨어

  • KPC 툴박스는 MATLAB 스크립트 라이브러리를 사용하여 [10]MAP을 데이터에 맞춥니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Asmussen, S. R. (2003). "Markov Additive Models". Applied Probability and Queues. Stochastic Modelling and Applied Probability. Vol. 51. pp. 302–339. doi:10.1007/0-387-21525-5_11. ISBN 978-0-387-00211-8.
  2. ^ a b Asmussen, S. (2000). "Matrix-analytic Models and their Analysis". Scandinavian Journal of Statistics. 27 (2): 193–226. doi:10.1111/1467-9469.00186. JSTOR 4616600.
  3. ^ Chakravarthy, S. R. (2011). "Markovian Arrival Processes". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0499. ISBN 9780470400531.
  4. ^ Neuts, Marcel F. (1979). "A Versatile Markovian Point Process". Journal of Applied Probability. Applied Probability Trust. 16 (4): 764–779. doi:10.2307/3213143. JSTOR 3213143.
  5. ^ Casale, G. (2011). "Building accurate workload models using Markovian arrival processes". ACM SIGMETRICS Performance Evaluation Review. 39: 357. doi:10.1145/2007116.2007176.
  6. ^ Fischer, W.; Meier-Hellstern, K. (1993). "The Markov-modulated Poisson process (MMPP) cookbook". Performance Evaluation. 18 (2): 149. doi:10.1016/0166-5316(93)90035-S.
  7. ^ Lucantoni, D. M. (1993). "The BMAP/G/1 queue: A tutorial". Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science. Vol. 729. pp. 330–358. doi:10.1007/BFb0013859. ISBN 3-540-57297-X.
  8. ^ Singh, Gagandeep; Gupta, U. C.; Chaudhry, M. L. (2016). "Detailed computational analysis of queueing-time distributions of the BMAP/G/1 queue using roots". Journal of Applied Probability. 53 (4): 1078–1097. doi:10.1017/jpr.2016.66. S2CID 27505255.
  9. ^ Buchholz, P. (2003). "An EM-Algorithm for MAP Fitting from Real Traffic Data". Computer Performance Evaluation. Modelling Techniques and Tools. Lecture Notes in Computer Science. Vol. 2794. pp. 218–236. doi:10.1007/978-3-540-45232-4_14. ISBN 978-3-540-40814-7.
  10. ^ Casale, G.; Zhang, E. Z.; Smirni, E. (2008). "KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes" (PDF). 2008 Fifth International Conference on Quantitative Evaluation of Systems. p. 83. doi:10.1109/QEST.2008.33. ISBN 978-0-7695-3360-5. S2CID 252444.