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

• US 6,389,031 B1
• Filed: 11/04/1998
• Issued: 05/14/2002
• Est. Priority Date: 11/05/1997
• Status: Expired due to Fees

• Current Assignee: Polytechnic University (New York University)
• Original Assignee: Polytechnic University (New York University)
• Inventors: Chao, Hung-Hsiang Jonathan, Jenq, Yau-Ren
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): Harper, Kevin C.
• Application Number:
  US09/185,754
• Time in Patent Office: 1,287 Days
• Field of Search: 370/412, 370/395, 370/229, 370/235, 370/389, 370/351, 713/502
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 2012/5683 for avoiding head of line blocking
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/568 Calendar queues or timing rings
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/20 Support for services
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/503 Policing
• CPC Class Codes: H04L 49/508 Head of Line Blocking Avoidance
• CPC Class Codes: H04L 49/90 : Buffering arrangements
• CPC Class Codes: H04L 49/9031 : Wraparound memory, e.g. overrun or underrun detection

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 g_lM_l−1. The string at the highest level in the hierarchy (l=0) can be stored in an M₀ bit register. The number of address bits need to address any bit at a level l may be expressed as: $\begin{array}{cc}{m}_l={\log }_2M_l=m_{l-1}+{\log }_2g_l=\sum _{i=0}^l{\log }_2g_i,\mathrm{where}g_0=M_0.& \left(11\right)\end{array}$

Equation (11) illustrates a method of the present invention for addressing in a hierarchical search. That is, m₀ 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 g_l bit word in its g_lM_l−1 memory. Another log₂g_l bits following the previous m_l−1 bits is extracted from the time stamp address and used to locate the proper bit in the g_l 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.

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 g<sub>L−

1</sub> bits,

ii) logically ORing the g<sub>L−

1</sub> validity bits in each of the groups,

iii) defining bits of a next level by concatenating the OR results thereby generating M/g<sub>L−

1</sub> 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 M_l bits into groups of g_l bits,

B) logically ORing the g_l bits in each of the groups,

C) concatenating the OR results thereby generating M_l/g_l 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.

2. The method of claim 1 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.

3. The method of claim 2 herein the time stamp values are represented by log₂M+1 bits,

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 log₂M+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 g<sub>L−

1</sub> bits,

ii) the g<sub>L−

1</sub> validity bits of each of the groups are logically ORed,

iii) results of the logical ORing are concatenated to define M/g<sub>L−

1</sub> 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) M_l bits are grouped into groups of g_l bits,

B) the g_l bits in each of the groups are logically ORed,

C) the OR results are concatenated thereby generating M_l/g_l 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. The apparatus of claim 13 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.

15. The apparatus of claim 14 further comprising at least two decoders adapted to update validity-based bits of the at least one addressable memory and the storage device when a flow queue has a new head-of-line packet.

16. The apparatus of claim 13 further comprising at least two decoders adapted to update validity-based bits of the at least one addressable memory and the storage device when new information is stored.

17. The apparatus of claim 14 wherein the packets are head-of-line packets of flow queues, and further comprising at least two decoders adapted to update validity-based bits of the at least one addressable memory and the storage device when a session queue becomes empty.

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.

20. The network element of claim 19 wherein each of the plurality of queues is associated with one of a flow and a session.