Maintaining packet order using hash-based linked-list queues

• US 8,611,216 B2
• Filed: 09/30/2011
• Issued: 12/17/2013
• Est. Priority Date: 06/14/2002
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Ferguson, Dennis C., Lacroute, Philippe, Chen, Chi-Chung, Cheung, Gerald, Chuang, Tatao, Patel, Pankaj, Ananthakrishnan, Viswesh
• Primary Examiner(s): Jagannathan, Melanie
• Application Number:
  US13/250,765
• Publication Number:
  US 20120027019A1
• Time in Patent Office: 809 Days
• Field of Search: None
• US Class Current: 370/230
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/3036 Shared queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element

Abstract

Ordering logic ensures that data items being processed by a number of parallel processing units are unloaded from the processing units in the original per-flow order that the data items were loaded into the parallel processing units. The ordering logic includes a pointer memory, a tail vector, and a head vector. Through these three elements, the ordering logic keeps track of a number of “virtual queues” corresponding to the data flows. A round robin arbiter unloads data items from the processing units only when a data item is at the head of its virtual queue.

Claims

1. A device comprising:

a first memory to store a plurality of groups of entries,

each group of entries, of the plurality of groups of entries, corresponding to a different one of a plurality of data flows, and

each group of entries, of the plurality of groups of entries, identifying an order of data units of a corresponding one of the plurality of data flows;

a second memory to store information identifying a head data unit of each of the plurality of data flows;

a third memory to store data units of a particular data flow of the plurality of data flows; and

an output unit to transmit the data units, of the particular data flow, based on;

a group of entries, of the plurality of groups of entries, corresponding to the particular data flow, and

the information, stored in the second memory, associated with the particular data flow,

a particular address of a first entry, of the group of entries corresponding to the particular data flow, corresponding to a processing unit that processes information related to a particular data unit of the data units of the particular data flow, and

the first entry identifying another processing unit that processes information related to another data unit of the data units of the particular data flow,

the particular data unit preceding the other data unit in the particular data flow.

2. The device of claim 1, further comprising:

a component to generate a value for each data unit of the plurality of data flows,

where the values, generated for the data units of the particular data flow, identify the particular data flow, and

where entries, of the group of entries corresponding to the particular data flow,

are stored based on the values generated for the data units of the particular data flow.

3. The device of claim 2, where the component is to generate the value for a data unit, of the data units of the plurality of data flows, based on at least one of:

a protocol type associated with the data unit,

an incoming interface associated with the data unit,

an Internet Protocol (IP) source address associated with the data unit,

an IP destination address associated with the data unit, or

a source port associated with the data unit.

4. The device of claim 2, where one or more entries, of the group of entries corresponding to the particular data flow, identify one or more other entries of the group of entries corresponding to the particular data flow.

5. The device of claim 1, where the particular data unit corresponds to a first data unit of the particular data flow,

where the other data unit corresponds to a second data unit of the particular data flow, and

where the second memory stores information identifying the particular data unit.

6. The device of claim 1, further comprising:

a fourth memory to store information identifying a last data unit of each of the plurality of data flows,

where the output unit, when transmitting the data units of the particular data flow, transmits the data units further based on the information, stored in the fourth memory, identifying the last data unit of the particular data flow.

7. A method comprising:

storing, by a device and in a first memory, a plurality of groups of entries,

each group of entries, of the plurality of groups of entries, corresponding to a different one of a plurality of data flows, and

each group of entries, of the plurality of groups of entries, identifying an order of data units of a corresponding one of the plurality of data flows;

storing, by the device and in a second memory, information identifying a head data unit of each of the plurality of data flows; and

transmitting, by the device, data units of a particular data flow of the plurality of data flows,

the data units, of the particular data flow, being transmitted based on;

a group of entries, of the plurality of groups of entries, corresponding to the particular data flow, and

the information, stored in the second memory, identifying the head data unit of the particular data flow,

a particular address of a first entry, of the group of entries corresponding to the particular data flow, corresponding to a processing unit that processes information related to a particular data unit of the data units of the particular data flow, and

the first entry identifying a processing unit that processes information related to another data unit of the data units of the particular data flow,

 

the particular data unit preceding the other data unit in the particular data flow.

8. The method of claim 7, further comprising:

storing, in a third memory, information identifying a last data unit of the particular data flow,

where transmitting the data units of the particular data flow includes;

transmitting the data units of the particular data flow further based on the information identifying the last data unit.

9. The method of claim 8, further comprising:

generating a value for a data unit of the data units of the particular data flow;

determining, based on the generated value, whether the data unit is the last data unit of the particular data flow,

where storing the information identifying the last data unit includes;

storing, in the third memory, information identifying the data unit when the data unit is the last data unit.

10. The method of claim 7, further comprising:

generating a value for each of the data units of the particular data flow,

where each of the values is generated based on a corresponding one of the data units of the particular data flow, and

where entries, of the group of entries corresponding to the particular data flow, are stored in the first memory based on the values generated for the data units of the particular data flow.

11. The method of claim 10, where generating the value for the particular data unit includes:

generating the value for the particular data unit based on at least one of;

a protocol type associated with the particular data unit,

an incoming interface associated with the particular data unit, or

an Internet Protocol (IP) address associated with the particular data unit.

12. The method of claim 10, further comprising:

determining whether the particular data unit is the head data unit of the particular flow unit, based on the value generated for the particular data unit; and

storing, in the second memory, information associated with the particular data unit when the particular data unit is the head data unit of the particular flow unit.

13. The method of claim 7, where one or more entries, of the group of entries corresponding to the particular data flow, identify one or more other entries of the group of entries corresponding to the particular data flow.

14. A system comprising:

a device comprising;

a first memory to store a plurality of groups of entries,

each group of entries, of the plurality of groups of entries, corresponding to a different one of a plurality of data flows,

each group of entries, of the plurality of groups of entries, identifying an order of data units of a corresponding one of the plurality of data flows; and

a second memory to store information identifying a head data unit of each of the plurality of data flows,

the device transmitting data units, of a particular data flow of the plurality of data flows, based on;

a group of entries, of the plurality of groups of entries, corresponding to the particular data flow, and

the information, stored in the second memory, identifying the head data unit of the particular data flow,

a particular address of a first entry, of the group of entries corresponding to the particular data flow, corresponding to a processing unit that processes information related to a particular data unit of the data units of the particular data flow, and

the first entry identifying a processing unit that processes information related to another data unit of the data units of the particular data flow,

 

the particular data unit preceding the other data unit in the particular data flow.

15. The system of claim 14, where the device is further to:

generate a value for each data unit of the plurality of data flows,

where the values, generated for the data units of the particular data flow, identify the particular data flow, and

where the group of entries corresponding to the particular data flow are stored based on the values generated for the data units of the particular data flow.

16. The system of claim 15, where the device is further to:

determine whether the particular data unit, of the data units of the particular data flow, is the head data unit of the particular data flow, based on the value generated for the particular data unit, and

store, in the second memory, information associated with the particular data unit when the particular data unit is the head data unit of the particular flow unit.

17. The system of claim 15, where the device is further to:

determine, based on the value generated for a data unit of the particular data flow, whether the data unit is a last data unit of the particular data flow;

store, in a third memory, information identifying the data unit based on a result of whether the data unit is the last data unit of the particular data flow,

where the third memory stores information identifying a last data unit of each data flow of the plurality of data flows.

18. The system of claim 17, where, when transmitting the data units of the particular data flow, the device is to:

transmit the data units, of the particular data flow, further based on the information, stored in the third memory, identifying the data unit.

19. The system of claim 14, where one or more entries, of the group of entries corresponding to the particular data flow, identify one or more other entries of the group of entries corresponding to the particular data flow.

20. The system of claim 14, where the particular data unit corresponds to a first data unit of the particular data flow,

where the other data unit corresponds to a second data unit of the particular data flow, and

where the second memory stores information identifying the particular data unit.