M/D/1 큐

큐잉 이론에서 M/D/1 큐는 단일 서버를 가진 시스템에서 큐 길이를 나타내며, 여기서 도착은 포아송 프로세스에 의해 결정되고 작업 서비스 시간은 고정된다(결정론적).모델명은 Kendall 표기법으로 ^[1]기재되어 있습니다.Agner Krarup Erlang은 1909년에 큐잉 ^[2][3]이론의 주제를 시작하며 이 모델에 대해 처음 발표했다.여러 서버를 가진 이 모델의 확장은 M/D/c 큐입니다.

모델 정의

M/D/1 큐는 상태 공간이 집합 {0,1,2,3,...인 확률 프로세스입니다.}. 이 값은 현재 사용 중인 엔티티 수를 포함하여 시스템의 엔티티 수에 해당합니다.

• 도착은 포아송 공정에 따라 θ 비율로 발생하며 공정이 상태 i에서 i + 1로 이동합니다.
• 서비스 시간은 결정론적 시간 D(환율 μ = 1/D로 제공)입니다.
• 단일 서버는 선착순 규칙에 따라 큐의 앞쪽에서 한 번에 하나씩 엔티티를 처리합니다.서비스가 완료되면 엔티티는 큐에서 탈퇴하고 시스템 내의 엔티티 수는 1개 줄어듭니다.
• 버퍼는 무한 크기이므로 포함할 수 있는 엔티티 수에 제한이 없습니다.

이행 매트릭스

도달 레이트와 서비스 시간 1을 가지는 M/D/1 큐의 전이 확률 매트릭스(^[4]큐의 안정성을 위해)는 다음과 같이 P에 의해 주어집니다.

$display style$$0$$\\a_{0}&a_{1}&a_{2}&a_{3}&...$$\\0&a_{0}&a_{1}&a_{2}&...$$\\0&a_{0}&a_{1}&...$$\\...&...&...&...&...$$\\\end${pmatrix$}}$ = $a{\displaystyle {}_{}}$ ${\displaystyle n_{}\frac{}{}{}_{}}$ ${\displaystyle \frac{}{}{}^{}}$-$$（ $displaystyle$ a$_$ { n } =$flac$ {$displayda$^ { $n$} { n ） 。$}}e$^{-\$lambda$}}}, n = 0,1,....

클래식한 퍼포먼스 지표

다음 표현은 M/D/1과 같은 단일 서버 큐잉 시스템의 표준 성능 메트릭을 나타냅니다.

• 도착률 $={\displaystyle }$ \ $displaystyle$= \ $displayda$ ,
• 서비스 ${\displaystyle \mathrm{레이트}}$ $=$μ {\$displaystyle$ =\$mu$
• 사용률 $={\displaystyle }$ ${\displaystyle \mathrm{사용률}}$ ${\displaystyle =}$ ${\displaystyle \frac{\mathrm{사용률}}{}}$ {\$displaystyle$ =\$rho$= 사용률 $frac {\mu }}$

시스템의 평균 엔티티 수 L은 다음과 같이 표시됩니다.

$({displaystyle L=\rho +{\frac {1}{2}}\frac {rho ^{2}}{1-\rho }}\오른쪽);}$

큐(행)의 평균 엔티티 수_Q(L)는 다음과 같습니다.

$({displaystyle L_{Q}=frac {1}{2}}\leftfrac {rho ^{2}}{1-\rho }}\right);}$

시스템의 평균 대기시간 is은 다음과 같이 표시됩니다.

${\displaystyle \omega = prac {1}{\mu }}+{\frac {rho }{2\mu (1-\rho)}};}$

큐(회선)의 평균 대기시간은 다음과 같습니다.

${\displaystyle \mega _{Q}=snarfrac {rho }{2\mu (1-\rho)}}$

예

서버가 1대뿐인 시스템에 대해 시간당 엔티티 20개, 서비스 레이트가 시간당 30개로 일정하다고 가정합니다.

따라서 서버의 사용률은 "=20/30=2/3" 입니다.위의 메트릭을 사용하면 1) L라인의_Q 평균수 = 0.6667, 2) L라인의 평균수 = 1.333, 3) L라인의 평균시간 ω_Q = 0.033시간, 4) 시스템 평균시간 ω = 0.067시간이 됩니다.

M/M/1 및 M/D/1 큐의 평균 대기 시간 관계

평형 M/G/1 큐의 경우 고객이 큐에서 보낸 시간 W의 예상값은 ^[5]다음과 같은 Pollaczek-Khintchine 공식으로 제공됩니다.

${\displaystyle E(W)=frac {2(1-\rho)}}\left(1+{\frac ^{2}}{\frac ^{2}}\right}$

여기서 τ 、 is² 、 is 、 is 、 λ 、 λ time = ;; <1, being the the the;;;;; time time the the the the the the 고객의 도착 레이트입니다.

M/M/1 큐의 경우 서비스 시간은 지수적으로 분산되고 다음으로² "="이며² W로 나타나는_M 큐의 평균 대기 시간은 ^[5]다음 방정식으로 나타납니다.

${\displaystyle {W_{M}}=syslogfrac {rho \display}{1-\rho }}$

이를 통해 일정한 서비스 시간을 가정하여 M/D/1 큐에 대응하는 방정식을 도출할 수 있습니다.그러면 서비스 시간의 분산은 0이 됩니다. 즉, θ² = 0이 됩니다.W로 표시되는_D M/D/1 큐의 평균 대기 시간은 다음 ^[5]방정식으로 나타납니다.

$({displaystyle {W_{D}}=param frac {rho \display}{2(1-\rho)}})$

위의 2개의 방정식에서 M/M/1 큐의 평균 큐 길이는 M/D/1 큐의 2배임을 알 수 있습니다.

고정 분포

대기열에 있는 작업 수는 M/G/1 타입 마르코프 체인으로 작성될 수 있으며, D = 1일^[4] 경우 상태 i(written로_i 작성됨)에 대해 찾은 고정 분포는 다음과 같다.

${\displaystyle {displaystyle }\pi _{0}&\pi \pi _{1}&=(1-\displayda)\\pi _{n}&=(1-\displayda)\left(e^{n\displayda}+\sum _k=1^{n}^{n}-1}-n}{e}{n}{n}{e}{n}{n}{n}{n}{n}{n}{n}{n}{n}{e}{n}{e}}+{\frac {(k\fracda)^{n-k-1}{(n-k-1)!}}\right]\right)\syslog (n\geq 2)\end { aligned}}$

지연

δ = δ/μ를 사용률로 정의하면 M/D/1 큐에서^[6] 시스템의 평균 지연은 다음과 같다.

${\displaystyle {\frac {1}{2\mu}}\cdot {\frac {2-\rho}{1-\rho}}.}$

큐에 있습니다.

${\displaystyle\frac{1}{2\mu}}\cdot{frac{rho}{1-\rho}}.}$

바쁜 기간

비지 기간은 첫 번째 고객이 빈 큐에 도착한 순간부터 다시 빈 큐가 될 때까지의 기간입니다.이 기간은 서비스된 고객 수에 D를 곱한 것과 같습니다.' < 1'의 경우 큐의 비지 기간 동안 서비스된 고객 수는 파라미터 ^[7][8]'의 보렐 분포가 됩니다.

유한 용량

고정 분포

확률 생성 함수를 사용하여 큐 내의 고객 수와 평균 큐 길이에 대한 ^[9]고정 분포를 계산할 수 있다.

일시적인 솔루션

종종 M/D/1/N으로 쓰여진 유한 용량 N의 M/D/1 큐의 과도 솔루션은 2002년에 가르시아 등에 의해 발표되었다.^[10]

어플

와이드 에리어 네트워크 ^[11]설계의 애플리케이션을 포함합니다.단일 중앙 프로세서가 기하급수적으로 착신하는 패킷의 헤더를 읽어낸 후, 각 패킷의 송신지가 되는 다음의 어댑터를 계산해, 거기에 따라서 패킷을 디스패치 합니다.여기서 서비스 시간은 패킷헤더의 처리와 사이클릭 용장성 체크입니다.이것은, 착신 패킷의 길이와는 무관합니다.따라서 M/D/1 ^[12]큐로 모델링할 수 있습니다.

레퍼런스