On Guaranteed Smooth Scheduling For Input-Queued Switches

Input-queued switches are used extensively in the design of high-speed routers. As switch speeds and sizes increase, the design of the switch scheduler becomes a primary challenge, because the time interval for the matching computations needed for the determining switch configurations becomes very small. Possible alternatives in scheduler design include increasing the scheduling interval by using envelopes (1), and using a frame-based scheduler that guarantees fixed rates between input-output pairs. Howvever, both these alternatives have significant jitter drawbacks: the jitter increases with the envelope size in the first alternative, and previously-known methods do not guarantee tight jitter bounds in the second.