Traffic management in communication environments like the Internet is vital in meeting the demand of users. The recent introduction of various dynamic scheduling algorithms has been to target improvements in QoS (Quality of Service). The Multi-Priority Dual Queue (MPDQ) was designed to reduce congestion levels in communications models with finite buffers. By splitting a single finite buffer space into two queues, known as dual queues, and by administering a priority scheme to arriving customers, the MPDQ has shown its advantages to communications providers in QoS. The MPDQ is especially relevant for the Internet’s development, and also has merits for use in certain manufacturing systems where a second holding area is available.
In this paper we use the matrix analytic methods to define the state rate transitions and uniquely implement them into an algorithm to obtain a solution. We analyze the differences in loss between a MPDQ and a basic single queue with preemptive and non-preemptive priority service disciplines and then prove the results in Bedford and Zeephongsekul (EJOR, 2003) are not correct. And we analyze the differences in loss between preemptive and non-preemptive service disciplines and show that non-preemptive service discipline is superior than the preemptive scheme.
인터넷과 같은 통신환경에서 고객의 요구를 만족시키기 위한 트래픽의 관리가 매우 중요하다. 서비스 품질 (QoS) 향상을 위해 다양한 동적 스케줄링 알고리즘이 제안되어 왔으며 Bedford와 Zeephongsekul 은 기존의 대기행렬 모형의 대기공간을 두 개의 유한용량 대기행렬 형태로 나눈 Dual Queue 개념과 도착하는 고객이 속한 클래스의 우선순위에 따라 서비스의 순서를 정하는 Priority 서비스 규칙의 개념을 결합한 Multi-Priority Dual Queue (MPDQ)를 제안하였다. 이들은 시뮬레이션과 행렬 분석적 방법(matrix analytic method)을 통하여 각각 비축출형과 축출형 우선순위 서비스 규칙하에서 MPDQ가 기존의 일반 단일 대기행렬 모형에 비해서 우수하다고 주장하였다.
그러나 이들이 EJOR (European Journal of Operation Research)에 수록한 행렬 분석적 방법을 통한 축출형 우선순위를 갖는 MPDQ의 분석에 관한 논문의 결과가 잘못되었기에 이를 수정하고, 연구를 비축출형 우선순위 서비스 규칙의 경우로 확장하여 MPDQ와 일반 단일 대기행렬모형의 비교분석을 행하고자 한다. 또한 각 대기행렬 모형 형태에 대하여 비축출형과 축출형 중 어느 우선순위 규칙이 더 좋은 성능을 주는지 알아보고자 한다.
비교 분석 방법은 행렬 분석적 방법으로써 상태전이 다이어그램과 상태전이 행렬로부터 시스템의 평형상태 확률분포를 구하고 이로부터 각 시스템의 성능 특성치를 구한다. 이 중 새로 도착하는 고객이 손실될 확률(loss probability)을 비교함으로써 각 우선순위 서비스 규칙에 따른 대기행렬 시스템의 성능을 비교 분석한다. 분석의 편이를 위하여 MPDQ의 용량 을 primary queue와 secondary queue 각각 2로 정하고, 두 가지 클래스의 고객을 정의하였다. 하나의 클래스의 고객은 다른 클래스의 고객에 대하여 우선순위를 갖고 이들의 도착은 서로 독립적인 포아송 분포를 따른다. Primary queue에 있는 단일 서버는 각 클래스의 고객에 대해 지수 분포의 서비스를 수행하며, secondary queue는 서비스 시설은 없고 단지 primary queue에 고객이 차서 더 이상 고객이 들어갈 수 없을 때 도착하는 고객이 대기하는 공간이다. 시스템 내에서 고객들은 우선순위에 따라 순서를 정렬한다. 축출형 우선순위 서비스 규칙인 경우 우선순위가 낮은 고객이 서비스 받는 도중에 우선순위가 높은 고객이 도착하면 서비스를 멈추고 뒤로 밀려나지만, 비축출형 우선순위 서비스 규칙인 경우에는 우선순위가 낮은 고객이라도 일단 서비스가 시작한 이후에는 축출당하지 않는다.
본 논문에서는 축출형 우선순위 서비스 규칙을 갖는 경우 MPDQ가 기존의 단일 대기행렬 모형보다 손실확률이 줄어드는 우수성을 갖지만, 비축출형 우선순위의 경우에는 두 시스템간에 성능차이가 없음을 보였다. MPDQ와 단일 대기행렬 모형 각각의 경우에서 비축출형 우선순위 서비스 규칙을 사용하여 서비스가 이루어질 때가 축출형 우선순위 서비스 규칙에 의해 하위 고객의 서비스 중단이 발생하는 경우보다 시스템에 더 우수한 성능을 가져옴을 보였다.
본 논문에서 사용한 행렬 분석적 방법은 이해가 쉽고 정확하여 다양한 대기행렬 모형의 분석에 편리하며, 본 논문에서 얻은 결과는 MPDQ라는 새로운 대기행렬 모형을 통신시스템이나 생산시스템 등 실제 분야에 응용 하여 시스템의 성능과 서비스 품질을 향상시키는데 기여할 것이다.
