Patent ID: 6961342

Claim:
In a switch having N in input ports applied to K in input shared blocks, a central switching fabric, and N out output ports provided from K out output shared blocks, a method for scheduling packets queued at the input shared blocks for application to the output ports, the method comprising steps of: a) for each of the input shared blocks, providing a request token associated with one of the output shared blocks, each of the request tokens including an indication based on a number of requested links for the output shared block with which it is associated; b) for each of the input shared blocks, providing a release token associated with one of the output shared blocks, each of the release tokens including an indication based on a number of released links for the output shared block with which it is associated; c) for each of one or more reservation time slots within a cell time slot, i) accepting, by an input shared block, a request token from another input shared block, ii) determining whether a virtual output queue of the input shared block associated with the output shared block with which the request token is associated, is heavily occupied, iii) if it is determined that the virtual output queue of the input shared block associated with the output shared block with which the request token is associated is heavily occupied, then A) requesting at least one extra link to the output shared block associated with the accepted request token, iv) determining whether the virtual output queue of the input shared block associated with the output shared block with which the request token is associated, is lightly occupied, v) if it is determined that the virtual output queue of the input shared block associated with the output shared block with which the request token is associated is lightly occupied, then A) releasing at least one link to the output shared block associated with the accepted request token if it is indicated that a number of requested links for the output shared block is greater than zero, vi) if it is determined that the virtual output queue of the input shared block associated with the output shared block with which the request token is associated is not lightly occupied, then A) releasing at least one link to the output shared block associated with the accepted request token if the input shared block reserved more than a predetermined number of links and if it is indicated that a number of requested links for the output shared block is greater than zero, vii) accepting, by the input shared block, a release token from another input shared block; viii) determining whether or not the input shared block can take a link to the output shared block associated with the release token, ix) if it is determined that the input shared block can take a link to the output shared block associated with the release token, then taking a link from the release token.