To estimate the packet delay in the Weighted Deficit Round Robin algorithm, we consider an M/G/1 queueing system with multiple vacations and the E-limited service discipline. We give two different approaches: In the first approach we obtain a closed form expression of the mean packet delay, and in the second approach we obtain an approximated formula for the mean packet delay which is simpler to compute than in the first approach. Numerical studies indicate that the exact value and the approximation value are acceptably identical. Some further discussions on the mean packet delay are also provided.
최근 인터넷의 급속한 발전으로 인해 종단 간 QoS 보장을 요구하는 실시간 멀티미디어 응용서비스에 대한 수요가 증가하고 있다. 이에 따라 현재 제공되고 있는 모든 트래픽이 차별없이 가능한 한 빠르고 많은 대역폭을 활용하는 방식인 최선형 서비스 (best effort) 서비스 만으로는 엄격한 서비스 품질의 보장을 할 수가 없게 되었다. 새로운 변화에 부응하기 위한 노력으로 차별화된 수준의 QoS를 지원하기 위한 기술에 대한 연구가 진행되고 있으며 이 중에서도 Differentiated Service 모델 구현을 위한 패킷 스케쥴링의 성능분석과 예측에 관한 문제는 더욱 중요해지고 있다.
본 논문에서는 패킷의 서비스 순서를 결정하여 자원을 할당하는 스케쥴링 알고리즘 중 Weighted Deficit Round Robin (WDRR)에 대하여 간단히 알아보고 WDRR 에서 스케쥴링의 성능평가를 위해 고려되어야 할 중요사항인 패킷지연시간을 확률적 분석을 통하여 구해보도록 한다. 먼저 확률적 분석을 위해 WDRR 을 이용한 패킷 서비스 모델을 복수휴가를 갖는 M/G/1 대기행렬시스템으로 모델링한다. 특정 클래스에 속하는 패킷의 관점에서 서버가 다른 클래스의 패킷을 서비스하는 시간은 휴가 기간으로 생각할 수 있으며 WDRR 알고리즘에 의해 하나의 클래스에 대응되는 큐는 고정된 가중치 만큼의 패킷을 연속적으로 서비스 해줄 수 있기 때문에 이 모델은 복수휴가를 갖는 E-limited service 시스템으로 분류되어진다고 할 수 있다. 패킷지연시간을 구하는 방법으로 변환 방법을 이용하여 closed form 을 얻는 것과 또 다른 방법으로 변환을 이용하지 않고 패킷지연시간의 근사값을 구하는 방법을 제시한다. 두 가지 방법으로 얻은 수치적 결과를 통해 두 값이 거의 일치함을 알 수 있고 큰 가중치를 갖는 클래스에 속하는 패킷일수록 지연시간의 upper bound 값이 작음을 확인할 수 있다.
