평균값 분석

큐잉 이론에서 확률, 평균값 분석(MVA)의 수학적 이론 내의 규율은 큐의 길이, 큐잉 노드에서의 대기 시간 및 큐의 닫힌 분리 가능한 시스템에 대한 평형 상태의 throughput을 계산하기 위한 재귀 기법이다.최초의 대략적인 기술은 슈바이처와^[1] ^[2]^[3]바드에 의해 독립적으로 출판되었고, 이후 라벤버그와 라이저에 의해 1980년에 ^[4]^[5]출판되었다.

M-Customer Closed System의 한 고객이 서비스 시설에 도착했을 때 M - 1 고객이 있는 시스템의 나머지 고객이 평형 상태에 있음을 관찰하는 도착정리에 기초한다.

문제 셋업

K M/M/1 큐의 폐쇄형 큐잉 네트워크를 검토하여 M의 고객이 시스템 내에서 순환합니다.고객이 서로 구별할 수 없기 때문에 네트워크에 단일 클래스의 고객이 있다고 가정합니다.시스템의 각 노드 및 throughput에서의 평균 큐 길이와 대기 시간을 계산하기 위해 고객 수가 0인 네트워크부터 시작하는 반복 알고리즘을 사용합니다.

고객 라우팅 매트릭스에 대해 노드 i 및 P의 서비스 레이트에 대해 μ를 쓴다_i.여기서 요소_ij p는 노드 i에서 서비스를 종료한 고객이 노드 j로 이동할 확률을 나타낸다.알고리즘을 사용하기 위해 먼저 v = v P와 같은 벡터인 방문 비율 행 벡터 v를 계산합니다.

시스템 내에 총 n명의 고객이 있는 경우 큐 i의 평균 고객 수(현재 큐 i에서 서비스되고 있는 작업 포함)에는 L(n)을, 시스템_j 내에 총 n명의 고객이 큐 i에서 소비하는 평균 시간에는 W(n)를 입력합니다_i.고객 수가 m인 시스템의 throughput을 λ로_m 나타냅니다.

알고리즘.

이^[6] 알고리즘은 빈 네트워크(고객 제로)에서 시작하여 시스템 내에 필요한 고객 수(M)가 있을 때까지 반복할 때마다 고객 수를 1씩 늘립니다.

초기화하려면 k = 1,....,K에 대해 L(0) = 0을 설정합니다_k(이것에 의해, 고객이 없는 시스템의 평균 큐 길이가, 모든 노드에 0으로 설정됩니다).

m = 1,......M에 대해 반복합니다.

1. k = 1, ...에 대하여 K는 도착정리를 이용하여 각 노드의 대기시간을 계산한다.

W_{k}(m)=flac {1+L_{k}\left(m-1\right)}{\mu _{k}}}.

2. 다음으로 리틀의 법칙을 사용하여 시스템 throughput을 계산합니다.

\displayda _{m}=displayfrac {m}{\sum _{k=1}^{K}W_{k}(m)v_{k}}}.

3. 마지막으로 각 큐에 적용되는 리틀의 법칙을 사용하여 k = 1, ..., K의 평균 큐 길이를 계산합니다.

L_{k}(m)=v_{k}\lambda_{m}W_{k}(m)

종료 반복

바르드-슈바이처법

바드-슈바이처 근사치는 노드의 평균 작업 수를 추정한다.k될^[1]^[7] 것

L_{k}(m-1)\약 {frac {m-1}{m}L_{k}(m)

선형 보간법이죠위의 공식에서 이 근사치는 수치적으로 풀 수 있는 고정점 관계를 산출합니다.이 반복적 접근법은 종종 근사 MVA(AMVA)라는 이름으로 사용되며,^[8]^{: 38} 일반적으로 MVA의 재귀적 접근법보다 빠릅니다.

유사 코드

set_k L(m) = M/K

컨버전스가 될 때까지 반복합니다.

\displayda _{m}=sum _{k=1}^{K}{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}v_{k}}}}

L_{k}(m)=v_{k}\lambda_{m}{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}

멀티클래스 네트워크

고객의 R클래스를 가지는 멀티클래스 네트워크의 경우, 멀티클래스 케이스에서의 BCMP 정리의 가정으로 선착순 스테이션의 경우에는 일정한 제약이 존재하지만, 각 큐 k는 작업 클래스 r=1,…R 마다 다른 서비스 레이트μ를_k,r 특징으로 할 수 있다.

큐 k에서 클래스 r 작업이 경험하는 대기 시간 W는_k,r 도착 정리의 일반화를 사용하여 노드 k의 총 평균 큐 길이와 여전히 관련될 수 있습니다.

{\displaystyle W_{k,r}(\mathbb {m})=flac {1+L_{k}\left(\mathbb {m} -1_{r}\right)}{\mu _{k,r}}}.

$\mathbb {m} =(m_{1},\ldots ,m_{R})$ 서 m $\mathbb {m} =(m_{1},\ldots ,m_{R})$ ( m $\mathbb {m} =(m_{1},\ldots ,m_{R})$ , $\mathbb {m} =(m_{1},\ldots ,m_{R})$ , $\mathbb {m} =(m_{1},\ldots ,m_{R})$ $\mathbb {m} =(m_{1},\ldots ,m_{R})$ ) { $displaystyle \mathbb { m$ } = ( m $_$ { $1$ , \ $ldots$ , m $_$ { $R$ } )는 $\mathbb {m} =(m_{1},\ldots ,m_{R})$ R 클래스의 고객 모집단의 $1_{r}$ 이며 $,$ $1_{r}$ 1 $1_{r}$ { $displaystyle 1$ _ { $r$ $1_{r}$ }s는 $1_{r}$ $m_{r}\geq 1$ { $displaystyle$ \ m $\mathbb {m}$ 의 r의 r에서1을 뺀다고 가정합니다 $.$

고객 클래스가 1개인 네트워크의 경우 MVA 알고리즘은 매우 고속이며, 소요 시간은 고객 수 및 큐의 수에 따라 선형적으로 증가합니다.그러나 멀티클래스 모델에서는 MVA에 대한 증배 및 추가 수와 스토리지 요구사항이 고객 클래스의 수와 함께 기하급수적으로 증가합니다.실제로는 이 알고리즘은 3-4개의 고객 ^[9]클래스에서 잘 동작하지만, 이는 일반적으로 모델의 구현과 구조에 따라 달라집니다.예를 들어 라우팅 매트릭스가 ^[10]희박한 경우 Tree-MVA 메서드는 더 큰 모델로 확장할 수 있습니다.

평균 성능 메트릭의 정확한 값은 로그 2차 시간이 필요한 모멘트 방법을 사용하여 대형 모델에서 얻을 수 있습니다.모멘트의 방법은 최대 10개의 클래스 이상의 고객이 있는 프랙티스 모델에서 해결할 수 있습니다.이러한 모델은 일반적으로 정확한 ^[9]^[11]MVA를 통해서는 액세스 할 수 없습니다.그러나 이 기술은 도착 정리를 사용하지 않고 큐잉 네트워크에 대한 상태 확률의 정규화 상수를 포함하는 선형 방정식 시스템의 해결에 의존합니다.

Bard-Schweitzer 메서드와 같은 근사 MVA(AMVA) 알고리즘은 대신 멀티클래스 네트워크에서도 복잡도가 낮고 일반적으로 매우 정확한 ^[12]결과를 제공하는 대체 솔루션 기술을 제공합니다.

내선번호

평균값 분석 알고리즘은 큐잉 네트워크 및 키 배포 ^[13]센터의 성능을 설명하는 PEPA 모델의 클래스에 적용되었습니다.

소프트웨어

JMVA는 Java로 작성된 툴로,^[14] MVA를 구현합니다.
큐잉은 MVA를 포함한 ^[15]GNU 옥타브용 라이브러리입니다.
Line(라인)은 정확하고 대략적인 MVA 알고리즘을 포함하는 MATLAB 도구 상자입니다.

「」를 참조해 주세요.

큐잉 이론

레퍼런스

^ ^a ^b Schweitzer, P. J.; Serazzi, G.; Broglia, M. (1993). "A survey of bottleneck analysis in closed networks of queues". Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science. Vol. 729. p. 491. doi:10.1007/BFb0013865. ISBN 978-3-540-57297-8.
^ Bard, Yonathan (1979). Some Extensions to Multiclass Queueing Network Analysis. Proceedings of the Third International Symposium on Modelling and Performance Evaluation of Computer Systems: Performance of Computer Systems. North-Holland Publishing Co. pp. 51–62. ISBN 978-0-444-85332-5.
^ Adan, I.; Wal, J. (2011). "Mean Values Techniques". Queueing Networks. International Series in Operations Research & Management Science. Vol. 154. p. 561. doi:10.1007/978-1-4419-6472-4_13. ISBN 978-1-4419-6471-7.
^ 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.
^ Reiser, M. (2000). "Mean Value Analysis: A Personal Account". Performance Evaluation: Origins and Directions. Lecture Notes in Computer Science. Vol. 1769. pp. 491–504. doi:10.1007/3-540-46506-5_22. ISBN 978-3-540-67193-0.
^ Bose, Sanjay K. (2001). An introduction to queueing systems. Springer. p. 174. ISBN 978-0-306-46734-9.
^ Schweitzer, Paul (1979). "Approximate analysis of multiclass closed networks of queues". Proceedings of International Conference on Stochastic Control and Optimization.
^ Tay, Y. C. (2010). "Analytical Performance Modeling for Computer Systems". Synthesis Lectures on Computer Science. 2: 1–116. doi:10.2200/S00282ED1V01Y201005CSL002.
^ ^a ^b Casale, G. (2011). "Exact analysis of performance models by the Method of Moments" (PDF). Performance Evaluation. 68 (6): 487–506. CiteSeerX 10.1.1.302.1139. doi:10.1016/j.peva.2010.12.009.
^ Hoyme, K. P.; Bruell, S. C.; Afshari, P. V.; Kain, R. Y. (1986). "A tree-structured mean value analysis algorithm". ACM Transactions on Computer Systems. 4 (2): 178–185. doi:10.1145/214419.214423.
^ Casale, G. (2008). "CoMoM: A Class-Oriented Algorithm for Probabilistic Evaluation of Multiclass Queueing Networks". IEEE Transactions on Software Engineering. 35 (2): 162–177. CiteSeerX 10.1.1.302.1139. doi:10.1016/j.peva.2010.12.009.
^ Zahorjan, John; Eager, Derek L.; Sweillam, Hisham M. (1988). "Accuracy, speed, and convergence of approximate mean value analysis". Performance Evaluation. 8 (4): 255–270. doi:10.1016/0166-5316(88)90028-4.
^ Thomas, N.; Zhao, Y. (2010). "Mean value analysis for a class of PEPA models". Comput. J. 54 (5): 643–652. doi:10.1093/comjnl/bxq064.
^ Bertoli, M.; Casale, G.; Serazzi, G. (2009). "JMT: performance engineering tools for system modeling" (PDF). ACM SIGMETRICS Performance Evaluation Review. 36 (4): 10. doi:10.1145/1530873.1530877.
^ Marzolla, M. (2014). "The Octave Queueing Package". Quantitative Evaluation of Systems. Lecture Notes in Computer Science. Vol. 8657. pp. 174–177. doi:10.1007/978-3-319-10696-0_14. ISBN 978-3-319-10695-3.

외부 링크

J. Virtamo: 큐잉 네트워크헬싱키 테크에서 제공하는 유인물로 잭슨의 정리 및 MVA의 개요를 알 수 있습니다.
Simon Lam: MVA 알고리즘의 단순한 파생입니다.Buzen의 알고리즘과 MVA의 관계를 나타냅니다.

[Schweitzer-1] Schweitzer, P. J.; Serazzi, G.; Broglia, M. (1993). "A survey of bottleneck analysis in closed networks of queues". Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science. Vol. 729. p. 491. doi:10.1007/BFb0013865. ISBN 978-3-540-57297-8.

[2] Bard, Yonathan (1979). Some Extensions to Multiclass Queueing Network Analysis. Proceedings of the Third International Symposium on Modelling and Performance Evaluation of Computer Systems: Performance of Computer Systems. North-Holland Publishing Co. pp. 51–62. ISBN 978-0-444-85332-5.

[3] Adan, I.; Wal, J. (2011). "Mean Values Techniques". Queueing Networks. International Series in Operations Research & Management Science. Vol. 154. p. 561. doi:10.1007/978-1-4419-6472-4_13. ISBN 978-1-4419-6471-7.

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

[5] Reiser, M. (2000). "Mean Value Analysis: A Personal Account". Performance Evaluation: Origins and Directions. Lecture Notes in Computer Science. Vol. 1769. pp. 491–504. doi:10.1007/3-540-46506-5_22. ISBN 978-3-540-67193-0.

[6] Bose, Sanjay K. (2001). An introduction to queueing systems. Springer. p. 174. ISBN 978-0-306-46734-9.

[7] Schweitzer, Paul (1979). "Approximate analysis of multiclass closed networks of queues". Proceedings of International Conference on Stochastic Control and Optimization.

[8] Tay, Y. C. (2010). "Analytical Performance Modeling for Computer Systems". Synthesis Lectures on Computer Science. 2: 1–116. doi:10.2200/S00282ED1V01Y201005CSL002.

[casale-9] Casale, G. (2011). "Exact analysis of performance models by the Method of Moments" (PDF). Performance Evaluation. 68 (6): 487–506. CiteSeerX 10.1.1.302.1139. doi:10.1016/j.peva.2010.12.009.

[hoyme-10] Hoyme, K. P.; Bruell, S. C.; Afshari, P. V.; Kain, R. Y. (1986). "A tree-structured mean value analysis algorithm". ACM Transactions on Computer Systems. 4 (2): 178–185. doi:10.1145/214419.214423.

[casale2-11] Casale, G. (2008). "CoMoM: A Class-Oriented Algorithm for Probabilistic Evaluation of Multiclass Queueing Networks". IEEE Transactions on Software Engineering. 35 (2): 162–177. CiteSeerX 10.1.1.302.1139. doi:10.1016/j.peva.2010.12.009.

[12] Zahorjan, John; Eager, Derek L.; Sweillam, Hisham M. (1988). "Accuracy, speed, and convergence of approximate mean value analysis". Performance Evaluation. 8 (4): 255–270. doi:10.1016/0166-5316(88)90028-4.

[13] Thomas, N.; Zhao, Y. (2010). "Mean value analysis for a class of PEPA models". Comput. J. 54 (5): 643–652. doi:10.1093/comjnl/bxq064.

[14] Bertoli, M.; Casale, G.; Serazzi, G. (2009). "JMT: performance engineering tools for system modeling" (PDF). ACM SIGMETRICS Performance Evaluation Review. 36 (4): 10. doi:10.1145/1530873.1530877.

[15] Marzolla, M. (2014). "The Octave Queueing Package". Quantitative Evaluation of Systems. Lecture Notes in Computer Science. Vol. 8657. pp. 174–177. doi:10.1007/978-3-319-10696-0_14. ISBN 978-3-319-10695-3.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

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

평균값 분석

네임스페이스

더

목차

문제 셋업

알고리즘.

바르드-슈바이처법

유사 코드

멀티클래스 네트워크

내선번호

소프트웨어

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

평균값 분석

문제 셋업

알고리즘.

바르드-슈바이처법

유사 코드

멀티클래스 네트워크

내선번호

소프트웨어

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.