B-ISDN are required to support a variety of services such as audio, data, and video, etc., so that the guarantee of Quality-of-Service (QoS) has become an increasingly important problem. An effective fair scheduling algorithm enables high-speed intermediate nodes to distribute link bandwidth fairly among competing connections. Therefore, it helps networks to guarantee the QoS requirements of connections.
Generally, fair scheduling algorithms meets requirements of both the high performance and the easy implementation. In this thesis, we propose and analyze high-performance simple fair scheduling algorithms. The one is called "Virtual-Time-based Round Robin(VTRR)." This scheme maps the priorities of packets into classes and provides service to the first non-empty class in each round, and it uses and estimation method of the virtual time necessary to this service discipline. To find the first non-empty class, VTRR adopts a priority queueing system using a bitvector which decreases the number of instructions which need to be carried out in one packet transmission time segment. These policies help VTRR implementation in software, which presents flexibility for upgrades. Our analysis has demonstrated that VTRR provides bounded unfairness and its performance is close to that of Weighted Fair Queuing. Therefore, VTRR has a good performance as well as simplicity, so that it is suitable for B-ISDN.
And, we propose and analyze the preemptive and nonpreemptive rate-based schedulers fir ABR service in the ATM network which ETRI is now developing. Since the switching network of this ATM network has no separate buffer for each class, TCB (Traffic Control Block) was adopted. This equips separate buffers in which the traffic scheduler operates. The proposed schedulers are non-work-conserving so as not to generate bursty ABR traffic. The preemptive scheduler saves cells in sorting bin keeping the transmission interval corresponding to the transmission rate. If a conflict occurs while saving, the sorting bin sorts cells out according to service finishing time. It is analyzed to have an ideal performance, but it also has O(N) complexity to sort where N is the number of connections. The nonpreemptive scheduler is a simplified version of the preemptive scheduler. It has the advantage to be easy to implement in ATM networks. We show that the performance of the nonpreemptive scheduler is close to that of the preemptive scheduler, even under severe simulation conditions. And we also simulated the nonpreemptive scheduler with the ABR traffic control, which showed that the nonpreemptive scheduler operates well in ATM networks.'
멀티미디어 서비스에 대한 점증하는 요구를 수용하기 위해 제안되어진 광대역 종합정보통신망(B-ISDN)은 소리, 데이터, 동영상 등의 다양한 서비스를 종합적으로 서비스할 수 있어야 한다. 이러한 망에서 각 서비스가 요구하는 서비스 품질(QoS)를 보장하는 것은 망의 구현을 위한 중요한 문제로 대두되고 있다. 효과적인 공정 스케줄링 알고리즘(Fair Scheduling Algorithm)은 고속의 통신 노드들에서 대역폭을 공유하는 연결들에게 공정하게 할당함으로써, 각 연결이 요구하는 서비스 품질을 보장하도록 한다.
지금까지 많은 공정 스케줄링 알고리즘들이 연구, 제안되어 왔지만, 높은 성능과 용이한 구현성을 함께 가진 알고리즘은 아직 미흡한 실정이다. 본 논문에서는 높은 성능을 제고하면서도 고속 통신망에서 구현이 용이한 공정 스케줄링 알고리즘들을 제안한다. 제안한 첫번째 공정 스케줄링 알고리즘은 "가상시간 기반 라운드 로빈"(VTRR)이다. 이 알고리즘은 패킷들을 처리 우선순위에 따라 해당 클래스에 할당하고 매 라운드마다 첫번째 비지 않은 클래스부터 서비스를 제공한다. 이때, 같은 클래스에 있는 연결들은 라운드 로빈 방식으로 서비스한다. 첫번째 비지 않은 클래스를 찾기 위해 bitvector 방식의 우선순위 큐를 채택한다. 또한 가상 시간 계산을 위해 간단한 추정 방법을 제안, 사용한다. 이러한 서비스 방법은 스케줄링에 필요한 구현 복잡도를 줄여 고속 통신망에서도 소프트웨어로 구현을 가능하게 하며 시스템의 확장성을 향상시켜 준다. 분석을 통해 간단한 구현에도 불구하고 VTRR의 성능이 Weighted Fair Queueing에 근사함을 보인다.
또한 현재 전자통신연구원에서 개발 중인 ATM 망에서의 ABR 서비스를 위한 전송률 기반 스케줄러를 제안, 분석한다. 이 ATM 망의 스위칭 망은 내부에 각 서비스 클래스를 위한 개별 버퍼를 구비하지 않았기 때문에 TCB(Traffic Control Block)을 스위칭 망과 종단 간에 두고 있다. TCB는 각 서비스 클래스를 위한 개별적인 버퍼를 두고 트래픽 스캐줄러를 적용한다. 제안된 스케줄러는 폭주성의 ABR 트래픽을 생성하지 않도록 비작업보존적(non-work-conserving)인 알고리즘이다. 선점적 스케줄러는 ATM셀들을 허용된 전송간격을 유지하도록 소팅빈에 저장한다. 이때 소팅빈에서 충돌이 생기는 경우 서비스 종료시간에 따라 셀들을 정렬한다. 선점적 스케줄러는 분석을 통해 이상적인 성능을 가지는 것으로 증명되었으나, 연결의 수를 N이라 할 때 O(N)의 복잡도를 가진다. 비선점적 스케줄러는 소팅빈에서 충돌 시 비교를 생략함으로써 정렬의 복잡도를 줄여 구현을 용이하도록 하였다. 모의 실험 결과는 비선점적 스케줄러의 성능이 심한 부하에서도 선점적 스케줄러의 성능에 근사함을 보여준다. 또한 모의 실험을 통해 비선점적 스케줄러가 ABR 트래픽 제어 기능과 연동되어 잘 동작함을 보인다.
본 논문에서 제안한 공정 스케줄링 알고리즘들은 이러한 분석 결과를 통해 높은 성능과 간단한 구조를 함께 지니며, B-ISDN에 적합하다고 결론지을 수 있다.
