Network traffic management system with floating point sorter

• US 7,362,765 B1
• Filed: 12/15/2003
• Issued: 04/22/2008
• Est. Priority Date: 12/15/2003
• Status: Expired due to Fees

• Current Assignee: Dinochip Incorporated
• Original Assignee: Dinochip Incorporated
• Inventors: Chen, Li-Sheng
• Primary Examiner(s): Shah; Chirag G.
• Application Number:
  US10/737,461
• Time in Patent Office: 1,590 Days
• Field of Search: None
• US Class Current: 370/395.4
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• 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 a network traffic management system with an integrated multidimensional floating point 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, represented in a floating point format, and the time stamp value is divided (412) into at least two portions, exponent and mantissa. The memory is organized as a pointer memory (505, 508, 513, and 520). An integrated multidimensional floating point 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) or class of service (CoS) 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, represented in a floating point format, 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,

wherein upon receiving a first packet of information on a first port, storing a first time stamp, represented in a floating point format, 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, represented in a floating point format, 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, represented in a floating point format, 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, represented in a floating point format, and a fourth connection value in a second entry of the second sorter.

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

3. 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.

4. 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.

5. The integrated circuit of claim 1 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.

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

7. 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, represented by a mantissa and exponent, entries in the first sorter block are sorted according to their time stamp value, and the number of entries N(1) is user-selectable; 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, represented by a mantissa and exponent, entries in the second sorter block are sorted according to their time stamp value, and the number of entries N(2) is user selectable,

wherein upon receiving a first packet of information on a first port, storing a first time stamp, represented by a mantissa and exponent, and a first connection value in a first entry of the first sorter block,

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

upon receiving a third packet of information on a second port storing a third time stamp, represented by a mantissa and exponent, and a third connection value in a first entry of the second sorter block, and

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

8. The integrated circuit of claim 7 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.

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

10. An integrated circuit comprising:

first control circuitry to implement a first sorter block comprising N(1) entries, wherein each entry comprises a connection value and a time stamp value, represented by a fraction multiplied by a power of a number base indicated by an exponent, entries in the first sorter block are sorted according to their time stamp value, and the number of entries N(1) is user-selectable; and

second control circuitry to implement a second sorter block comprising N(2) entries, wherein each entry comprises a connection value and a time stamp value, represented by a fraction multiplied by a power of a number base indicated by an exponent, entries in the second sorter block are sorted according to their time stamp value, and the number of entries N(2) is user-selectable,

wherein upon receiving a first packet of information on a first port, storing a first time stamp, represented by a fraction multiplied by a power of a number base indicated by an exponent, and a first connection value in a first entry of the first sorter block,

upon receiving a second packet of information on the first port, storing a second time stamp, represented by a fraction multiplied by a power of a number base indicated by an exponent, and a second connection value in a second entry of the first sorter block,

upon receiving a third packet of information on a second port, storing a third time stamp, represented by a fraction multiplied by a power of a number base indicated by an exponent, and a third connection value in a first entry of the second sorter block, and

upon receiving a fourth packet of information on the second port, storing a fourth time stamp, represented by a fraction multiplied by a power of a number base indicated by an exponent, and a fourth connection value in a second entry of the second sorter block.

11. The integrated circuit of claim 10 wherein the entries for the first and second sorter blocks are stored in another integrated circuit comprising random access memory.

12. The integrated circuit of claim 10 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.

13. An integrated circuit comprising:

control circuitry to implement 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, represented in a floating point format, 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,

wherein upon receiving a first packet of information on a first port, storing a first time stamp, represented in a floating point format, 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, represented in a floating point format, 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, represented in a floating point format, 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, represented in a floating point format, and a fourth connection value in a second entry of the second sorter.

14. The integrated circuit of claim 13 wherein M is user-selectable.

15. A method comprising:

receiving a first entry to be stored in a memory location, wherein the first entry has a time stamp value, represented in a floating point format, 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 the body of the first pointer memory structure based on the first time stamp portion; and

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

16. The method of claim 15 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.

17. The method of claim 16 further comprising:

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

18. A method comprising:

receiving an entry comprising a binary time stamp;

converting the binary time stamp into a time stamp, represented by a mantissa and an exponent, having a first time stamp portion and a second time stamp portion;

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

initializing the two or more 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 two or more memory positions, changing a first bit of the two or more bits of the head of the first pointer memory structure to a second state; and

when storing the second pointer address in a second memory position of the two or more memory positions, changing a second bit of the two or more bits of the head of the first pointer memory structure to the second state.

19. The method of claim 18 further comprising:

storing the second pointer address in a memory position based on the first time stamp portion.

20. The method of claim 19 wherein when the first time stamp portion is 00, store in the first memory position, and

when the first time stamp portion is “

01,”

store in the second memory position.

21. The method of claim 19 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 two or more bits and the body comprises two or more memory positions,

each bit in the bit map field representing one of the two or more memory positions, and the method further comprises:

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

when storing the third pointer address in a second memory position of the two or more memory positions of the second pointer memory structure, changing a second bit of the two or more bits of the head of the first pointer memory structure to the second’

state.

22. The method of claim 21 further comprising:

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

23. The method of claim 18 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.

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

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

26. The method of claim 18 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.

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

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