RP(Rate Proportional)-SCFQ : a packet scheduling algorithm for high-speed packet-switched networks

Abstract

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 simul...