Patent ID: 6940851

Claim:
For use with a multi-stage switch having a plurality of central modules, each having outgoing links, and a plurality of input modules, each including a first number of input ports, each of the input ports having a second number of 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 or packets stored in the virtual output queues, the method comprising: a) for each of the virtual output queues, maintaining a first indicator for indicating whether the virtual output queue is storing a cell awaiting dispatch arbitration; and b) 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 via an outgoing link of the input module, wherein the matching operation includes: i) for an input module, matching a non-empty virtual output queue with an outgoing link of the input module, and ii) matching the outgoing link of the input module with an outgoing link of the associated central module, 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.