In this dissertation, we propose an efficient buffer management with priority, a scheduling algorithm guaranteeing the statistical QoS, and a multi-class scheduler supporting heterogeneous service classes.
First, we propose an ATM multiplexer with a resume level control. The selective cell discarding scheme can be used to meet the different loss requirements of QoS by selectively discarding low priority cells form arrival traffic during periods of congestion. Control procedures depend on identifying the threshold or resume level of selectively discarding specific classes of cells. In ATM networks, priority control is explicitly performed using a one-bit cell loss priority (CLP) field in an ATM header within one connection. For digitized voice and video traffic, the packet classification is based on the significancy of information and codec. We examine a selective cell discarding scheme with a resume level control for two priority classes, in which cells are selectively discarded from arrival traffic during periods of congestion. we approximate a superposition of several independent and homogeneous On-Off bursty sources into a Markov-modulated deterministic process (MMDP) model, and use the embedded Markov chain approach to derive the steady-state queue distribution. The performance analysis of an ATM multiplexer with a resume level control derived here includes as special cases one without priority and one with a threshold level. We compare a resume level control with a threshold level control in terms of cell loss probabilities, mean queue length, mean queuing delay, level crossing rate, and queue length distribution at the embedded points. From the numerical results, it is shown that by controlling a higher level and a lower resume level a resume level control, the level crossing rate and the queue length distribution can be greatly reduced to improve the system operation. Also, we suggest the method to determine an appropriate higher and lower levels in a resume level control.
Second, we present the bufferless multiplexer with proportional weights (BMW) with smoothers guaranteeing the statistical QoS given by the delay bound and the cell loss probability bound. Because deterministic service is based on the worst-case behavior of sessions without loss, it cannot obtain a high link utilization. To improve the utilization drawback of a deterministic service, the connection admission control (CAC) methods to guarantee the statistical QoS in a shared buffer, have been proposed. However, because these schemes did not consider each connection''s delay bound requirement, it did not apply to the heterogeneous connections which require each different QoS. To guarantee per-connection QoS requirements such as different delay and loss requirements, Reisslein proposed the bufferless multiplexer with smoothers. However, because the bufferless multiplexer has no parameter to reflect efficiently the different characteristics of smoothed traffic and QoS requirements, it cannot increase a link utilization maximally. To improve a utilization gain of the bandwidth, we present the BMW rather than the bufferless multiplexer as a link sharing scheme. Based on the assumption that the worst-case smoothed traffic is an extremal periodic on-off process, we derive the cell loss probability using the Chernoff large deviation and the Gaussian approximations. From the numerical results, it is shown that the BMW can allow for the larger number of heterogeneous connections guaranteeing each connection''s QoS requirement. Also, we present a simple CAC and resource allocation scheme based on the Gaussian approximation.
Lastly, we propose an efficient CAC algorithm in the multi-class scheduler reflecting the characteristic of each service class efficiently in the multiple service classes environment. In future integrated services networks, diverse heterogeneous services including a deterministic service, statistical service, and best-effort service, will coexist in a single integrated network. Qui proposed a CAC scheme using a statistical service envelope in a multi-class generalized processor sharing (GPS). In the multi-class GPS, the unused bandwidth of deterministic classes is redistributed to the flows belonging to the deterministic classes. However, it is shown that redistribution of the unused bandwidth does not improve the worst-case delay bound. In this paper, we characterize the output of deterministic classes more tightly by assigning its minimum bandwidth to each deterministic class and distributing the unused bandwidth to the statistical classes efficiently. To show that by reflecting the characteristic of each service class efficiently we can increase the admissible region, we propose two multi-class schedulers: a multi-class GPS with the tight characterization of deterministic classes (TCD) and a multi-class BMW with smoothers with TCD. From the numerical results, we show that by characterizing the output statistics for the deterministic service class more tightly we can increase the admissible region guaranteeing QoS for each service class.
본 논문에서는 우선순위를 갖는 입력트래픽에 대해서 효율적인 버퍼관리기법과 통계적 QoS를 보장하는 스케쥴링 알고리듬, 그리고 이종의 여러 서비스 클래스들을 지원하는 스케쥴링 알고리듬 방식에 대하여 다루고 있다.
먼저 버퍼관리기법으로 resume 레벨제어를 이용한 ATM 다중화기의 성능을 분석하였다. 기존에 혼잡이 발생할 경우에 도착하는 트래픽중 낮은 우선순위를 갖는 셀들을 선택적으로 페기하는 선택적 셀 폐기기법이 제안되었다. 선택적 셀 폐기비법은 문턱레벨 또는 resume 레벨을 이용하여 트래픽을 제어한다. ATM 망에서는 ATM 셀 헤더에 있는 한 비트의 CLP 필드를 이용하여 각 트래픽에 우선순위를 부여할 수 있다. 또한 음성과 영상 트래픽의 경우 각 정보의 중요도나 코딩방식에 따라 우선순위를 두어 전송할 수 있다. 본 논문에서는 두 개의 우선순위를 갖는 입력트래픽에 대해서 resume 레벨제어를 이용한 선택적 셀 폐기비법에 대한 분석방법을 제안하였다. Resume 레벨에 의한 제어는 높은 레벨과 낮은 레벨의 두 레벨에 의해 이루어지며 문턱레벨에 의한 제어는 높은 레벨과 낮은 레벨이 같은 resume 레벨의 특수한 경우가 된다. 분석을 위하여 버퍼에 들어 오는 다중화된 트래픽을 MMDP로 모델링하였고 embedded Markov chain 해석기법을 이용하여 정상상태 큐 길이 분포를 유도하였다. 수치결과계산에서는 resume 레벨제어와 문턱레벨제어를 각 우선순위 트래픽에 대한 셀손실율과 평균 큐 길이, 평균 큐잉 지연, 레벨 crossing 율, 그리고 큐 길이 분포 관점에서 비교하였다. 수치계산결과를 통해 resume 레벨제어에서 높은 레벨과 낮은 레벨을 적절히 조절함으로써 시스템의 성능을 향상시킬 수 있었다. 또한 높은 레벨과 낮은 레벨을 효과적으로 결정할 수 있는 방법을 제시하였다.
다음으로는 QoS 변수로 지연한계와 셀손실율로 주어지는 통계적 QoS를 보장할 수 있는 bufferless multiplexer with proportional weights (BMW)를 이용한 스케쥴링 알고리듬을 제안하였다. 기존의 셀손실이 없도록 하는 확정적 서비스는 높은 링크 사용을 얻을 수 없었다. 이러한 단점을 개선하기 위한 방법으로 공유버퍼를 갖는 ATM 다중화기에서 통계적 QoS를 지원할 수 있는 여러 CAC 기법들이 제안되었다. 하지만 이러한 CAC 방법들에서는 서로 다른 지연한계를 요구하는 트래픽을 지원할 수 없었다. 이러한 문제점을 해결하기 위해 버퍼가 없는 다중화기가 제안되었다. 이 방식을 이용하여 서로 다른 통계적 QoS를 보장할 수 있었다. 그러나 이 방식에서는 트래픽의 특성과 QoS를 효과적으로 반영할 수 있는 변수가 없어서 높은 대역 사용을 얻을 수 없었다. 이 논문에서 제안된 BMW는 트래픽의 특성과 QoS를 효과적으로 반영할 수 있는 변수를 두어 상황에 따라 적응적으로 변경할 수 있도록 함으로써 높은 대역 사용을 얻을 수 있었다. Worst-case smoothed 트래픽이 extremal periodic on-off process라는 가정을 기반으로 셀손실율을 Chernoff large deviation 근사방법과 가우시언 근사방법의 두 근사방법을 이용하여 유도하였다. 수치계산결과를 통해 제안된 BMW 방식이 통계적 QoS 요구사항을 만족시키면서 기존의 버퍼가 없는 다중화기보다 많은 연결을 수용할 수 있음을 확인하였다. 또한 가우시언 근사방식을 이용한 간단한 CAC 방법과 자원할당방식을 제안하였다.
마지막으로 확정적 서비스 클래스와 통계적 서비스 클래스의 이종의 서비스 클래스들을 제공하는 다중클래스 스케쥴러에서의 CAC 방법을 제안하였다. 차세대 통합 서비스 망에서는 서로 다른 트래픽 특성과 다양한 QoS를 제공하는 여러 서비스들이 하나의 망에서 공존할 것이다. 그러기 위해서는 다양한 서비스 클래스 환경에서의 효율적인 CAC방식과 자원할당방식이 중요하다. 기존에 Qui는 다중클래스 GPS에서 statistical service envelope를 이용한 CAC 방식을 제안하였다. 다중클래스 GPS에서는 확정적 클래스에서 남는 대역을 확정적 클래스에 속한 연결들에게 공정하게 나눠줌으로써 높은 대역 사용을 얻을 수 없었다. 왜냐하면 확정적 서비스는 각 연결에게 최소한의 대역만을 보장해줌으로써 셀손실없이 지연한계를 보장해 줄 수 있기 때문이다. 이 논문에서는 확정적 클래스에서 남는 대역을 통계적 클래스에서 사용함으로써 확정적 클래스의 출력을 보다 효과적으로 표현할 수 있는 방법을 제안하였다. 그리고 이 방법을 이용한 두 개의 다중클래스 스케쥴러를 제안하였다. 하나는 다중클래스 GPS with TCD이고 다른 하나는 다중클래스 BMW with smoothers with TCD이다. 수치계산결과를 통해 확정적 클래스의 출력을 효과적으로 표현함으로써 기존의 다중클래스 GPS보다 많은 연결을 수용할 수 있음을 확인하였다.
