In this thesis, we present our research on the design and analysis of efficient scheduling algorithms used in multiple input-queued switches for building next generation scalable high-speed packet switches/routers....[ Read more ]

In this thesis, we present our research on the design and analysis of efficient scheduling algorithms used in multiple input-queued switches for building next generation scalable high-speed packet switches/routers.

First, we present a performance analysis for a multiple input-queued ATM switch scheduled by the PIM scheduling algorithm. A closed-form solution for the maximum throughput of the switch under saturated condition is derived. Using the tagged input queue approach, an analytical model for evaluating the switch performance under an i.i.d. Bernoulli or 2-state Markov Modulated Bernoulli Process (MMBP) bursty traffic offered at each input port with the cell destinations uniformly distributed over all output ports, is developed. The switch throughput, mean cell delay, and cell loss probability are computed from the analytical model. The accuracy of the analytical model is verified using simulation.

Second, quantitative evaluations are carried out to compare the performances of PIM algorithm -- which is a cell-based scheduling algorithm -- with our newly proposed IP-PIM algorithm -- which is a burst-based variation of the PIM algorithm. Extensive analysis and simulation results demonstrate that IP-PIM outperforms PIM under a variety of realistic parameters. The queueing model developed for analyzing the mean burst delays of both the PIM and the IP-PIM scheduling algorithms provides a novel way to solve the difficult problem of performance analysis of PIM-like algorithms.

Finally, the problem of providing QoS guarantees for any traffic offered onto a multiple input-queued switch is addressed using stable matching of inputs and outputs for scheduling enqueued packets to be transmitted across the switching fabric. With an in-depth theoretic analysis on the properties of stable matching in the context of a multiple input-queued switch, we propose efficient schemes to guarantee the QoS of both unicast and multicast traffic with fixed-length or variable-length packets. Using these schemes, the QoS of packets can be guaranteed by independently employing suitable service disciplines at the packets' destined outputs like what is being done in an output queueing switch. This renders the designed QoS guaranteeing schemes general, yet flexible and efficient.