Patent ID: 7486683

Claim:
A method of selecting requests to be acknowledged in a shared-memory switch core comprising: receiving data packets at a plurality of ingress locations; assigning at least one data packet to a queue in a virtual output queue array having a plurality of queues, the queue having a column assignment based on an ingress location where the at least one data packet was received, and a row assignment based on an egress location assigned to output the queue; providing a collapsed virtual output queuing array (cVOQ) having a plurality of up/down counters mapped to the plurality of queues to store an indicator of a number of packets stored in each of the queues, the up/down counters arranged in predefined rows and columns; determining a number of queues assignable to each egress location; determining a number of queues received from each ingress location; calculating a degree of freedom in response to the determined number of queues assignable to each egress location and the determined number of queues received from each ingress location, the degree of freedom indicating a number of decisions required to move a queue into an egress location; ignoring any row of ingress location with a zero degree of freedom or no waiting packets in a queue selection analysis; ignoring any column of egress locations with a zero degree of freedom or no waiting packets, in the queue selection analysis; determining a maximum number of acknowledgements to be generated based on the ignored rows and ignored columns; performing the queue selection analysis utilizing the degree of freedom, said queue selection analysis further comprising: assigning a queue to an egress location if the queue has a degree of freedom of one or if a queue has a lower degree of freedom than all other unassigned queues; selecting a queue from a group of unassigned queues to be assigned to an open egress location not having an assigned queue, where the group of queues has queues with a same degree of freedom; assigning the selected queue to the open egress location; returning acknowledgements corresponding to the assignments; excluding from the queue selection analysis assigned queues; and repeating the selecting from a group if said maximum number is not reached.