[확률과정] 1.3-(2) Example: Queueing Model (1)

네트워크에서 요청을 받아 처리할 때 여러 서버에 분산하는 것은 중요한 주제이다. 가장 쉽게 접할 수 있는 예가 바로 대형 마트에서 계산을 위해 계산대에서 줄을 기다리는 상황일 것이다. 이번 페이지에서는 이러한 큐 모델의 가장 간단한 형태를 Markov chain으로 기술하는 것을 살펴보 것이다.

 

전화가 2개 있는 사무실을 생각해보자. 이 전화 시스템은 매우 오래되었기 때문에 대기 기능이 없어 회선이 사용 중일 때 다른 전화를 받지 못한다. 이 사무실에 1분 동안 문의 전화가 새롭게 들어올 확률을 \(p\)라고 하자. 그리고 들어온 문의가 처리될 확률을 \(q\)라고 하자. 1분 사이에 연속으로 2건 이상의 문의가 동시에 들어오지는 않는다. 마찬가지로 1분 사이에 한번에 2건 이상의 문의가 처리되지는 않는다. (이러한 가정이 비정상적이라고 한다면, 시간 인터벌을 매우 짧은 시간, 예를 들어 0.1초라고 생각하면 가능한 상황일 것이다.)

 

\(t\) 시점에 사용 중인 전화의 개수를 \(X_t\)라고 하자. 예를 들어, \(X_3=1\) 은 일을 시작하고 3분에 사용중인 전화가 1개라는 뜻이다.

 

transition matrix를 구하기 위해 transition probability를 생각해보자. 먼저 \(t\) 시점에 \(X_t=0\) 인 경우, \(t+1\)에도 사용중인 전화가 0개일 확률은 \(1-p\) 이고, 1개일 확률은 \(p\)이다. 2개일 확률은 가정에 따라 0이다.

\[ \begin{align} p(0,0) &= 1-p \\ p(1,1) &= p \\ p(1,2) &= 0 \end{align} \]

\(t\) 시점에 \(X_t=2\)인 경우에는 새로운 문의가 들어올 수는 없고 처리되느냐 아니냐에 따라 결정된다. \(t+1\)에도 사용중인 전화가 2개일 확률은 \(1-q\)이고, 1개일 확률은 \(q\)이다. 0개일 확률은 가정에 따라 0이다.

\[ \begin{align} p(2,0) &= 0 \\ p(2,1) &= q \\ p(2,2) &= 1-q \end{align} \]

\(t\) 시점에 \(X_t=1\)인 경우에는 조금 복잡하다. \(t+1\)에 사용중인 전화가 0개일 확률은, 새로운 전화는 들어오지 않고 기존 문의는 처리될 확률이므로 \((1-p)q\)가 된다. 사용중인 전화가 2개일 확률은, 새로운 전화가 들어오고 기존 문의는 처리되지 않을 확률이므로 \(p(1-q)\)가 된다.

\[ \begin{align} p(1,0) &= (1-p)q \\ p(1,2) &= p(1-q) \end{align} \]

사용중인 전화가 1개일 확률은 \(p(1,0) + p(1,1) + p(1,2) = 1\) 이라는 점을 이용하여,

\[ p(1,1) = 1 - p - q + 2pq \]

 

따라서 이 Markov chain의 transition matrix는

\[ \begin{bmatrix} 1-p & p & 0 \\ (1-p)q & 1 - p - q + 2pq & p(1-q) \\ 0 & q & 1-q \end{bmatrix} \]

이다.