Packet scheduling algorithm is a critical component of future integrated-services packet networks that will provide a broad range of quality-of-service (QoS) guarantees. Among various performance metrics that characterize a scheduling algorithm, the implementation simplicity can be considered as one of the most important advantageous factors especially in high-speed packet network. On the complexity point of view, SCFQ (Self-Clocked Fair Queueing) has been known to be the simplest algorithm even though it could not be implemented in reality since its delay bound depends on the number of connections.
On the other hands, in heterogeneous network environment where multiple packet nodes implemented with different scheduling algorithms are interconnected, the performance requirements such as delay, delay jitter and buffer space, should be guaranteed by each node to keep the end-to-end performance. The concept of RPS (Rate Proportional Server) was defined in the literature to describe the general requirements for the scheduling algorithm. Once a scheduler is designed according to the guideline of RPS, it can guarantee the bounded end-to-end delay.
In this thesis, a new scheduling algorithm, RP(Rate Proportional)-SCFQ, is proposed to improve the delay property of SCFQ. It is well suited for high-speed packet-switched networks because of its ability to guarantee the performance bound with low implementation complexity. RP-SCFQ algorithm provides simple mechanism to maintain the system potential without GPS (Generalized Processor Sharing) approximation. As the name implies, RP-SCFQ can be categorized into the RPS (rate Proportional Server) class, so it guarantees the end-to-end delay performance even in the heterogeneous network environment. The algorithm also provides low implementation complexity. Since the system potential is updated only once during a packet's transmission, its computational complexity for the system potential is O(1). Using a commercial simulation tool, BONeS (Block Oriented Network Simulator), we analyze the performance of RP-SCFQ in comparison with existing scheduling algorithms such as WFQ, SCFQ and SPFQ (Starting Potential Fair Queueing). The simulation reveals that the proposed algorithm guarantees the RPS delay bound as well as the excellent short-term fairness.
다양한 서비스 품질에 대한 요구조건을 갖는 서비스들이 복합적으로 존재하는 향후의 패킷 교환망에서 패킷 스케줄링 알고리즘은 매우 중요한 의미를 갖는다. 스케줄링 알고리즘을 특징짓는 여러가지 성능지표 중 고속 패킷망에서 가장 중요하게 고려되어야 할 요소는 용이한 구현을 위한 알고리즘의 단순성이다. 구현 복잡성 측면만을 고려할 경우 SCFQ (Self-Clocked Fair Queueing) 알고리즘이 가장 단순한 것으로 알려져 왔으나 이 알고리즘은 지연 바운드가 연결의 수에 비례하여 커지는 특성을 갖는다.
한편 실제 망 환경에서 서로 다른 스케줄링 알고리즘이 구현된 이기종 패킷 노드가 상호 접속되는 경우에도 각 연결별 지연, 지연 지터 또는 요구 버퍼 크기 등의 성능은 종단간 보장되어야 한다. 이러한 망 환경에서의 성능 요구사항을 만족시킬 수 있는 스케줄링 알고리즘 설계가 가능하도록 RPS (Rate Proportional Server)라고 하는 스케줄링 알고리즘에 대한 일반적인 가이드라인이 제시된 바 있으며 이 범주에 의거 설계된 스케줄링 알고리즘들은 공정성 특면에서는 서로 다르지만 동일한 지연 바운드를 보장할 수 있다.
따라서 이 논문에서는 SCFQ의 단순성을 유지하면서 지연 바운드 속성을 개선한 RP-SCFQ라고 하는 새로운 스케줄링 알고리즘을 제안한다. 제안된 알고리즘은 RPS와 동일한 낮은 지연 바운드를 보장하고 낮은 복잡도에서 구현 가능하므로 고속 패킷 교환망 환경에 적합한 스케줄링 알고리즘이다. 특히 RP-SCFQ 알고리즘은 GPS (Generalized Processor Sharing) 서버를 모방하지 않고 간단한 방식에 의하여 시스템 포텐셜을 유지 관리한다. 제안된 알고리즘은 RPS 범주에 속하는 알고리즘으로서 RPS의 지연 바운드를 그대로 지원하므로 RPS 계열의 이기종 패킷 노드가 상호 연결된 환경에서도 종단간 지연 보장이 가능하다. 시스템 포텐셜은 매 패킷의 전송 종료 시에만 갱신되므로 계산에 소요되는 복잡성은 O(1)이다.
또한 제안된 알고리즘의 지연, 지연 지터 및 공정성 등의 성능을 상용 도구인 BONeS 시뮬레이터를 이용하여 분석하였으며, 시뮬레이션 결과로부터 제안된 알고리즘이 SCFQ 알고리즘에 비하여 우수한 성능을 갖는 스케줄링 알고리즘임을 알 수 있다.
