Patent ID: RE43466

Claim:
For use with a multi-stage switch having a first number, k×n, of output ports, a plurality of central modules, each having outgoing links, and a second number of input modules, each including k groups of n virtual output queues and outgoing links coupled with each of the plurality of central modules, and a third number of sub-schedulers, each of the third number of sub-schedulers being able to arbitrate matching an input port with an outgoing link of one of the plurality of central modules via an outgoing link of the input module including the input port, a method for scheduling the dispatch of cells stored in the virtual output queues, the method comprising for each of the sub-schedulers, performing a matching operation, if it has been reserved, to match a cell buffered at a virtual output queue with an outgoing link of one of the plurality of central modules, wherein the matching operation includes comprises : a) matching a non-empty virtual output queue of an input module with an outgoing link in the input module, wherein the outgoing link has an associated master arbitration operation for selecting one of the k groups of n virtual output queues; and b) matching the outgoing link with an outgoing link of one of the plurality of central modules, wherein each of the sub-schedulers requires more than one cell time slot to generate a match from its matching operation, and wherein the sub-schedulers can collectively generate a match result in each cell time slot.