Guaranteed smooth switch scheduling with low complexity

A smooth scheduling with guaranteed rate service and bounded packet delay is a desired objective of any switch scheduling algorithm. We present a scheme that generates low jitter schedules with low computational complexity. The scheduler uses an integer decomposition of the rate-matrix, similar to the Birkhoff-von Neumann decomposition. It improves the delay and jitter performance of the smooth scheduler as described in Keslassy et al. with an increase in the number of permutation matrices that the switch fabric has to cycle through. This increase is shown to be a constant for all practical purposes. Two algorithms are presented that have time complexity O(n² + log n) and space complexity O(n²) and O(n) respectively. An existing scheduling algorithm for single links, smoothed round robin, is employed for scheduling the permutation matrices. This algorithm has a computational complexity overhead of O(1) and ensures smooth scheduling.