Approximated per-flow rate limiting

• US 6,724,721 B1
• Filed: 05/07/1999
• Issued: 04/20/2004
• Est. Priority Date: 05/07/1999
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheriton, David R.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Jain, Raj K.
• Application Number:
  US09/307,305
• Time in Patent Office: 1,810 Days
• Field of Search: 370/412, 370/428, 370/427, 370/229, 370/232, 370/233, 370/234, 370/235, 370/236, 370/413, 711/158, 711/202, 711/216
• US Class Current: 370/229
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/39 Credit based
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools

Abstract

A method and apparatus to limit the throughput rate of non-adapting aggressive flows on a packet-by-packet basis. Each packet of an input flow is mapped to an entry in a flow table for each output queue. The mapping is based on a subset of the packet'"'"'s header data, giving an approximation of per-flow management. Each entry contains a credit value. On packet reception, the credit value is compared to zero; if there are no credits, the packet is dropped. Otherwise, the size of the packet is compared to the credit value. If sufficient credits exist (i.e., size is less than or equal to credits), the credit value is decremented by the size of the packet in cells and the processing proceeds according to conventional methods, including but not limited to those disclosed in the co-pending DBL Application, incorporated herewith by reference in its entirety. If, however, the size of the packet exceeds the available credits, the credit value is set to zero and the packet is dropped. A periodic task adds credits to each flow table entry up to a predetermined maximum. The processing rate of each approximated flow is thus maintained to the rate determined by the number of credits present at each enqueuing decision, up to the allowed maximum. The scheme operates independently of packet flow type, providing packet-specific means for rapidly discriminating well-behaved flows that adapt to congestion situations signaled by packet drop from aggressive, non-adapting flows and managing throughput bandwidth accordingly. Bandwidth is shared fairly among well-behaved flows, large and small, and time-critical (low latency) flows, thereby protecting all from non-adapting aggressive flows.

Claims

1. A method of rate limiting traffic in a communications system comprising:

parsing an incoming packet comprising a plurality of fields to generate an extracted plurality of fields;

transforming said extracted plurality of fields according to an algorithm to generate a result wherein said transforming comprises at least one of, hashing data of said extracted plurality of fields, and concatenating data of said extracted plurality of fields;

mapping said result according to a mapping function wherein the output of said mapping function is an index corresponding to a flow table entry;

reading the flow table entry identified by said index, said flow table entry containing at least a field identifying a credit value;

comparing said credit value to a quantity signifying insufficient credits;

processing or dropping the packet based on said comparing; and

periodically incrementing said credit value by an increment.

2. The method of claim 1 wherein said processing further comprises:

testing a size of the packet against said credit value;

decrementing said credit value by the size of the packet if the size is less than or equal to said credit value; and

setting said credit value to zero and dropping the packet if the size is greater than said credit value.

3. The method of claim 1 wherein said processing further comprises:

enqueuing the packet if said credit value is greater than or equal to zero; and

dropping the packet if said credit value is less than zero.

4. A computer system for communications, wherein said computer system comprises:

a buffer manager receiving a plurality of input flows, each input flow comprising a plurality of packets;

a controller coupled to said buffer manager and configured to,

map each of said input flows into a flow table, said flow table comprising a plurality of entries each containing at least a field identifying a credit value wherein said controller to map each of said input flows into a flow table further comprises at least one of, a controller to hash data of said plurality of input flows, and a controller to concatenate data of said plurality of input flows;

compare said credit value to a quantity signifying insufficient credits;

process or drop a packet based on said comparison; and

periodically increment said credit value by an increment.

5. The computer system of claim 4 wherein said controller further comprises circuitry to:

test a size of the packet against said credit value;

decrement said credit value by the size of the packet if the size is less than or equal to said credit value; and

set said credit value to zero and drop the packet if the size is greater than said credit value.

6. The computer system of claim 4 wherein said controller further comprises circuitry to:

enqueue the packet if said credit value is greater than or equal to zero; and

drop the packet if said credit value is less than zero.

7. A computer system for communications, wherein said computer system comprises computer instructions for:

parsing an incoming packet comprising a plurality of fields to generate an extracted plurality of fields;

transforming said extracted plurality of fields according to an algorithm to generate a result wherein said transforming comprises at least one of, hashing data of said extracted plurality of fields, and concatenating data of said extracted plurality of fields;

mapping said result according to a mapping function wherein the output of said mapping function is an index corresponding to a flow table entry;

reading the flow table entry identified by said index, said flow table entry containing at least a field identifying a credit value;

comparing said credit value to a quantity signifying insufficient credits;

processing or dropping the packet based on said comparing; and

periodically incrementing said credit value by an increment.

8. The computer system of claim 7 wherein said processing further comprises:

testing a size of the packet against said credit value;

decrementing said credit value by the size of the packet if the size is less than or equal to said credit value; and

setting said credit value to zero and dropping the packet if the size is greater than said credit value.

9. The computer system of claim 7 wherein said processing further comprises:

enqueuing the packet if said credit value is greater than or equal to zero; and

dropping the packet if said credit value is less than zero.

10. A computer readable storage medium comprising computer instructions for:

parsing an incoming packet comprising a plurality of fields to generate an extracted plurality of fields;

transforming said extracted plurality of fields according to an algorithm to generate a result wherein said transforming comprises at least one of, hashing data of said extracted plurality of fields, and concatenating data of said extracted plurality of fields;

mapping said result according to a mapping function wherein the output of said mapping function is an index corresponding to a flow table entry;

reading the flow table entry identified by said index, said flow table entry containing at least a field identifying a credit value;

comparing said credit value to a quantity signifying insufficient credits;

processing or dropping the packet based on said comparing; and

periodically incrementing said credit value by an increment.

11. The computer readable storage medium of claim 10 wherein said processing further comprises:

testing a size of the packet against said credit value;

decrementing said credit value by the size of the packet if the size is less than or equal to said credit value; and

setting said credit value to zero and dropping the packet if the size is greater than said credit value.

12. The computer readable storage medium of claim 10 wherein said processing further comprises:

enqueuing the packet if said credit value is greater than or equal to zero; and

dropping the packet if said credit value is less than zero.