The MAP/G/1 queueing system has been considered to study the effects of high burstiness and strong correlation between interarrival times. This type of queueing system can be easily found in broadband-integrated services digital networks (B-ISDNs) based on Asynchronous Transfer Mode (ATM) which is expected to be a suitable transfer mode to integrate various kinds of traffics such as voice, data, image, motion video, and so on.
In the analysis of queueing systems with MAPs, the matrix analytic method and Markov renewal theory have been employed until recent years. Note that the matrix analytic method allows no more than one random variable to have the countably infinite state space for the description of system dynamics. However, in most real systems we have models which require two or more random variables, each of which is defined in either a countably infinite space (e.g., the number of customers in the queue) or a continuous space (e.g., the unfinished work in the system, or the elapsed/remaining service time) to describe them properly. For those models the matrix analytic method does not give any help in analysis, and hence a new analytic method should be needed.
In this thesis we present how to apply the supplementary variable method to analyze the MAP/G/1 queueing system and its variants which can be applicable for ATM networks. The supplementary variable method is known as a simple and convenient method to derive the double transform of the queue length and the supplementary variable used. To solve the matrix differential equations arising in queueing systems with MAPs when we use the supplementary variable method, we need to extend the notion of Laplace transform for positive real numbers $s$ to that of Laplace transform for matrices S.
In chapter 3, we consider a packet voice/data multiplexer which is modeled by the MAP/G/1 queueing system where a single server queue is fed by an MAP and served in first-come-first-served (FCFS) manner, with general service time distribution. The main work of this chapter is how to apply the supplementary variable method to the derivation of the double transform for the MAP/G/1 queueing system. As one dimensional marginal transform of the double transform, we obtain the probability generating function of the number of customers in the system for the MAP/G/1 queue.
In chapter 4, we consider the MAP,M/$G_1,G_2$/1 queue with preemptive resume priority, where low priority customers arrive to the system according to an MAP with $(C_1,D_1)$ and high priority customers according to a Poisson process with rate γ. The service time density function of low (respectively: high) priority customers is $g_1(x)$ (respectively: $g_2(x)$). By using our supplementary variable analysis, we obtain the joint transform of the number of customers in each priority queue, as well as the remaining service time of the customer in service in steady state. We also derive the distribution for the number of customers of low (respectively: high) priority in the system just after the service completion epochs for customers of low (respectively: high) priority.
In chapter 5, we investigate the MAP/G/1 queue with multiple vacations where the service time distributions depend on the state of the underlying Markov chain of the MAP immediately before and after arrivals. This model can be applicable for an ATM switch with several input and output links where the transmission medium is shared by all links (i.e., an ATM switch with shared transmission medium). We derive the Laplace-Stieltjes transforms of the unfinished work and the virtual waiting time. We also show that the stochastic decomposition property holds for our model: the virtual waiting time is a sum of two independent random variables, one of which is the virtual waiting time in the same queueing system without vacations and the other is the remaining vacation time. This result is an extension of the previous result for the MAP/G/1 queue with server vacations and i.i.d. service times. We find a formula for relation on the actual waiting time and the response time (the actual waiting time + the service time) under FCFS service discipline.
MAP/G/1 대기체계는 통신망에 입력되는 트래픽의 높은 burstiness와 패킷 발생 시간들의 강한 상관성이 통신망의 성능에 주는 영향을 조사하기위하여 제안되었고, 분석 결과들은 ATM을 기반으로하는 광대역 통신망의 해석에 매우 유용하게 사용된다. 지금까지 MAP를 입력 트래픽으로 갖는 대기체계의 분석에는 matrix analytic method와 Markov renewal theory가 주로 사용되었다. 그러나, matrix analytic method는 두 개 이상의 무한 버퍼를 갖는 대기체계등의 분석에는 이용될 수 없는 단점이 있어 다양한 통신망 해석에 적용하기에는 한계가 있다. 본 논문에서는 M/G/1 대기체계의 분석에 이용되었던 보조변수 방법을 MAP/G/1 대기체계의 분석에 적용, 이러한 한계를 보완하였다. 현재 남아있는 서비스 시간을 보조변수로 이용하여 MAP/G/1 대기체계를 분석할 경우, 행렬에 대하여 확장된 개념의 Laplace transform이 필요하다. 우리는 확장된 개념의 Laplace transform을 이용한 보조변수 방법을 통하여 MAP/G/1 대기체계 및 광대역 통신망과 관련된 여러 대기체계들을 분석하였다.
3장에서는 패킷 음성/데이타 다중화기의 분석에 응용가능한 MAP/G/1 대기체계를 보조변수 방법을 통하여 분석하였다. 음성 트래픽와 데이타 트래픽의 합성 트래픽은 MAP로 모델링할 수 있고, 일반적으로 서로 다른 패킷들의 서비스 시간은 서로 다르므로, 서비스 시간은 각 트래픽의 서비스시간이 고려된 일반적인 분포로 모델링할 수 있다. 분석 결과로써, 임의의 시간에 버퍼에 있는 고객의 수와 남아있는 서비스 시간에 대한 결합분포를 구하였다. 이 결과로부터 임의의 시간에 시스템에 있는 고객의 수에 대한 분포를 구하였다.
4장에서는 preemptive resume priority를 갖는 MAP,M/$G_1,G_2$/1 대기체계를 연구하였다. ATM망은 서로 다른 서비스 품질(Quality of Service: QOS)을 요구하는 다양한 트래픽들을 수용할 수 있어야 하므로, 망 구현시 적절한 서비스 품질을 제공할 수 있는지 여부는 매우 중요한 문제이다. 이러한 문제들은 보다 나은 서비스 품질을 요구하는 트래픽에 우선순위를 주는 방법을 통하여 해결하고 있다. 본 연구에서는 입력 트래픽을 MAP와 포아송 확률과정으로 가정하고, 포아송 확률과정에 preemptive priority를 주었다. 각 트래픽의 서비스 시간은 서로 다른 분포를 따른다고 가정하였고, 각 트래픽에 대하여 무한 버퍼가 있다고 가정하였다. 보조변수 방법을 통하여 먼저 임의의 시간에 각 버퍼에 있는 고객의 수와 현재 서비스를 받고 있는 고객의 남아있는 서비스 시간에 대한 결합분포를 구하였다. 이를 이용하여 각 우선순위에 대하여 고객이 시스템을 떠나는 순간에서의 남아 있는 고객의 수에 대한 확률분포를 구하였다.
5장에서는 휴가시간을 갖고, 서비스 시간의 분포는 도착시점에 의존하는 MAP/G/1 대기체계를 고려하였다. 이 모델은 여러개의 입력 링크와 출력 링크를 갖고, 입력 링크들이 transmission medium을 공유하는 ATM 스위치에 적용할 수 있다. 예를 들어, 각 입력 링크들에 대한 서비스 방식이 polling mechanism을 따르는 ATM 스위치일 경우, 여러개의 입력 링크들 중 하나의 입력 링크에 대하여 살펴보면 polling time을 vacation time으로 모델링할 수 있고, 입력트래픽은 MAP로 모델링할 수 있다. 결과로써, 주어진 시스템에 대한 unfinished work와 virtual waiting time의 분포들을 계산하였다. 이 결과로부터 휴가시간을 갖는 대기체계의 대표적인 특성인 decomposition property가 성립함을 증명하였으며, 이것은 기존의 결과에 대한 확장이다. 또한, 주어진 대기체계에 대한 actual waiting time과 response time과의 관계에 대한 식을 구하였다.
본 논문에서는 기존의 matrix analytic method로 계산할 수 없었던 다양한 대기체계를 분석하였으며, 위와 같은 계산결과들은 ATM망 성능측도들, 즉, mean waiting time, variance of waiting time, cell delay variation, cell loss probability등을 유도하는데 이용될 수 있어, 망 구현 또는 설계에 있어 망 성능 예측에 큰 도움이 될것으로 기대된다.
