Crossbar switch and recursive scheduling

A crossbar switch, comprising

• n input ports, each feeding an associated group of m virtual output queues;
• an n×m switching matrix arranged in n rows and m columns;
• 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;
• n row queues, one in each row of said n×m matrix;
• n row multiplexers, each 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 one in communication with each of said n row queues,
• m column queues, one in each column of said n×matrix;
• m column multiplexers each in communication with one of said m column queues,
• said n row de-multiplexers and said m column multiplexers in communication with each other, and operating in synchronization to move queued packets from said n row queues to said m column queues, as dictated by routing information in each queued packet;
• m output ports, each in communication with a respective one of said m column queues to output packets therefrom.

A method of scheduling n traffic flows through a multiplexer in F time slots, comprising:

• a. specifying a first traffic rate vector with n elements for the n traffic flows, wherein each element of the traffic rate vector specifies a number of requested packet transmission opportunities for each of said n traffic flows in a scheduling frame of F time slots;
• b. using the first traffic vector as an input rate vector to a partitioning routine and F as the number of time slots of a defined scheduling frame length;
• c. performing said partitioning routine using the input rate vector, said performing comprising decomposing said input vector relatively fairly into K substantially-similar output traffic rate vectors, and wherein the sum of the K output rate vector equals the input rate vector;
• e. scheduling each of the K output rate vectors, to return a transmission schedule of length 1/K of said defined scheduling frame length;
• f. concatenating the K schedules computed for the K output rate vectors, to achieve a schedule for the number of time sots of the defined scheduling frame length.