SCHEDULING AND RATE PROVISIONING FOR INPUT-BUFERED CELL BASED SWITCH FABRICS

Abstract

In this dissertation, we develop and analyze algorithms for scheduling in input-buffered switch fabrics. We have introduced new deterministic and randomized scheduling algorithms that are capable of rate provisioning, achieves 100% throughput and have lower complexity than other proposed solutions. We consider QoS provisioning in general and rate provisioning in particular as the basic requirements for the next generation switch fabrics.

To do rate provisioning, we extend the concept of packetized tracking policies for fluid policies to the input-buffered switches. It is considered that the speed up of the switch is one and the fluid policy is feasible, i.e., utilization of all ports is less than one. For the 2x2 switches, we show that ideal non-anticipative tracking policies always exist. By ideal, we mean a tracking policy that is at most one cell behind the corresponding fluid policy. Using a 3x3 counter example, we show that non-anticipative policies do not generally exist. For the NxN switches, a heuristic tracking policy is provided.

The encouraging results for the heuristic policy motivated us to explore for analytical result for its performance. This effort leads us to the introduction of maximum node contained matching (MNCM) a new class of deterministic maximal size matching algorithms. We use fluid model techniques to prove that these algorithms achieve 100% throughput with no speedup. The only assumption on the arrival pattern is that it satisfies strong law of large numbers. We also introduce a new weighted matching algorithm in MNCM, maximum first matching (MFM) with complexity O(N^{2.5}). MFM, to the best of our knowledge, is the lowest complexity deterministic algorithm that delivers 100% throughput. We extend the concept of MNCM schedulers and introduce the Maximum Size Unit Interval Matching (MSUIM) algorithm for rate provisioning. MSUIM is at most N cells behind the corresponding fluid policy.

Finally, we propose a general parallel architecture for self-randomized algorithms that is appropriate for practical applications. We introduce the concept of max-min fair self-randomized scheduling algorithms for rate provisioning. Using fluid model technique, we provide analytical results for the performance of the self-randomized schedulers.