Granted Patent B2

US 8,804,507 · App. 13/077,577 · Granted Aug 12, 2014

Abstract

Claims (52)

1. A computer-implemented method in which a computer system performs operations comprising:

receiving a packet as part of an m-tuple flow, wherein m is a non-zero value indicating a number of tuples;

computing a hash identifier (ID) for said packet;

using said hash ID to index into a State Table and retrieving a corresponding record, wherein said record includes a time credit field and a Packet Processing Engine (PE) number and does not include m-tuple flow information; and

when a time credit field of said record is zero then:

setting said time credit field to a new value;

selecting the Packet Processing Engine whose First-In-First-Out buffer (FIFO) has the lowest fill level; and

updating a PE number field in the state table record with the selected PE number; and

when the time credit field of said record is non-zero then:

sending the packet to the PE based on the value stored in said record; and

decrementing said time credit field in the record only if said time credit field is greater than zero.

2. The method of claim 1 , wherein said setting said time credit field to a new value comprises setting said time credit field to a maximum value.

3. The method of claim 1 , wherein an average m-tuple flow bandwidth is at least an order of magnitude less than a high speed link bandwidth.

4. The method of claim 1 , wherein average inter-packet arrival time within said m-tuple flow is larger than the packet processing latency.

5. The method of claim 1 , wherein an input rate to each FIFO is ‘r’, wherein r is an input port rate.

6. The method of claim 5 , wherein a sustained output rate is r/n where n is the number of PEs.

7. The method of claim 1 , wherein said using a time credit field to determine which packet processing engine is used provides fair bandwidth distribution and packet order within a flow.

8. A non-transitory computer readable storage medium having computer readable code thereon for temporal-based flow distribution across multiple packet processors, the medium including instructions in which a computer system performs operations comprising:

receiving a packet as part of an m-tuple flow, wherein m is a non-zero value indicating a number of tuples;

computing a hash identifier (ID) for said packet;

using said hash ID to index into a State Table and retrieving a corresponding record wherein said record includes a time credit field and a Packet Processing Engine (PE) number and does not include m-tuple flow information; and

when a time credit field of said record is zero then:

setting said time credit field to a new value;

selecting the Packet Processing Engine whose First-In-First-Out buffer (FIFO) has the lowest fill level; and

updating a PE number field in the state table record with selected PE number; and

when the time credit field of said record is non-zero then:

sending the packet to the PE based on the value stored in said record; and

decrementing said time credit field in the record only if said time credit field is greater than zero.

9. The non-transitory computer readable storage medium of claim 8 , wherein said setting said time credit field to a new value comprises setting said time credit field to a maximum value.

10. The non-transitory computer readable storage medium of claim 8 , wherein an average m-tuple flow bandwidth is at least an order of magnitude less than a high speed link bandwidth.

11. The non-transitory computer readable storage medium of claim 8 , wherein average inter-packet arrival time within an m-tuple flow is larger than the packet processing latency.

12. The non-transitory computer readable storage medium of claim 8 , wherein an input rate to each FIFO is ‘r’, wherein r is an input port rate.

13. The non-transitory computer readable storage medium of claim 12 , wherein a sustained output rate is r/n where n is the number of PEs.

14. The non-transitory computer readable storage medium of claim 8 , wherein said using a time credit field to determine which packet processing engine is used provides fair bandwidth distribution and packet order within a flow.

15. A computer system comprising a flow distributor and a plurality of Packet Processing Engines (PEs), each of said flow distributor and said PEs comprising:

a memory;

a processor;

a communications interface;

an interconnection mechanism coupling the memory, the processor and the communications interface; and

wherein the memory is encoded with an application providing for temporal-based flow distribution across multiple packet processors, that when performed, provides a process for processing information, the process causing the computer system to perform the operations of:

receiving a packet as part of an m-tuple flow, wherein m is a non-zero value indicating a number of tuples;

computing a hash identifier (ID) for said packet;

using said hash ID to index into a State Table and retrieving a corresponding record wherein said record includes a time credit field and a Packet Processing Engine (PE) number and does not include m-tuple flow information; and

when a time credit field of said record is zero then:

setting said time credit field to a new value;

selecting the Packet Processing Engine whose First-In-First-Out buffer (FIFO) has the lowest fill level; and

updating a PE number field in the state table record with selected PE number; and

when the time credit field of said record is non-zero then:

sending the packet to the PE based on the value stored in said record; and

decrementing said time credit field in the record only if said time credit field is greater than zero.

16. The computer system of claim 15 , wherein average inter-packet arrival time within an m-tuple flow is larger than a packet processing latency.

17. The computer system of claim 15 , wherein said using a time credit field to determine which packet processing engine is used provides fair bandwidth distribution and packet order within a flow.

Assignments (13)