Design and performance analysis of efficient packet scheduling algorithms for Internet routing switches

This research is concerned with the design, implementation, and performance analysis of an Internet Routing Switch (IRS) that (i) supports both IP and ATM traffic, and (ii) provides multiple level QoS support. This dissertation presents procedures to achieve the following goals: (1) per flow QoS guarantee; (2) 100% switch throughput; (3) high link utilization; and (4) optimal system performance. To this end, an IRS architecture with a two-step scheduling and group scheduling is presented.; This research also develops techniques for link isolation and flow isolation for different QoS guarantees at the IRS. A Worst-case Controller is designed for this purpose. It can be used together with existing scheduling algorithms to achieve above mentioned goals. One example of such an application is Worst-case Longest Port First (WLPF). To guarantee real-time traffic QoS, a Prioritized Longest Port First (PLPF) scheduling algorithm is designed. A Washington University Gigabit Router (WUGR) is used to create a real-time simulation testbed for analyzing performance of the proposed scheduling algorithms. The results obtained are discussed and compared with existing algorithms. It is shown that the proposed algorithms give superior performance to existing algorithms.