Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.43 No.4 pp.1-14
DOI : https://doi.org/10.11627/jkise.2020.43.4.001

M/G/1 Preemptive Priority Queues With Finite and Infinite Buffers

Kilhwan Kim†

Department of Management Engineering, Sangmyung University

^†Corresponding Author : khkim@smu.ac.kr

Received 13/11/2020 Finally Revised 15/12/2020 Accepted 18/12/2020

Abstract

Recently, M/G/1 priority queues with a finite buffer for high-priority customers and an infinite buffer for low-priority customers have applied to the analysis of communication systems with two heterogeneous traffics : delay-sensitive traffic and loss-sensitive traffic. However, these studies are limited to M/G/1 priority queues with finite and infinite buffers under a work-conserving priority discipline such as the nonpreemptive or preemptive resume priority discipline. In many situations, if a service is preempted, then the preempted service should be completely repeated when the server is available for it. This study extends the previous studies to M/G/1 priority queues with finite and infinite buffers under the preemptive repeat-different and preemptive repeat-identical priority disciplines. We derive the loss probability of high-priority customers and the waiting time distributions of high- and low-priority customers. In order to do this, we utilize the delay cycle analysis of finite-buffer M/G/1/K queues, which has been recently developed for the analysis of M/G/1 priority queues with finite and infinite buffers, and combine it with the analysis of the service time structure of a low-priority customer for the preemptive-repeat and preemptive-identical priority disciplines. We also present numerical examples to explore the impact of the size of the finite buffer and the arrival rates and service distributions of both classes on the system performance for various preemptive priority disciplines.

Key Words : M/G/1 Priority Queues , Delay Cycle Analysis , Preemptive Priority Disciplines , Finite and Infinite Buffers

유한 및 무한 용량 대기열을 가지는 선점 우선순위 M/G/1 대기행렬

김 길 환†

상명대학교 경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

이 논문에서는 서비스 우선순위가 높은 고객 클래스 에는 유한 용량 대기열이, 서비스 우선순위가 낮은 고객 클래스에는 무한 용량 대기열이 제공되는 M/G/1 선점 우선순위 대기행렬 모형을 다룬다. 이 논문에서는 이러 한 대기행렬 모형은 M/G/1/(K,∞) 선점 우선순위 대기행렬 이라고 부를 것이다.

고객 클래스 별로 유한 용량과 무한 용량 대기열을 모 두 가지는 우선순위 대기행렬 모형은 서비스 요구사항이 상이한 두 트래픽을 서비스하는 통신 시스템의 성능을 분 석하기 위하여 도입되었다[1, 4]. 지연에 민감한 실시간 트래픽과 손실에 민감한 데이터 트래픽을 동시에 처리해 야 하는 다음과 같은 통신 시스템을 고려해 보자. 이 통신 시스템에서는 지연에 민감한 실시간 트래픽에는 서비스 에 대한 시간 우선순위(time priority)를 부여하여 데이터 트래픽보다 먼저 서비스를 받도록 하지만 버퍼 공간의 사 용에는 제한을 둔다. 그렇기 때문에 실시간 트래픽에는 서비스 지연을 최소화할 수 있지만 패킷 손실이 발생할 수 있다.반면 손실에 민감한 데이터 트래픽에는 실질적으로 무한의 버퍼 공간을 제공하여 공간 우선순위(space priority) 를 부여하지만, 시간 우선순위는 낮추어 대기열에 실시간 트래픽이 없을 때만 서비스를 시작할 수 있도록 한다. 그 렇기 때문에 데이터 트래픽은 패킷의 손실을 방지할 수 있으나 상대적으로 긴 서비스 지연을 경험할 수 있다.

유한 및 무한 용량 대기열을 모두 가지는 우선순위 대 기행렬에 대한 기존 연구를 살펴보면 다음과 같다. Al- Begain et al.[1]은 3G 모바일 통신망의 HSDPA 다운링크 를 분석하기 위해 처음으로 M/G/1/(K,∞) 우선순위 대기 행렬을 분석하였다. Demoor et al.[4]은 인터넷에서 서비 스 차별화를 위해 도입된 DiffServ 아키텍처에서 패킷 포 워딩 성능을 분석하기 위해서 유한 및 무한 용량 대기열 을 가지는 이산 시간 우선순위 대기행렬 모형을 분석하 였다. 아울러 Velthoven et al.[17]은 유한 대기열이 고객 손실 확률에 미치는 영향을 분석하기 위하여 서비스 시 간이 한 시간 슬롯인 다양한 형태의 유한-무한 용량 이 산 시간 우선순위 대기행렬에 대하여 분석을 수행하였으 며, Charkravarthy[2]은 M/M/1/(K,∞) 우선순위 대기행렬 모형을 연구하였다.

그러나 이러한 유한 및 무한 용량 대기열을 가지는 우 선순위 대기행렬에 대한 연구들은 모두 시간 우선순위 정책으로 비선점(nonpreemptive) 우선순위 정책만을 고려 하였다. 비선점 우선순위 정책에서는, 시간 우선순위가 낮은 데이터 트래픽의 패킷이 이미 서비스를 시작하였으 면, 시간 우선순위가 높은 실시간 트래픽이 도착하였어 도 이미 서비스 중인 패킷의 서비스가 완료된 후에야 서 비스를 제공받을 수 있다.

비선점 우선순위 정책은 서비스의 중단에 따른 서비스 의 비효율성을 방지한다는 측면에서는 장점이 있지만, 우 선순위가 낮은 트래픽의 패킷의 길이가 길거나 변동성이 크면 우선순위가 높은 트래픽의 평균 지연 시간이 늘어나 는 단점이 있다. 이러한 이유로 최근에 대용량의 멀티미디 어 트래픽과 지연에 민감한 실시간 트래픽을 동시에 서비 스 하는 통신 시스템에서 선점(preemptive) 기반 스케줄링 기법에 대한 연구가 활발히 진행되고 있다[13, 14, 19-21].

선점 우선순위 정책에서는 시간 우선순위가 높은 트래 픽은 시간 우선순위가 낮은 트래픽이 서비스 중이어도 이 를 중단시키고 즉시 서비스를 받을 수 있다. 예를 들어, 5G 모바일 통신망의 다운링크는 대용량 멀티미디어 트 래픽인 eBBB(enhanced mobile broadband)와 지연을 최소 화해야 하는 트래픽인 URLLC(ultra reliable low latency communication)을 동시에 서비스 할 것을 요구받고 있다 [15, 16]. eBBB 트래픽에 대한 통신망의 처리율(throughput) 을 높이기 위해서는 패킷의 길이가 충분히 긴 것이 유리 하지만, 서비스 시간 우선순위를 가지는 URLLC 트래픽 의 지연을 최소화하기 위해서는 패킷의 길이가 짧은 것이 유리하다. 이러한 상충하는 요구사항을 해결하는 한 방법 이, 패킷의 길이는 충분히 길게 하지만 시간 우선순위가 높은 URLLC 트래픽에 선점 우선순위를 부여하여 지연 시간을 최소화하는 것이다[14, 19, 20].

앞서 언급하였듯이 유한 및 무한 용량 대기열을 가지 는 우선순위 대기행렬에 대한 지금까지의 연구 대부분은 비선점 우선순위 정책만을 고려하고 있어서[1, 2, 4, 17], 선점 우선순위 정책을 적용하는 통신 시스템의 성능 분석 에 적용하는데 한계가 있었다. 특히, 이러한 연구는 모두 행렬해석법(matrix analytic method)을 사용하고 있는데, 행렬해석법은 비선점 우선순위 대기행렬 분석에는 활용 이 용이하지만, 선점 우선순위 정책이나 다양한 혼합형 우선순위 정책[8-12]을 가지는 M/G/1 우선순위 대기행렬 의 분석으로 확장하기 어렵다. 그런데 최근 Kim[7]은 무 한 용량 M/G/1 대기행렬에 주로 사용되던 지체 사이클 분석(delay cycle analysis)을 유한 용량 M/G/1/K 대기행렬 에 적용하는 방법을 제안하고, 지체 사이클 분석을 이용 하여 M/G/1/(K,∞) 비선점 우선순위 대기행렬뿐 아니라, 선점 계속(preemptive resume) 우선순위 대기행렬을 분석 하는 방법을 제시하였다.

Kim[7]의 연구는 선점형 우선순위 정책을 가지는 M/G/ 1/(K,∞) 우선순위 대기행렬을 분석할 수 있는 방법을 제 시하였다는 점에서 의의를 가지지만, 실제 문제에 적용 하기에는 다음의 한계가 있다. 선점 계속 우선순위 정책 에서는 우선순위가 높은 고객의 도착으로 중지(선점)된 서비스는 자기보다 우선순위가 높은 고객이 모두 서비스 받은 후에 중지된 지점부터 서비스가 '계속' 진행된다. 그 러나 많은 실제 시스템에서는 서비스가 중지되면 처음부 터 서비스가 ’반복’되어야 하는 경우가 많다. 예를 들어 패킷의 전송이 중지되면 상태를 보존할 수 없는 시스템 의 경우 패킷의 전송이 처음부터 다시 수행되어야 한다.

선점 반복 우선순위 정책은 다시, 서비스를 반복할 때 원래의 서비스 시간과 동일한 서비스 시간으로 반복하는 선점 동일-반복(preemptive repeat identical) 정책과, 반복 시 동일한 서비스 시간 분포에서 새로운 서비스 시간을 재샘플링하여 서비스를 받는 선점 재샘플링-반복(preemptive repeat different) 정책으로 나눠진다[3, 6, 9]. 본 연구 에서는 Kim[7]의 연구를 선점 동일-반복과 선점 재샘플링 -반복 정책을 가지는 M/G/1/(K,∞) 대기행렬 모형에 대한 분석으로 확장한다. 이를 통해 Kim[7]의 연구 결과와 결 합하여 다양한 선점 우선순위 정책에 따라 시스템 성능이 어떻게 변화하는지를 탐구한다.

이 논문의 나머지 부분의 구성은 다음과 같다. 제 2장에 서는 이 논문에서 다루고자 하는 대기행렬 모형을 정식화 한다. 제 3장에서는 시간 우선순위가 낮은 고객의 실질적 인 서비스 시간의 분포를 분석한다. 제 4장에서는 시간 우 선순위가 높은 고객의 손실률과 대기시간의 분포와, 시간 우선순위가 낮은 고객의 대기시간의 분포를 분석한다. 제 5장에서는 다양한 수치 예제를 사용하여 다양한 선점 우 선순위 정책에 대해 시스템 관련 요인의 변화에 따른 시스 템 성능의 변화를 탐구한다. 마지막으로 제 6장에서는 본 연구의 결과를 종합하고 향후 연구의 방향을 제시한다.

2. 모 형

본 연구에서는 클래스 1과 2라는 두 개의 고객 클래스를 가진 M/G/1 우선순위 대기행렬을 다룬다. 클래스-i, i = 1, 2, 고객은 도착률 λ_i의 포아송 과정으로 시스템에 도착 한다. 단, λ_i > 0. 클래스-i 고객의 서비스 시간 S_i 는 서로 독립이고 일반 분포를 따른다. S_i 의 분포함수는 x ≥ 0인 정의역에서 S_i (x) , 라플라스-스틸체스 변환(LST; Laplace- Stieltjes transform)은 Re(θ ) ≥ 0인 정의역에서 $S_{i}^{*} (θ)$ 로 표 기한다. 서비스 시간 S_i에 대한 1, 2차 모멘트는 $0 < E [S_{i}], E [S_{i}^{2}] < \infty$ 이고, 클래스 1과 2의 도착과정과 서비스 시간 은 서로 독립이라고 가정한다.

클래스-1 고객에게는 크기가 K인 유한 용량 대기열이, 클래스-2 고객에게는 무한 용량의 대기열이 제공된다. 단, K ≥ 0. 따라서 클래스-2 고객은 도착 시 손실 없이 시스템 에 합류하나, 클래스-1 고객은 도착 시 대기열에 이미 K명 의 클래스-1 고객이 있으면 도착한 클래스-1 고객은 시스 템에 합류하지 못하고 손실된다. K는 대기열에 있을 수 있는 클래스-1 고객 수의 한계치이지 시스템 전체에 있을 수 있는 클래스-1 고객수의 한계치가 아님에 주의해야 한 다. 현재 서비스를 받고 있는 고객이 클래스-1 고객이면, 서비스 중인 고객과 대기열에 있는 고객을 모두 포함하여 최대 K + 1명의 클래스-1 고객이 시스템에 있을 수 있다.

클래스-1 고객은 클래스-2 고객에 대한 선점 우선순위 를 가진다. 클래스-2 고객은 시스템에 클래스-1 고객이 없 을 때만 서비스를 받을 수 있으며, 이미 클래스-2 고객의 서비스가 시작된 후에도 클래스-1 고객이 도착하면 클래 스-2 고객의 서비스는 중지되고 클래스-1 고객에 대한 서 비스가 바로 시작된다. 서비스가 중지된 클래스-2 고객의 서비스는 클래스-1 고객이 더 이상 시스템에 없을 때에야 다시 재개될 수 있다. 본 논문에서는 서비스가 중지된 고 객의 원래의 서비스 시간이 S₂일 때, 동일한 서비스 시간 S₂로 서비스가 처음부터 반복되는 선점 동일-반복(PRI) 우선순위 정책과, 동일한 서비스 분포 S₂ (x)로부터 새로 운 서비스 시간이 재샘플링 되어 서비스가 반복되는 선점 재샘플링-반복(PRD) 우선순위 정책 하에서의 M/G/1/(K, ∞) 대기행렬을 분석한다. 동일한 클래스 고객은 선입선 출(FCFS : First Come, First Served) 순으로 서비스를 받 는다고 가정한다.

3. 클래스-2 고객의 서비스 시간의 구조

선점형 우선순위 대기행렬에서는 클래스-2 고객 한 명 의 서비스 시간으로 간주될 수 있는 확률변수로 다음 세 가지 기간이 있다[3, 5, 9-11]. 첫 번째 확률변수는 고객의 원래 서비스 시간 S₂이다. 두 번째 확률변수는 고객이 서 버로부터 서비스 받는 총 서비스 시간 G이다. 선점 계속 우선순위 정책에서는 총 서비스 시간 G가 S₂와 동일하지 만, 선점 동일-반복이나 선점 재샘플링-반복 우선순위 정 책에서는 선점 후에 서비스가 처음부터 다시 반복되므로 일반적으로 G는 S₂와 다른 분포를 가진다. 마지막으로 세 번째 확률변수는 클래스-2 고객이 처음으로 서비스를 시작한 시점부터 서비스를 다 받고 떠날 때까지의 기간인 서비스 완성 시간 H이다. 완성 시간 H 안에는 클래스-1 고객에 의해 서비스가 중지된 시간이 모두 포함된다. 하 나의 완성 시간마다 오직 한 명의 클래스-2 고객이 서비 스 받고 나가므로 클래스-2 고객의 관점에서는 실질적인 서비스 시간이라 볼 수 있다. 이 논문에서 사용할 주요 확률변수에 대한 정의는 <Table 1>에서 확인할 수 있다. 총 서비스 시간 G와 완성 시간 H에 대한 LST를 정의역 R e(θ ) ≥ 0에서 G^*(θ ) = E [e^-^θG ]와 H^*(θ ) = E [e^-θH ]로 정 의하자. 이 장에서는 선점 우선순위 정책에 따라 클래스 -2 고객 한 명의 실질적인 서비스 시간인 G와 H의 LST 를 유도하기로 한다.

3절의 내용 중 M/G/1/k 대기행렬의 바쁜 기간 Θ_(k)에 대한 결과는 Kim[7]의 계속 우선순위 정책 하의 M/G/1/(K, ∞) 대기열의 분석의 결과를 이용하였음을 밝혀둔다.

3.1 선점 재샘플링-반복 정책에서 서비스 시간의 구조

선점 재샘플링-반복 정책 하에서 어떤 클래스-2 고객 이 처음으로 서비스를 시작한 시점을 고려해 보자. 이 고 객의 서비스 시간을 S₂라 하고, 이 고객이 서비스를 처 음 시작한 시점부터 그 시점 이후 클래스-1 고객이 처음 으로 도착할 때까지의 시간을 I₁이라고 하자. 만약 S₂가 I₁보다 작거나 같으면 클래스-2 고객은 서비스의 중지(선 점) 없이 S₂ 시간 이후에 모든 서비스가 완료되어 시스 템을 떠난다. 따라서 다음이 성립한다.

반면 서비스 시간 S₂가 I₁보다 길면, 서비스가 시작된 후 I₁ 시간이 경과된 시점에 도착한 클래스-1 고객에 의해 서비스가 중지(선점)된다. 선점된 클래스-2 고객의 서비 스는 시스템 내에 클래스-1 고객이 모두 사라질 때까지 중지된다. 이러한 클래스-2 고객의 서비스 중지 기간은 M/G/1/(K+1) 대기열의 바쁜 기간(busy period)과 확률적 으로 동일하다. 왜냐하면 클래스-1 고객의 대기열은 K로 제한되어 있어서 클래스-1 고객의 관점에서는 시스템의 용량은 K + 1이고, 클래스-2 고객의 서비스 중지 기간은 클래스-2 고객을 선점한 클래스-1 고객 한 명의 서비스로 시작하여 연속적으로 시스템에 있는 클래스-1 고객이 모 두 서비스를 받은 후 더 이상 시스템에 클래스-1 고객이 없을 때 끝나기 때문이다. 이러한 클래스-2 고객의 서비 스 중지 기간의 길이를 Θ_(k), 이 기간 동안 도착해서 대기 열에 합류한 클래스-1 고객의 수(클래스-2 고객의 서비스를 선점하고 Θ_(k) 기간을 시작한 클래스-1 고객은 제외)를 $A_{1}^{a} (Θ_{(K)})$ , 이 기간 동안 도착하였으나 대기열이 가득 차 있어서 손실된 클래스-1 고객의 수를 $A_{1}^{b} (Θ_{(K)})$ )라고 하자. 그리고 이 세 확률변수의 결합변환을 다음과 같이 정의하자.

Θ_{(K)}^{*} (θ, z, w) = E [e^{- θ Θ_{(K)}} z^{A_{1}^{a} (Θ_{(K)})} w^{A_{1}^{a} (Θ_{(K)})}] .

단, $Re (Θ) \geq 0, | z | \leq 1, | w | \leq 1$ . 그러면 $Θ_{(K)}^{*} (θ, z, w)$ 는 다 음과 같은 재귀식을 이용하여 계산할 수 있다[7].

Θ_{(0)}^{*} (θ, z, w) = \sum_{j = 0}^{\infty} S_{1}^{*} (θ; j) w^{j},

(1)

단, k = 1, 2, ⋯, K이고 A₁ (S₁ )은 서비스 시간 S₁ 동안 도 착하는 클래스-1 고객의 수이고, $S_{1}^{*} (θ, j)$ 는 다음과 같이 정의된다.

\begin{matrix} Θ_{(k)}^{*} (θ, z, w) = S_{1}^{*} (θ; 0) \\ \times [1 - \sum_{j = 1}^{k - 1} S_{1}^{*} (θ; j) z^{j} \prod_{h = k - j + 1}^{k - 1} Θ_{(h)}^{*} (θ, z, w) \\ {- z^{k} \sum_{j = k}^{\infty} S_{1}^{*} (θ; j) w^{j - k} \prod_{h = 1}^{k - 1} Θ_{(h)}^{*} (θ, z, w)]}^{- 1} . \end{matrix}

(2)

단, j = 0, 1, ⋯. 아울러 식 (1)과 식 (2)를 미분하여 θ = 0 과 z = w = 1을 대입하면 k = 1, 2, ⋯, K에 대하여 다음과 같은 모멘트에 대한 재귀식도 구할 수 있다[7].

E [Θ_{(0)}] = E [S_{1}]

(3)

E [Θ_{(0)}^{2}] = E [S_{1}^{2}]

(4)

E [A^{a_{1}} (Θ_{(0)})] = 0

(5)

E [A^{b_{1}} (Θ_{(0)})] = λ_{1} E [S_{1}]

(6)

E [Θ_{(k)}] = S_{1}^{*} {(0; 0)}^{- 1} [E [S_{1}] + \sum_{h = 1}^{k - 1} E [Θ_{(h)}] \sum_{j = k - h + 1}^{\infty} S_{1}^{*} (0; j)]

(7)

\begin{matrix} E [Θ_{(k)}^{2}] = S_{1}^{*} {(0; 0)}^{- 1} \\ \times {[E [S_{1}^{2}] - 2 \sum_{h = 1}^{k} E [Θ_{(h)}] \sum_{j = k - h + 1}^{\infty} \frac{\partial}{\partial θ} S_{1}^{*} (θ; j)]}_{θ = 0} \\ + \sum_{h = 1}^{k - 1} E [Θ_{(h)}^{2}] \sum_{j = k - h + 1}^{\infty} S_{1}^{*} (0; j) \\ + 2 \sum_{h = 1}^{k - 1} \sum_{g = h + 1}^{k} E [Θ_{(h)}] E [Θ_{(g)}] \sum_{j = k - h + 1}^{\infty} S_{1}^{*} (0; j)] \end{matrix}

(8)

\begin{array}{l} E [A^{a_{1}} (Θ_{(k)})] = S_{1}^{*} {(0; 0)}^{- 1} \\ \times \sum_{h = 1}^{k} \sum_{j = h}^{\infty} S_{1}^{*} (0; j) + \sum_{h = 1}^{k - 1} E [A^{a_{1}} (Θ_{(h)})] \sum_{j = k - h + 1}^{\infty} S_{1}^{*} (0; j)] \end{array}

(9)

\begin{array}{l} E [A^{b_{1}} (Θ_{(k)})] = S_{1}^{*} {(0; 0)}^{- 1} \\ \times [\sum_{h = k + 1}^{\infty} \sum_{j = h}^{\infty} S_{1}^{*} (0; j) + \sum_{h = 1}^{k - 1} E [A^{b_{1}} (Θ_{(h)})] \sum_{j = k - h + 1}^{\infty} S_{1}^{*} (0; j)] \end{array}

(10)

선점 재샘플링-반복 정책에서는 클래스-1 고객의 도착 으로 중지된 클래스-2 고객의 서비스는 Θ_(k) 기간이 끝 난 후 동일한 서비스 분포에서 서비스 시간이 재샘플링 되어 서비스가 반복된다. 따라서 두 번째 서비스 시도의 시점 이후부터 클래스-2 고객이 서비스 받고 나갈 때까 지의 기간은 원래의 H 기간과 확률적으로 동일하고 앞 선 서비스 시도와 확률적으로 독립이다. 따라서 다음과 같은 관계식이 성립한다.

\begin{array}{l} E [e^{- θ G} | S_{2} > I_{1}] = E [e^{- θ I_{1}} | S_{2} > I_{1}] \cdot G^{*} (θ) \\ E [e^{- θ H} | S_{2} > I_{1}] = E [e^{- θ I_{1}} | S_{2} > I_{1}] \cdot Θ_{(K)} (θ, 1, 1) \cdot H^{*} (θ) \end{array}

클래스-2 고객이 처음 서비스를 시도할 때 S₂ ≤ I₁인 사건이 발생하는 경우와 S₂ > I₁인 사건이 발생하는 경우 를 모두 고려하면 G의 LST는 다음과 같이 표현된다.

\begin{matrix} G^{*} (θ) = Pr {S_{2} \leq I_{1}} \cdot E [e^{- θ S_{2}} | S_{2} \leq I_{1}] \\ + Pr {S_{2} > I_{1}} \cdot E [e^{- θ I_{1}} | S_{2} > I_{1}] \cdot G^{*} (θ) . \end{matrix}

그런데

\begin{matrix} Pr {S_{2} \leq I_{1}} \cdot E [e^{- θ S_{2}} | S_{2} \leq I_{1}] \\ = \int_{0}^{\infty} e^{- θ x} e^{- λ_{1} x} d S_{2} (x) = S_{2}^{*} (θ + λ_{1}) \end{matrix}

이고,

\begin{matrix} Pr {S_{2} > I_{1}} \cdot E [e^{- θ I_{1}} | S_{2} > I_{1}] \\ = \int_{0}^{\infty} e^{- θ x} (1 - S_{2} (x)) λ_{1} e^{- λ_{1} x} d x = \frac{λ_{1}}{λ_{1} + θ} {1 - S_{2}^{*} (θ + λ_{1})} \end{matrix}

이다. 이 결과를 G^*(θ )에 대한 관계식에 대입한 다음 G^*(θ )에 대하여 정리하면 다음 결과를 얻는다(선점 재샘 플링-반복 정책에서의 결과와 선점 동일-반복 정책에서 의 결과를 비교하기 위하여 앞으로 필요한 경우 각 정책 의 결과를 PRD와 PRI라는 아래 첨자를 사용하여 구분하 기로 한다).

G_{P R D}^{*} (θ) = \frac{S_{2}^{*} (θ + λ_{1})}{1 - \frac{λ_{1}}{λ_{1} + θ} {1 - S_{2}^{*} (θ + λ_{1})}} .

(11)

마찬가지 방식으로 완성 시간의 LST H^*(θ )에 대해 S₂ ≤ I₁인 경우와 S₂ > I₁인 경우의 관계식을 모두 고려 하면 다음과 같은 결과를 얻는다.

H_{P R D}^{*} (θ) = \frac{S_{2}^{*} (θ + λ_{1})}{1 - \frac{λ_{1}}{λ_{1} + θ} {1 - S_{2}^{*} (θ + λ_{1})} \cdot Θ_{(K)} (θ, 1, 1)} .

(12)

선점 재샘플링-반복 우선순위 정책 하에서의 총 서비 스 시간 G와 서비스 완성 시간 H의 1, 2차 모멘트는 식 (11)과 식 (12)를 1, 2차 미분하여 θ = 0을 대입하여 다음 과 같이 구할 수 있다.

E [G_{P R D}] = \frac{1 - S_{2}^{*} (λ_{1})}{λ_{1} S_{2}^{*} (λ_{1})}

(13)

E [G_{P R D}^{2}] = \frac{2 (1 - S_{2}^{*} (λ_{1}) + λ_{1} S_{2}^{*} (λ_{1}))}{λ_{1}^{2} S_{2}^{*} {(λ_{1})}^{2}}

(14)

E [H_{P R D}] = \frac{(1 - S_{2}^{*} (λ_{1})) (1 + λ_{1} E [Θ_{(K)}])}{λ_{1} S_{2}^{*} (λ_{1})}

(15)

\begin{array}{l} E [H_{P R D}^{2}] = \frac{(1 - S_{2}^{*} (λ_{1})) E [Θ_{(K)}^{2}]}{S_{2}^{*} (λ_{1})} + 2 (1 + λ_{1} E [Θ_{(K)}]) \\ \times \frac{1 - S_{2}^{*} (λ_{1}) + λ_{1} S_{2}^{*} (λ_{1}) + λ_{1} E [Θ_{(K)}] {(1 - S_{2}^{*} (λ_{1}))}^{2}}{λ_{1}^{2} S_{2}^{*} {(λ_{1})}^{2}} . \end{array}

(16)

단, $S_{2}^{*}^{'} (θ)$ 는 $S_{2}^{*} (θ)$ 의 일차 미분이다.

3.2 선점 동일-반복 정책에서 서비스 시간의 구조

선점 동일-반복 정책에서의 서비스 시간의 구조에 대 한 분석도 선점 재샘플링-반복 정책과 비슷하다. 다만 서 비스 시간이 재샘플링 되는 것이 아니라 동일한 서비스 시간이 반복되는 점에서만 차이가 있다.

어떤 클래스-2 고객의 서비스 시간이 S₂ = x라고 하자. 단, x ≥ 0. 그러면 선점 동일-반복 정책 하에서는 x ≤ I₁ 이면 이 클래스-2 고객은 서비스 중지(선점) 없이 서비스 시간 x가 지난 후 서비스가 완료되어 시스템을 떠난다. 따라서 x ≤ I₁이면 다음이 성립한다.

E [e^{- θ H} | x \leq I_{1}, S_{2} = x] = E [e^{- θ G} | x \leq I_{1}, S_{2} = x] = e^{- θ x} .

반면 x > I₁이면, 서비스 시작 후 I₁시간 경과 시점에 도착한 클래스-1 고객에 의해 클래스-2 고객의 서비스가 중지(선점)된다. 선점 재샘플링-반복 정책과 마찬가지로 클래스-2 고객의 서비스 중지 기간은 Θ_(k)이며, 그 기간, 그동안 도착하여 서비스 받고 나가는 클래스-1 고객 수, 그동안 손실되는 클래스-1 고객 수에 대한 결합변환 Θ_(k)^* (θ,z,w )는 식 (1)과 식 (2)의 재귀식으로 표현된다. 선 점 재샘플링-반복 정책과 다르게, 선점 동일-반복 정책에 서는 클래스-1 고객의 도착으로 중지된 클래스-2 고객의 서비스가 Θ_(k) 기간이 끝난 후 S₂ (x) 분포에서 재샘플링 된 서비스 시간이 아니라, 원래와 동일한 서비스 시간 x 로 반복된다. 그리고 두 번째 서비스 시도 이후의 과정은 서비스 시간 x를 가지고 처음 서비스 시도할 때와 동일 한 확률 구조를 갖는다. 따라서 선점 재심플링-반복 경우 와 유사하지만 서비스 시간 S₂에 조건이 있는 다음과 같 은 관계식이 성립한다.

\begin{array}{l} E [e^{- θ G} | x > I_{1}, S_{2} = x] = E [e^{- θ I_{1}} | x > I_{1}] \cdot E [e^{- θ G} | S_{2} = x] \\ E [e^{- θ H} | x > I_{1}, S_{2} = x] = E [e^{- θ I_{1}} | x > I_{1}] \\ \times Θ^{*_{(K)}} (θ, 1, 1) \cdot E [e^{- θ H} | S_{2} = x] . \end{array}

서비스 시간이 x인 클래스-2 고객의 처음 서비스 시도 에서 x ≤ I₁인 사건이 발생한 경우와 x > I₁인 사건이 발 생한 경우를 모두 고려하면, 서비스 시간이 x일 때의 G 의 조건부 LST는 다음과 같이 표현된다.

\begin{array}{l} E [e^{- θ G} | S_{2} = x] = Pr {x \leq I_{1}} \cdot e^{- θ x} \\ + Pr {x > I_{1}} \cdot E [e^{- θ I_{1}} | x > I_{1}] \cdot E [e^{- θ G} | S_{2} = x] \end{array}

그런데

Pr {x \leq I_{1}} = e^{- λ_{1} x}

이고,

\begin{matrix} Pr {x > I_{1}} \cdot E [e^{- θ I_{1}} | x > I_{1}] = \int_{0}^{x} e^{- θ x} λ_{1} e^{- λ_{1} y} d y \\ = \frac{λ_{1}}{λ_{1} + θ} {1 - e^{- (θ + λ_{1}) x}} \end{matrix}

이다. 이 결과를 E [G|S₂ = x]에 대한 관계식에 대입하여 정리한 후, 서비스 S₂에 대한 조건을 제거하면, G^*(θ )에 대하여 다음 결과를 얻는다.

\begin{matrix} G_{P R I}^{*} (θ) = \int_{0}^{\infty} E [e^{- θ G} | S_{2} = x] d S_{2} (x) \\ = \int_{0}^{\infty} \frac{e^{- (θ + λ_{1}) x}}{1 - \frac{λ_{1}}{λ_{1} + θ} {1 - e^{- (θ + λ_{1}) x}}} d S_{2} (x) . \end{matrix}

(17)

마찬가지 방식으로 완성 시간의 조건부 LST E [e^-θH|S₂ = x]에 대해 x ≤ I₁인 경우와 x > I₁인 경우의 관계식을 모두 고려한 후, S₂에 대한 조건을 제거하면 H^*(θ )에 대 한 다음의 식을 얻는다.

\begin{matrix} H_{P R I}^{*} (θ) \\ = \int_{0}^{\infty} \frac{e^{- (θ + λ_{1}) x}}{1 - \frac{λ_{1}}{λ_{1} + θ} {1 - e^{- (θ + λ_{1}) x}} Θ_{(K)} (θ, 1, 1)} d S_{2} (x), \end{matrix}

(18)

선점 동일-반복 우선순위 정책에서 총 서비스 시간 G 와 서비스 완성 시간 H의 1, 2차 모멘트는 식 (17)과 식 (18)를 1, 2차 미분하여 θ = 0을 대입하여 다음과 같이 구 할 수 있다.

E [G_{P R I}] = \frac{1}{λ_{1}} \int_{0}^{\infty} (e^{λ_{1} x} - 1) d S_{2} (x)

(19)

E [G_{P R I}^{2}] = \frac{2}{λ_{1}^{2}} \int_{0}^{\infty} {- λ_{1} t e^{λ_{1} t} + e^{λ_{1} x} (e^{λ_{1} x} - 1)} d S_{2} (x)

(20)

E [H_{P R I}] = \frac{1 + λ_{1} E [Θ_{(K)}]}{λ_{1}} \int_{0}^{\infty} {e^{λ_{1} x} - 1} d S_{2} (x)

(21)

\begin{array}{l} E [H_{P R I}^{2}] = E [Θ_{(K)}^{2}] \int_{0}^{\infty} {e^{λ_{1} x} - 1} d S_{2} (x) + \frac{2 (1 + λ_{1} E [Θ_{(K)}])}{λ_{1}^{2}} \\ \times \int_{0}^{\infty} {- λ_{1} t e^{λ_{1} t} + e^{λ_{1} x} (e^{λ_{1} x} - 1) + λ_{1} E [Θ_{(K)}] {(e^{λ_{1} x} - 1)}^{2}} d S_{2} (x) . \end{array}

(22)

4. 고객 손실 확률과 대기시간의 분포

이번 장에서는 3장에서 얻어진 클래스-2 고객의 서비 스 시간의 분포를 이용하여 클래스-1 고객의 손실 확률 과 클래스-1과 클래스-2 고객의 대기시간의 분포를 구한 다. 이 장의 분석 방법과 결과는 Kim[7]의 선점 계속 우 선순위 정책 하의 M/G/1/(K, ∞) 대기열의 분석과 동일 하나, 논문의 완결성을 위하여 주요 결과만을 중심으로 간략히 서술하기로 한다.

4.1 클래스-1 고객의 손실 확률과 대기시간

선점 우선순위 정책 하에서 클래스-1 고객의 손실 확률 과 대기시간의 분포는 클래스-2 고객의 도착 과정 및 서 비스 과정에 전혀 영향을 받지 않는다. 아울러 선점 정책 의 종류가 선점 계속인지, 선점 재샘플링-반복인지, 선점 동일-반복인지에 대한 영향도 받지 않는다. 선점 정책의 종류는 선점된 후의 클래스-2 고객의 서비스 재개 방식과 만 관련이 있기 때문이다. 따라서 클래스-1 고객의 손실 확률과 대기시간 분포는 표준적인 M/G/1/(K+1) 대기행렬 의 손실 확률과 대기시간 분포와 동일하다. Kim [7]은 유 한 용량 대기행렬의 지체 사이클 분석을 통해 M/G/1/(K+ 1) 대기행렬의 고객 손실 확률과 대기시간의 분포를 구하 는 재귀식을 유도하였다. 그 결과를 이용하면 클래스-1 고객의 손실 확률 P^b와, 대기열에서의 대기시간 W₁과 시 스템에서의 체류시간 T₁의 LST $W^{*_{1}} (θ)$ 와 $T_{1}^{*} (θ)$ 을 다음 과 같이 표현할 수 있다[7].

P^{b} = \frac{E [A_{1}^{b} (Θ_{(K)})]}{1 + E [A_{1} (Θ_{(K)})]}

(23)

W_{1}^{*} (θ) = \frac{1 + E [A_{1}^{a} (Θ_{1, (K)})] \cdot W_{Θ (K)}^{*} (θ)}{1 + E [A_{1}^{a} (Θ (K))]}

(24)

T_{1}^{*} (θ) = W_{1}^{*} (θ) \cdot S_{1}^{*} (θ)

(25)

식 (23)과 식 (24)의 $E [A_{1}^{a} (Θ_{(K)})]$ 와 $E [A_{1}^{b} (Θ_{(K)})]$ 는 식 (5), 식 (6), 식 (9), 식 (10)의 재귀식을 이용하여 구할 수 있으 며, E [A₁ (Θ_(k) )] = $E [A_{1}^{a} (Θ_{(K)})]$ + $E [A_{1}^{b} (Θ_{(K)})]$ 이다. 아울러 식 (24)의 $E [A_{1}^{a} (Θ_{1, (K)})] \cdot W_{Θ_{(K)}}^{*} (θ)$ 는 다음의 재귀식을 사 용하여 구한다[7].

\begin{array}{l} E [A_{1}^{a} (Θ_{(k)})] \cdot W_{Θ_{(k)}}^{*} (θ) = \frac{1}{S_{1}^{*} (0; 0)} E [A_{1}^{a} (S_{1})] \cdot W^{* S_{1}} (θ) \\ + \frac{1}{S_{1}^{*} (0; 0)} \sum_{h = 1}^{k - 1} E [A_{1}^{a} (Θ_{(h)})] W_{Θ_{(h)}}^{*} (θ) S_{1}^{*} {(θ)}^{k - h} \sum_{j = k - h + 1}^{\infty} S_{1}^{*} (0; j) . \end{array}

(26)

단, k = 1, 2, ⋯, K이고,

\begin{array}{l} E [A_{1}^{a} (S_{1})] \cdot W^{*_{S_{1}}} (θ) = \\ \sum_{n = 0}^{k - 1} [{(\frac{λ_{1}}{λ_{1} - θ})}^{n + 1} S_{1}^{*} (θ) - \sum_{h = 0}^{n} {(\frac{λ_{1}}{λ_{1} - θ})}^{n - h + 1} S_{1}^{*} (0; h)] S_{1}^{*} {(θ)}^{n} . \end{array}

그리고 식 (24)와 식 (25)를 한 번 미분한 후 θ = 0을 대 입하면 W₁과 T₁의 기대치를 다음과 같이 구할 수 있다.

E [W_{1}] = \frac{E [A_{1}^{a} (Θ_{1, (K)})] \cdot E [W_{Θ_{1, (K)}}]}{1 + E [A_{1}^{a} (Θ_{1, (K)})]}

(27)

E [T_{1}] = E [W_{1}] + E [S_{1}] .

(28)

식 (27)의 $E [A_{1}^{a} (Θ_{1, (K)})] \cdot E [W_{Θ_{1, (K)}}]$ 는 식 (26)을 한 번 미분 한 후 θ = 0을 대입하여 구한 재귀식을 사용하여 구한다.

4.2 클래스-2 고객의 대기시간

클래스-2 고객의 대기시간을 고려할 때는 항상 다음과 같은 클래스-2 고객의 대기열에 대한 안정성 조건(stability condition)이 만족한다고 가정한다.

λ_{2} E [H] < 1

클래스-2 고객의 대기열 용량은 무한이므로 일반적인 무한 용량 대기행렬의 지체 사이클 분석을 사용하면 클 래스-2 고객의 대기시간의 분포를 쉽게 구할 수 있다[3, 5, 10, 11]. 대기열에 대한 안정성 조건이 만족되면 M/G/ 1/(K, ∞) 우선순위 대기행렬은 유휴 기간(idle periods)과 바쁜 기간(busy period)으로 구성된 일반 사이클(general cycle)이 반복되는 재생성 확률과정(regenerative process) 이 된다. 또한 클래스-2 고객의 관점에서 일반 사이클의 바쁜 기간은, 유휴 기간 동안에 클래스-1 고객이 도착하 면, Θ_(k)를 지체 기간으로, H를 서비스 시간으로 하는 M/ G/1 대기행렬의 지체 사이클로 간주될 수 있다. 그리고 유휴 기간 동안에 클래스-2 고객이 도착하면, 서비스 시 간이 H인 표준적인 M/G/1 대기행렬의 바쁜 기간으로 간 주될 수 있다. 이러한 사실을 이용하면 클래스-2 고객의 대기시간 W₂의 LST를 다음과 같이 구할 수 있다[7].

W_{2}^{*} (θ) = \frac{θ + λ_{1} - λ_{1} Θ_{(K)}^{*} (θ)}{(1 + λ_{1} E [Θ_{(K)}])} \cdot \frac{1 - λ_{2} E [H]}{θ - λ_{2} + λ_{2} H^{*} (θ)} .

(29)

모든 선점 우선순위 정책에 대하여 일반 사이클의 구 조는 같으므로 클래스-2 고객의 대기시간 분포에 대한 식 (29)의 형태는 동일하다. 다만 선점 우선순위 정책의 종류에 따라 완성 시간의 구조가 달라져서 H^*(θ )만 차이 가 날 뿐이다.선점 우선순위 정책 하에서는 클래스-2 고 객은 서비스가 시작된 후 완성 시간 H 이후에 시스템을 떠난다. 따라서 클래스-2 고객의 시스템 체류 시간 T₂의 LST는 다음과 같다.

T_{2}^{*} (θ) = W_{^{2, P R}}^{*} (θ) \cdot H^{*} (θ) .

(30)

아울러 식 (29)와 식 (30)을 미분하여 θ = 0을 대입하 면 클래스-2 고객의 대기시간과 체류시간의 기대치를 다 음과 같이 구할 수 있다.

\begin{array}{l} E [W_{2}] = \frac{λ_{1} E [Θ_{(K)}^{2}]}{2 (1 + λ_{1} E [Θ_{(K)}])} + \frac{λ_{2} E {[H]}^{2}}{2 (1 - λ_{2} E [H])} \\ E [T_{2}] = E [W_{2}] + E [H] . \end{array}

(31)

5. 수치 예제

이 장에서는 각각의 선점 우선순위 정책에 대해 유한 용량 대기열의 크기와, 각 클래스의 도착률과 서비스 시 간의 분포가 시스템의 주요 성능 지표인 클래스-1 고객 의 손실 확률과 평균 대기 시간, 그리고 클래스-2 고객의 평균 대기 시간에 어떠한 영향을 미치는지 수치적으로 탐색해 본다. 다양한 선점 우선순위 정책에 대한 성능 지 표의 변화를 좀 더 총체적으로 조망하기 위해서, 본 논문 에서는 선점 재샘플링-반복과 선점 동일-반복 정책뿐 아 니라 Kim[7]에서 도출한 선점 계속 우선순위 정책의 결 과도 함께 비교해 본다.

먼저 유한 용량 대기열의 크기 K의 변화가 시스템 성능에 미치는 영향을 살펴보기 위해 다음과 같은 수치 예제를 사용한다. 클래스-1과 클래스-2 고객의 도착률은 λ₁ = 2와 λ₂ = 1로 설정한다. 서비스 시간의 변동성이 시 스템 성능에 미치는 영향을 제거하기 위해서 서비스 시간 은 확정적 분포를 따르도록 설정하고, S₁ = 1/8, S₂ = 1/8 로 설정한다. 서비스 시간의 변동성에 따른 시스템 성능 의 변화는 서비스 시간의 분포와 관련된 수치 예제에서 살펴볼 것이다.

<Figure 1>은 선점 계속(PR), 선점 재샘플링-반복(PRD), 선점 동일-반복(PRI) 정책에 대하여, 유한 용량 대기열의 크기 K가 변함에 따라 클래스-1 고객의 손실 확률 P^b와 평균 대기 시간 E [W₁ ], 그리고 클래스-2 고객의 평균 대기 시간 E [W₂ ]가 어떻게 변화하는지를 보여준다.

<Figure 1>의 왼쪽과 가운데 그래프에서 보듯이, 선점 우선순위 정책의 종류는 클래스-1 고객에 대한 서비스 성능에 전혀 영향을 미치지 못한다. 이는 어떠한 선점 우 선순위 정책 하에서도 클래스-1 고객에 대한 서비스는 클래스-2 고객의 서비스와 무관하게 수행되기 때문이다. 왼쪽 그래프에서 보듯이 클래스-1 고객의 손실 확률은 유한 용량 대기열의 크기 K가 늘어남에 따라 급속히 감 소하여 0에 가까워진다. 반면 대기열의 크기 K가 늘어남 에 따라 클래스-1 고객의 평균 대기 시간은 증가하여 클 래스-1 고객을 위한 대기열이 무한인 M/G/1/(∞, ∞) 선 점 우선순위 대기열의 평균 대기 시간에 근접함을 볼 수 있다. 이러한 현상은 대기열의 크기가 커짐에 따라 고객 의 손실이 줄어들고 대기열에 머물고 있는 고객수가 증 가하기 때문에 발생한다.

<Figure 1>의 오른쪽 그래프는 대기열의 크기 K가 변함 에 따라 클래스-2 고객의 평균 대기 시간의 변화를 보여준 다. 클래스-1 고객의 대기 시간과 마찬가지로 대기열의 용 량 K가 늘어나면 평균 대기 시간이 증가하여 대기열의 크 기가 무한인 M/G/1/(∞, ∞) 선점 우선순위 대기열의 대기 시간으로 수렴한다. 이는 대기열 크기의 증가가 클래스-1 고객의 바쁜 기간 Θ_(k)의 길이를 늘리고, 이러한 사실은 다시 클래스-2 고객의 완성 시간 H의 길이를 증가시키기 때문에 발생한다. 그러나 클래스-1의 대기 시간과는 다르 게, 클래스-2 고객의 대기 시간은 선점 우선순위 정책의 종류에 따라 달라진다. <Figure 1>의 오른쪽 그래프에서 클래스-2 고객의 서비스 시간이 확정적 분포를 따르면, 선 점 계속(PR) 우선순위 정책이 선점 동일-반복(PRI) 우선순 위 정책에 비해 클래스-2 고객의 평균 대기시간 E [W₂ ]가 모든 K에 대하여 더 낮음을 볼 수 있다. 이러한 현상은, 선점 계속 정책에서는 클래스-2 고객의 서비스가 클래스-1 고객의 도착에 의해서 중지된 후에 서비스가 중지된 지점 에서 재개되므로 원래의 서비스 시간보다 항상 짧은 잔여 서비스 시간으로 서비스가 재개되는데 반해, 선점 동일-반 복 정책에서는 서비스가 중지된 후 원래의 서비스 시간과 동일한 서비스 시간으로 서비스가 반복되기 때문에 발생 한다. 아울러 클래스-2 고객의 서비스 시간이 확정적인 분 포일 때는 선점 재샘플링-반복이나 선점 동일-반복 모두 동일한 평균 대기 시간을 보인다. 이는 확정적 분포인 경 우 재샘플링 하나 원래의 서비스 시간으로 반복하나 모두 동일한 서비스 시간 S₂ = 1/8로 서비스가 반복되기 때문 이다. 서비스 시간의 분포가 달라지면 두 우선순위 정책의 효과는 달라진다(<Figure 6> 참조).

다음으로 클래스-1 고객의 도착률이 시스템 성능에 미 치는 영향을 살펴보기 위해 다음과 같은 수치 예제를 사 용한다. 클래스-1 고객의 대기열의 크기는 K = 2, 클래스 -2 고객의 도착률은 λ₂ = 1로 설정한다. 서비스 시간은 확정적 분포를 따르고 S₁ = 1/8과 S₂ = 1/8로 설정한다. 그리고 클래스-1 고객의 도착률을 0.4에서 4까지 증가시 키면 시스템의 성능의 변화를 살펴보았다.

<Figure 2>는 클래스-1 고객의 손실 확률 P^b와 평균 대기 시간 E [W₁ ], 그리고 클래스-2 고객의 평균 대기 시 간 E [W₂ ]가 클래스-1 고객의 도착률 λ₁이 변함에 따라 어떻게 변화하는지를 선점 계속(PR), 선점 재샘플링-반복 (PRD), 선점 동일-반복(PRI) 정책에 대하여 보여준다. 유 한 용량 대기열의 크기 K의 수치 예제와 마찬가지로 클 래스-1 고객의 손실확률과 대기시간은 선점 우선순위 정 책의 종류에 영향을 받지 않는다.

<Figure 2>의 왼쪽 그래프는 클래스-1 고객의 도착률 λ₁이 증가함에 따라 클래스-1 고객의 손실확률이 급격하 게 증가하는 것을 보여준다. 반면 가운데 그래프에서는 클래스-1 고객의 도착률 λ₁이 증가함에 따라 평균 대기 시간 E [W₁ ]이 완만하게 증가하는 것을 보여준다. 이러한 현상은, 대기열이 무한인 M/G/1/(∞,∞) 우선순위 대기행 렬에서 고객 도착률이 증가함에 따라 급격하게 대기 시 간이 증가하는 것과 차이가 있다(<Figure 2>의 가운데 그래프 참조). 유한 용량 우선순위 대기행렬에서 고객 도 착률에 따른 대기 시간의 증가가 완만한 이유는 고객의 도착률이 증가하면 고객의 손실도 늘어나서 대기 시간의 증가 효과가 제한되기 때문이다. λ₁이 0에 가까워지면 고객 손실 확률이 0에 수렴되므로 유한 용량 대기열의 클래스-1 고객의 평균 대기 시간이 상응하는 무한 용량 대기열의 평균 대기시간에 수렴함을 볼 수 있다.

<Figure 2>의 오른쪽 그래프는 클래스-1 고객의 도착률 이 증가하면 클래스-2 고객의 평균 대기 시간 E [W₂ ]도 증 가하는 것을 보여준다. 유한 용량 대기열 K의 수치 예제 와 마찬가지로 서비스 시간이 확정적 분포일 때는 선점 재샘플링-반복 책과 선점 동일-반복 정책의 평균 대기 시 간은 동일하며, 선점 계속 정책에서는 선점 반복 우선순 위 정책에 비해 클래스-2 고객의 평균 대시 시간에 대한 클래스-1 고객의 도착률의 영향이 완만하게 나타난다.

다음으로 클래스-2 고객의 도착률이 시스템 성능에 미 치는 영향을 살펴보기 위해 다음과 같은 수치 예제를 사 용한다. 클래스-1 고객의 대기열의 크기는 K = 1, 클래스 -1 고객의 도착률은 λ₁ = 2로 설정한다. 서비스 시간은 확정적 분포를 따르고 S₁ = 1/8과 S₂ = 1/8로 설정한다. 그리고 클래스-2 고객의 도착률을 0.4에서 4까지 증가시 키면 시스템의 성능을 살펴보았다.

<Figure 3>의 왼쪽과 가운데 그래프는 클래스-1 고객의 손실 확률 P^b와 평균 대기 시간 E [W₁ ]이 클래스-2 고객의 도착률 λ₂에 전혀 영향을 받지 않음을 보여준다. <Figure 2>의 오른쪽 그래프는 클래스-2 고객의 도착률 λ₂가 증가 함에 따라 클래스-2 고객의 평균 대기시간 E [W₂ ]가 증가 하는 것을 보여준다. 클래스-1 고객의 도착률 λ₁의 수치 예제와 마찬가지로, 서비스 시간이 확정적 분포일 때는 선 점 재샘플링-반복 정책과 선점 동일-반복 정책의 평균 대 기 시간은 동일하고, 선점 계속 정책에서는 선점 반복 우 선순위 정책에 비해 클래스-2 고객의 평균 대시 시간에 대 한 클래스-2 고객의 도착률의 영향이 완만하게 나타난다.

다음으로 클래스-1 고객의 서비스 분포가 시스템 성능 에 미치는 영향을 살펴보기 위해 다음과 같은 수치 예제를 사용한다. 클래스-1 고객의 대기열 크기는 K = 1, 고객의 도착률은 λ₁ = 2와 λ₂ = 1로 설정한다. 클래스-2 고객의 서 비스 시간은 확정적 분포를 따르고 S₂ = 1/8로 설정한다. 그리고 클래스-1 고객의 서비스 시간의 변동성에 따라 시 스템 성능이 어떻게 변화하는지를 살펴보기 위하여 클래 스-1 고객의 서비스 시간 S₁이 발생률이 8n인 Erlang-n 분포 를 따르도록 설정하고, n을 1에서부터 128까지 증가시키 면 시스템의 성능을 살펴본다. 그러면 n의 값이 변화해도 E [S₁ ] = 1/8로 일정하지만, Var[S₁ ] = (1/8)²⋅1/n로 n이 커짐에 따라 분산이 줄어들어 확정적 분포에 가까워진다.

<Figure 4>의 왼쪽과 가운데 그래프는 서비스 시간 S₁ 의 변동계수(CV; coefficient of variation)가 증가하면 클래 스-1 고객의 손실 확률과 평균 대기 시간이 증가함을 보여 준다. <Figure 4>의 오른쪽 그래프는 S₁의 변동계수가 증 가하면 클래스-2 고객의 평균 대기 시간도 증가함을 보여 준다. 이러한 결과는 흥미로운 사실이다. 왜냐하면, S₁의 변동계수가 줄어들면 클래스-1 고객의 손실 확률이 줄어 들므로, 평균 서비스 시간이 동일하면 클래스-1 고객의 바 쁜 기간의 평균을 증가시킬 것이기 때문이다, 이는 다시 클래스-2의 평균 완성 시간 E [H ]를 증가시켜서, 평균 완 성 시간의 효과만 보면 S₁의 변동계수가 줄어들면 클래스 -2 고객의 평균 대기 시간의 증가하여야 한다. 그러나 <Figure 4>의 오른쪽 그래프를 보면 오히려 E [W₂ ]가 S₁의 변동계수가 줄어들면서 같이 감소한다. 이러한 현상이 발 생한 이유에 대한 실마리는 <Figure 5>에서 찾을 수 있다. <Figure 5>의 왼쪽 그래프는 S₁의 변동계수의 변화에 따 른 완성시간의 평균 E [H ]를, 오른쪽 그래프는 완성시간의 2차 모멘트 E [H²]을 보여준다. <Figure 5>는 S₁의 변동계 수가 감소하면 클래스-1 고객의 손실률의 감소로 E [H ]는 증가하지만, 서비스 시간의 변동성의 감소로 완성시간의 분산이 감소하여 E [H²]은 오히려 감소함을 보여준다. 따 라서 이 수치 예제에서는, E [W₂ ]에 대한 식 (31)에서 E [H ] 의 증가에 따른 분모의 효과보다는 E [H²]의 증가에 따른 분자의 효과가 더 크기 때문에 클래스-1의 서비스 시간의 변동성의 감소에 따라 클래스-2 고객의 평균 대시시간이 감소하였음을 알 수 있다.

마지막으로 클래스-2 고객의 서비스 분포가 시스템 성 능에 미치는 영향을 살펴보기 위해 다음과 같은 수치 예제 를 사용한다. 클래스-1 고객의 대기열 크기는 K = 2, 고객 의 도착률은 λ₁ = 2와 λ₂ = 1로 설정한다. 클래스-1 고객의 서비스 시간은 확정적 분포를 따르고 S₁ = 1/8로 설정한 다. 그리고 클래스-2 고객의 서비스 시간의 변동성에 따라 시스템 성능이 어떻게 변화하는지를 살펴보기 위해 클래 스-2 고객의 서비스 시간 S₂를 발생률이 8n인 Erlang-n 분 포로 설정하여 n을 1에서부터 128까지 증가시키면 시스 템의 성능을 살펴보았다. 그러면 n의 값의 변화에도 E [S₂ ] = 1/8로 일정하지만, Var[S₂ ] = (1/8)²⋅1/n로 n이 커짐에 따라 분산이 줄어들어 확정적 분포에 가까워진다.

<Figure 6>의 왼쪽과 가운데 그래프는 클래스-1 고객의 손실 확률 P^b와 평균 대기 시간 E [W₁ ]이 서비스 시간 S₂의 변동계수의 변화와 무관함을 보여준다. <Figure 6> 의 오른쪽 그래프는 변동계수가 증가하면 모든 선점 우 선순위 정책에 대하여 클래스-2 고객의 평균 대기 시간 E [W₂ ]가 증가함을 보여준다. 이는 클래스-2 고객의 서비 스 시간의 변동성이 증가하면 완성시간의 변동성도 증가 하고, 이는 다시 대기시간의 증대효과를 발생시키기 때 문이다(<Figure 7>에 대한 설명 참조).

<Figure 6>의 오른쪽 그래프는 S₂의 변동성의 증가가 E [W₂ ]에 미치는 영향이 선점 우선순위 정책의 종류에 따 라 크게 바뀜을 보여준다. 먼저 선점 재샘플링-반복 우선 순위 정책이 S₂의 변동계수의 증가에 따른 E [W₂ ]의 변화 가 가장 완만하다(다른 두 정책의 E [W₂ ]의 변화가 크기 때문에 거의 변화가 없는 것처럼 그래프에는 표현되었다).

선점 계속 정책의 E [W₂ ]는 S₂의 변동계수가 1일 때 선 점 재샘플링-반복 정책의 E [W₂ ]와 동일하다. 그 이유는 S₂의 변동계수가 1이면 서비스 시간이 지수 분포를 따르 므로 지수 분포의 무기억 속성에 의해 서비스가 중단 지 점에서 재개되나 처음부터 재샘플링 되어 반복되나 선점 된 후의 잔여 서비스 시간의 분포가 동일하기 때문이다. 그러나 변동계수가 점차 줄어들어 확정 분포에 가까워지 면 재샘플링 되어 서비스가 재개되는 것보다 서비스가 중단된 지점에서 다시 서비스하는 것이 잔여 서비스 시 간이 짧아지므로 점차 선점 계속 정책에서의 E [W₂ ]가 선 점 재심플링-반복 정책보다 더 크게 감소한다.

선점 동일-반복 정책의 E [W₂ ]는 S₂의 변동계수가 0에 가까워지면 선점 재샘플링-반복 정책의 E [W₂ ]에 수렴한다. 그 이유는 S₂의 변동계수가 0이면 확정분포가 되므로 재샘 플 되어 다시 서비스가 재개되거나 원래의 서비스 시간으로 다시 서비스 되거나 항상 동일한 서비스 시간이므로 서비스 가 반복되기 때문이다. 그러나 변동계수가 커져서 지수 분 포에 가까워지면 클래스-2 고객의 서비스의 변동성이 커질 수록 선점 동일-반복의 E [W₂ ]가 매우 빠르게 증가함을 볼 수 있다.이러한 이유는 클래스-2 고객의 서비스 시간의 변동 성이 선점 재샘플링과 선점 동일-반복 정책에 다른 효과가 있기 때문이다. 선점 재샘플링-반복 정책에서는 예외적으 로 긴 서비스 시간을 갖는 고객의 서비스는 첫 번째 서비스 시도에서 선점될 가능성이 커진다. 그리고 이 서비스가 선 점되면 원래의 서비스 시간보다 짧은 서비스 시간이 재샘플 링 되어 서비스가 반복될 가능성이 커진다. 반면 선점 동일- 반복 정책 하에서는 예외적으로 긴 서비스 시간을 갖는 고객은 선점될 가능성이 큰 것은 동일하나, 이 고객의 서비 스가 선점되면 다시 원래의 긴 서비스 시간으로 다시 반복 된다. 따라서 예외적으로 긴 서비스 시간을 갖는 고객은 반복적으로 선점될 확률이 높아지므로 서비스 완성시간의 길이가 매우 크게 증가한다. 따라서 클래스-2 고객의 서비스 시간의 분산이 커지면 선점 재샘플링-반복보다는 선점 동일 -반복 정책에서 클래스-2 고객의 완성 시간의 길이와 변동 성이 증가하여 E [W₂ ]도 급격하게 증가하게 된다.

앞서 설명한 내용을 <Figure 7>에서 다시 확인할 수 있 다. <Figure 7>의 왼쪽 그래프는 S₂의 변동계수의 변화에 따른 완성시간의 평균 E [H ]를, 오른쪽 그래프는 완성시 간의 2차 모멘트 E [H²]을 보여준다. <Figure 7>의 왼쪽 그 래프를 보면 선점 계속 정책에서는 S₂의 분산(변동계수) 이 변화하여도 완성시간의 평균 E [H ]는 변화가 없음을 볼 수 있다. 이러한 이유는 선점 계속 정책에서는 S₂의 분 산(변동계수)이 변화하여도 총 서비스 시간의 평균 E [G] 가 E [S₂ ]로 항상 동일하므로 완성시간의 평균 E [H ]는 변 화가 없기 때문이다([7], 식 (53) 참조). 반면 선점 재샘플 링-반복 정책의 E [H ]는 S₂의 변동계수가 1인 지수 분포 일 때는 선점 계속의 E [H ]와 같지만, 변동계수가 0에 근 접하면 확정분포에 가까워져서 선점이 발생될 때마다 거 의 동일한 서비스 시간으로 서비스가 반복되어 E [H ]가 증가한다. 그리고 선점 동일-반복 정책의 완성시간의 평균 E [H ]는 변동계수가 0에 근접하면 확정 분포를 따르는 서 비스 시간이 되므로 선점 재샘플링-반복 정책의 E [H ]와 동일해진다. 그러나 변동계수가 점차 증가하면 평균보다 긴 서비스 시간들이 동일한 서비스 시간으로 반복적으로 선 점되는 효과 때문에 선점 재샘플링-반복 정책의 E [H ]에 비해 매우 커지는 것을 볼 수 있다. <Figure 7>의 오른쪽 그래프를 보면 모든 선점 우선순위 정책에서 S₂의 변동계 수가 증가하면 E [H²]이 증가함을 볼 수 있다(선점 재샘플 링-반복의 E [H²]의 증가 경향이 다른 정책에 비해 미미하 여 거의 변화가 없는 것처럼 그래프에 표현되었다). 식 (31)에서 E [H²]과 E [H ]가 모두 증가하면 E [W₂ ]도 증가하 는 것을 알 수 있다. 그렇기 때문에 <Figure 6>의 오른쪽 그래프에서 선점 계속과 선점 동일-반복 정책은 변동계수 가 증가함에 따라 E [W₂ ]가 뚜렷하게 증가하였다. 반면 선 점 재샘플링-반복 정책은 변동계수가 증가하면 E [H²]는 증가하나 E [H ]는 감소한다. 그렇기 때문에 두 효과가 합 쳐져서 E [W₂ ]의 증가가 매우 완만하였다.

클래스-2 고객의 서비스 시간의 변동성에 따라 선점 우 선순위 정책의 효과가 매우 크게 변화하므로 이를 좀 더 자세히 살펴보기 위해, S₂의 변동계수가 1보다 큰 경우의 시스템 성능의 변화를 살펴본다. 이를 위해 앞의 Erlang 분포의 수치 예제와 동일한데, S₂의 분포가 다음과 같은 두 개의 지수 분포로 이루어진 초지수분포를 따른다고 가 정한다. 발생률이 8m과 8/m인 두 개의 지수분포가 있을 때, 서비스 시간 S₂는 α의 확률로 8m을 발생률로 하는 지수분포를 따르고 1 - α의 확률로 8/m을 발생률로 하는 지수분포를 따른다. 단, m ≥ 1.따라서 m이 커짐에 따라 두 지수 분포의 차이가 커져 초지수분포의 분산이 점차 증가한다.m의 변화에 무관하게 서비스 시간 S₂의 평균이 동일하도록 α = m/(m + 1)로 설정한다. 그러면 E [S₁ ] = 1/8이고 S₂의 변동계수(CV)는 $\sqrt{(2 m^{2} - 3 m + 2) / m}$ 이 되 어, m이 증가할수록 변동계수의 값도 커지게 된다. 그리 고 m의 값을 1부터 2까지 변화시키며 시스템 성능의 변화 를 살펴본다.

<Figure 8>은 S₂의 변동계수의 변화에 따라 E [W₂ ], E [H ], E [H²]의 변화를 보여준다. 왼쪽 그래프에서 확인하듯이 선점 계속과 선점 동일-반복 정책에서는 S₂의 변동계수가 증가하면 클래스-2의 평균 대기 시간 E [W₂ ]가 증가하나, 선점 재샘플링-반복의 경우 오히려 E [W₂ ]가 감소하는 경 향을 보인다. 이러한 현상은, <Figure 8>의 가운데와 오른 쪽 그래프에서 볼 수 있듯이, 선점 재샘플링-반복의 경우 S₂의 변동성이 증가하면 선점에 의해 긴 서비스 시간이 더 짧은 서비스 시간으로 교체될 수 있는 가능성이 커져서 오히려 완성시간의 평균뿐 아니라 변동성도 감소하기 때 문에 발생한다. 따라서 선점 우선순위 정책에 따라 클래스 -2 고객의 서비스 시간의 변동성이 시스템 성능에 미치는 영향이 매우 크게 바뀌는 것을 다시 한 번 확인할 수 있다.

6. 결 론

이 논문에서는 최근에 발표된 Kim[7]의 비선점 및 선 점 계속 우선순위 정책을 가지는 M/G/1/(K, ∞) 대기행렬 에 대한 연구를 선점 재샘플링-반복 및 선점 동일-반복 정책을 가지는 M/G/1/(K, ∞) 대기행렬의 분석으로 확장 하였다. 그리고 분석의 결과를 사용하여 다양한 선점 우 선순위 정책에서 유한 용량 대기열의 크기 K , 고객 도착 률, 서비스 시간의 분포가 시스템 성능에 미치는 영향을 수치 예제로 탐색해 보았다. 특히 클래스-2 고객의 서비 스 시간의 변동성에 따라 선점 정책의 효과가 클래스-2 고객의 서비스 성능에 큰 영향을 미치는 것을 확인할 수 있었다. 서론에서 언급하였듯이 M/G/1/(K, ∞) 선점 우선 순위 대기행렬 모형은, 5G 모바일 다운링크 등 이질적인 트래픽을 서비스하기 위해 선점 스케줄링 기법을 사용하 는 통신 시스템의 성능 분석에 활용될 수 있다. 본 연구는 기존의 연구가 선점 계속 우선순위 정책으로 한정되어 있 었던 것을 선점 반복 우선순위 정책으로 확장함으로써, 우선순위가 높은 고객의 선점으로 중지된 서비스가 중지 된 지점에서 계속되는 시스템뿐 아니라 처음부터 반복되 어야 하는 시스템의 성능 분석에 사용할 수 있는 방법을 제공하였다는데 그 의의가 있다. 특히 통신 트래픽은 서 비스의 변동성이 매우 큰 두터운 꼬리(heavy tail) 분포인 경우가 많고[18], 이 경우 수치 예제에서 살펴본 바와 같 이 선점 계속 정책과 선점 동일-반복 정책의 성능 차이가 매우 크게 발생하므로 본 연구에서 제시된 결과를 이용하 면 좀 더 정확한 시스템 성능 분석이 가능해질 것으로 예 상된다.

마지막으로 본 연구의 한계와 발전 방향에 대하여 언 급하고자 한다. 수치 예제에서 살펴본 바와 같이, 선점 동일-반복 정책으로 운영되는 시스템에서는 우선순위가 낮은 고객의 서비스 시간의 변동성이 커지면 우선순위가 낮은 고객의 평균 대기 시간이 급격하게 증가한다. 따라 서 우선순위가 높은 고객이 도착할 때마다 무조건적으로 선점을 하는 선점 동일-반복 정책보다는 혼합형 선점 우 선순위 정책[8-10, 12] 등이 시스템의 스케줄링 정책으로 적용되는 것이 좋다. 그러므로 본 연구는 혼합형 선점 우 선순위 정책을 갖는 M/G/1/(K, ∞) 대기행렬의 분석으로 확장될 필요가 있다. 아울러 본 연구에서는 시스템의 성 능 지표에 대한 분석만을 수행하였지, 시스템의 성능을 최적화하기 위한 방법을 다루지 않았다. 시스템 운영자 의 관점에서 시스템의 성능을 분석하는 것만큼이나 시스 템의 최적화는 중요한 문제이다. 따라서 트래픽의 손실 과 지연에 따른 비용, 그리고 시스템 운영비용을 고려하 여 최적 대기열의 크기와 우선순위 정책을 결정하는 최 적화 문제에 대한 연구도 향후 수행되어야 할 것이다.

Figure

<Figure 1>.

Performance Measures Over Various Buffer Sizes of K

<Figure 2>.

Performance Measures Over Various Arrival Rates of λ₁

<Figure 3>.

Performance Measures Over Various Arrival Rates of λ₂

<Figure 4>.

Performance Measures Over Various CVs of S₁

<Figure 5>.

The Moments of Effective Service Times Over Various CVs of S₁

<Figure 6>.

Performance Measures Over Various CVs of S₂

<Figure 7>.

The Moments of Effective Service Times Over Various CVs of S₂

<Figure 8>.

Performance Measures Over Various CVs of S₂ (CV > 1) 긴 서비스

Table

<Table 1>.

Key Random Variables

Reference

Al-Begain, K., Dudin, A., Kazimirsky, A., and Yerima, S., Investigation of the M2/G2/1/∞, N queue with restricted admission of priority customers and its application to HSDPA mobile systems, Computer Networks, 2009, Vol. 53, No. 8, pp. 1186-1201.
Chakravarthy, S.R., A dynamic non-preemptive priority queueing model with two types of customers, International Conference on Mathematics and Computing, 2018, pp. 23-42.
Conway, R.W., Maxwell, W.L., and Miller, L.W., Theory of scheduling, Addison-Wesley, 1967.
Demoor, T., Walraevens, J., Fiems, D., De Vuyst, S., and Bruneel, H., Influence of real-time queue capacity on system contents in DiffServ’s expedited forwarding per-hop-behavior, Journal of Industrial and Management Optimization, 2010, Vol. 6, No. 3, pp. 587-602.
Drekic, S. and Stanford, D.A., Reducing delay in preemptive repeat priority queues, Operations Research, 2001, Vol. 49, pp. 145-156.
Jaiswal, N.K., Priority queues, Academic Press, 1968.
Kim, K., Delay cycle analysis of finite-buffer M/G/1 queues and its application to the analysis of M/G/1 priority queues with finite and infinite buffers, Performance Evaluation, 2020, Vol. 143, pp. 102133.
Kim, K., (N, n)-preemptive priority queues, Performance Evaluation, 2011, Vol. 68, No. 7, pp. 575-585.
Kim, K., (N, n)-preemptive repeat-different priority queues, Journal of Society of Korea Industrial and Systems Engineering, 2017, Vol. 40, No. 3, pp. 66-75.
Kim, K., The analysis of an opportunistic spectrum access with a strict T-preemptive priority discipline, Journal of Society of Korea Industrial and Systems Engineering, 2012, Vol. 35, No. 4, pp. 162-170.
Kim, K., T-preemptive priority queue and its application to the analysis of an opportunistic spectrum access in cognitive radio networks, Computers & Operations Research, 2012, Vol. 39, No. 7, pp. 1394-1401.
Kim, K. and Chae, K.C., Discrete-time queues with discretionary priorities, European Journal of Operational Research, 2010, Vol. 200, No. 2, pp. 473-485.
Miao, W., Min, G., Wu, Y., and Wang, H., Performance modelling of preemption-based packet scheduling for data plane in software defined networks, 2015 IEEE international conference on Smart City/SocialCom/SustainCom(SmartCity), 2015, pp. 60-65.
Pandey, S.R., Alsenwi, M., Tun, Y.K., and Hong, C.S., A downlink resource scheduling strategy for URLLC traffic, 2019 IEEE International Conference on Big Data and Smart Computing(bigcomp), 2019, pp. 1-6.
Parkvall, S., Dahlman, E., Furuskar, A., and Frenne, M., NR : The new 5G radio access technology, IEEE Communications Standards Magazine, 2017, Vol. 1, No. 4, pp. 24-30.
Sachs, J., Wikstrom, G., Dudda, T., Baldemair, R., and Kittichokechai, K., 5G radio network design for ultrareliable low-latency communication, IEEE Network, 2018, Vol. 32, No. 2, pp. 24-31.
Van Velthoven, J., Van Houdt, B., and Blondia, C., The impact of buffer finiteness on the loss rate in a priority queueing system, European Performance Engineering Workshop, 2006, pp. 211-225.
Willinger, W., Paxson, V., and Taqqu, M.S., Self-similarity and heavy tails : Structural modeling of network traffic, A Practical Guide to Heavy Tails : Statistical Techniques and Applications, 1998, Vol. 23, pp. 27-53.
Wu, W.-R., Lin, T.-H., and Lee, Y.-H., An indicator-free eMBB and URLLC multiplexed downlink system with correlation-based sfbc, Proceedings of the 3^rd International Conference on Telecommunications and Communication Engineering, 2019, pp. 105-110.
Yang, W., Li, C.-P., Fakoorian, A., Hosseini, K., and Chen, W., Dynamic URLLC and eMBB multiplexing design in 5G new radio, 2020 IEEE 17^th Annual Consumer Communications & Networking Conference(CCNC), 2020, pp. 1-5.
Zhou, Z., Yan, Y., Ruepp, S., and Berger, M., Analysis and implementation of packet preemption for time sensitive networks, 2017 IEEE 18^th International Conference on High Performance Switching and Routing(HPSR), 2017, pp. 1-6.