US 6,389,031 B1 · Methods and apparatus for fairly scheduling queued packets using a ram-based search engine

Abstract

A hierarchical searching technique is used to find the first memory location of a calendar queue with a validity bit of “1” (that is, the lowest time stamp). The bit string at any level l (l≠0) can be stored in a RAM of size glMl−1. The string at the highest level in the hierarchy (l=0) can be stored in an M0 bit register. The number of address bits need to address any bit at a level l may be expressed as: m l = log 2 ⁢ M l = m l - 1 + log 2 ⁢ g l = ∑ i = 0 l ⁢ log 2 ⁢ g i , ⁢ where ⁢ ⁢ g 0 = M 0 . ( 11 ) Equation (11) illustrates a method of the present invention for addressing in a hierarchical search. That is, m0 most significant bits of the time stamp address should be used at level 0. Then, at level l, the complete address used at upper level (l−1) will be used to locate the proper gl bit word in its glMl−1 memory. Another log2gl bits following the previous ml−1 bits is extracted from the time stamp address and used to locate the proper bit in the gl bit word that has just been identified. In this way, the search time depends on the number L of levels. Thus, a scheduler based on the present invention can schedule large numbers of flows to be placed on a high speed data link (i.e., with a small time slot). A two (2) dimensional shaper uses a similar hierarchical searching and addressing technique. Finally, any overflow of binary encoded time stamp and system potential values is tracked so that time stamp aging does not cause problems.

Claims20

Dependent claims

In a system having a parameter queue for referencing stored information based on their respective parameter values, and having a validity bit associated with each of M parameter values for indicating whether any of the stored information have that parameter value, a method for selecting, from candidate information, an information having an extreme parameter value, the method comprising steps of:

a) generating a hierarchy of L levels from the validity bits, the hierarchy generated via sub-steps of,
i) grouping the M validity bits into groups of gL−1 bits,
ii) logically ORing the gL−1 validity bits in each of the groups,
iii) defining bits of a next level by concatenating the OR results thereby generating M/gL−1 bits,
iv) storing the bits of the next level in an addressable memory, and
v) at each of the remaining levels l, except a highest level l=0, repeatedly
A) grouping Ml bits into groups of gl bits,
B) logically ORing the gl bits in each of the groups,
C) concatenating the OR results thereby generating Ml/gl bits which define bits of a next level, and
D) if the next level is not the highest level l≠0, storing the bits of the next level in a next addressable memory and if the next level is the highest level l=0, storing the bits of the next level in a storage device;
and
b) searching for an information having an extreme parameter value.

9 more elements

In a system having a parameter queue for addressing stored information based on their respective parameter values, and having a validity bit associated with each of M parameter values for indicating whether any of the stored information have that parameter value, an apparatus for searching for an extreme parameter value, the apparatus comprising:

a) at least one addressable memory;
b) a storage device;
c) at least two encoders;
and
d) means for concatenating bit strings,
wherein the at least one addressable memory and the storage device define a hierarchy having L levels, in which,
i) the M validity bits are grouped into groups of gL−1 bits,
ii) the gL−1 validity bits of each of the groups are logically ORed,
iii) results of the logical ORing are concatenated to define M/gL−1 bits of a next level which are stored in one of the at least one addressable memory, and
iv) at each of the remaining levels l, except the highest level l=0,
A) Ml bits are grouped into groups of gl bits,
B) the gl bits in each of the groups are logically ORed,
C) the OR results are concatenated thereby generating Ml/gl bits which define bits of a next level, and
D) if the next level is not the highest level l≠0, the bits of the next level are stored in a next one of the at least one addressable memory and
if the next level is the highest level l=0, the bits of the next level are stored in the storage device,
wherein each of the at least two encoders is associated with one of the storage device and each of the at least one addressable memory and is adapted to encode contents of the associated one of the storage device and each of the at least one addressable memory, and
wherein the means for concatenating bit strings concatenates outputs of the at least two encoders to form addresses to the at least one addressable memory.

14 more elements

a) a storage device;
b) at least one addressable memory;
c) a first decoder for decoding at least some bits of a binary coded parameter value;
d) a first inverter coupled with an output of the first decoder;
e) a first AND gate having a first input coupled with an output of the first inverter and a second input coupled with an output of the storage device;
f) a first OR gate having a first input coupled with the output of the first decoder and a second input couple with the output of the storage device;
g) a first switch having a first input coupled with an output of the first AND gate, a second input coupled with an output of the first OR gate, and an output coupled with an input of the storage device;
h) a first encoder having an input coupled with the output of the storage device;
i) a second switch having a first input coupled with an output of the first encoder, and second input coupled with at least some bits of the binary encoded parameter value;
j) first shift register having an input coupled with an output of the second switch and having an output coupled with address lines of the at least one addressable memory;
k) a second decoder for decoding at least some bits of a binary coded parameter value;
l) a second inverter coupled with an output of the second decoder;
m) a second AND gate having a first input coupled with an output of the second inverter and a second input coupled with a data output of the at least one addressable memory;
n) a second OR gate having a first input coupled with the output of the second decoder and a second input coupled with a data output of the at least one addressable memory;
o) a third switch having a first input coupled with an output of the second AND gate, a second input coupled with an output of the second OR gate, and an output coupled with a data input of the at least one addressable memory;
and
p) a controller for generating read/write signals for the at least one addressable memory.

14 more elements

Dependencies are inferred from the claim text.

Methods and apparatus for fairly scheduling queued packets using a ram-based search engine

Life of this patent

Methods and apparatus for fairly scheduling queued packets using a ram-based search engine

Life of this patent

Abstract

Claims20