Importance

Loading Importance Indicators...

Abstract

A method for scheduling cell transmissions through a switch with rate and delay guarantees and with low jitter is proposed. The method applies to a classic input-buffered N×N crossbar switch without speedup. The time axis is divided into frames each containing F time-slots. An N×N traffic rate matrix specifies a quantized guaranteed traffic rate from each input port to each output port. The traffic rate matrix is transformed into a permutation with NF elements which is decomposed into F permutations of N elements using a recursive and fair decomposition method. Each permutation is used to configure the crossbar switch for one time-slot within a frame of size F time-slots, and all F permutations result in a Frame Schedule. In the frame schedule, the expected Inter-Departure Time (IDT) between cells in a flow equals the Ideal IDT and the delay jitter is bounded and small. For fixed frame size F, an individual flow can often be scheduled in O(log N) steps, while a complete reconfiguration requires O(N log N) steps when implemented in a serial processor. An RSVP or Differentiated Services-like algorithm can be used to reserve bandwidth and buffer space in an IP-router, an ATM switch or MPLS switch during a connection setup phase, and the proposed method can be used to schedule traffic in each router or switch. Best-effort traffic can be scheduled using any existing dynamic scheduling algorithm to fill the remaining unused switch capacity within each Frame. The scheduling algorithm also supports multicast traffic.

Loading the Abstract Image...

First Claim