Scheduling in packet switches with relaxed constraint

In this thesis, I present a series of new scheduling algorithms for an ATM-like crossbar input-queued switching fabric of an IP router. These new scheduling algorithms are developed based on three popular existing scheduling algorithms: Parallel Iterative Matching, Round Robin Matching, and Iterative Round Robin Matching with SLIP. The basic idea of our research is to divide all outputs of the IP router into a few groups. All outputs in the same output group are multiplexed into a high-speed link. Cells (traffic) can be directed to a group of outputs instead of an individual output. The performance of our new scheduling algorithms are measured with simulation. The simulation results indicate that our new scheduling algorithms can achieve an excellent throughput while consuming much less computing time than existing scheduling algorithms