Multidimensional network sorter integrated circuit

• US 8,447,950 B1
• Filed: 11/02/2010
• Issued: 05/21/2013
• 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): DOAN, DUC T
• Application Number:
  US12/917,954
• Time in Patent Office: 931 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. An integrated circuit comprising:

M sorter blocks, wherein each sorter block has a user-selectable number of entries of one or more entries, each entry comprises a time stamp value and a connection value, there are a total of N entries for all the M sorter blocks, and M is an integer 2 or greater,

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

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 a first pointer memory structure to a second state from a first 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, and

the pointer-to-body field stores a pointer pointing to one of the four memory location positions.

2. The integrated circuit of claim 1 comprising:

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.

3. The integrated circuit of claim 2 wherein when a second sorter block is configured to have Z entries, the sorter blocks, not including the first and second sorter blocks, have at most (N-Y-Z) entries.

4. The integrated circuit of claim 3 wherein the first and second entries are sorted so an entry with an earlier time stamp is placed before the entry with a later time stamp.

5. The integrated circuit of claim 1 comprising:

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 from the first state.

6. The integrated circuit of claim 1 wherein M is user-selectable.

7. The integrated circuit of claim 1 wherein when a first sorter block is configured to have Y entries, there are M-1 remaining sorter blocks which have at most a total of (N-Y) entries.

8. The integrated circuit of claim 7 wherein the first and second entries placed in the first sorter are sorted according to the first and second time stamps, and the third and fourth entries placed in the second sorter are sorted according to the third and fourth time stamps.

9. The integrated circuit of claim 1 wherein upon receiving a first packet of information on a first port, storing a first time stamp and a first connection value in a first entry of a first sorter,

upon receiving a second packet of information on the first port, storing a second time stamp and a second connection value in a second entry of the first sorter,

upon receiving a third packet of information on a second port, storing a third time stamp and a third connection value in a first entry of a second sorter, and

upon receiving a fourth packet of information on the second port, storing a fourth time stamp and a fourth connection value in a second entry of the second sorter.

10. The integrated circuit of claim 1 comprising:

after storing the second memory address in one of the four memory positions in the first pointer memory structure, storing a third pointer address in one of the four memory positions not occupied by the second memory address;

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

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

11. The integrated circuit of claim 1 wherein a first time stamp value is divided into at least a first time stamp portion and a second time stamp portion, and the second pointer address is stored in one of the four memory positions of the first pointer memory structure based on the first time stamp portion.

12. The integrated circuit of claim 11 wherein a third pointer address is stored in one of four memory positions of a second pointer memory structure based on the second time stamp portion.

13. An integrated circuit comprising:

a first sorter block portion of the integrated circuit comprising N(1) entries, wherein each entry comprises a connection value and a time stamp value, entries in the first sorter block are sorted according to their time stamp value; and

a second sorter block portion of the integrated circuit comprising N(2) entries, wherein each entry comprises a connection value and a time stamp value, entries in the second sorter block are sorted according to their time stamp value,

wherein the second sorter block comprises 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, the head comprises a pointer-to-body field, each bit in the bit map field representing one of the n memory positions, wherein n is an integer,

upon receiving a first time stamp value for a first entry for the second sorter block, dividing the first time stamp value into at least a first portion and a second portion, wherein the first portion has n bits and the second portion has m bits, and m is an integer,

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 first time stamp value,

storing in the pointer-to-body field a pointer pointing to one of the n memory location positions.

14. The integrated circuit of claim 13 wherein each entry in the first sorter block is placed at a location based on its time stamp value, and each entry in the second sorter block is placed at a location based on its time stamp value.

15. The integrated circuit of claim 13 wherein the entries are stored in a random access memory portion of the integrated circuit.

16. The integrated circuit of claim 13 comprising:

altering at least one bit in the bit map field of the head of the first pointer memory structure.

17. A circuit comprising:

logic circuitry to receive an input entry comprising a binary time stamp having at least four bits and a data value;

logic circuitry to allow splitting of 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;

logic circuitry to implement 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, the head comprises a first pointer-to-body field and a second pointer-to-body field, each bit in the bit map field representing one of the n memory positions;

logic circuitry to allow storing of 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;

logic circuitry to allow altering of at least one 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;

logic circuitry to allow storing in the first pointer-to-body field a pointer pointing to one of the n memory location positions; and

logic circuitry to allow storing in the second pointer-to-body field a pointer pointing to one of the n memory location positions.

18. The circuit of claim 17 wherein a plurality of memory addresses are between the head and body.

19. The circuit of claim 17 wherein the logic circuitry comprises gates.