Integrated multidimensional sorter

• US 7,594,092 B1
• Filed: 07/17/2007
• Issued: 09/22/2009
• 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): Sough; Hyung S
• Assistant Examiner(s): Doan; Duc T
• Application Number:
  US11/778,826
• Time in Patent Office: 798 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 is to store data such that it may be retrieved in a sorted fashion. Entries are stored into a memory according to time stamp value, and the time stamp value is divided into multiple portions. The memory is organized as a pointer memory. An integrated multidimensional sorter may be implemented using integrated circuit technology using one or more integrated circuits. These integrated circuits may be used in management of network traffic, and provides quality of service (QoS) control.

Claims

1. A method comprising:

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

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 added to a value in the bit map field will reference a memory position where the second pointer address is stored.

2. The method of claim 1 wherein the address is stored in a pointer-to-body field in the head of the first pointer memory structure.

3. The method of claim 1 further comprising:

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; and

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

4. The method of claim 3 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.

5. The method of claim 3 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 represents 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 second 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 second 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 second pointer memory structure to the second state.

6. The method of claim 5 wherein the third pointer address points to a third 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 represents one of the four memory positions, and the method further comprises:

when storing a fourth 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 third 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 third 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 third 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 third pointer memory structure to the second state.

7. The method of claim 5 wherein the third pointer address points to the data of the value of the entry.

8. The method of claim 1 wherein

when the first bit is in the second state, the value in the bit map field is “

00,”

when the second bit is in the second state, the value in the bit map field is “

01,”

when the third bit is in the second state, the value in the bit map field is “

01,”

when the fourth bit is in the second state, the value in the bit map field is “

11.”

9. 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 at least a first portion and a second portion, wherein the first portion has n bits and the second portion has m bits, where n and m are integers;

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 n bits and the body comprises n memory positions, each bit in the bit map field representing one of the n memory positions;

storing a second pointer address at a memory position in the body of the first pointer memory structure corresponding to the first portion of the binary time stamp; and

changing a bit in the bit map field of the head of the first pointer memory structure corresponding to the memory position in the body of the first pointer memory structure corresponding to the first portion of the binary time stamp.

10. The method of claim 9 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 m bits and the body comprises m memory positions, each bit in the bit map field represents one of the m memory positions, and the method comprises:

storing a third pointer address at a memory position in the body of the second pointer memory structure corresponding to the second portion of the binary time stamp; and

changing a bit in the bit map field of the head of the second pointer memory structure corresponding to the memory position in the body of the second pointer corresponding to the second portion of the binary time stamp.

11. The method of claim 9 comprising:

searching for the entry by scanning the head of the first pointer memory structure.

12. The method of claim 9 wherein the first pointer memory structure comprises n+1 words, the head is stored in one word of the first pointer memory structure having at least n bits, and each memory position of body is stored in one of the remaining n words of the first pointer memory structure not occupied by the head.

13. The method of claim 9 comprising:

storing in a pointer-to-body field, an address to the body of the first pointer memory structure, wherein the head comprises the pointer-to-body field.

14. The method of claim 13 wherein the address is to a first address of the body of the first pointer memory structure.

15. The method of claim 13 wherein the address is to the memory position in the body where the second pointer address is stored.

16. The method of claim 9 comprising:

storing in a pointer to body field, an address to the body of the first pointer memory structure, wherein the head comprises the pointer to body field; and

storing the second pointer address in the pointer-to-first-pointer field.

17. The method of claim 9 wherein n and m are different.