Patent ID: 7139280

Claim:
A method for allocating space among a plurality of queues in a buffer, comprising: sorting the plurality of queues of the buffer according to size, thereby to establish a sorted order of the queues; selecting at least one group of the queues comprising a given number of the queues in accordance with the sorted order; allocating a portion of the space in the buffer to the at least one group, responsive to the number of the queues in the at least one group; and accepting a data packet into one of the queues in the at least one group responsive to whether the data packet will cause the space occupied in the buffer by the queues in the group to exceed the allocated portion of the space; wherein selecting the at least one group comprises selecting for inclusion in the at least one group the queues that are largest among the plurality of queues; wherein allocating the portion of the space comprises setting a size of the space proportional to a sum of a harmonic series; wherein setting the size of the space comprises establishing a total maximum buffer size B k for the k largest output queues, wherein B k is substantially given by B k = M ( ln ⁢ ⁢ N + 1 ) ⁢ ∑ i = 1 k ⁢ 1 i wherein M is the total buffer space available to all queues, N is the number of output queues, and i is an integer index.