Crossbar switch and recursive scheduling

Abstract

A crossbar switch has N input ports, M output ports, and a switching matrix with N×M crosspoints. In an embodiment, each crosspoint contains an internal queue (XQ), which can store one or more packets to be routed. Traffic rates to be realized between all Input/Output (IO) pairs of the switch are specified in an N×M traffic rate matrix, where each element equals a number of requested cell transmission opportunities between each 10 pair within a scheduling frame of F time-slots. An efficient algorithm for scheduling N traffic flows with traffic rates based upon a recursive and fair decomposition of a traffic rate vector with N elements, is proposed. To reduce memory requirements a shared row queue (SRQ) may be embedded in each row of the switching matrix, allowing the size of all the XQs to be reduced. To further reduce memory requirements, a shared column queue may be used in place of the XQs. The proposed buffered crossbar switches with shared row and column queues, in conjunction with the row scheduling algorithm and the DCS column scheduling algorithm, can achieve high throughput with reduced buffer and VLSI area requirements, while providing probabilistic guarantees on rate, delay and jitter for scheduled traffic flows.

What is claimed is: 
     
         1 . A crossbar switch for switching packets from inputs to outputs, said crossbar switch comprising
 n input ports, each feeding an associated group of m virtual output queues;   an n×m switching matrix, having n×m cross points arranged in n rows and m columns, and a buffer at each of said n×m cross points;   n row queues, each one interposed between one of said groups of m virtual output queues, and cross-points in a respective one of said n rows,   at least one de-multiplexer to feed a packet at each of said n input ports into one virtual output queue of its associated group of m virtual output queues, as dictated by routing information in said packet,   at least one multiplexer to empty m virtual output queues in a group in accordance with a schedule, into an interposed one of said n row queues,   n row de-multiplexers each in communication with one of said n row queues, to feed queued packets to cross point buffers at a row corresponding to a row queue, and in a column dictated by routing information in said packets; and   m output ports, each in communication with a respective column of said of n×m cross points to receive data from buffers in said column.