Integrated multidimensional sorter

• US 7,284,111 B1
• Filed: 04/17/2002
• Issued: 10/16/2007
• Est. Priority Date: 04/17/2002
• Status: Expired due to Fees

• Current Assignee: Dinochip Incorporated
• Original Assignee: Dinochip Incorporated
• Inventors: Sae-Koe, Katie
• Primary Examiner(s): Portka; Gary
• Assistant Examiner(s): Doan; Duc T.
• Application Number:
  US10/125,686
• Time in Patent Office: 2,008 Days
• Field of Search: None
• US Class Current: 711/202
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers

Abstract

A technique to implement an integrated multidimensional sorter (306) is to store data such that it may be retrieved in a sorted fashion. Entries are stored (407) into a memory according to time stamp value, and the time stamp value is divided (412) into multiple portions. The memory is organized as a pointer memory (505, 508, 513, and 520). An integrated multidimensional sorter may be implemented using integrated circuit technology using one or more integrated circuits (306). These integrated circuits may be used in management of network traffic, and provides quality of service (QoS) control.

Claims

1. A method comprising:

receiving a first entry to be stored in a memory location, wherein the first entry has a time stamp value and a data value;

dividing the time stamp value of the first entry into two or more portions, a first time stamp portion and a second time stamp portion;

providing a first pointer memory structure, referred to by a first pointer address, having a head and a body, wherein the head comprises a bit map field and a pointer-to-body field;

providing a second pointer memory structure having a head and a body, wherein the head comprises a bit map field and a pointer-to-body field;

storing a second pointer address in a first position in the body of the first pointer memory structure based on the first time stamp portion; and

indicating the first position in the head of the first pointer, wherein an address stored in the pointer-to-body field added to a value in the bit map field of the first pointer will reference the first position, and the second pointer address points to the second pointer memory structure.

2. The method of claim 1 further comprising:

storing a third pointer address at a location in the body of the second pointer memory structure based on the second time stamp portion.

3. The method of claim 2 further comprising:

storing at a memory location referenced by the third pointer address the data value.

4. The method of claim 1 wherein the first position is indicated in the bit map field of the head of the first pointer.

5. The method of claim 1 wherein two or more pointer addresses are stored in the body of the first pointer structure, and the positions in the body of each of these two or more pointer addresses are indicated in the head of the first pointer.

6. The method of claim 1 further comprising:

storing a third pointer address in a second position in the body of the first pointer memory structure based on the first time stamp portion; and

indicating the second position in the head of the first pointer, wherein the second pointer address points to another pointer memory structure, different from the second pointer memory structure.

7. The method of claim 6 further comprising:

storing a fourth pointer address in a third position in the body of the first pointer memory structure based on the first time stamp portion; and

indicating the third position in the head of the first pointer, wherein the second pointer address points to another pointer memory structure, different from the second and third pointer memory structures.

8. The method of claim 1 wherein the pointer-to-body field of the first pointer memory structure comprises a pointer address to the body of the first pointer memory structure.

9. The method of claim 1 wherein the body of the first pointer memory structure comprises at least two positions, each to store a pointer address.

10. The method of claim 1 wherein the body of the first pointer memory structure comprises at least four positions, each to store a pointer address.

11. The method of claim 1 wherein for the first pointer memory structure, a number of bits n in the bit map field is less than or equal to a maximum number of positions in the body, and n is at least 2.

12. The method of claim 1 wherein the indicating the first position in the head of the first pointer occurs after the storing a second pointer address in a first position in the body of the first pointer memory structure.

13. The method of claim 1 wherein each position in the body of the first pointer memory structure is assigned a unique binary value, the body of the first pointer memory structure has two or more positions, and the first position is assigned a unique binary value that matches bits of the first time stamp portion.

14. The method of claim 1 wherein the first time stamp portion has i bits and the body of the first pointer memory structure has at least 2ⁱ positions.

15. The method of claim 14 wherein second time stamp portion has j bits, j is less than i, and the second pointer memory structure has at least 2^j positions, but less than 2ⁱ positions.

16. The method of claim 14 wherein the bit map field of the first pointer structure has 2ⁱ bits.

17. The method of claim 14 wherein the bit map field of the first pointer structure has 2ⁱ or fewer bits.

18. The method of claim 1 wherein each successive position in the body of the first pointer memory structure is assigned a successive binary value.

19. The method of claim 1 wherein each bit of the first time stamp portion of the time stamp value is a more significant bit than each bit of the second time stamp portion.

20. A method comprising:

receiving an entry comprising a binary time stamp having at least four bits and a data value;

dividing the binary time stamp into a first time stamp portion having at least two bits and second time stamp portion having at least two bits;

providing a first pointer memory structure, referenced using a first pointer address and having a head and a body, wherein the head comprises a bit map field comprising four bits and the body comprises four memory positions, each bit in the bit map field representing one of the four memory positions;

initializing the four bits of the head of the first pointer memory structure to a first state;

when storing a second pointer address in a first memory position of the four memory positions, changing a first bit of the four bits of the head of the first pointer memory structure to a second state;

when storing the second pointer address in a second memory position of the four memory positions, changing a second bit of the four bits of the head of the first pointer memory structure to the second state;

when storing the second pointer address in a third memory position of the four memory positions, changing a third bit of the four bits of the head of the first pointer memory structure to the second state; and

when storing the second pointer address in a fourth memory position of the four memory positions, changing a fourth bit of the four bits of the head of the first pointer memory structure to the second state,

wherein an address stored in a pointer-to-body field in the first point memory structure added to a value in the bit map field will reference a memory position where the second pointer address is stored.

21. The method of claim 20 further comprising:

storing the second pointer address in the first, second, third, or fourth memory position based on the first time stamp portion.

22. The method of claim 21 wherein when the first time stamp portion is 00, store in the first memory position,

when the first time stamp portion is “

01,”

store in the second memory position,

when the first time stamp portion is “

10,”

store in the third memory position, and

when the first time stamp portion is “

11,”

store in the fourth memory position.

23. The method of claim 21 wherein the second pointer address points to a second pointer memory structure, having a head and a body, wherein the head comprises a bit map field comprising four bits and the body comprises four memory positions, each bit in the bit map field representing one of the four memory positions, and the method further comprises:

when storing a third pointer address in a first memory position of the four memory positions of the second pointer memory structure, changing a first bit of the four bits of the head of the second pointer memory structure to a second state;

when storing the third pointer address in a second memory position of the four memory positions of the second pointer memory structure, changing a second bit of the four bits of the head of the first pointer memory structure to the second state;

when storing the third pointer address in a third memory position of the four memory positions of the second pointer memory structure, changing a third bit of the four bits of the head of the first pointer memory structure to the second state; and

when storing the third pointer address in a fourth memory position of the four memory positions of the second pointer memory structure, changing a fourth bit of the four bits of the head of the first pointer memory structure to the second state.

24. The method of claim 23 further comprising:

storing the data value at a memory location referenced by the third pointer address.

25. The method of claim 20 further comprising:

checking each bit in the bit map field of the first pointer memory structure in sequence from a most significant bit to a least significant bit until a first output bit is found to be in the second state; and

retrieving a second pointer address value associated with the first output bit.

26. The method of claim 25 wherein the stored data value associated with the first output bit has a minimum binary time stamp value.

27. The method of claim 25 wherein the stored data value associated with the first output bit has a maximum binary time stamp value.

28. The method of claim 20 further comprising:

checking each bit in the bit map field of the first pointer memory structure in sequence from a least significant bit to a most significant bit until a first output bit is found to be in the second state; and

retrieving a stored data value associated with the first output bit.

29. The method of claim 28 wherein the stored data value associated with the first output bit has a minimum binary time stamp value.

30. The method of claim 28 wherein the stored data value associated with the first output bit has a maximum binary time stamp value.