Journal Search Engine

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

Journal of Society of Korea Industrial and Systems Engineering Vol.47 No.4 pp.39-55
DOI : https://doi.org/10.11627/jksie.2024.47.4.039

Space and Time Priority Queues with Partial Buffer Sharing

Kilhwan Kim†

Department of Management Engineering, Sangmyung University

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

Received 18/08/2024 Finally Revised 04/10/2024 Accepted 04/10/2024

Abstract

Recently, there have been studies on space and time priority queues, where space priorities are given to a class of packets that are sensitive to loss, and time priorities to another class of packets that are sensitive to delay. However, these studies have been restricted to such models with push-out space priorities. In this paper, we extend the studies to the space and time priority M/G/1 model with partial-buffer-sharing (PBS) space priorities, where the whole buffer is divided into two regions: one is shared by packets of all classes and the other is dedicated only for packets of the higher space-priority class. Since the PBS space-priority mechanism can be implemented more readily in communication systems than the push-out one, there have been a lot of contributions on PBS space-priority queues. However, there are no contributions on space and time priority queues with PBS space priorities. To analyze the proposed queueing model, we first study the probabilistic structure of the service time of a packet, which is more involved to analyze than the push-out alternative because it may be divided into three different regimes: a regime (S-period) from the beginning of the service until the shared buffer region becomes full, a second one (P-period) from the end of the S-period until the whole buffer becomes full, a third one (F-period) from the end of the P-period until the end of the service. Using the distributions of the S-, P-, F-periods, we then construct and analyze the embedded Markov chain and the corresponding semi-Markov process governing the system state, and also derive system performance measures such as expected sojourn times and loss probabilities of different priority classes of packets. In numerical examples, we finally explore the effect of the shared buffer size, which is a major system control parameter of PBS priority queues, and the distributions of the service times of packets of different classes on the system performance measures.

Key Words : Priority Queues , Space and Time Priorities , Partial Buffer Sharing

부분 버퍼 공유 정책을 가지는 공간-시간 우선순위 대기행렬

김길환†

상명대학교 경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

스위치나 라우터 같은 통신 시스템은 즉시 처리하기 어려운 패킷을 버퍼에 저장하여 폭주하는 트래픽에 대응한다. 버퍼의 크기는 유한하므로 버퍼 관리 정책에 따라 패킷 손실률 등의 시스템 성능이 크게 영향을 받는다[8]. 또한 통신 시스템은 여러 종류의 트래픽을 동시에 처리하기 때문에 서로 다른 서비스 요구사항을 가지는 트래픽에 대해 서비스를 차별화하기 위해서는 적절한 서비스 우선순위 정책이 필요하다.

통신 시스템에서 서비스 우선순위는 크게 시간 우선순위와 공간 우선순위로 나눌 수 있다. 시간 우선순위는 버퍼에 있는 패킷 중 어느 패킷을 먼저 서비스할지를 결정하는 정책이다. 반면 공간 우선순위는 버퍼 공간의 사용의 우선순위를 결정하는데, 폭주하는 트래픽 때문에 유한용량 버퍼가 가득 찼을 때 새로운 패킷이 도착하면 어떤 패킷이 손실될지를 결정하는 정책이다.

여러 종류의 트래픽을 서비스하는 통신 시스템의 성능 분석에 우선순위 대기행렬 모형이 자주 사용된다[5, 21]. 그런데 우선순위 대기행렬 모형에 대한 대부분의 연구는 버퍼가 무한이라고 가정하고 시간 우선순위만 고려하거나 [16, 17, 19, 20], 서비스 순서는 고려하지 않고 공간 우선 순위만 고려한 연구가 대부분이었다[2, 14, 24, 30]. 공간과 시간 우선순위를 모두 고려한 대기행렬 모형에 대한 연구도 더러 있었지만 이 연구들은 한 트래픽에 공간과 시간 우선순위를 모두 부여하거나[3, 4, 9, 23, 24], 공간과 시간 우선순위를 계층적으로 부여하는 등의 제약이 있었다[23].

인터넷 라우터에는 TCP 패킷처럼 패킷 손실에 민감한 트래픽도 도착할 수 있지만, UDP 패킷처럼 시간 지연에 민감한 트래픽도 함께 도착한다[6]. 그러므로 이러한 시스템에서는 시간 우선순위와 공간 우선순위를 각기 다른 트래픽에 할당할 수 있는 유연한 우선순위 정책이 필요하다. 이러한 이유로 최근에 서로 다른 트래픽에 공간과 시간 우선순위를 다르게 부여하는 공간-시간 우선순위 대기행렬 모형에 대한 연구가 수행되었다[6, 15, 18].

그런데 최근에 수행된 공간-시간 우선순위 대기행렬에 대한 연구는 모두 시간 우선순위로 비선점 정책(nonpreemptive policy)[31]을, 공간 우선순위로 밀어내기 정책 (push-out policy)을 채택하였다.

공간 우선순위 정책은 크게 밀어내기(push-out) 정책과 부분 버퍼 공유(이하 PBS(partial buffer sharing)) 정책으로 나눌 수 있다. 밀어내기 정책에서는 버퍼가 가득 차 있을 때 공간 우선순위가 높은 패킷이 도착하면 버퍼에 있는 공간 우선순위가 낮은 패킷을 밀어내고 버퍼에 들어간다 [3, 7, 22]. 이 정책은 다시 버퍼에 낮은 우선순위 패킷이 있으면 항상 밀어내기에 성공하는 엄격한 밀어내기 정책 (strict push-out policy)과 베르누이 확률로 밀어내기에 성 공하는 확률적 밀어내기 정책(randomized push-out policy) 으로 나뉘어진다. 반면 PBS 정책은 버퍼의 일정 부분은 모든 트래픽이 공용으로 공유하지만 버퍼의 나머지 부분은 공간 우선순위가 높은 패킷만 전용으로 사용하는 정책이다. 공용 버퍼와 전용 버퍼의 크기를 어떻게 조정하는지에 따라 서로 다른 트래픽에 할당되는 공간 우선순위의 차별화 정도가 달라진다. 밀어내기 정책에서는 특정 트래픽을 위한 전용 공간이 없이 모든 버퍼를 공유하므로 버퍼의 활용도가 증가하고, 트래픽의 도착 상황에 따라 버퍼 공간의 사용이 동적으로 조정되는 장점이 있으나, 버퍼 중간에서 밀어내기 당한 패킷의 공간을 재정렬하도록 통신 시스템을 구현하는 것이 까다롭다[1]. 반면 PBS 정책은 버퍼를 공용과 전용 공간으로 나누기만 하면 되므로 통신 시스템에서 구현하는 것이 매우 간단하나, 우선순위가 높은 트래픽을 위한 전용 공간을 할당해야 하므로 밀어내기 정책에 비해 버퍼 활용도가 감소하고 사전에 트래픽의 강도를 예측하여 전용 공간의 비율을 결정해야 하는 단점이 있다. 그러나 SDN(software-defined networking) 기술의 발달로 버퍼에서 전용 공간의 비율을 동적으로 조정할 수 있으므로 PBS의 단점은 점차 감소하고 있다[32].

PBS 정책의 이러한 구현 상의 용이성 때문에 아직까지도 다양한 통신 시스템에 사용되고 있고, 이러한 시스템의 성능 분석을 위한 대기행렬 연구가 지속되고 있다. [27]에서는 인지 무선 네트워크(cognitive radio networks)에서 주 사용자와 부사용자의 패킷 손실 확률을 차별화하기 위하 여 PBS 정책을 사용하는 대기행렬 모형을 분석하였다. Gudimalla and Perati[11], Gudimalla et al.[10], Perati and Gudimalla[26]에서는 WDM(wavelength division multiplexing) 인터넷 라우터에서 PBS 정책의 효과를 대기행렬 모형으로 분석을 수행하였다. Gudimalla et al.[10]과 Reddy et al.[28]에서는 인터넷 라우터에서 자기 유사성(self-similarity) 트래픽의 서비스 차별화를 위하여 PBS 정책을 사용하는 대기행렬 모형을 분석하였다. Huang et al.[13]에서는 GNSS(Global Navigation Satellite System)에서 다른 유형의 트래픽에 대한 차별화된 처리를 위하여 PBS 정책을 사용하는 대기행렬 모형을 분석하였다. Mallikarjuna[25]에서는 스마트 그리드 시스템에서 서로 다른 SLA(Service Level Agreement)의 트래픽을 만족시키기 위하여 PBS 정책을 가지는 대기행렬 모형을 분석하였다. 그러나 이러한 PBS 우선순위 대기행렬에 대한 연구는 모두 공간 우선순위에 따른 패킷 손실률을 분석하는 연구였고, 시간과 공간 우선순위를 서로 다른 트래픽에 배분했을 때의 효과를 살펴본 연구는 아니었다.

본 연구에서는 지금까지 공간 우선순위를 밀어내기 정책으로 한정하였던 공간-시간 우선순위 M/G/1 대기행렬에 대한 연구를 PBS 정책으로 확장한다. 시간 우선순위는 이전 연구처럼 비선점 정책을 택한다. 본 연구는 공간 우선순위 정책을 PBS로 확장한 것 외에도 다음과 같은 의의를 가진다.

첫째, PBS 정책 하의 M/G/1 대기행렬의 분석은 밀어내기 정책보다 시스템의 확률적 상태 전이를 분석하는 것이 까다롭다. 왜냐하면 밀어내기 정책 하에서는 서비스 시간 동안의 상태 전이를 서비스 시작 시점의 시스템 상태와 서비스 시간 동안 도착하는 우선순위가 다른 패킷의 수만 알고 있으면 도출할 수 있으나[18], PBS 정책 하에서는 서 비스 시간 동안 우선순위가 다른 패킷의 도착 순서가 공용 버퍼에 있는 패킷의 분포에 영향을 주고 이는 다시 시스템의 상태 전이에 영향을 준다. 본 연구에서는 이러한 복잡 한 시스템 상태 전이를 분석하기 위하여 일반 분포를 따르는 서비스 시간 동안 공용 버퍼와 전체 버퍼가 가득차는 사건이 일어날 확률과 이러한 사건 이후의 잔여 서비스 시간의 분포를 분석한다(제3장 참조).

둘째, PBS 정책 하에서는 공용 버퍼의 크기라는 조절 변수가 우선순위가 다른 트래픽의 패킷 손실률에 크게 영향을 준다. 뿐만 아니라 공간-시간 우선순위 대기행렬에서는 공간과 시간의 우선순위가 한 트래픽이 모두 가지고 있지 않기 때문에 공간 우선순위의 효과가 시간 우선순위가 다른 트래픽의 지연 시간에 영향을 준다. 본 연구에서는 공간 우선순위의 조절 변수가 패킷 손실률뿐 아니라 평균 대기시 간에 어떤 영향을 주는지를 다양한 수치 예제로 분석한다. 이를 통해 공간-시간 우선순위가 전반적인 시스템 성능에 어떤 영향을 주는지에 대한 이해를 도모한다.

이 논문의 나머지 부분은 다음처럼 구성되어 있다.

제2장에서는 이 논문에서 탐구하고자 하는 공간-시간 우선순위 대기행렬 모형을 정식화 한다. 제3장에서는 시스템 분석에 필요한 패킷 서비스 시간의 확률적 구조를 분석한다. 제4장에서는 서비스 종료 시점의 시스템 상태 변화를 분석하기 위해 시스템 상태를 내재 마코프 체인과 상응하는 준마코프 과정으로 모형화 하고 시스템 상태의 안정상태 확률을 구한다. 제5장에서는 내재 마코프 체인과 준마코프 과정의 분석 결과를 이용하여 주요 시스템 성능 지표를 도출한다. 제6장에서는 다양한 서비스 시간 분포에서 공간 우선순위 조절 변수인 공용 버퍼 크기가 주요 성능 지표에 미치는 영향을 수치적으로 분석한다. 마지막으로 제7장에서 연구의 주요 결론과 시사점을 제시하 며 논문을 마무리한다.

2. 모 형

이 논문에서는 다음과 같은 유한용량 M/G/1 대기행렬 모형을 다룬다. 시스템에는 두 종류의 트래픽이 도착하는 데, 한 종류의 트래픽은 패킷의 손실에 민감하고, 다른 종류의 트래픽은 패킷의 지연 시간에 민감하다. 우리는 손실에 민감한 트래픽과 지연에 민감한 트래픽을 각각 클래스- L과 클래스-D라고 부르기로 한다. 클래스-h 패킷은 시스템에 도착률 λ_h의 포아송 과정으로 도착한다. 단, λ_h > 0, h = L ,D . 총 패킷 도착률을 λ라고 하면 λ = λ_L + λ_D이다. 시스템의 패킷 전송 링크는 한 개이고, 클래스-h 패킷 하 나를 전송하는 데 소요되는 서비스 시간 S_h는 i.i.d. 일반 분포 S_h (t)를 따르고 기대치는 0보다 크지만 유한하다고 가정한다. 즉, 0 < E [S_h] < ∞. $S_{h}^{*}$ (s)는 서비스 시간의 분포 S_h (t)의 LST(Laplace-Stieltjes Transform)이다. 단, t ≥ 0, R (s) ≥ 0.

패킷이 도착했을 때 링크가 다른 패킷의 전송으로 바쁘면 시스템의 버퍼에 들어가서 대기한다. 버퍼는 K개의 슬롯으로 구성되어 있고, 하나의 슬롯에 하나의 패킷이 저장된다. 버퍼의 모든 슬롯이 가득 차 있을 때 새로운 패킷이 도착하면 그 패킷은 즉시 손실된다.

클래스-D 패킷은 지연에 민감하므로, 클래스-L 패킷에 대해 다음의 비선점 시간 우선순위를 가진다. 패킷 전송이 완료되어 전송 링크가 유휴 상태가 되었을 때, 버퍼에 클래스-D 패킷이 대기하고 있으면 먼저 도착한 클래스-L 패킷이 있더라도 먼저 전송된다. 동일한 클래스의 패킷은 선입선출(FIFO)로 전송 순서가 정해진다.

반면 클래스-L 패킷은 손실에 민감하므로, 클래스-D 패킷에 비해 다음과 같은 PBS 공간 우선순위를 가진다. 크 키 K의 전체 버퍼는 크기 Ks의 공용 버퍼와 크기 K -K_s 의 클래스-L 패킷만의 전용 버퍼로 나뉜다. 단, 0 ≤ K_s ≤ K . PBS 정책은 먼저 공용 버퍼를 채운 후에 전용 버퍼를 사용하는데, 버퍼에 대기중인 패킷의 수를 N_Q 라고 하면 다음처럼 작동된다.

0 ≤ N_Q < K_s이면, 공용 버퍼에 빈자리가 존재한다. 그러므로 전송 링크가 바쁠 때 도착한 패킷은 자신의 클래스에 무관하게 항상 공용 버퍼에 저장되고 손실 되지 않는다.
K_s ≤ N_Q < K이면, 공용 버퍼는 가득 차 있지만, 전용 버퍼에는 빈자리가 있는 상태이다. 그러므로 전송 링크가 바쁠 때 새로 도착한 클래스-L 패킷은 전용 버퍼에 저장되고 손실되지 않지만, 새로 도착한 클래스 -D 패킷은 즉시 손실된다.
N_Q = K이면, 전체 버퍼가 가득 찼으므로 클래스에 무관하게 모든 도착한 패킷은 손실된다.

K_s = K이면, 전체 버퍼를 모든 클래스가 공유하므로 공간 우선순위가 없는 대기행렬 모형이 된다. 반면 K_s = 0이면, 전체 버퍼가 클래스-L 패킷의 전용 공간이므로 클래스 -D 패킷은 전송 링크가 유휴 상태일 때 도착하여야만 시스템에 입장이 가능하고 그 외의 경우에는 모두 손실되는 극단적인 공간 우선순위 대기행렬 모형이 된다.

3. 서비스 시간의 확률적 구조

패킷 하나를 전송하는 서비스 시간은 다음과 같은 기간으로 나눠볼 수 있다. (1) 공용 버퍼가 비어 있어서 모든 클래스의 패킷이 도착할 수 있는 기간, (2) 공용 버퍼는 가득 찼지만 전용 버퍼가 비어 있어서 클래스-L 패킷은 도착할 수 있는 기간, (3) 전체 버퍼가 가득 차서 모든 클래스의 패킷이 손실되는 기간. 이 기간들을 각각 S(ared)-기간, P(artial)-기간, F(ull)-기간이라고 하자. 서비스를 시작 했을 때의 시스템의 상태와 서비스 동안의 패킷 도착 과정에 의해, 한 패킷의 서비스 시간 동안 S, P, F-기간이 모두 발생할 수도 있고, 그중 한두 기간만 발생할 수도 있다. 그리고 서비스 시간 동안 S, P, F-기간 발생의 확률적 구조는 서비스 시간 직후의 시스템 상태와 서비스 시간 동안의 패킷 손실 사건에 영향을 미친다. 그러므로 본격적으로 시스템의 상태 변화를 확률적으로 분석하기에 앞서서, 서비스 시간의 확률적 구조를 먼저 탐구해 본다.

확률적으로 결정되는 어떤 시간 구간 Y를 고려해 보자. 시간 구간 Y는 주로 한 패킷의 서비스 시간 S_L 또는 S_D를 나타내지만, 어떨 때는 앞서 설명한 S, P, F-기간처럼 좀 더 복잡한 구조를 가지는 시간 구간일 수도 있다. Y와 관련된 다음 기호를 정의한다.

Y (t) : Y의 분포 함수.
E [Y]: Y의 기대치. 0 < E [Y] < ∞로 가정된다.
Y^*(s) : Y (t)의 LST.
A_h (Y) , h = L ,D : Y 동안 도착한 클래스-h 패킷수.
A (Y) : Y 동안 도착하는 총 패킷수. 즉, A (Y) = A_L (Y) + A_D (Y) .

A_h (Y)와 A (Y)와 관련된 다음 확률을 정의한다.

\begin{matrix} a_{(l, m)} (Y) = P r {A_{L} (Y) = l, A_{D} (Y) = m} \\ = \int_{t = 0}^{\infty} \frac{{(λ_{L} t)}^{l}}{l!} \frac{{(λ_{D} t)}^{m}}{m!} e^{- (λ_{L} + λ_{D}) t} d Y (t) \\ a_{(l, .)} (Y) = P r {A_{L} (Y) = l} = \int_{t = 0}^{\infty} \frac{{(λ_{L} t)}^{l}}{l!} e^{- λ_{L} t} d Y (t) \\ a_{n} (Y) = P r {A (Y) = n} = \int_{t = 0}^{\infty} \frac{{(λ t)}^{n}}{n!} e^{- λ t} d Y (t) \\ b_{(l, m)} = P r {A_{L} (Y) = l, A_{D} (Y) = m | A (Y) = l + m} \\ = (\begin{matrix} l + m \\ l \end{matrix}) {(\frac{λ_{L}}{λ})}^{l} {(\frac{λ_{D}}{λ})}^{m} . \end{matrix}

단, l, m, n ≥ 0. b_(l,m)의 정의에서 Y가 제거된 이유는 포아송 과정의 성질에 의해서 조건부 확률 Pr{A_L (Y) = l,A_D (Y) = m∣A (Y) = l + m }이 Y의 분포에 독립이기 때문이다[29]. 그리고 정의에 의해 다음이 성립한다.

a_{(l, m)} = a_{l + m} b_{(l, m)} .

A_h (Y), A (Y) , Y의 결합분포를 나타내는 다음과 같은 부분 LST를 정의한다.

\begin{matrix} a_{(l, m)}^{*} (s; Y) = P r {A_{L} (Y) = l, A_{D} (Y) = m} \\ \times E [e^{- s Y} | A_{L} (Y) = l, A_{D} (Y) = m] \\ = \int_{t = 0}^{\infty} \frac{{(λ_{L} t)}^{l}}{l!} \frac{{(λ_{D} t)}^{m}}{m!} e^{- (s + λ_{L} + λ_{D}) t} d Y (t) \end{matrix}

(1)

\begin{matrix} a_{(l, .)}^{*} (s; Y) = P r {A_{L} (Y) = l} \cdot E [e^{- s Y} | A_{L} (Y) = l] \\ = \int_{t = 0}^{\infty} \frac{{(λ_{L} t)}^{l}}{l!} e^{- (s + λ_{L}) t} d Y (t) \end{matrix}

(2)

\begin{matrix} a_{n}^{*} (s; Y) = P r {A (Y) = n} \cdot E [e^{- s Y} | A (Y) = n] \\ = \int_{t = 0}^{\infty} \frac{{(λ t)}^{n}}{n!} e^{- (s + λ) t} d Y (t) . \end{matrix}

(3)

단, l, m, n ≥ 0이고 R (s) ≥ 0. 더불어 S, P, F-기간의 분석에 사용할 다음 확률변수를 정의한다.

B_n : 시행 횟수가 n이고 성공확률이 λ_D/λ인 이항 분포를 따르는 이산확률변수.
E_υ : 도착률이 λ이고 모양 매개변수가 υ인 Erlang 분포를 따르는 연속확률변수.
$E_{l}^{L}$ : 도착률이 λ_L이고 모양 매개변수가 l인 Erlang 분포를 따르는 연속확률변수.

B_n의 정의와 포아송 과정의 성질에 의해 다음이 성립 한다.

P r {B_{n} = m} = b_{(n - m, n)}, 0 \leq m \leq n .

어떤 시간 구간 Y 동안 발생할 수 있는 S, P, F-기간을 분석하기 위하여 다음과 같은 확률변수를 정의하자. 구간 Y의 시작 시점에 버퍼에 K_s - υ 개의 패킷이 있다고 하자. 단, 0 ≤ υ ≤ K_s . 즉, 공용 버퍼에 υ 개의 빈 슬롯이 있는 상태에서 구간 Y가 시작된다. Y 동안 도착하는 총 패킷 수 A (Y) ≥ υ이면, 구간 Y 중에 공용 버퍼가 가득 차는 사건이 발생한다. 그리고 Erlang 분포와 포아송 과정의 정의에 의해 A (Y) ≥ υ와 E_υ ≤ Y는 동일한 사건이다. 따라서 E_υ ≤ Y이면, E_υ는 Y가 시작되어 공용 버퍼가 가득 찰 때까지의 경과시간(elapsed time)이 되고, Y -E_υ는 공용 버퍼가 가득 찬 이후의 의 잔여시간(remaining time)이 된다(<Figure 1> 참조). 편의를 위해 E₀를 확률 1로 0의 값으로 퇴적된 확률변수라고 하면, υ = 0일 때의 공유 버퍼가 가득 찰 때까지의 경과시간과 잔여시간을 E₀ = 0와 Y -E₀ = Y로 나타낼 수 있다. 그러면 E_υ ≤ Y라는 사건과 경과시간 E_υ와 잔여시간 Y -E_υ의 부분 LST $R_{υ}^{*} (s_{1}, s_{2}; λ, Y)$ 는 다음과 같이 표현된다.

\begin{array}{l} R_{υ}^{*} (s_{1}, s_{2}, λ, Y) \\ = P r {E_{υ} \leq Y} \cdot E [e^{- s_{1} E_{υ}} e^{- s_{2} (Y - E_{υ})} | E_{υ} - Y] \\ = {\begin{array}{l} P r (Y \geq 0) \cdot E [e^{- s_{10}} e^{- s_{2} Y} | Y \geq 0], & υ = 0 \\ \int_{x = 0}^{\infty} \int_{t = 0}^{x} e^{- s_{1} t} e^{- s_{2} (x - t)} λ e^{- λ t} \frac{{(λ t)}^{υ - 1}}{(υ - 1)!} d t d Y (x), & υ \geq 1 \end{array} \\ = {\begin{array}{l} Y^{*} (s_{2}), & υ = 0 \\ \int_{x = 0}^{\infty} e^{- s_{2} x} \int_{t = 0}^{x} λ e^{- (λ + s_{1} - s_{2}) t} \frac{{(λ t)}^{υ - 1}}{(υ - 1)!} d t d Y (x), & υ \geq 1 \end{array} \end{array}

(4)

단, R (s₁), R (s₂) ≥ 0. υ = 0,1일 때의 식 (4)를 초기 조 건으로 하여, υ ≥ 2일 때의 식 (4)를 부분적분하여 얻은 결 과를 축차적으로 풀면 다음을 얻는다.

\begin{matrix} R_{υ}^{*} (s_{1}, s_{2}; λ, Y) = {(\frac{λ}{λ + s_{1} - s_{2}})}^{υ} Y^{*} (s_{2}) \\ - \sum_{n = 0}^{υ - 1} {(\frac{λ}{λ + s_{1} - s_{2}})}^{υ - n} a_{n}^{*} (s_{1}; Y) \end{matrix}

(5)

단, υ ≥ 0, R (s₁), R (s₂) ≥ 0, λ + s₁ - s₂ ≠ 0.

A_L (Y -E_υ)를 E_υ ≤ Y일 때 잔여시간 Y -E_υ 동안 도착한 클래스-L 패킷수라고 하자. 그리고 공용 버퍼가 가득 차는 사건 E_υ ≤ Y , 경과시간, 잔여시간, 그리고 A_L (Y -E_υ)의 결합분포와 관련된 부분 LST를 다음처럼 정의하자.

\begin{array}{l} {\tilde{a}}_{υ; (l, .)}^{*} (s_{1}, s_{2}; Y) \\ = P r {E_{υ} \leq Y, A_{L} (Y - E_{υ}) = l} \\ \times E [e^{- s_{1} E_{υ}} e^{- s_{2} (Y - E_{υ})} | E_{υ} \leq Y, A_{L} (Y - E_{υ}) = l] \\ = {\begin{array}{l} a_{(l, .)}^{*} (s_{2}; Y), & υ = 0 \\ \int_{x = 0}^{\infty} \int_{t = 0}^{x} (\begin{matrix} e^{- s_{1} t} e^{- s_{2} (x - t)} \frac{{λ_{L} (x - t)}^{l}}{l!} \\ \times e^{- λ_{L} (x - t)} λ e^{- λ t} \frac{{(λ t)}^{υ - 1}}{(υ - 1)!} \end{matrix}) d t d Y (x), & υ \geq 1 \end{array} \\ {\tilde{a}}_{υ; (l, .)}^{*} (s; Y) \\ = P r {E_{υ} \leq Y, A_{L} (Y - E_{υ}) = l} \\ \times E [e^{- s Y} | E_{υ} \leq Y, A_{L} (Y - E_{υ}) = l] \\ = {\begin{array}{l} a_{(l, .)}^{*} (s; Y), & υ = 0 \\ \int_{x = 0}^{\infty} e^{- s x} \int_{t = 0}^{x} (\begin{matrix} \frac{{λ_{L} (x - t)}^{l}}{l!} e^{- λ_{L} (x - t)} \\ \times λ e^{- λ t} \frac{{(λ t)}^{υ - 1}}{(υ - 1)!} \end{matrix}) d t d Y (x), & υ \geq 1. \end{array} \end{array}

단, l ≥ 0. ${\tilde{a}}_{υ; (l, .)}^{*} (s_{1}, s_{2}; Y)$ 와 $R_{υ}^{*} (s_{1}, s_{2}; λ, Y)$ 의 정의에 의해서 다음 관계가 성립한다.

\sum_{l = 0}^{\infty} {\tilde{a}}_{υ; (l, .)}^{*} (s_{1}, s_{2}; Y) z^{l} = R_{υ}^{*} (s_{1}, s_{2} + λ_{L} - λ_{L} z; λ, Y)

(6)

또한 $a_{(l, .)}^{*} (s; Y)$ 와 Y^*(s)의 정의에 의해서 다음 관계가 성립한다.

\sum_{l = 0}^{\infty} a_{(l, .)}^{*} (s; Y) z^{l} = Y^{*} (s + λ_{L} - λ_{L} z)

(7)

그러므로 (5), (6), (7)에서 다음 식을 얻는다.

\begin{array}{l} \sum_{l = 0}^{\infty} {\tilde{a}}_{υ; (l, .)}^{*} (s_{1}, s_{2}; Y) z^{l} \\ = {(\frac{λ}{s_{1} - s_{2} + λ_{D} + λ_{L} z})}^{υ Y^{*}} (s_{2} + λ_{L} - λ_{L} z) \\ - \sum_{n = 0}^{υ - 1} {(\frac{λ}{s_{1} - s_{2} + λ_{D} + λ_{L} z})}^{υ - n} a_{n}^{*} (s_{1}; Y) \\ = {(\frac{λ}{s_{1} - s_{2} + λ_{D} + λ_{L} z})}^{υ} \sum_{l = 0}^{\infty} a_{(l, .)}^{*} (s_{2}; Y) z^{l} \\ - \sum_{n = 0}^{υ - 1} {(\frac{λ}{s_{1} - s_{2} + λ_{D} + λ_{L} z})}^{υ - n} a_{n}^{*} (s_{1}; Y) \end{array}

(8)

단, υ ≥ 0, R (s₁), R (s₂) ≥ 0, |z| ≤ 1, λ + s₁ - s₂ ≠ 0. (8) 의 양변의 zl 계수의 관계식에서 ${\tilde{a}}_{υ; (l, .)}^{*} (s_{1}, s_{2}; Y)$ 에 대한 다음 식을 얻는다.

\begin{array}{l} {\tilde{a}}_{υ; (l, .)}^{*} (s_{1}, s_{2}; Y) \\ = {(\frac{λ}{s_{1} - s_{2} + λ_{D}})}^{υ} a_{(l, .)}^{*} (s_{2}; Y) \\ - \sum_{g = 1}^{min {υ, l}} (\begin{matrix} υ \\ g \end{matrix}) {(\frac{λ_{L}}{s_{1} - s_{2} + λ_{D}})}^{g} {\tilde{a}}_{υ; (l - g, .)}^{*} (s_{1}, s_{2}; Y) \\ - \sum_{n = 0}^{υ - 1} (\begin{matrix} n \\ l \end{matrix}) {(\frac{λ}{s_{1} - s_{2} + λ_{D}})}^{υ - n} {(\frac{λ_{L}}{s_{1} - s_{2} + λ_{D}})}^{l} a_{n}^{*} (s_{1}; Y) . \end{array}

(9)

단, υ,l ≥ 0. 그리고 ${\tilde{a}}_{υ; (l, .)}^{*} (s_{1}, s_{2}; Y)$ 와 ${\tilde{a}}_{υ; (l, .)}^{*} (s; Y)$ 의 정 의에 의해 υ,l ≥ 0에 대해 다음 식을 얻는다.

\begin{matrix} {\tilde{a}}_{υ; (l, .)}^{*} (s; Y) = {{\tilde{a}}_{υ; (l, .)}^{*} (s_{1}, s_{2}, Y) |}_{s_{1} = s_{2} = s} \\ = {(\frac{λ}{λ_{D}})}^{υ} a_{(l, .)}^{*} (s; Y) - \sum_{g = 1}^{min {υ, l}} (\begin{matrix} υ \\ g \end{matrix}) {(\frac{λ_{L}}{λ_{D}})}^{g} {\tilde{a}}_{υ; (l - g, .)}^{*} (s; Y) \\ - \sum_{n = l}^{υ - 1} (\begin{matrix} n \\ l \end{matrix}) {(\frac{λ}{λ_{D}})}^{υ - n} {(\frac{λ_{L}}{λ_{D}})}^{l} a_{n}^{*} (s; Y) . \end{matrix}

(10)

시간 구간 Y 동안 공용 버퍼가 가득 찬 후에 다시 전체 버퍼가 가득 차는 사건을 분석하기 위하여 다음과 같은 좀 더 복잡한 Y의 잔여시간을 고려해 보자. 클래스-L을 위한 전용 버퍼의 크기를 l = K -K_s이라고 하자. 사건 E_υ ≤ Y가 발생하여 공용 버퍼가 가득 찬 후, 잔여 시간 Y -E_υ 동안 도착한 클래스-L 패킷수 A_L (Y -E_υ) ≥ l이라고 하자. 그러면 전체 버퍼가 가득 차는 사건이 시간 구간 Y 중에 발생한다. 그리고 $E_{l}^{L}$ 의 정의에 의해, 사건 A_L (Y -E_υ) ≥ l과 $E_{l}^{L}$ ≤ Y -E_υ는 동일한 사건이 된다. 따라 서 Y -E_υ ≥ $E_{l}^{L}$ ≥ 0이면 Y -E_υ - $E_{l}^{L}$ 는 공용 버퍼와 전체 버퍼가 가득 차는 사건이 발생한 후의 Y의 잔여 시간이 된다(<Figure 1> 참조). 아울러 분석의 편의를 위해서 $E_{0}^{L}$ = 0 으로 퇴적된 확률변수라고 정의한다(이 경우에는 K_s = K로 클래스-L의 전용 공간이 없이 전체 버퍼가 공유되는 경우이다.). 따라서 E_υ + $E_{l}^{L}$ ≤ Y이면, E_υ , $E_{l}^{L}$ , Y -E_υ - $E_{l}^{L}$ 은 각각 시간 구간 Y의 S, P, F-기간의 길이가 된다.

<Figure 1>에서 보듯이 $E_{l}^{L}$ 과 Y -E_υ - $E_{l}^{L}$ 는 E_υ와 Y -E_υ와 동일한 확률 구조를 가진다. 단지 Y가 (Y -E_υ|E_υ ≤ Y)로, 포아송 과정의 도착률이 λ에서 λ_L으 로, 그리고 υ가 l로 대체된 것이다. 따라서 Y -E_υ - $E_{l}^{L}$ 의 분포와 관련된 부분 LST는 다음처럼 표현된다.

\begin{array}{l} {\tilde{R}}_{υ; (l, .)}^{*} (s; λ, λ_{L}, Y) = Pr {E_{υ} \leq Y, E_{l}^{l} \leq Y - E_{υ}} \\ \times E [e^{- s (Y - E_{υ} - E_{l}^{L})} | E_{υ} \leq Y, E_{l}^{L} \leq Y - E_{υ}] \\ = Pr {E_{υ} \leq Y} Pr {E_{l}^{L} \leq Y - E_{υ} | E_{υ} \leq Y} \\ \times E [e^{- s (Y - E_{υ} - E_{l}^{L})} | E_{υ} \leq Y, E_{l}^{L} \leq Y - E_{υ}] \\ = Pr {E_{υ} \leq Y} R_{l}^{*} (0, s; λ_{L}, Y - E_{υ} | E_{υ} \leq Y) . \end{array}

단, $R_{l}^{*}$ (0, s ; λ_L, Y -E_υ∣E_υ ≤ Y)은 $R_{^{υ}}^{*}$ (0, s ; λ, Y)에서 υ, λ, Y가 l , λ_L , (Y -E_υ|E_υ ≤ Y)로 대체된 부분 LST이 다. 따라서 (5)를 얻었을 때와 같은 과정으로 다음 식을 얻는다.

\begin{array}{l} R_{l}^{*} (0, s; λ_{L}, Y - E_{υ} | E_{υ} \leq Y) \\ = {(\frac{λ_{L}}{λ_{L} - s})}^{l} E [e^{- s (Y - E_{υ})} | E_{υ} \leq Y] \\ - \sum_{n = 0}^{l - 1} {(\frac{λ_{L}}{λ_{L} - s})}^{l - n} Pr {A_{L} (Y - E_{υ}) = n | E_{υ} \leq Y} \end{array}

이 식은 식 (5)에 υ = l , s₁ = 0, s₂ = s , λ = λ_L , Y = (Y - E_υ∣E_υ ≤ Y)를 대입한 결과와 같다. 그러므로 위의 두 식과 (5)에서 다음 결과를 얻는다.

\begin{array}{l} {\tilde{R}}_{υ; (l, .)}^{*} (s; λ, λ_{L}, Y) \\ = {(\frac{λ_{L}}{λ_{L} - s})}^{l} Pr {E_{υ} \leq Y} E [e^{- s (Y - E_{υ})} | E_{υ} \leq Y] \\ - \sum_{n = 0}^{l - 1} {(\frac{λ_{L}}{λ_{L} - s})}^{l - n} Pr {E_{υ} \leq Y, A_{L} (Y - E_{υ}) = n} \\ = {(\frac{λ_{L}}{λ_{L} - s})}^{l} R_{υ}^{*} (0, s; λ, Y) - \sum_{n = 0}^{l - 1} {(\frac{λ_{L}}{λ_{L} - s})}^{l - n} {\tilde{a}}_{υ; (n, \cdot)}^{*} (0; Y) \\ = {(\frac{λ_{L}}{λ_{L} - s})}^{l} {(\frac{λ}{λ - s})}^{υ} Y^{*} (s) \\ - {(\frac{λ_{L}}{λ_{L} - s})}^{l} \sum_{n = 0}^{υ - 1} {(\frac{λ}{λ - s})}^{υ - n} a_{n} (Y) \\ - \sum_{n = 0}^{l - 1} {(\frac{λ_{L}}{λ_{L} - s})}^{l - n} {\tilde{a}}_{υ; (n, \cdot)}^{*} (0; Y), υ, l \geq 0. \end{array}

(11)

마지막으로, 시간 구간 Y의 시작 시점에 공용 버퍼에는 υ개의 여유 공간이 있고 전용 버퍼에는 l개의 여유 공간이 있다고 할 때, S, P, F-기간의 길이 Y_s, Y_p, Y_f의 기대치를 구해 보자. S-기간은 Y 동안 클래스와 무관하게 υ개의 패 킷이 도착하면 길이가 E_υ이고 그렇지 않으면 Y이므로, $R_{υ}^{*} (s_{1}, s_{2}; λ, Y)$ 의 정의에 의해 다음이 성립한다.

\begin{array}{l} E [Y_{s}] = E [min {Y, E_{υ}}] \\ = Pr {E_{υ} > Y} \cdot E [Y | E_{υ} > Y] \\ + Pr {E_{υ} \leq Y} \cdot E [E_{υ} | E_{υ} \leq Y] \\ = E [Y] - Pr {E_{υ} \leq Y} \cdot E [Y - E_{υ} | E_{υ} \leq Y] \\ = {E [Y] + \frac{\partial}{\partial s} R_{υ}^{*} (0, s; λ, Y) |}_{s = 0} \end{array}

(12)

마찬가지로 P-기간은 Y 동안 공용 버퍼가 가득 차는 사건이 발생한 후 전용 버퍼가 가득 차기 전까지의 기간이므로, $R_{υ}^{*} (s_{1}, s_{2}; λ, Y)$ 와 ${\tilde{R}}_{υ; (l, \cdot)}^{*} (s; λ, λ_{L}, Y)$ 의 정의에서 다음 이 성립한다.

그리고 F-기간은 Y 동안 공용 버퍼가 가득 차고 전용 버퍼도 가득 찬 이후의 잔여기간이므로, 다음이 성립한다.

\begin{array}{l} E [Y_{f}] = E [max {0, Y - E_{υ} - E_{l}^{L}}] \\ = Pr {E_{υ} \leq Y, E_{l}^{L} \leq Y - E_{υ}} \\ \times E [Y - E_{υ} - E_{l}^{L} | E_{υ} \leq Y, E_{l}^{L} \leq Y - E_{υ}] \\ {= - \frac{\partial}{\partial s} {\tilde{R}}_{υ; (l, \cdot)}^{*} (s; λ, λ_{L}, Y) |}_{s = 0} \end{array}

(14)

(12)-(14)에서 다음이 성립한다.

E [Y] = E [Y_{s}] + E [Y_{p}] + E [Y_{f}] .

4. 대기행렬 모형의 EMC와 SMP 분석

이 절에서는 PBS 정책을 가지는 공간-시간 대기행렬 모형의 EMC(embedded Markov chain)와 SMP(semi-Markov process) 를 분석한다. 시스템에서 패킷을 전송한 직후 시점과 관련된 다음의 확률변수를 정의하자.

$N_{h}^{d} (n)$ : n-번째 패킷 전송 완료 직후의 시스템에 있는 class-h 패킷의 수. 단, h = L ,D .
N^d(n): n-번째 패킷 전송 완료 직후의 시스템에 있는 전체 패킷의 수.
X (n) : n-번째와 (n + 1) -번째 패킷 전송 완료 시점 사이의 시간 간격.

정의에 의해 $N^{d} (n) = N_{L}^{d} (n) + N_{D}^{d} (n)$ 이고, 공용 버퍼의 크기 K_s와 전체 버퍼의 크기 K의 제한 때문에 다음이 성립한다.

0 \leq N^{d} (n) \leq K, 0 \leq N_{D}^{d} (n) \leq m i n {N^{d} (n), K_{s}}

그리고 패킷 전송 완료 직후 시점의 시스템 상태 ${(N^{d} (n), N_{D}^{d} (n)) : n = 0, 1, \dots}$ 는 EMC가 되고, ${((N^{d} (n), N_{D}^{d} (n)) : X (n)) : n = 0, 1, \dots}$ 는 EMC에 상응하는 SMP가 된다.

$p_{(i, j), (l, m)}$ 와 $p_{(i, j), (l, m)}^{*} (s)$ 을 EMC와 상태 (i,j)에서 상태 (l,m)로의 전이확률(transition probabilities)과 SMP의 상응 하는 전이분포(transition distributions)의 LST라고 하자. 즉,

\begin{matrix} p_{(i, j), (l, m)} = Pr {(N^{d} (n + 1), N_{D}^{d} (n + 1)) = (l, m) | \\ (N^{d} (n), N_{D}^{d} (n)) = (i, j)} \\ p_{(i, j), (l, m)}^{*} (s) = Pr {(N^{d} (n + 1), N_{D}^{d} (n + 1)) = (l, m) | \\ (N^{d} (n), N_{D}^{d} (n)) = (i, j)} \\ \times E [e^{- s X (n)} | (N^{d} (n), N_{D}^{d} (n)) = (i, j), \\ (N^{d} (n + 1), N_{D}^{d} (n + 1)) = (l, m)] \end{matrix}

단, 0 ≤ i,l ≤ K , 0 ≤ j ≤ min{i,K_s }, 0 ≤ m ≤ min {l,K_s }. 정의에 의해 $p_{(i, j), (l, m)} = p_{(i, j), (l, m)}^{*} (0)$ 이다.

레벨 i를 0 ≤ j ≤ min(i,K_s)를 만족하는 모든 상태 (i,j)라고 하자. 단, 0 ≤ i ≤ K . 그리고 한 레벨에서 다른 한 레벨로 전이분포 행렬 $P_{i,l}^{*} (s)$ 를 다음과 같이 정의하자.

\begin{array}{l} P_{i,l}^{*} (s) = \\ [\begin{matrix} p_{(i, 0), (l, 0)}^{*} (s) & p_{(i, 0), (l, 1)}^{*} (s) & \dots & p_{(i, 0), (l, min {l, K_{s}})}^{*} (s) \\ p_{(i, 1), (l, 0)}^{*} (s) & p_{(i, 1), (l, 1)}^{*} (s) & \dots & p_{(i, 1), (l, min {l, K_{s}})}^{*} (s) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ p_{(i, min {i, K_{s}}), (l, 0)}^{*} (s) & p_{(i, min {i, K_{s}}), (l, 1)}^{*} (s) & \dots & p_{(i, min {i, K_{s}}), (l, min {l, K_{s}})}^{*} (s) \end{matrix}] \end{array}

(15)

그리고 이에 상응하는 부분 전이확률 행렬 P_{i, l}을 다음과 같이 정의하자.

\begin{array}{l} P_{i,l} = P_{i,l}^{*} (0) = \\ [\begin{matrix} p_{(i, 0), (l, 0)} & p_{(i, 0), (l, 1)} & \dots & p_{(i, 0), (l, min {l, K_{s}})} \\ p_{(i, 1), (l, 0)} & p_{(i, 1), (l, 1)} & \dots & p_{(i, 1), (l, min {l, K_{s}})} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ p_{(i, min {i, K_{s}}), (l, 0)} & p_{(i, min {i, K_{s}}), (l, 1)} & \dots & p_{(i, min {i, K_{s}}), (l, min {l, K_{s}})} \end{matrix}] \end{array}

(16)

단, 0 ≤ i,l ≤ K . 이웃한 두 내재점 사이에 오직 한 패킷만 전송될 수 있으므로 0 ≤ i ≤ K이고 0 ≤ l < i - 1인 부분 전이확률 행렬과 부분 전이분포 행렬은 P_i,l = $P_{i,l}^{*} (s)$ = 0이다. 그러므로 전체 전이확률 행렬 P는 다음과 같은 구조를 가진다.

P = [\begin{matrix} P_{0, 0} & P_{0, 1} & P_{0, 2} & \dots & P_{0, K - 2} & P_{0, K - 1} & P_{0, K} \\ P_{1, 0} & P_{1, 1} & P_{1, 2} & \dots & P_{1, K - 2} & P_{1, K - 1} & P_{1, K} \\ 0 & P_{2, 1} & P_{2, 1} & \dots & P_{2, K - 2} & P_{2, K - 1} & P_{2, K} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & \dots & P_{K - 1, K - 2} & P_{K - 1, K - 1} & P_{K - 1, K} \\ 0 & 0 & 0 & \dots & 0 & P_{K, K - 1} & P_{K, K} \end{matrix}]

SMP의 전이분포의 LST $p_{(i, j), (l, m)}^{*} (s)$ 을 도출하기 위하 여 EMC의 상태 집합 ${(N^{d} (n), N_{D}^{d} (n)) : 0 \leq i \leq K, 0 \leq j \leq m i n {i, K_{s}}}$ 을 다음과 같은 부분집합으로 나누어 분석한다.

<case 1>. $1 \leq N_{D}^{d} (n) \leq m i n {N^{d} (d), K_{s}}$ :

이 경우 패킷 전송 완료 직후에 클래스-D 패킷이 버퍼에 있으므로 시간 우선순위에 의해 클래스-D 패킷의 전송이 시작된다. 따라서

X (n) = S_{D}

(18)

또한 전송이 시작되는 패킷은 버퍼에서 제거되므로 전송 시작 시점에 버퍼에 있는 패킷수는 N^d(n) - 1이 된다. 따라서 N^d(n) - 1의 값에 따라 전송 시작 시점에 공유 버 퍼에 여유 공간이 있는지가 결정되고, 그에 따라 다음 내 재점으로 전이 확률이 달라진다. 그러므로 <case 1>을 다 음과 같이 <case 1-1>과 <case 1-2>로 더 세분화한다.

<case 1-1>. $K_{s} + 1 \leq N^{d} (n) \leq K$ :

이 조건에서는 공용 버퍼가 가득 찬 상태에서 패킷 전송이 시작된다. 따라서 다음 내재점까지 오직 클래스-L 패 킷만 전용 버퍼가 가득 차기 전까지 시스템에 입장이 가능하다. 그리고 (n + 1)-번째 전송 완료 시점에는 클래스-D 패킷 하나가 전송 완료되어 시스템에서 사라진다. 그러므로 다음 관계가 성립한다.

\begin{array}{l} N^{d} (n + 1) = min {N^{d} (n) + A_{L} (S_{D}) - 1, K} \\ N_{D}^{d} (n + 1) = N_{D}^{d} (n) -1. \end{array}

<case 1-2>. $1 \leq N^{d} (n) \leq K_{s}$ :

이 조건에서는 공용 버퍼에 여유 공간이 있는 상태에서 패킷 전송이 시작되고, 공용 버퍼의 여유 공간의 크기는 K_s -N^d(n) + 1이다. 그러므로 패킷 전송 동안 공용 버퍼가 가득 차는 사건이 발생하는지에 따라 다음 내재점에서의 시스템 상태를 다음과 같이 나누어 살펴볼 수 있다. 0 ≤ A (S_D) ≤ K_s -N^d(n)이면,

\begin{array}{l} N^{d} (n + 1) = N^{d} (n) + A (S_{D}) - 1 \\ N_{D}^{d} (n + 1) = N_{D}^{d} (n) + B_{A (S_{D})} - 1. \end{array}

$A (S_{D}) \geq K_{s} - N^{d} (n) + 1$ 이면,

\begin{array}{l} N^{d} (n + 1) = min {K_{s} + A_{L} (S_{D} - E_{K_{s} - N^{d} (n) + 1}), K} \\ N_{D}^{d} (n + 1) = N_{D}^{d} (n) + B_{K_{s} - N^{d} (n) + 1} - 1. \end{array}

<case 2>. 1 ≤ N^d (n) ≤ K , $N_{D}^{d}$ (n) = 0:

이 경우 패킷 전송 완료 직후에 클래스-D 패킷이 버퍼에 없고 클래스-L 패킷만 있으므로 클래스-L 패킷의 전송이 시작된다. 따라서

X (n) = S_{L}

(19)

앞의 분석과 마찬가지로 전송 시작 시점에 공용 버퍼가 가득 차 있는지 아닌지에 따라 상태 집합을 두 부분으로 세분화한다.

<case 2-1>. K_s + 1 ≤ N^d (n) ≤ K :

패킷 전송 시작 시점에 공용 버퍼가 가득 차 있으므로, 패킷 전송 동안 클래스-L 패킷만 전용 버퍼가 가득 차기 전까지 시스템에 입장할 수 있다. 그리고 전송이 완료되면 전송되던 클래스-L 패킷은 시스템에서 사라진다. 그러므로 다음 내재점에서의 시스템 상태는 다음과 같다.

\begin{array}{l} N^{d} (n + 1) = min {N^{d} (n) + A_{L} (S_{L}) - 1, K} \\ N_{D}^{d} (n + 1) = 0. \end{array}

<case 2-2>. 1 ≤ N^d (n) ≤ K_s :

공용 버퍼에 여유 공간이 있는 상태에서 패킷 전송이 시작되고, 공용 버퍼의 여유 공간의 크기는 K_s -N^d(n) + 1 이다. 그러므로 A (S_L)의 크기에 따라 다음의 두 가지 부분 집합으로 나누어 다음 내재점의 상태 전이 식을 나타낼 수 있다. 0 ≤ A (S_L) ≤ K_s -N^d(n)이면,

\begin{array}{l} N^{d} (n + 1) = N^{d} (n) + A (S_{L}) - 1 \\ N_{D}^{d} (n + 1) = B_{A (S_{L})} \end{array}

A (S_L) ≥ K_s -N^d(n) + 1이면,

\begin{array}{l} N^{d} (n + 1) = min {K_{s} + A_{L} (S_{L} - E_{K_{s} - N^{d} (n) + 1}), K} \\ N_{D}^{d} (n + 1) = B_{K_{s} - N^{d} (n) + 1} \end{array}

<case 3>. N^d(n) = $N_{D}^{d}$ (n) = 0:

패킷 전송 완료 직후에 시스템에 남아있는 패킷이 없으므로 시스템은 유휴(idle) 상태에 들어선다. 유휴 기간의 길이를 I라고 하자. 유휴 기간은 패킷의 도착으로 종료되므로, I는 exp (λ)를 따른다. 유휴 기간 동안 도착한 패킷이 클래스 h일 확률은 λ_h/λ이다. 단, h = L ,D . 그러므로 n과 (n + 1)번째 내재점 사이의 전이 시간은 다음처럼 표현된다.

X (n) = I + S_{h} = {\begin{array}{l} I + S_{D}, with prob . λ_{D} / λ \\ I + S_{L}, with prob . λ_{L} / λ . \end{array}

(20)

유휴 기간에 도착한 패킷의 전송 시작 시점에는 버퍼가 완전히 비어 있다. 그러므로 패킷 전송 중에 공용 버퍼가 가득 차는가에 따라 다음 내재점에서의 상태를 다음과 같이 표현할 수 있다. 0 ≤ A (S_h) ≤ K_s - 1이면,

\begin{array}{l} N^{d} (n + 1) = A (S_{h}) \\ N_{D}^{d} (n + 1) = B_{A (S_{h})} \end{array}

A (S_h) ≥ K_s이면,

\begin{array}{l} N^{d} (n + 1) = min {K_{s} + A_{L} (S_{h} - E_{K_{s}}), K} \\ N_{D}^{d} (n + 1) = B_{K_{s}} . \end{array}

지금까지 살펴본 내재점 n에서 다음 내재점까지의 상태 변화의 관계식에서 SMP의 전이확률 $p_{(i, j), (l, m)}^{*} (s)$ 를 다음처럼 구할 수 있다. 단, 상태 집합은 ${(i, j) : 0 \leq i \leq K, 0 \leq j \leq m i n {i, K_{s}}}$ .

<case 1-1>. K_s + 1 ≤ i ≤ K , 1 ≤ j ≤ K_s :

\begin{array}{l} p_{(i, j), (l, m)}^{*} (s) = \\ {\begin{array}{l} a_{(l - i + 1, .)}^{*} (s; S_{D}) & i - 1 \leq l \leq K - 1, m = j - 1 \\ \begin{array}{l} \sum_{n = K - i + 1}^{\infty} a_{(n, .)}^{*} (s; S_{D}), \\ 0, \end{array} & \begin{array}{l} l = K, m = j - 1 \\ otherwise. \end{array} \end{array} \end{array}

(21)

<case 1-2>. 1 ≤ i ≤ K_s , 1 ≤ j ≤ i:

\begin{array}{l} p_{(i, j), (l, m)}^{*} (s) = \\ {\begin{cases} a_{l - i + 1}^{*} (s; S_{D}) \cdot b_{(l - i - m + j, m - j + 1)}, \\ i - 1 \leq l \leq K_{s} - 1, j - 1 \leq m \leq l - i + j \\ {\tilde{a}}_{K_{s - i} + 1; (l - K_{s}, .)}^{*} (s; S_{D}) \cdot b_{(K_{s} - i - m + j, m - j + 1)}, \\ K_{s} \leq l \leq K - 1, j - 1 \leq m \leq K_{s} - i + j \\ \sum_{n = K - K_{s}}^{\infty} {\tilde{a}}_{K_{s} - i + 1; (n, .)}^{*} (s; S_{D}) \cdot b_{(K_{s} - i - m + j, m - j + 1)}, \\ l = K, j - 1 \leq m \leq K_{s} - i + j \\ 0, otherwise \end{cases} \end{array}

(22)

<case 2-1>. K_s + 1 ≤ i ≤ K , j = 0:

\begin{array}{l} p_{(i, 0), (l, m)}^{*} (s) = \\ ​ {\begin{cases} a_{(l - i + 1, .)}^{*} (s; S_{L}), i - 1 \leq l \leq K - 1, m = 0 \\ \sum_{n = K - i + 1}^{\infty} a_{(n, .)}^{*} (s; S_{L}), l = K, m = 0 \\ 0, otherwise \end{cases} \end{array}

(23)

<case 2-2>. 1 ≤ i ≤ K_s , j = 0:

\begin{array}{l} p_{(i, 0), (l, m)}^{*} (s) = \\ ​ {\begin{cases} a_{l - i + 1}^{*} (s; S_{L}) \cdot b_{(l - i + 1 - m, m)}, \\ i - 1 \leq l \leq K_{s} - 1, 0 \leq m \leq l - i + 1 \\ {\tilde{a}}_{K_{s} - i + 1; (l - K_{s})}^{*} (s; S_{L}) \cdot b_{(K_{s} - i + 1 - m, m)}, \\ K_{s} \leq l \leq K - 1, 0 \leq m \leq K_{s} - i + 1 \\ \sum_{n = K - K_{s}}^{\infty} {\tilde{a}}_{K_{s} - i + 1; (n, .)}^{*} (s; S_{L}) \cdot b_{(K_{s} - i + 1 - m, m)}, \\ l = K, 0 \leq m \leq K_{s} - i + 1 \\ 0, otherwise \end{cases} \end{array}

(24)

<case 3>. i = j = 0:

\begin{array}{l} p_{(0, 0) (l,} m)^{*} (s) = \\ ​ {\begin{cases} \sum_{h = {L, D}} \frac{λ_{h}}{λ + s} \cdot a_{l}^{*} (s; S_{h}) \cdot b_{(l - m, m)}, \\ 0 \leq l \leq K_{s} - 1, 0 \leq m \leq l \\ \sum_{h = {L, D}} \frac{λ_{h}}{λ + s} \cdot {\tilde{a}}_{K_{s}; (l - K_{s}, .)}^{*} (s; S_{h}) \cdot b_{(K_{s} - m, m)}, \\ K_{s} \leq l \leq K - 1, 0 \leq m \leq K_{s} \\ \sum_{h = {L, D}} \frac{λ_{h}}{λ + s} \sum_{n = K - K_{s}}^{\infty} {\tilde{a}}_{K_{s}, (n, .)}^{*} (s; S_{h}) \cdot b_{(K_{s} - m, m)}, \\ l = K, 0 \leq m \leq K_{s} \\ 0, otherwise \end{cases} \end{array}

(25)

단, h = L ,D이고, (21)-(25)의 $a_{(l, .)}^{*} (s; S_{h}), a_{n}^{*} (s; S_{h}), {\tilde{a}}_{υ; (l, .)}^{*} (s; S_{h})$ 는 (2), (3), (10)에서 Y를 S_h로 대체하여 얻는다. 식 (21)-(25)과 식 (15)-(17)에서 모든 부분 전이분포 행 렬 P_i,l (s) , 부분 전이확률 행렬 P_i,l, 그리고 전체 전이확률 행렬 P를 구할 수 있다. 또한 EMC의 전이행렬 P의 구조에 의해 EMC가 기약 에르고딕 마코프 체인(irreducible ergodic Markov chain)임을 증명할 수 있다([15], Lemma 1 참조).

π_(i,j)를 EMC가 상태 (i, j)에 있을 극한 확률(limiting probability)이라고 하자. 즉,

π_{(i, j)} = lim_{n \to \infty} Pr {(N^{d} (n), N_{D}^{d} (n)) = (i, j)}

단, 0 ≤ i ≤ K , 0 ≤ j ≤ min(i,K_s) . 또한 레벨 i의 부분 극한 확률 벡터를 다음과 같이 정의하자.

그리고 모든 상태에 대한 극한 확률 벡터를 다음처럼 정의하자.

π = [π_{0} π_{1} \dots π_{K}] .

그러면 EMC가 기약 에르고딕 마코프 체인이므로 다음을 만족하는 유일한 정상 확률 벡터(stationary probability vector)가 존재하고, 정상 확률 벡터는 극한 확률 벡터 π와 동일하다[12].

π = π P, π e = 1,

(26)

단, e는 모든 요소가 1인 열벡터이다.

극한 확률 벡터 π는 식 (26)에서 수치적으로 구할 수 있다. 또는 Kim[15]에서처럼 (17)에 표현된 P의 특수한 구조를 사용하여 π를 더 효율적인 방법으로 구할 수도 있다.

5. 성능 지표

이 장에서는 제4장에서 도출한 EMC와 SMP 분석 결과를 사용하여 공간-시간 우선순위 대기행렬의 성능 지표를 도출한다.

먼저 안정상태에서 시스템의 전송 상태와 버퍼 상태와 관련된 다음 확률을 정의하자.

ρ: 시스템이 패킷 전송으로 바쁠 확률.
ρ^s : 시스템이 패킷 전송으로 바쁘고 공유 버퍼에 여유 공간이 있을 확률.
ρ^p : 시스템이 패킷 전송으로 바쁘고 공유 버퍼는 가득 찼으나 클래스-L 전용 버퍼에는 여유 공간이 있을 확률.
ρ^f: 시스템이 패킷 전송으로 바쁘고 전체 버퍼가 가득 차 있을 확률.

안정상태에서 SMP의 전이시간을 X라고 하자. 그러면 (18), (19), (20)에서 다음을 구할 수 있다.

\begin{matrix} E [X] = \sum_{i = 1}^{K} \sum_{j = 1}^{min (i, K_{s})} π_{(i, j)} E [S_{D}] + \sum_{i = 1}^{K} π_{(i, 0)} E [S_{L}] \\ + π_{(0, 0)} (\frac{1}{λ} + \frac{λ_{L}}{λ} E [S_{L}] + \frac{λ_{D}}{λ} E [S_{D}]) \end{matrix}

(27)

N^d를 안정상태에서 패킷 전송 종료 직후 시점의 버퍼에 있는 패킷수라고 하자. 안정상태에서 SMP의 전이시간 X는 시스템의 전송 상태와 버퍼 상태에 따라 다음 4개의 기간을 정의하자.

X_I : 전이시간 X 중에 시스템이 유휴한 기간.
X_s : 전이시간 X 중에 시스템이 전송으로 바쁘고, 공용버퍼에 여유 공간이 있는 기간(S-기간).
X_p : 전이시간 X 중에 시스템이 전송으로 바쁘고, 공용버퍼는 가득 차고, 전용 버퍼에 여유 공간이 있는 기간(P-기간).
X_f: 전이시간 X 중에 시스템이 전송으로 바쁘고, 전체 버퍼가 가득 차 있는 기간(F-기간).

시스템이 유휴한(패킷을 전송하지 않는) 기간은 패킷 전송 직후 N^d = 0일 때 다음 패킷이 도착할 때까지의 유휴 기간 I 동안 발생한다. 그러므로

X_{I} = {\begin{array}{l} I, & N^{d} = 0 \\ 0, & otherwise . \end{array}

그러므로 X_I의 기대치는 다음과 같다.

E [X_{I}] = π_{(0, 0)} E [I] = \frac{π_{(0, 0)}}{λ}

(28)

X_s는 전송 종료 직후 시점에 공용 버퍼가 가득 차 있지 않은 상태에서 시작하여 공용 버퍼가 가득 차거나 전송이 완료되는 사건이 발생할 때까지의 기간이다. 그러므로 다음 관계식이 성립한다.

\begin{array}{l} X_{s} = \\ {\begin{array}{l} 0, & K_{s} + 1 \leq N^{d} \leq K \\ min {S_{D}, E_{K_{s} - N^{d} + 1}}, & 1 \leq N^{d} \leq K_{s}, 1 \leq N_{D}^{d} \leq N^{d} \\ min {S_{L}, E_{K_{s} - N^{d} + 1}}, & 1 \leq N^{d} \leq K_{s}, N_{D}^{d} = 0 \\ min {S_{h}, E_{K_{s}}}, & N^{d} = 0 \end{array} \end{array}

단, h는 유휴 기간에 도착한 패킷의 클래스이고, S_h는 유휴 기간 후에 도착한 패킷의 전송 시간. 그러므로 X_s의 기대치를 다음처럼 구할 수 있다.

\begin{matrix} E [X_{s}] = \sum_{i = 1}^{K_{s}} \sum_{j = 1}^{i} π_{(i, j)} E [min {S_{D}, E_{K_{s} - i + 1}}] \\ + \sum_{i = 1}^{K_{s}} π_{(i, 0)} E [min {S_{L}, E_{K_{s} - i + 1}}] \\ + π_{(0, 0)} \sum_{h \in {L, D}} \frac{λ_{h}}{λ} E [min (S_{h}, E_{K_{s}})] . \end{matrix}

(29)

단, h = L ,D일 때 E [min {S_h, E_υ }]는 (12)에서 Y를 S_h로 대체하여 구한다.

마찬가지 논리로 X_p는 공용 버퍼가 가득 찬 이후부터 전체 버퍼가 가득 차기 전까지의 기간이므로, 다음 관계식이 성립한다.

그러므로 X_p의 기대치에 대한 다음 식을 얻는다.

\begin{matrix} E [X_{p}] = \sum_{i = K_{s} + 1}^{K} \sum_{j = 1}^{K} π_{(i, j)} E [min {S_{D}, E_{K - i + 1}^{L}}] \\ + \sum_{i = K_{s} + 1}^{K} π_{(i, 0)} E [min {S_{L}, E_{K - i + 1}^{L}}] \\ + \sum_{i = 1}^{K_{s}} \sum_{j = 1}^{i} π_{(i, j)} E [min {max {0, S_{D} - E_{K_{s} - i + 1}}, E_{K - K_{s}}^{L}}] \\ + \sum_{i = 1}^{K_{s}} π_{(i, 0)} E [min {max {0, S_{L} - E_{K_{s} - i + 1}}, E_{K - K_{s}}^{L}}] \\ + π_{(0, 0)} \sum_{h \in {L, D}} \frac{λ_{h}}{λ} E [min {max {0, S_{h} - E_{K_{s}}}, E_{K - K_{s}^{L}}}] \end{matrix}

(30)

단, h = L ,D일 때 E [min {S_h, $E_{K - N^{d} + 1}^{L}$ }]는 (12)에서 Y 를 S_h로 λ를 λ_L로 대체하여 구하고, E [min {max {0,S_h -E_υ }, $E_{l}^{L}$ }]는 (13)에서 Y를 S_h로 대체하여 얻는다.

마지막으로, 시스템은 유휴중이거나 전송일 때는 S, P, F-기간 중에 하나이므로, (27), (28), (29), (30)에서 X_f의 기대치를 얻는다.

\begin{matrix} E [X_{f}] = E [X] - E [X_{I}] - E [X_{s}] - E [X_{p}] \\ = - \sum_{i = K_{s} + 1}^{K} \sum_{j = 1}^{K_{s}} π_{(i, j)} \frac{\partial}{\partial s} R_{K - i + 1}^{*} {(0, s; λ_{L}, S_{D}) |}_{s = 0} \\ - \sum_{i = K_{s} + 1}^{K} π_{(i, 0)} \frac{\partial}{\partial s} R_{K - i + 1}^{*} {(0, s; λ_{L}, S_{D}) |}_{s = 0} \\ - \sum_{i = 1}^{K_{s}} \sum_{j = 1}^{i} π_{(i, j)} \frac{\partial}{\partial s} {\tilde{R}}_{K_{s} - i + 1; (K - K_{s}, .)}^{*} {(s, λ, λ_{L}, S_{D}) |}_{s = 0} \\ - \sum_{i = 1}^{K_{s}} π_{(i, 0)} \frac{\partial}{\partial s} {\tilde{R}}_{K_{s} - i + 1; (K - K_{s}, .)}^{*} {(s, λ, λ_{L}, S_{L}) |}_{s = 0} \\ - π_{(0, 0)} \sum_{h \in {L, D}} \frac{λ_{h}}{λ} \frac{\partial}{\partial s} {\tilde{R}}_{K_{s}; (K - K_{s}, .)}^{*} {(s, λ, λ_{L}, S_{h}) |}_{s = 0} \end{matrix}

(31)

따라서 SMP 이론으로 다음을 계산할 수 있다[12].

ρ_{s} = \frac{E [X_{s}]}{E [X]}, ρ_{p} = \frac{E [X_{p}]}{E [X]}, ρ_{f} = \frac{E [X_{f}]}{E [X]}

그리고 시스템이 전송으로 바쁠 확률은 다음과 같다.

ρ = 1 - \frac{E [X_{I}]}{E [X]} = \frac{E [X] - π_{(0, 0)} / λ}{E [X]}

클래스-L 패킷은 F-기간에만 손실되고, 클래스-D 패킷 은 P-, F-기간에 손실이 발생하므로, 두 클래스의 패킷 손 실 확률 $P_{L}^{l o s s}$ 와 $P_{D}^{l o s s}$ 는 다음과 같다.

P_{L}^{l o s s} = ρ_{f}, P_{D}^{l o s s} = ρ_{p} + ρ_{f}

$λ_{L}^{e}$ 와 $λ_{D}^{e}$ 를 클래스-L과 클래스-D 패킷이 손실되지 않 고 시스템에 들어오는 유효 도착률이라고 하자. 클래스-L 패킷은 전체 버퍼가 가득 차지 않으면 시스템에 입장할 수 있으나, 클래스-D 패킷은 공용 버퍼가 가득 차지 않아 야 시스템에 입장할 수 있다. 그러므로 포아송 과정의 특 성에 의해 다음이 성립한다.

λ_{L}^{e} = λ_{L} (1 - ρ_{f}), λ_{D}^{e} = λ_{D} (1 - ρ_{p} - ρ_{f})

그러므로 전체 클래스의 유효 도착률 λ^e는 다음처럼 표 현된다.

λ^{e} = λ_{L}^{e} + λ_{D}^{e} .

지금부터 임의 시점에 시스템에 있는 패킷수를 고려해 보자. N과 N_h를 안정상태에서 임의 시점에 시스템에 있는 총 패킷수와 클래스-h 패킷수라고 하자. 단, h = L ,D . 정의 에 의해 N = N_L +N_D .

$S_{h}^{e}$ 를 안정상태에서 클래스-h 패킷을 전송 중일 때 패킷 전송의 경과 시간(elapsed time)이라고 정의하자. 그러면 제4장의 이웃하는 두 내재점 사이의 시스템 상태의 관계 식을 도출할 때와 마찬가지 방법으로 안정상태에서 패킷 전송 직후 시점의 상태 (N^d, $N_{D}^{d}$ )와 임의 시점의 상태 (N, N_D)에 대한 다음의 관계를 도출할 수 있다. 단, 임의 시점 상태에서는 전송 중인 패킷이 아직 시스템에 머물고 있으며, N과 N_D는 전송 중인 패킷까지 포함하여 최대 K + 1과 K_s + 1일 수 있다는 점을 유의한다.

<case 1-1>. K_s + 1 ≤ N^d ≤ K , N^d ≥ 1:

(N, N_{D}) = (1 + min {N^{d} + A_{L} (S_{D}^{e}) - 1, K}, N_{D}^{d}) .

<case 1-2>. 1 ≤ N^d ≤ K_s , N^d ≥ 1:

\begin{array}{l} (N, N_{D}) = \\ {\begin{cases} (N^{d} + A (S_{D}^{e}), N_{D}^{d} + B_{A (S_{D}^{e})}), \\ 0 \leq A (S_{D}^{e}) \leq K_{s} - N^{d} \\ (1 + min {K_{s} + A_{L} (S_{D}^{e} - E_{K_{s} - N^{d} + 1}), K}, N_{D}^{d} + B_{K_{s} - N^{d} + 1}), \\ A (S_{D}^{e}) \geq K_{s} - N^{d} + 1. \end{cases} \end{array}

<case 2-1>. K_s + 1 ≤ N^d ≤ K , $N_{D}^{d}$ = 0:

(N^{d}, N_{D}^{d}) = (1 + min {N^{d} + A_{L} (S_{L}) - 1, K}, 0) .

<case 2-2>. 1 ≤ N^d ≤ K_s , $N_{D}^{d}$ = 0:

\begin{array}{l} (N, N_{D}) = \\ {\begin{cases} (N^{d} + A (S_{L}^{e}), B_{A (S_{L}^{e})}), \\ 0 \leq A (S_{L}^{e}) \leq K_{s} - N^{d} \\ (1 + min {K_{s} + A_{L} (S_{L}^{e} - E_{K_{e} - N^{d} + 1}), K}, B_{K_{s} - N^{d} + 1}), \\ A (S_{L}^{e}) \geq K_{s} - N^{d} + 1. \end{cases} \end{array}

<case 3>. N^d(n) = $N_{D}^{d} (n)$ = 0:

\begin{array}{l} (N, N_{D}) = \\ {\begin{cases} (1 + A (S_{h}^{e}), I (h = D) + B_{A (S_{h}^{e})}), \\ 0 \leq A (S_{h}^{e}) \leq K_{s} - 1 \\ (1 + min {K_{s} + A_{L} (S_{h}^{e} - E_{K_{s}}), K}, I (h = D) + B_{K_{s}}), \\ A (S_{h}^{e}) \geq K_{s} . \end{cases} \end{array}

단, h는 유휴 기간에 도착한 패킷의 클래스이며, I (⋅)는 지시 함수로 조건이 성립하면 1, 아니면 0의 값을 가진다.

내재점의 시스템 상태와 임의 시점의 시스템 상태의 관 계에서 임의 시점의 상태 (N,N_D)의 확률분포를 내재점의 확률 분포 π_(i,j)로 나타낼 수 있으나, 여기서는 논의의 단 순화를 위하여 기대치만을 구하기로 한다. <case 1-1>에서 <case 3>까지의 내재점 상태와 임의 시점 상태의 관계식 에서 다음 식을 얻는다.

단,

\begin{matrix} n_{p} (i; Y) = \sum_{l = 0}^{K - i} (i + 1) a_{(l, .)} (Y) + (K + 1) \sum_{l = K - i + 1}^{\infty} a_{(l, .)} (Y) \\ n_{s} (i; Y) = \sum_{n = 0}^{K_{s} - i} (i + n) a_{n} (Y) \\ + \sum_{l = 0}^{K - K_{s} - 1} (K_{s} + l + 1) {\tilde{a}}_{K_{s} - i + 1; (l, .)}^{*} (0; Y) \\ + \sum_{l = K - k_{s}}^{\infty} (K + 1) {\tilde{a}}_{K_{s} - i + 1; (l, .)}^{*} (0; Y) \\ n_{D} (i, j; Y) = \sum_{n = 0}^{K_{s} - i} a_{n} (Y) \sum_{m = 0}^{n} (j + m) \cdot b (n - m, m) \\ + \sum_{n = K_{s} - i + 1}^{\infty} a_{n} (Y) \sum_{m = 0}^{K_{s} - i + 1} (j + m) \\ \cdot b (K_{s} - i + 1 - m, m) \end{matrix}

아울러 안정상태에서의 클래스-h 패킷의 시스템 체류 시간을 W_h라고 하면, 리틀의 법칙에 의해서 다음처럼 구 할 수 있다.

\begin{array}{l} E [W_{D}] = E [N_{D}] / λ_{^{D}}^{e} \\ E [W_{L}] = E [N_{L}] / λ_{L}^{e} = (E [N] - E [N_{D}]) / λ_{L}^{e} \end{array}

6. 수치 예제

이 장에서는 수치 예제를 사용하여 공용 버퍼의 크기 K_s와 패킷 서비스 시간의 분포가 클래스-L과 클래스-D 패킷의 서비스 성능에 미치는 영향을 살펴본다.

수치 예제는 공용 버퍼의 크기와 서비스 시간의 분포의 효과를 집중적으로 살펴보기 위하여 두 클래스의 패킷 도착 률과 패킷 서비스 시간의 평균은 동일하도록 균등하게 설정 한다. 두 클래스의 패킷 도착률은 λ_L = λ_D = 1로 설정하고, 두클래스의패킷서비스시간의평균은E [S_L] = E [S_D] = 1/4로 설정한다. 그리고 전체 버퍼의 크기는 K = 10으로 설정한다. 공용 버퍼의 크기 변화에 따른 효과를 살펴보기 위하여 K_s를 0부터 10까지 2씩 증가시키며 두 클래스의 서비스 성능을 살펴본다. 또한 각 클래스의 패킷 서비스 시간의 평균은 1/4이지만, 서비스 시간의 분포를 지수 분포 exp (4), 발생률은 8이고 형상(shape) 매개변수는 2인 얼랑 분포 Erlang (2,8) , 형상(shape) 매개변수 α = 4.2, 2.6, 1.8인 유형 2 파레토 분포(Lomax 분포)로 설정한다. 파레토 분포의 위치 (location) 매개변수는 μ = 0, 규모(scale) 매개변수는 σ = (α - 1)/4로 설정한다. 그러면 지수 분포의 변동계수 (CV; coefficient of variation)는 1이 되고, Erlang 분포의 변동 계수는 $1 / \sqrt{2}$ , α = 4.2, 2.6, 1.8인 파레토 분포의 변동계수는 약 1.38, 2.08, 무한대가 된다.

<Figure 2>는 S_L과 S_D의 분포의 조합에 대하여 공유 버 퍼 크기 K_s에 따라 두 클래스의 패킷 처리 시간의 기대치 E [W_L]과 E [W_D], 그리고 패킷 손실률 $P_{L}^{l o s s}$ 와 $P_{D}^{l o s s}$ 의 변화 를 보여준다. 단, 그래프가 너무 복잡해지는 것을 방지하 려고 이 그래프에서는 서비스 시간의 분포로 지수 분포와 α = 2.6의 파레토 분포의 조합에 대해서만 도시하였다. (나머지 분포에 대해서는 <Figure 3>과 <Figure 4> 참조.) 시간 우선순위 때문에 모든 서비스 시간 분포와 공유 버퍼 크기 K_s에 대해 E [W_D]는 E [W_L]보다 작다. 공용 버퍼 크 기 K_s가 증가함에 따라 두 클래스의 처리 시간의 기대치 E [W_L]과 E [W_D] 모두 상승하는 현상을 보이는데, 그 이유 는 공용 버퍼의 크기가 증가함에 따라 클래스-D의 손실률 이 빠르게 하강하고(<Figure 2> 우하단 그래프 참조), 이는 두 클래스 모두에게서 대기하는 패킷의 수를 증가시키기 때문이다.

두 클래스의 서비스 시간 분포의 변동계수가 커질수록 E [W_L]과 E [W_D] 모두 상승하는 경향을 보인다. (<Figure 2> 상단의 그래프 참조.) 그러나 E [W_L]에 대한 서비스 시 간 분포의 차이에 따른 효과는 공용 버퍼의 크기 K_s에 크 게 영향을 받지 않는 반면, E [W_D]에 대한 효과는 K_s가 작 을 때는 명확하지 않다가 K_s가 커짐에 따라 뚜렷하게 확 대된다. 이러한 현상이 발생하는 이유는 다음과 같다. 클 래스-L 패킷은 공간 우선순위가 높기 때문에 공용 버퍼의 크기와 무관하게 어느 정도 시스템에 입장이 보장되지만 시간 우선순위가 낮아서 시스템에 있는 모든 클래스의 패 킷뿐 아니라 자신이 대기하는 동안 입장하는 클래스-D 패 킷의 서비스 시간의 변동이 모두 자신의 대기시간의 변동 으로 나타난다. 반면 클래스-D 패킷은 공간 우선순위가 낮지만 시간 우선순위가 높기 때문에 서비스 중인 패킷을 제외하면 공용 버퍼 크기 K_s미만의 클래스-D 패킷의 서 비스 변동만 자신의 대기시간에 영향을 준다. 그러므로 클 래스-D 패킷은 K_s가 작으면 패킷의 서비스 시간의 변동이 패킷 처리 시간에 영향을 주는 효과가 줄어들고 K_s가 커 지면 늘어나게 된다.

<Figure 2> 하단의 그래프는 두 클래스 패킷의 손실률 $P_{L}^{l o s s}$ 와 $P_{D}^{l o s s}$ 의 변화를 보여준다. 두 그래프 모두 세로축이 로그 스케일로 그려져 있다. 먼저 공간 우선순위 때문에 서비스 시간의 분포와 공용 버퍼 크기와 무관하게 클래스-L 패킷의 손실률이 클래스-D 패킷의 손실률보다 크지 않다는 것을 확인할 수 있다. 특히 K_s의 크기가 작아질수록 공간 우선순위가 낮은 클래스-D 패킷의 손실률은 로그 스케일에서 선형적으로 높아지고, 공간 우선순위가 높은 클래스-L 패킷의 손실률이 로그 스케일에서 선형적으로 낮아진다. 두 클래스의 패킷 손실률은 서비스 시간의 변동 성이 커지면 모두 증가하는 경향을 보였다. 이는 패킷의 서비스 시간의 변동성이 패킷의 대기시간을 증가시키고, 다시 증가된 대기시간이 공용 버퍼와 전체 버퍼가 가득 찰 확률을 증가시키기 때문이다. 아울러 로그 스케일에서 공용 버퍼 크기에 따른 두 클래스의 손실률의 기울기는 패킷 서비스 시간의 변동성이 작을수록 커져서, 공간 우선 순위의 효과가 더 민감하게 나타난다. 이는 서비스 변동성 이 적을수록 평균적으로 버퍼에 대기하는 패킷의 수가 전체 버퍼의 크기보다 작아서 공용 버퍼의 조정에 더 민감하게 반응하기 때문인 것으로 추론된다.

공용 버퍼의 크기 K_s가 두 클래스의 성능 지표에 미치는 영향을 더 상세히 살펴보기 위하여, 두 클래스의 평균 처리 시간의 비(ratio)와 손실률의 비가 어떻게 변화하는지 살펴보자. <Figure 3>은 클래스-L의 서비스 시간은 지수 분포로 고정시켜 놓고, 클래스-D의 서비스 시간의 분포를 평균은 동일한데 변동 계수가 다른 분포로 변화시켰을 때의 결과를 보여준다. <Figure 3>의 우측 그래프는 공용 버퍼의 크기 K_s에 따라 두 클래스의 손실률의 비의 변화를 로그 스케일로 보여준다. K_s = 0일 때는 모든 버퍼를 클래스-L이 전용하는 극단적인 공간 우선순위가 적용되는 것 이므로, 클래스-L의 손실률이 클래스-D의 손실률에 수십 배에서 수십만 배 작은 것을 확인할 수 있다. K_s가 커짐에 따라 거의 모든 패킷 서비스 시간 분포에서 손실률 비의 로그 값이 선형적으로 증가한다. K_s = K = 10이 되면 두 클래스의 공간 우선순위는 사라지므로 두 클래스의 손실 률의 비가 1이 된다. 클래스-D의 서비스 시간 분포의 변동 계수가 작을수록 공용 버퍼의 크기 K_s에 따른 두 클래스의 손실률 비의 로그 값의 기울기가 더 커진다.

<Figure 3>의 좌측 그래프는 공용 버퍼의 크기 K_s에 따라 두 클래스의 평균 처리 시간의 비의 변화를 보여준다. 시간 우선순위 때문에 모든 공용 버퍼 크기에서 평균 대기 시간의 비는 1보다 크다. 공용 버퍼의 크기 K_s를 조정하는 것은 두 클래스 사이에서 공간 우선순위를 배분하는 것이므로, <Figure 3>의 우측 그래프에서 보는 바와 같이 패킷 손실률의 비는 매우 크게 변화하지만, 시간 우선순위와 주로 관련된 평균 처리 시간의 비는 크게 변화하지 않는 것을 살펴볼 수 있다. 손실률의 비가 공용 버퍼의 크기에 따라 일정한 방향으로 변화하는 것에 비해, 평균 처리 시간의 비는 일정한 경향성을 보이지 않는다. 그러나 대부분의 패킷 서비스 시간 분포에서 K_s의 값이 양 극단인 0과 10에 가까워지면 증가하다가 K_s = 2 근방에서 최소값에 가까워지는 현상을 보였다.

마지막으로 <Figure 4>는 클래스-D의 서비스 시간은 지수 분포로 고정시켜 놓고, 클래스-L의 서비스 시간의 분포를 평균은 동일한데 변동 계수가 다른 분포로 변화시켰을 때의 결과를 보여주는데, <Figure 3>에서 분석한 경향과 유사한 경향이 나타나는 것을 확인할 수 있다.

7. 결 론

공간-시간 우선순위 대기행렬 모형에 대한 연구가 최근에 수행되었지만, 공간 우선순위를 밀어내기 정책으로 제한되었다. 이 논문에서는 공간 우선순위를 부분 버퍼 공유 정책으로 확장하여 공간-시간 우선순위 M/G/1 대기행렬 모형을 분석하였다. 기존의 밀어내기 정책을 가지는 공간- 시간 우선순위 모형의 분석과는 달리, 부분 버퍼 공유 정책을 가지는 모형은 서비스 시간의 구조가 공유 버퍼가 가득 찰 때까지의 S-기간, 전체 버퍼가 가득 찰 때까지의 P-기간, 그리고 전체 버퍼가 가득 찬 이후의 F-기간으로 나눠질 수 있어서 이에 대한 복잡한 분석이 필요하다(제3장 참조). 이 연구에서는 S-, P-, F-기간에 대한 분석 방법을 제시하고 이를 사용하여 시스템의 상태와 성능 지표를 일관된 방식으로 분석하였다.

공간과 시간 우선순위를 가지는 두 클래스의 도착률과 평균 서비스 시간이 균등한 수치 예제에서, 공간 우선순위를 분배하는 시스템 매개변수인 공유 버퍼의 크기 K_s는 서비스 성능에 다음과 같은 효과를 보였다. (1) 공유 버퍼 크기가 변화하면 두 클래스의 손실률은 로그-선형적으로 변화하며, 서비스 시간의 변동성이 클수록 공유 버퍼 크기에 대한 손실률 변화의 민감도가 감소하였다. (2) 공유 버퍼 크기가 증가하면 버퍼의 사용률이 증가하여 두 클래스 모두 평균 대기시간이 증가하였다. 그러나 공유 버퍼 크기는 공간 우선순위를 클래스 사이에 배분하는 매개변수이기 때문에 시간 우선순위와 관련된 처리 시간에 대한 영향력은 어느 정도 제한된 형태였으며, 두 클래스 모두에 한 방향으로의 뚜렷한 영향력을 보이지 않았다. (3) 서비스 시간의 변동성은 K_s의 특정 범위에서는 두 클래스의 평균 처리 시간뿐만 아니라 손실률에도 큰 차이를 만들어 낸다. 그러므로 서비스 시간의 분포를 지수 분포로 근사하여 대기행렬의 성능을 분석하는 것에는 매우 큰 오류가 내재할 수 있다. 특히, 롱테일 분포를 가지는 통신 서비스에 대한 분석은 본 연구에서 제시한 분석방법을 사용하여 정확한 성능 분석이 필요하다.

본 연구는 부분 버퍼 공유 정책을 가지는 공간-시간 우선순위 M/G/1 대기행렬의 분석 방법을 제시하고, 두 클래스의 도착률과 평균 서비스 시간이 균등한 상황에서 공유 버퍼의 크기와 서비스 시간의 분포가 성능에 미치는 영향을 수치적으로 분석하였기 때문에, 여러 트래픽의 공간과 시간 우선순위를 다르게 관리해야 하는 통신 서비스 운영자들이 이러한 연구 결과를 활용할 수 있으리라 기대한다. 그러나 본 연구는 다음과 같은 한계점과 발전방향을 내포하고 있다. 첫째, 본 연구에서는 시스템 성능지표로 평균 대기시간과 평균 손실률만 분석하였다. 그러나 통신 시스템에서는 패킷의 연속적 손실에 의한 서비스 품질의 저하가 문제되는 경우가 많다. 그러므로 동일한 공간-시간 우선순위 대기행렬에서 바쁜 기간, 공용 버퍼가 가득 찬 기간, 전체 버퍼가 가득 찬 기간의 분포를 분석하여 패킷의 연속 손실 확률 등을 분석하는 연구가 향후 필요하다. 둘 째, 본 연구의 모형은 클래스 사이의 공간 우선순위 배분 은 공유 버퍼의 크기로 조정할 수 있지만 시간 우선순위는 비선점 방식으로 고정하였다. 향후 연구는 두 클래스의 대기열의 크기에 따라 동적으로 시간 우선순위를 조정하는 좀 더 유연한 공간-시간 우선순위 모형에 대한 연구로 발전할 수 있을 것이다. 셋째, 본 연구에서는 두 클래스의 서비스 부하가 균등한 사례에 대해서만 수치적으로 분석 하였다. 향후 연구에서는 서비스 부하가 불균등한 사례에 대한 성능 분석뿐 아니라, 다양한 형태의 시스템 운영 목적함수를 최적화하는 문제로 발전할 수 있을 것이다.

Figure

<Figure 1>.

Y , E_υ , and ElL

<Figure 2>.

Performance Measures over Various Values of K_s for Different Distributions of S_L and S_D

<Figure 3>.

Performance ratios of Both Classes over Various Values of K_s for the Exponential Distribution of S_L and Different Distributions of S_D

<Figure 4>.

Performance Ratios of Both Classes over Various Values of K_s for Different Distributions of S_L and the Exponential Distribtion of S_D

Table

Reference

Arpaci, M. and Copeland, J.A., Buffer management for shared-memory ATM switches, IEEE Communications Surveys & Tutorials, 2000, Vol. 3, No. 1, pp. 2-10.
Avrachenkov, K.E., Vilchevsky, N.O., and Shevlyakov, G.L., Priority queueing with finite buffer size and randomized push-out mechanism, ACM SIGMETRICS Performance Evaluation Review, 2003, Vol. 31, No. 1, pp. 324-325.
Avrachenkov, K.E., Vilchevsky, N.O. and Shevlyakov, G.L., Priority queueing with finite buffer size and randomized push-out mechanism, Performance Evaluation, 2005, Vol. 61, No. 1, pp. 1-16.
Avrachenkov, K., Shevlyakov, G. and Vilchevskii, N., Randomized push-out disciplines in priority queueing, Journal of Mathematical Sciences, 2004, Vol. 122, No. 4, pp. 3336-3342.
Bruneel, H. and Kim, B.G., Discrete-time models for communication systems including ATM, 1993.
Carballo-Lozano, C., Ayesta, U., and Fiems, D., Performance analysis of space-time priority queues, Performance Evaluation, 2019, Vol. 133, pp. 25-42.
Cheng, X. and Akyildiz, A., A finite buffer two class queue with different scheduling and push-out schemes, [Proceedings] IEEE INFOCOM’92: The Conference on Computer Communications, 1992, pp. 231-241.
Eugster, P., Kesselman, A., Kogan, K., Nikolenko, S., and Sirotkin, A., Admission control in shared memory switches, Journal of Scheduling, 2018, Vol. 21, No. 5, pp. 533-543.
Gravey, A. and Hebuterne, G., Mixing time and loss priorities in a single server queue, Proceedings of 13^th international teletraffic congress, Copenhagen, Denmark, 1991, pp. 147-152.
Gudimalla, R.K., Kumar, L.R., and Perati, M.R., Loss behaviour analysis of asynchronous internet switch under self-similar traffic input using MMPP/PH/c/k queueing system employing PBS mechanism, International Journal of Communication Networks and Distributed Systems, 2017, Vol. 19, No. 3, pp. 257-269.
Gudimalla, R.K. and Perati, M.R., Performance analysis of wavelength division multiplexing asynchronous internet router employing space priority mechanism under self-similar traffic input—multi-server queueing system with markovian input and erlang-k services, Applied Mathematics, 2016, Vol. 7, No. 15, pp. 1707-1725.
Heyman, D.P. and Sobel, M.J., Stochastic models in operations research. 1. Stochastic processes and operating characteristics, McGraw-Hill, 1982.
Huang, J., Su, Y., Liu, W., Li, J., Wang, F., and Liu, Z., Analysis of buffer sharing strategy for satellites in the intermittently connected GNSS satellite network, Proceedings of the ION 2017 pacific PNT meeting, 2017, pp. 217-222.
Kapadia, A.S., Kazmi, M.F. and Mitchell, A.C., Analysis of a finite capacity non preemptive priority queue, Computers & Operations Research, 1984, Vol. 11, No. 3, pp. 337-343.
Kim, K., Finite-buffer M/G/1 queues with time and space priorities, Mathematical Problems in Engineering, 2022, Vol. 2022.
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., Space and time priority queues with randomized push-out scheme, Journal of Korean Society of Industrial and System Engineering, 2023, Vol. 46, No. 2, pp. 57-71.
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.
Kleinrock, L., Queueing systems, volume 2: Computer applications, Wiley, 1976.
Kroner, H., Hebuterne, G., Boyer, P. and Gravey, A., Priority management in ATM switching nodes, IEEE Journal on selected areas in communications, 1991, Vol. 9, No. 3, pp. 418-427.
Lee, Y. and Choi, B.D., Queueing system with multiple delay and loss priorities for ATM networks, Information Sciences, 2001, Vol. 138, No. 1-4, pp. 7-29.
Lin, A.-M. and Silvester, J.A., Priority queueing strategies and buffer allocation protocols for traffic control at an ATM integrated broadband switching system, IEEE Journal on Selected Areas in Communications, 1991, Vol. 9, No. 9, pp. 1524-1536.
Mallikarjuna, B., An effective management of scheduling- tasks by using MPP and MAP in smart grid, International Journal of Power and Energy Conversion, 2022, Vol. 13, No. 1, pp. 99-116.
Perati, M.R. and Gudimalla, R.K., Performance analysis of asynchronous priority-based internet router under self-similar traffic input-queueing system with markovian input and hyper-exponential services, International Journal of Operational Research, 2021, Vol. 40, No. 2, pp. 239-260.
Phan, H., Chu, T.M.C., Zepernick, H.-J., and Arlos, P., Packet loss priority of cognitive radio networks with partial buffer sharing, 2015 IEEE international conference on communications (ICC), 2015, pp. 7646-7652.
Reddy, D.M., Krishna, T.V., and Sarla, P., Markovian model for internet router employing PBS mechanism under self-similar traffic, AIP Conference Proceedings, 2020.
Ross, S.M., Stochastic Processes, John Wiley & Sons, 1996.
Sharma, V. and Virtamo, J.T., A finite buffer queue with priorities, Performance Evaluation, 2002, Vol. 47, No. 1, pp. 1-22.
Takagi, H., Queueing analysis, volume 1: Vacation and priority systems, part 1, North-Holland, 1991.
Xue, H., Kim, K.T., and Youn, H.Y., Packet scheduling for multiple-switch software-defined networking in edge computing environment, Wireless Communications and Mobile Computing, 2018, Vol. 2018.