Patent ID: 7103056
Filing Date: 2006-09-05
Classification: H04L

Abstract:
1. A method for use in a multi-stage switch including a number, k×n, of output ports, a plurality of central modules, and a plurality of input modules, each including k groups of n virtual output queues and outgoing links coupled with each of the plurality of central modules, for matching a non-empty virtual output queue of an input module with an outgoing link in the input module, the method comprising: a) sending, on behalf of each non-empty virtual output queue, a request to slave arbiters, each of the slave arbiters being associated with one of each of the outgoing links of the input module, and each of the slave arbiters being associated with the group of virtual output queues to which the non-empty virtual output queue belongs; b) sending, on behalf of each group of virtual output queues to which a non-empty virtual output queue belongs, a request to master arbiters, each of the master arbiters being associated with one of each of the outgoing links of the input module; c) selecting, with each of the master arbiters, a virtual output queue group having at least one non-empty virtual output queue, from among one or more virtual output queue groups that sent a request; d) selecting, with each of the slave arbiters, a non-empty virtual output queue, belonging to its associated group, from among one or more virtual output queues that sent a request; and e) selecting, with the arbiter of the each of the selected non-empty virtual output queues of each of the selected virtual output queue groups, an outgoing link from among the one or more candidate outgoing links, each of the one or more candidate outgoing links being associated with a master arbiter that selected the virtual output queue group and a slave arbiter that selected the non-empty virtual output queue.