Methods and apparatus for fairly scheduling queued packets using a ram-based search engine
First Claim
1. 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.
3 Assignments
0 Petitions
Accused Products
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:
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.
-
Citations
20 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
wherein the calendar queue has two zones, and wherein a most significant bit of a time stamp value of a newly arriving packet indicates which of the zones of the calendar queue is to identify a flow queue of the newly arriving packet. -
4. The method of claim 2 wherein the time stamp values are represented by log2M+1 bits,
wherein the calendar queue has two zones, wherein a current zone bit is used to indicate which of the zones of the calendar queue is currently being searched, and wherein if the most significant bit of a time stamp is the same as the current zone bit, the time stamp is considered as non-overflow, and if the most significant bit of a time stamp differs from the current zone bit, the time stamp is considered as overflow. -
5. The method of claim 4 wherein if all validity bits in a zone of the calendar queue currently being searched become zero, and if there is at least one non-zero validity bit in the other zone of the calendar queue, then the current zone bit will be changed.
-
6. The method of claim 1 wherein the step of searching includes sub-steps of:
-
i) encoding the contents of the storage device at level l=0 to generate a bit string;
ii) for each lower level of the hierarchy, from second highest to lowest, A) reading contents of the addressable memory at the present level, as addressed by the bit string, B) encoding the contents of the addressable memory read out to generate a further bit string, and C) concatenating the bit string and the further bit string to form a bit string; and
iii) addressing the parameter queue using the bit string.
-
-
7. The method of claim 6 wherein the parameter queue is a calendar queue, wherein the information are packets, wherein the parameter values are time stamps, and wherein the extreme parameter value is a minimum time stamp.
-
8. The method of claim 1 further comprising a step of:
c) if there are no more information with the extreme parameter value, resetting the validity bit associated with the extreme parameter value, and bits depending therefrom.
-
9. The method of claim 2 further comprising a step of:
c) if there are no more packets with the lowest time stamp, resetting the validity bit associated with the time stamp, and bits depending therefrom.
-
10. The method of claim 8 wherein the step of resetting the validity bit associated with the parameter value, and bits depending therefrom included sub-steps of:
-
i) for all levels of the hierarchy except the highest hierarchical level l=0, and starting with a lowest hierarchical level l=L−
1,A) extracting bits from a binary coded parameter value to define extracted bits, B) addressing the addressable memory of the current hierarchical level with the extracted bits to read out validity-based bits, C) extracting further bits from the binary coded parameter value to define further extracted bits, D) decoding the further extracted bits to generate a word, E) inverting the word to generate an inverted word, F) logically ANDing, bit by bit, the inverted word and the validity-based bits to generate an AND result, and G) writing the AND result to the addressable memory of the current hierarchical level, as addressed by the extracted bits; and
ii) for the highest level of the hierarchy l=0 is zero, A) extracting bits from the binary coded parameter value to define final extracted bits, B) decoding the final extracted bits to define final decoded bits, C) inverting the final decoded bits to define a final inverted word, D) logically ANDing, bit by bit, the final inverted word with the bits stored in the storage device of the highest hierarchical level l=0 to generate a final AND result, and E) storing the final AND result in the storage device of the highest hierarchical level l=0.
-
-
11. The method of claim 2 further comprising a step of:
-
c) if a flow queue has a new head-of-line packet, i) storing a reference to the flow queue, and ii) updating a validity bit corresponding to the time stamp of the new head-of-line packet, and bits depending therefrom.
-
-
12. The method of claim 11 wherein the step of updating a validity bits and bits depending therefrom includes sub-steps of:
-
i) for the highest level of the hierarchy l=0, A) extracting bits of the binary coded time stamp to define first extracted bits, B) decoding the first extracted bits to generate a first decoded word, C) logically ORing, bit by bit, the contents of the storage device of the highest level of the hierarchy l=0 with the first decoded word to generate an OR result, D) storing the OR result in the storage device of the highest level of the hierarchy l=0, E) reading contents of the addressable memory of the next lower hierarchical level l=1, as addressed by the first extracted bits to define read bits, F) extracting further bits of the binary coded time stamp to define second extracted bits, G) decoding the second extracted bits to generate a second decoded word, and H) logically ORing, bit by bit, the contents of the addressable memory at the next lower level of the hierarchy l=1 with the additional second decoded word to generate another OR result, and I) writing the other OR result to the addressable memory at the next lower level of the hierarchy l=1; and
ii) for all of the lower levels of the hierarchy, from the second highest hierarchical level l=1 to the lowest hierarchical level l=L−
1,A) extracting bits from the binary coded time stamp to define first further extracted bits, B) extracting other bits from the binary coded time stamp to define second further extracted bits, C) reading the addressable memory of the next lower level as addressed by the first further extracted bits to generate a read result, D) decoding the second further extracted bits to generate a second further word, and E) logically ORing, bit by bit, the read result and the second further word and write result to the addressable memory of the next lower level as addressed by the first further extracted bits.
-
-
-
13. 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, andiv) 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 andif 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. - View Dependent Claims (14, 15, 16, 17)
-
-
18. 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) 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.
-
-
19. A network element having a plurality of output ports, each of the plurality of output ports comprising:
-
a) a plurality of queues for buffering packets, each of the packets having an associated time stamp;
b) a calendar queue for referencing the plurality of queues based on the time stamps of their respective head-of-line packets, and having a validity bit associated with each of the M time stamps for indicating whether a head-of-line packet at any of the plurality of queues has that time stamp; and
c) a search engine for searching for a minimum time stamp value by searching a hierarchical system including a storage device and at least one addressable memory device, wherein the search engine is adapted to encode the contents of the storage device to generate a first bit string, use the first bit string as at least a part of an address for reading a first of the at least one-addressable memory device to obtain read contents, encoding the read contents to generate a second bit string, and use the first and second bit strings as at least a part of an address for reading an addressable memory device of a next level of the hierarchical system. - View Dependent Claims (20)
-
Specification