In this dissertation, both a class of continuous-time BMAP/G/1 queues with generalized vacations and a class of discrete-time BMAP/G/1 queues with generalized vacations are considered. This dissertation aims at presenting a unified analysis of these systems that have applications in various areas such as computer, communication, manufacturing and other stochastic systems. To this end, this dissertation presents explicit forms of matrix decomposition for the queue length distributions, for the workload distribution, and for the joint distribution of the queue length and the remaining service time in these systems. The significance of these decompositions is that the analysis of any continuous- and discrete-time BMAP/G/1 vacation queue is reduced to characterizing the conditional vector generating function of the queue length at an arbitrary epoch given that the server is on a vacation period. This is demonstrated by deriving the queue length distributions of various continuous- and discrete-time BMAP/G/1 vacation queues based on the decomposition presented in this dissertation. Also, these decompositions provide qualitative insight that is not obvious in the detailed matrix analytic treatment. Further, it is shown that queue length distributions are easily derived compared to standard procedures (e.g. matrix analytic method and supplementary variable technique) if these decompositions are used. Finally, general recursions for the factorial moments of the queue length and the workload are presented as application of these decompositions.
The results in this dissertation would be beneficial not only to queueing theorists but also to practitioners who try to optimize his/her queueing systems.
1. 연구배경
1.1. 연속시간 대기행렬과 이산시간 대기행렬 (Continuous-time queues and Discrete-time queues)
서비스를 제공하는 서버와 서비스를 요구하는 고객으로 구성된 대기행렬은 우리의 일상생활에서 흔히 볼 수가 있다. 이러한 대기행렬을 분석하는 이론이 `대기행렬이론 (queueing theory)’이며 이는 시스템의 분석 및 설계를 위한 중요한 수학적 도구로 최근 생산, 컴퓨터, 통신 및 각종 서비스 시스템 등을 대상으로 광범위하게 활용되고 있다.
일반적으로 대기행렬은 크게 ‘연속시간 대기행렬 (Continuous-time queues)’과 ‘이산시간 대기행렬 (Discrete-time queues)’의 두 범주로 분류할 수 있다. 기본적으로 연속시간 대기행렬에서는 고객의 도착과 이탈이 시간 축 상의 임의의 시점에서 발생한다고 가정하는데 반해, 이산시간 대기행렬에서는 시간 축을 슬롯 (slot) 이라 불리는 기본단위의 등 간격으로 나누고, 고객의 도착과 이탈이 항상 슬롯경계 (slot boundary)에서 발생한다고 가정한다. 최근 대기행렬분야에서는 멀티미디어 서비스를 제공하는 통신시스템에의 광범위한 응용가능성으로 인해 이산시간 대기행렬에 대한 연구가 증대되고 있다. 1.2. 휴가형 대기행렬 (Vacation queues)과 분해속성 (Decomposition property)
일반적으로 대기행렬시스템을 효율적으로 제어하기 위해서 시스템의 운용상황에 여러 제어정책 (control policy)을 반영하게 된다. 대표적 제어정책 예로서 시스템 내 고객수가 N 명 (N은 자연수)이 되어야 비로소 유휴중인 서버가 서비스를 개시하는‘N정책’을 들 수 있다. 이와 같이 여러 정해진 제어정책에 따라서 서버가 서비스를 제공하지 않고 휴가를 떠나는 대기행렬을 `휴가형 대기행렬 (Vacation queues)’ 이라 일컫는다.
연속시간 휴가형 대기행렬 중에서 그 분석이 간단하면서도 실제시스템을 적절히 묘사한 모형이‘휴가형 M/G/1 대기행렬’이다. 이 `휴가형M/G/1 대기행렬’의 주 관심사인 안정상태 고객수의 분포에 대해서 ‘분해속성 (Decomposition Property)’ 이라고 하는 분석에 매우 유용한 속성이 성립한다는 것이 잘 알려져 있다.
분해속성이란 ‘휴가형 M/G/1 대기행렬’의 고객수분포가‘휴가정책에 따라 달라지는 고객수분포’와 휴가정책이 달라져도 불변인‘표준 M/G/1 대기행렬 고객수분포’의 중합 (convolution)으로 표현된다는 속성이다. 표준 M/G/1 대기행렬의 고객수분포는 이미 그 결과가 잘 알려져 있다. 따라서 이 분해속성이 우리에게 주는 효용성이란 ‘휴가정책에 따라 달라지는 고객수분포’만을 구하기만 하면, 휴가형 M/G/1 대기행렬의 고객수분포를 매우 용이하게 직접 얻을 수 있다는 점이다. 연속시간 휴가형 M/G/1 대기행렬에서 성립하는‘분해속성’과 매우 유사한 분해속성이 또한 이산시간 휴가형Geo/G/1 대기행렬에도 성립한다는 것이 잘 알려져 있다. 이 분해속성은 대부분의 휴가형 M/G/1 대기행렬과 휴가형 Geo/G/1 대기행렬의 고객수분포를 매우 용이하게 도출할 수 있는 획기적인 속성으로 대기행렬분야에서는 이 유용한 분해속성이 과연 어떤 일반적인 연속시간 대기행렬 및 이산시간 대기행렬에까지 성립하는지 많은 연구자들에게 큰 관심사가 되고 있다.
1.3. 집단 마코비안 도착과정 (Batch Markovian arrival process, BMAP)과 이산시간 집단 마코비안 도착과정 (Discrete-time batch Markovian arrival process, D-BMAP)
연속 및 이산시간 휴가형 대기행렬은 광범위한 응용성으로 인하여 활발한 연구가 진행되어 왔지만, 기존의 대부분의 연구가 고객의 도착과정이 포아송 과정 (Poisson process) 또는 베르누이 과정 (Bernoulli process) 이라는 가정 하에 진행되어 왔다. 하지만 이 가정은 실제시스템, 특히 통신시스템의 도착과정을 모형화 하는데 그 한계를 가지고 있다. 그 이유는 다양한 종류의 트래픽 (traffic)을 발생시키는 광대역종합정보통신망 (Broadband Integrated Service Digital Network, B-ISDN) 등과 같은 현대의 대규모 초고속 정보통신망에서 트래픽의 도착과정은 도착간격들간에 강한 상관관계를 가지고 있다는 특성이 알려져 있고 도착간격들이 서로 독립이라고 가정을 하고 있는 포아송 과정과 베르누이 과정 하에서의 대기행렬분석 결과들은 실제 통신시스템에 잘 부합되지 않기 때문이다. 따라서 최근 대기행렬분야에서는 실제시스템, 특히 통신시스템에서 트래픽의 도착과정을 적절히 묘사할 수 있는 새로운 도착과정을 적용한 대기행렬이 중점적으로 연구되고 있는 추세이다. 특히 이 중에서 ‘집단 마코비안 도착과정 (Batch Markovian Arrival Process, BMAP)’과 ‘이산시간 집단 마코비안 도착과정 (Discrete-time Batch Markovian Arrival Process, D-BMAP)’은 기존의 알려진 각종 연속 및 이산 시간 도착과정들을 특수경우로 포함하는 지극히 일반적인 틀로 도착간격들간의 상관관계를 적절히 묘사하면서 수학적 분석이 용이하여 활발히 연구되고 있다. 최근 대기행렬분야에서는 이들 도착과정을 적용한 ‘연속시간 휴가형 BMAP/G/1 대기행렬’과 ‘이산시간 휴가형 BMAP/G/1 대기행렬’에 대한 연구가 활발히 진행 중이다.
2. 연구목적 및 의의
본 연구의 목적은 일반적인 `연속 및 이산시간 휴가형 BMAP/G/1 대기행렬’의 주 관심사인 안정상태 고객수분포가‘휴가정책에 따라 달라지는 고객수분포’와 `휴가정책이 달라져도 불변인 분포’의 중합 (convolution)으로 표현되는‘분해속성 (Decomposition Property)’을 규명하는 것이다.
본 연구에서 규명된 이 분해속성을 활용하면 단지 `휴가정책에 따라 달라지는 고객수분포’ 만을 도출함으로써 다양한 ‘휴가형 BMAP/G/1 대기행렬’의 주 관심사인 고객수분포를 통합적으로 용이하게 도출할 수 있게 된다. 이로서 개개 휴가형 BMAP/G/1 대기행렬을 처음부터 개별적으로 분석하여 고객수분포를 도출하는데 필요한 노력이나 비용을 상당부분 절감할 수 있게 된다. 또한 본 연구에서 제시한 결과는 기존의 다양한 휴가형 대기행렬의 분해속성 결과들을 특수결과로 포함하는 일반성을 보이고 있다. 이러한 관점에서 본 연구에서 제시된 분해속성은 다양한 ‘휴가형 BMAP/G/1 대기행렬’의 통합적 분석 (Unified Analysis) 에 대한 지침을 제공할 수 있다.
