폴링 시스템

Polling system
n개의 큐잉노드를 처리하는 폴링 서버

큐잉 이론에서 확률의 수학적 이론, 폴링 시스템 또는 폴링 모델 내의 부문은 단일 서버가 일련의 큐를 일정한 [1]순서로 방문하는 시스템입니다.이 모델은 컴퓨터 네트워크 및 통신,[2] 제조[3][4]도로 교통 관리에 응용 프로그램을 갖추고 있습니다.폴링 시스템이라는 용어는 적어도 1968년에[5][6] 만들어졌으며 1957년에 영국 면화 산업의 단일 수리공 서비스 기계를 [7]모델링한 이러한 시스템에 대한 최초의 연구이다.

일반적으로 서버는 다른 큐를 순회적으로 [1]방문한다고 가정합니다.특정 [9]모델에서는 폴링 에폭에서의 대기시간, 한계 큐 길이 및 조인트큐[8] 길이에 대한 정확한 결과가 존재합니다.평균값 분석 기법을 적용하여 평균수량을 [10]계산할 수 있습니다.

유체 한계에서는 매우 많은 수의 작은 작업이 도달하는 개별 노드가 유체 대기열과 유사하게 동작하는 것을 볼 수 있습니다(2가지 상태 프로세스).[11]

모델 정의

n개의 큐 그룹이 1개의 서버에 의해 처리됩니다.일반적으로 순환순서는 1, 2, …, n, 1, …입니다.새로운 작업은 레이트 θi 포아송 프로세스에 따라 큐 i에 도착하여 각 작업이 독립적으로 동일한 분포의 랜덤 변수i S로 나타나는 서비스 시간을 가지며 선착순으로 처리된다.

서버는 다음 [12]기준 중 하나에 따라 다음 노드로 진행할 시기를 선택합니다.

  • expective service 버퍼가 비워질 때까지 노드가 서비스를 계속 수신합니다.
  • 게이트 서비스: 노드가 서버가 도착하여 서비스를 시작한 시점에서 존재했던 모든 트래픽을 처리합니다.단, 이 서비스 시간 동안 이후의 도착은 다음 서버 방문까지 기다려야 합니다.
  • 서버가 방문할 때마다 [13]최대 고정 수의 작업을 수행할 수 있는 제한된 서비스입니다.

큐잉 노드가 비어 있는 경우 서버는 즉시 다음 큐잉노드에 서비스를 제공하기 위해 이동합니다.

노드 i - 1 및 노드i에서 전환하는데 걸리는 시간은 랜덤 변수i d로 나타납니다.

이용률

ρi = λi E(Si)를 정의하고 = ρ12 + + + … + ρ으로n 적습니다.다음으로 is은 서버가 고객 [14]응대에 소비하는 시간의 장기 비율입니다.

대기시간

예상 대기시간

게이트 서비스의 경우 노드 i에서의[12] 예상 대기 시간은 다음과 같습니다.

철저한 서비스를 위해

여기i C는 노드i[15] 노드i 사이의 시간을 나타내는 랜덤 변수입니다.

Ci 분산은 더 복잡하며 간단한 계산을 위해서는 n개의 선형 방정식2 n개의 미지수를 [16]풀어야2 하지만 n개의 [17]방정식으로 계산하는 것은 가능하다.

교통량이 많다

워크로드 프로세스는 서버 전환이 즉시[18] 이루어지는 경우 부하가 높고 적절하게 확장되는 시스템에서 브라운 모션을 반영하여 추정할 수 있으며, 서버 전환에 [19]시간이 걸리는 경우 베셀 프로세스에 의해 추정할 수 있습니다.

적용들

폴링 시스템은 토큰링 네트워크의 [20]모델화에 사용되고 있습니다.

외부 링크

레퍼런스

  1. ^ a b Boxma, O. J.; Weststrate, J. A. (1989). "Waiting Times in Polling Systems with Markovian Server Routing". Messung, Modellierung und Bewertung von Rechensystemen und Netzen. Informatik-Fachberichte. Vol. 218. p. 89. doi:10.1007/978-3-642-75079-3_8. ISBN 978-3-540-51713-9.
  2. ^ Carsten, R.; Newhall, E.; Posner, M. (1977). "A Simplified Analysis of Scan Times in an Asymmetrical Newhall Loop with Exhaustive Service". IEEE Transactions on Communications. 25 (9): 951. doi:10.1109/TCOM.1977.1093936.
  3. ^ Karmarkar, U. S. (1987). "Lot Sizes, Lead Times and In-Process Inventories". Management Science. 33 (3): 409–418. doi:10.1287/mnsc.33.3.409. JSTOR 2631860.
  4. ^ Zipkin, P. H. (1986). "Models for Design and Control of Stochastic, Multi-Item Batch Production Systems". Operations Research. 34 (1): 91–104. doi:10.1287/opre.34.1.91. JSTOR 170674.
  5. ^ Leibowitz, M. A. (1968). "Queues". Scientific American. 219 (2): 96–103. doi:10.1038/scientificamerican0868-96.
  6. ^ Takagi, H. (2000). "Analysis and Application of Polling Models". Performance Evaluation: Origins and Directions. LNCS. Vol. 1769. pp. 423–442. doi:10.1007/3-540-46506-5_18. hdl:2241/530. ISBN 978-3-540-67193-0.
  7. ^ Mack, C.; Murphy, T.; Webb, N. L. (1957). "The Efficiency of N Machines Uni-Directionally Patrolled by One Operative when Walking Time and Repair Times are Constants". Journal of the Royal Statistical Society. Series B (Methodological). 19 (1): 166–172. doi:10.1111/j.2517-6161.1957.tb00253.x. JSTOR 2984003.
  8. ^ Resing, J. A. C. (1993). "Polling systems and multitype branching processes". Queueing Systems. 13 (4): 409–426. doi:10.1007/BF01149263.
  9. ^ Borst, S. C. (1995). "Polling systems with multiple coupled servers" (PDF). Queueing Systems. 20 (3–4): 369–393. doi:10.1007/BF01245325.
  10. ^ Wierman, A.; Winands, E. M. M.; Boxma, O. J. (2007). "Scheduling in polling systems" (PDF). Performance Evaluation. 64 (9–12): 1009. CiteSeerX 10.1.1.486.2326. doi:10.1016/j.peva.2007.06.015.
  11. ^ Czerniak, O.; Yechiali, U. (2009). "Fluid polling systems" (PDF). Queueing Systems. 63 (1–4): 401–435. doi:10.1007/s11134-009-9129-6.
  12. ^ a b Everitt, D. (1986). "Simple Approximations for Token Rings". IEEE Transactions on Communications. 34 (7): 719–721. doi:10.1109/TCOM.1986.1096599.
  13. ^ Takagi, H. (1988). "Queuing analysis of polling models". ACM Computing Surveys. 20: 5–28. doi:10.1145/62058.62059.
  14. ^ Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press. ISBN 9781439806586.
  15. ^ Eisenberg, M. (1972). "Queues with Periodic Service and Changeover Time". Operations Research. 20 (2): 440–451. doi:10.1287/opre.20.2.440. JSTOR 169005.
  16. ^ Ferguson, M. (1986). "Computation of the Variance of the Waiting Time for Token Rings". IEEE Journal on Selected Areas in Communications. 4 (6): 775–782. doi:10.1109/JSAC.1986.1146407.
  17. ^ Sarkar, D.; Zangwill, W. I. (1989). "Expected Waiting Time for Nonsymmetric Cyclic Queueing Systems—Exact Results and Applications". Management Science. 35 (12): 1463. doi:10.1287/mnsc.35.12.1463. JSTOR 2632232.
  18. ^ Coffman, E. G.; Puhalskii, A. A.; Reiman, M. I. (1995). "Polling Systems with Zero Switchover Times: A Heavy-Traffic Averaging Principle". The Annals of Applied Probability. 5 (3): 681. doi:10.1214/aoap/1177004701. JSTOR 2245120.
  19. ^ Coffman, E. G.; Puhalskii, A. A.; Reiman, M. I. (1998). "Polling Systems in Heavy Traffic: A Bessel Process Limit". Mathematics of Operations Research. 23 (2): 257. CiteSeerX 10.1.1.27.6730. doi:10.1287/moor.23.2.257. JSTOR 3690512.
  20. ^ Bux, W. (1989). "Token-ring local-area networks and their performance". Proceedings of the IEEE. 77 (2): 238–256. doi:10.1109/5.18625.