This thesis is concerned with the throughput analysis of communication, computer, and manufacturing systems where system performance is affected by their physical resource limitations (storage spaces or buffers). A finite-buffered queueing network has been a useful tool for predicting several performance measures of such real-life systems. An important feature of queueing networks with finite buffers is that a phenomenon called blocking occurs, which seriously degrades network performances, particularly throughput. These queueing networks are known to be difficult to analyze as they are analytically intractable in general.
First, we deal with finite-buffered fork/join queueing networks(FJQNs), which have been extensively used to predict the performances of parallel processing, assembly/disassembly manufacturing, and distributed replicated database systems.
Introducing the notion of evolutionarily equivalent relations, a key result on the throughput equivalence between dissimilar-appearing FJQNs with finite buffers and GI service time distributions is obtained. And additional throughput equivalencies are also noticed along with an observation on a multi-server case. The practical significance of these results is that throughput calculation of a general FJQN can be significantly facilitated from the multiplicity of equivalent networks which appear different in configuration. Moreover, these equivalent relations are very useful for developing some approximation and bounding methods.
To understand the effect of service times and buffer capacities on throughput of finite-buffered FJQNs we introduce the sample path technique, and show that speeding up service, reducing variability of service times, and increasing buffer capacities improve the network throughput. We also explore the concavity property of throughput with respect to buffer capacities, which has important implications in optimization studies. And then the comparisons between networks with different blocking mechanism are made in the two cases: exponential servers and general servers.
By utilizing the properties developed above, we devise throughput- bounding and simple approximation methods for exponential FJQNs under BBS: specifically, the former is based on the monotonicity properties of throughput with respect to service times and buffer capacities, and the latter the evolutionarily equivalent relations. And the tightness of suggested bounds and the efficiency of the approximation methods are verified by extensive computational experiments.
Finally, we focus our analysis on an open finite-buffered queueing network with Markov routing, and present a simple but effective decomposition method which yields tight throughput upper bounds under any commonly used blocking mechanism. The method is first elaborated on with three specialized network configuration, tandem, split and merge, and then extended to a general configuration. Also shown is that the existing throughput-bounding methods for open queueing networks with blocking can be improved via duality consideration. Computational experiments confirm that our method is superior to all other existing methods.
각종 통신, 컴퓨터, 생산시스템들은 대개 시스템 구성자원의 侑恨性으로 인해 시스템성능에 제한을 받고 있다. 즉, 통신 및 컴퓨터시스템의 경우 각 시스템요소에서의 통신/정보단위(units)의 저장용량에 의해 시스템性能 (특히 産出率(throughput))이 좌우되며, 생산시스템의 경우 재공품 및 완제품의 저장용량은 해당 생산시스템의 생산능력을 결정하는 중요한 결정요소 중 하나 이다. 위와 같은 자원의 유한성으로 인한 시스템성능에 대한 부정적인 영향을 줄이기 위해서는 근본적으로 자원의 효율적인 활용이 전제되어 야 하는데, 이를 위해서는 대상자원이 시스템성능에 어떠한 영향을 미치는지에 대한 효과적인 예측/측정 道具(tool)가 요구된다.
유한용량 대기행렬망(queueing networks with finite buffers)은 통신, 컴퓨터, 생산시스템들과 같이 시스템단위들의 흐름이 確率的으로 이루어지고, 유한한 저장용량을 가진 시스템들의 성능측정 방법으로 널리 활용되어왔다. 이러한 저장용량이 유한한 대기행렬망에서는 망흐름이 일시적으로 정지되는 막힘(blocking)현상이 있는데, 어떠한 현실시스템을 대상으로 하였느냐에 따라 막힘형태(blocking mechanism)들은 여러 가지 종류로 분류될 수 있다. 한편, 유한용량 대기행렬망은 용량이 무한한 경우와는 달리 수학적으로 확정적해(closed-form solution)를 가지지 않아 정확해(exact solution)을 구하기가 매우 어렵다. 특히, 병렬처리 컴퓨터시스템, 분해/조립 생산시스템, 분산 데이타베이스시스템에서 볼 수 있는 분기/접합(fork/join)이 반영된 유한용량 대기행렬망은 분기/접합 현상으로 가중된 문제의 복잡성 (complexity)으로 인해 비교적 작은 규모의 문제에 대해서도 그것의 정확해를 얻는 것이 거의 불가능하다.
본 연구는 유한용량 대기행렬망의 산출률분석에 관한 것으로, 크게 두가지 종류의 대기행렬망을 대상으로 한다. 분기/접합 형태를 지닌 대기행렬 망(FJQN)에 관한 것이 그 하나이고, 망내의 단위들(이하 고객(customers)) 의 흐름이 확률적으로 이루어지는 Markov 루팅하의 대기행렬망에 관한 것이 다른 하나이다. 이 모델은 분기/접합 형태를 가지지 않은 대기행렬망 중 가장 일반적인 형태이다. 개방직렬망(open tandem network)과 폐쇠회전망 (closed cyclic network)은 위의 두 망종류의 특별한 경우에 해당된다.
첫째, 일반적인 서비스시간 분포하에서, 서로 다른 망구조를 가진 FJQN들간의 산출률 동일성(equivalence) 성질을 규명하기 위해 표본경로추 적기법(sample path technique)을 이용하였다. 우선, 망의 진화와 관련된 진화식을 바탕으로, 進化同一性의 개념을 정의하였다. 이 정의를 근간으로, 일정한 망구조 및 초기조건(initial conditions) 관계가 성립하는 두 FJQN의 산출률이 동일함을 밝혔다. 또한, 망구조와 초기조건이 上記된 경우와 또 다른 시스템들간의 관계를 통해, 새로운 두가지 산출률 동일성을 유도했는데, 이는 FJQN에서의 새로운 결과인 동시에 개방직렬망과 폐쇠회전망에 관련하여, 고객/공간(hole)개념을 바탕으로한 기존연구의 독립적인 결과들을 하나의 틀하에 설명할 수 있는 결과이다. 위와 같은 결과의 실용적 의미를 어떤 FJQN의 산출률을 구하기 위해서, 다른 구조를 가진 망의 산출률을 구하기 위한 연구결과들을 적극적으로 이용할 수 있다는 점과, FJQN의 근사해 법(approximation method)을 구하기 위한 방법을 개발하는데 이를 활용할 수 있다는 점 등에서 찾을 수 있다.
둘째, 서비스시간의 분포특성과 버퍼용량이 망의 산출률에 어떠한 영향을 미치는가에 대한 내용을 다루었다. 먼저, 서비스시간의 분포특성에 따른 산출률에 대한 결과를 얻기 위해 확률변수간의 특정 순위관계(ordered relation)를 규정하는 확률이론을 이용해 서비스시간의 분포가 어떤 순위관계에 있을 때, 산출률의 관계가 어떻게 되는지를 파악하였다. 이 결과가 의미하는 직접적인 의미 중에 하나로는 서비스시간의 加速, 서비스시간의 變動性의 감소등이 FJQN의 산출률을 증대시킬 수 있다는 사실이다. 한편, 버퍼용량이 증가함에 따라 FJQN의 산출률은 증대된다는 사실뿐만 아니라 버퍼용량에 대하여 산출률은 아래로 오목(concave)함을 증명하였는데, 이러한 성질들은 最適化문제를 취급할 때 매우 중요한 개념이 된다. 또한 막힘형태가 서로 다른 FJQN의 산출률의 관계(同一性 또는 大小)도 밝혔다.
셋째, 위에서 얻은 FJQN의 산출률에 대한 서비스시간 및 버퍼용량의 영향관계를 바탕으로 산출률에 대한 상한/하한을 구하기 위한 방법을 제시하였다. 하한의 경우는 단순접합(또는 분기)구조를 가진 망에 대해서만 적용될 수 있지만, 상한의 경우는 일반적인 구조를 가진 망에 적용될 수 있는 방법이다. 또한 진화동일성에 관련된 이론과 망을 여러 개의 서브망 (subnetwork)으로 분해한 뒤 다시 종합화 하는 분해/종합(decomposition /aggregation) 원리를 이용하여, 비교적 손쉽게 FJQN의 산출률을 유도할 수 있는 근사해법을 개발하였다. 많은 입력자료를 이용한 계산결과 본 연구에서 제시한 상한/하한을 구하기 위한 방법 및 근사해법이 비교적 좋은 결과를 보여줌을 확인할 수 있었다.
마지막으로, Markov 경로하의 유한용량 개방대기행렬망(open queueing network)을 대상으로 산출률의 상한을 구하기 위한 방법을 제시하였다. 막힘형태(blocking mechanism)로는 기존의 연구에서 분류된 대부분의 형태를 대상으로 하였다. 먼저, 직렬망, 분할망, 병합망 등 특수한 망구조를 가진 경우를 대상으로 각기 다른 막힘형태하에서 상한을 구할 수 있는 방법을 제시하고, 뒤이어 이를 일반적인 구조를 가진 망으로 확장하였다. 또한 반복서비스(repetitive-servcie) 막힘형태하에 있는 망에서 적용되는 기존의 쌍대이론을 이용하면, 기존의 상한/하한을 위한 방법들을 개선시킬 수 있음을 보였다.
