This dissertation analyzes two discrete-time queueing systems: $GI^X$/D/c and $GI^X /Geom/ ∞$, which are applicable to analyses of communication systems. An extended version of the simple relation between GI/D/1 and GI/D/c systems allows us to obtain the explicit results of the waiting-time distributions of the $GI^X$ /D/c model with a restriction on the arrival group size distribution. Simple computational analysis is also presented for the usefulness of practitioners working in areas, such as ATM switching elements and traffic concentrators. Additionally, under the assumptions of EAS (Early Arrival System) and LAS (Late Arrival System), we derive the system size distributions of the infinite-server $GI^X/Geom/∞$ system at two different epochs-prearrival and random. Simple relations among the binomial moments of the steady-state system-size distributions of the two systems are derived. As a special case of the infinite-server system, this dissertation obtains the results of the $GI^X/D/∞$ system without any restriction on the arrival group size distribution, which can be used as an approximation of the $GI^X$ /D/c system under light traffic.
The conventional analyses of queueing systems obtain the results using transforms, such as PGF (Probability Generating Function) or LT (Laplace Transform), from which the aimed distribution is generally hard to extract. In contrast, for the usefulness of the practitioners, this dissertation gives the transform-free results of the waiting-time distribution of the discrete-time $GI^X$ /D/c systems. In getting the system-size distribution of the $GI^X/Geom/∞$ system, this dissertation uses the transform of binomial moment, from which we can easily get the explicit result of the distribution.
최근 통신시스템의 발달로 인해 이산시간 대기행렬 모형에 대한 관심이 높아지고 있다. 일반적으로 최근의 통신 시스템은 정보가 비트, 패킷, 셀 등의 작은 단위로 나누어져 처리 되고 이런 시스템의 경우 연속시간 대기행렬 모형보다 이산시간 대기행렬 모형이 더 잘 설명한다는 것이 알려져 있다. 이산시간 대기행렬 모형은 연속시간 대기행렬 모형과 달리 시간 축이 slot 이라 불리는 일정한 시간단위로 나누어져 있다. 이로 인해 연속시간 대기행렬 모형과는 다른 여러 성질이 발생되는데 이는 p.2 의 table 1.1 에 정리되어 있다. 본 논문은 통신 시스템, 특히 ATM 환경하의 통신 시스템 분석에 많이 이용되는 두 가지 이산시간 대기행렬 모형인 $GI^X$/D/c 시스템과 $GI^X /Geom/∞$ 시스템을 분석하고 유용한 성능 척도들의 결과를 제시하고자 한다.
I.고객이 한명씩 도착하는 이산시간 GI/D/c 모형의 분석
첫번째로 본 논문은 그룹 도착이 존재하지 않는 GI/D/c 모형에 대하여 고객들이 서비스 받기 전에 시스템에 머무는 시간 (대기시간) 의 분포를 구했다. 이 시스템은 ATM switching node 의 분석을 위해 기존의 여러 문헌에서 분석을 시도한 모형으로, 기존의 연구들은 서비스 시간 D의 값을 하나의 슬롯과 동일한 값을 갖도록 가정하였는데 (D=1) 본 논문에서는 서비스 시간 D가 1보다 큰 임의의 상수 값을 갖는 모형으로 확장하였다. 이 모형의 연구에는 다음의 두 가지 분석방법이 주로 이용되었다. 그 첫번째가 Iversen (1983)의 정리이다. 이 정리는 고정된 (constant) 서비스 시간을 가지는 연속시간 모형에 대해서 하나의 서버를 가지는 모형 $(GI^c/D/1)$ 의 대기시간과 복수 서버를 가지는 모형 (GI/D/c) 간의 대기시간 사이의 관계를 규명한 이론으로 본 논문에서는 이를 이산시간 모형에 확장하여 적용하였다. 또한, 이산시간 대기행렬 모형의 대기시간 분석에서 나오는 변환형태의 결과인 PGF (Probability Generating Function)에서 분포를 이끌어 내는 역 변환 과정에 효과적인 방법인 Outside roots rule을 적용하여 간단 명료한 결과 (explicit results)를 유도하였다.
II.고객이 집단으로 도착하는 이산시간 $GI^X$/D/c 모형의 분석
실제의 통신 네트워크에서 하나의 node에 연결된 arc의 수는 여러 개가 존재한다. 이로 인해, 임의의 시간(슬롯) 단위 안에 하나의 node에 들어오는 정보의 단위인 패킷 이나 셀 등은 하나씩 따로따로 들어오기 보다는 집단으로 동시에 들어오게 된다. 결과적으로 이런 node의 분석을 위해서는 집단 도착 (group arrival) 이 존재하는 대기행렬 모형의 분석이 필요하다. 일반적으로 고정된 서비스 시간을 가지는 대기행렬 모형의 분석에 사용되는 Iversen (1983)의 정리는 집단 도착 (group arrival)이 존재하는 모형에 적용하기가 쉽지 않다. 그러나, 집단 도착의 크기 (group arrival size)에 어떤 조건을 걸어 주면 Iversen (1983)의 정리의 적용이 가능하게 된다. 본 논문에서는 집단 도착의 크기 X 가 서버의 수 C 를 넘어서지 않는 경우에 대해서 Iversen의 정리를 확장하여 적용하는 것이 가능하다는 것을 밝혀냈다. 새로운 시스템 상태에 대한 정의를 통하여 기존에 알려진 Iversen의 정리를 확장하였고 이를 이용하여 집단 도착의 크기 X 가 서버의 수 c 를 넘어서지 않는 $GI^X$/D/c 시스템의 대기시간 분석 결과를 제시하였다. 또한, 이 확장된 Iversen의 정리의 활용과 적절한 가정을 통해 집단 도착의 크기 X 가 기하 (Geometric) 분포를 따르는 모형의 결과도 얻어냈다. 기하 분포는 일반적으로 시스템의 분석에 가장 많이 사용되는 이산 확률 분포의 하나로 이 결과는 실제 응용 분야에의 적용에 많이 이용될 것으로 기대한다.
III. 고객이 집단으로 도착하는 무한서버 $GI^X /Geom/∞$ 모형의 분석
마지막으로, 본 논문에서는 고객이 집단으로 도착하고 서비스 시간이 기하분포를 따르는 무한서버 모형인 $GI^X /Geom/∞$ 시스템에 대해 고객 도착시점과 임의시점의 시스템 내 고객 수 분포의 결과를 제시하였다. 무한 서버 모형은 고객의 대기장소가 필요하지 않고, 고객도 자신의 서비스 시간 만큼만 시스템에 머물러 있게 되므로 고객 수 분포가 중요 성능 척도가 된다. 본 논문에서는 Binomial Moments 라는 기존에 알려져 있지만 다소 생소한 변환 (transform)을 사용하여 본 모형을 분석하였다. Binomial Moments는 기존의 대기행렬 모형에서 사용되는 PGF 나 LT (Laplace Transform)에 비해 역 변환이 쉽다는 장점이 있다. 이 Binomial Moments를 이용해서 이산시간 $GI^X /Geom/∞$ 모형의 두 가지 가정, EAS (Early Arrival System) 과 LAS (Late Arrival System), 하에서의 고객 수 분포를 모두 제시하고 그 결과간의 간단한 관계도 보였다. 일반적으로 서비스 시간이 기하분포를 따르는 이산시간 복수서버 대기행렬 모형은 clustered web server system의 분석에 주로 이용된다는 것이 알려져 있다. 본 논문은 제시한 무한서버 모형의 결과를 통해 clustered web server system의 최적 서버 수를 근사적으로 구하는 방법을 제시하였다. 또한, 기하 분포의 특성을 이용해서 $GI^X /Geom/∞$ 모형의 결과도 제시하였는데, 이는 앞에서 구하지 못한 집단 도착 크기에 조건이 걸리지 않은 $GI^X /Geom/∞$ 모형의 근사치로써 사용할 수 있다.
IV. 결론 및 후속연구
본 논문에서는 통신시스템, 특히 ATM 환경 하에서의 통신 시스템 분석에 많이 활용되는 대표적인 이산시간 모형을 분석하여 각 성능척도에 대한 결과를 제시하였다. 그러나, 앞에서 설명했듯이 분석의 한계로 인해 집단 도착의 크기에 제약을 둔다던가, 서비스 시간의 분포를 기하분포로 제한 한다던가 하는 몇 가지 한계점을 드러냈다. 비단 현재의 통신시스템이나 ATM 분석 뿐만 아니라 앞으로의 차세대 통신 시스템의 분석을 위해서는 위의 제약들이 존재하지 않는 시스템으로의 확장이 필요하다. 이를 위해서는 본 논문에서 사용한 방법의 확장이나 다른 분석방법의 도입이 필요할 것으로 사료된다.
