A low-jitter Guaranteed-Rate scheduling algorithm for crosspoint-buffered switches

A Combined Input-Queued and Crosspoint-Queued (CIXQ) switch consists of N input ports, M output ports and an NxM switching matrix. Each crosspoint contains a FIFO queue which can hold at least one cell of data. Algorithms for scheduling low-jitter Guaranteed-Rate (GR) reservation-based traffic through the CIXQ Switch are presented. The algorithms can provide guarantees on the rate, delay and jitter for all provisioned GR traffic traversing the switch. The requested traffic rates between all IO pairs are specified in an NxM traffic rate matrix R. Each element of R specifies a requested number of cell transmission opportunities between one IO pair in a scheduling frame consisting of F time-slots. Each row of the traffic rate matrix is processed to yield a Cell Transmission Schedule (CTS) for each input port. The CTS specifies the guaranteed transmission opportunities from each input port to the appropriate crosspoints queues for a scheduling frame of fixed duration. Each column of the matrix is also processed to yield a Cell Reception Schedule (CRS) for each output port. The CRS specifies the guaranteed transmission opportunities from the appropriate crosspoints queues to the output port for a scheduling frame of fixed duration. The CTS and CRS schedules are re-used in consecutive scheduling frames, and are updated only when the traffic rate matrix is changed by an RSVP, IntServ or DiffServ protocol when traffic flows are added or removed. For all provisioned GR traffic flows, the schedules ensure that the delay, jitter and service lead/lag through the switch are small and bounded, and that each flow receives essentially-perfect QoS. Switching capacity unused by Guaranteed-Rate traffic can be used by Best-Effort traffic.