Patent ID: 7724760

Claim:
A method for selecting an ingress queue for service across a shared link, comprising: (A) maintaining information regarding a queue metric for each ingress queue from a group of ingress queues within a plurality of ingresses; (B) calculating a guaranteed rate for each ingress queue based on the information and a guaranteed bandwidth amount; (C) using the guaranteed rate to calculate a credit value for each ingress queue; (D) classifying each ingress queue into a corresponding one of a number of tiers, each tier having a priority, wherein the credit values are used to classify at least some of the queues into respective tiers, each tier being assigned a different priority, and wherein classifying each queue from the group of queues includes: (D)(i) ascertaining a size of a first-out packet in each queue from the group of queues; and (D)(ii) if the size of the first-out packet in any queue from the group of queues is too large for transmission across the shared link in a single timeslot, classifying its queue into a tier having a highest priority; (E) matching each ingress queue to one or more available egresses among a plurality of egresses by matching ingress queues classified within tiers having higher priorities before matching ingress queues classified within tiers having lower priorities such that a maximal matching between the group of ingress queues and the one or more available egresses is achieved for each tier, the maximal matching being achieved when a number of matches between ingress queues and egresses is maximized; and (F) selecting the ingress queue for service across the shared link after matching each ingress queue to the one or more available egresses.