High performance probabilistic rate policer

• US 8,004,980 B2
• Filed: 03/26/2010
• Issued: 08/23/2011
• Est. Priority Date: 03/18/2002
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Chen, Devereaux C, Ferguson, Dennis C, Zimmer, Jeffrey R, Stewart, John W III, Washburn, James
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): Haliyur; Venkatesh
• Application Number:
  US12/732,370
• Publication Number:
  US 20100177638A1
• Time in Patent Office: 515 Days
• Field of Search: 370228-503
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/39 Credit based

Abstract

A data flow rate policer enforces data flow policies for a number of data flows using a probabilistic policy enforcement mechanism. The policer includes a memory that stores the state of each data flow in a compact data structure. Additionally, the policer includes one or more policing engines that implement the actual data flow policies based on information derived from the data structures. The policing engines may be implemented in hardware to increase performance.

Claims

1. A method performed by a data flow policing device, the method comprising:

receiving, by the data flow policing device, a policing request associated with a packet belonging to a data flow;

retrieving, from a memory associated with the data flow policing device, a data structure corresponding to the data flow, the data structure including a credit count for the data flow;

calculating, by the data flow policing device, an amount to increment the credit count;

determining, by the data flow policing device, whether the packet is within a data flow specification using a function that compares a probability value to a random number, the probability value being based on the credit count, as modified by a length of the packet and the amount to increment the credit count;

sending an indication that the packet is within the data flow specification when the probability value is greater than the random number; and

storing, in the memory, an updated data structure corresponding to the data flow, the updated data structure including the credit count, as modified by the length of the packet and the amount to increment the credit count.

2. The method of claim 1, further comprising:

dropping the packet based on a determination that the packet is not within the data flow specification.

3. The method of claim 1, where all or a portion of the data flow policing device is implemented as an application specific integrated circuit.

4. The method of claim 1, further comprising:

storing, in the memory, a plurality of data structures corresponding to a plurality of data flows.

5. The method of claim 1, where calculating the amount to increment the credit count includes:

computing an elapsed time from a previous time, corresponding to when the credit count was incremented, to a current time, the previous time being read from the data structure; and

multiplying the elapsed time by a credit allotment, for the data flow, read from the data structure.

6. A policing device, comprising:

a memory to store a data structure that associates a data flow with a credit count;

at least one route lookup engine to forward a policing request associated with a packet, belonging to the data flow, when the packet includes an indication that policing is to be performed on the packet based on a specification associated with the data flow; and

a policer to;

receive, from the at least one route lookup engine, the policing request where the policing request includes a length of the packet,

increment the credit count associated with the data flow based on a credit allotment associated with the data flow and a period of time since the credit count was last incremented,

generate, using a function associated with the specification, a probabilistic value based on the incremented credit count as modified by the length of the packet,

determine that the packet is probabilistically within the specification when the probabilistic value is greater than a random number associated with the specification, and

determine that the packet is probabilistically outside the specification when the probabilistic value is less than or equal to the random number.

7. The policing device of claim 6, where the policer is further to:

determine that the packet is within the specification when the incremented credit count, as modified by the length of the packet, is greater than a threshold.

8. The policing device of claim 6, where the policer is further to:

determine that the packet is outside the specification when the incremented credit count, as modified by the length of the packet, is less than a threshold.

9. The policing device of claim 6, where the at least one route lookup engine is further to:

receive an indication that the packet is within the specification, and

forward the packet to a destination, using a destination address associated with the packet, based on the indication that the packet is within the specification.

10. The policing device of claim 6, where the at least one route lookup engine is further to:

receive an indication that the packet is outside the specification, and

based on the indication that the packet is outside the specification, one of;

drop the packet, or

tag the packet for special handling.

11. The policing device of claim 6, where the policer is further to:

update the data structure by storing at least one of a current time and the incremented credit count, as modified by the length of the packet, in the data structure, and

storing the updated data structure in the memory.

12. A method performed by a policing device, the method comprising:

receiving, by the policing device, a request to determine whether a packet, associated with a data flow, of a plurality of data flows, is within a data flow specification;

retrieving, from a memory associated with the policing device and in response to the request, a data structure, of a plurality of data structures, associated with the data flow, that includes information used for incrementing a credit count associated with the data flow;

generating, by the policing device and using a probability function, a probability value based on the credit count as modified by a length of the packet and the information used for incrementing the credit count;

sending, to a route look up engine, an indication that the packet is within the data flow specification when the probability value is greater than a random number; and

sending, to the route look up engine, an indication that the packet is outside the data flow specification when the probability value is less than or equal to the random number.

13. The method of claim 12, where generating the probability value using a probability function further includes:

determining whether the credit count, as modified by the length of the packet and the information used to increment the credit count, is greater than a credit limit stored in the data structure; and

setting the credit count, as modified by the length of the packet and the information used to increment the credit count, to the credit limit when the credit count, as modified by the length of the packet and the information used to increment the credit count, is greater than the credit limit.

14. The method of claim 12, where the information used to increment the credit count includes a prior time when the credit count was incremented and a credit allotment, and

where generating the probability value includes:

determining an elapsed time since the credit count was previously incremented based on a current time and the prior time; and

computing an incremented credit count based on the elapsed time and the credit allotment.

15. The method of claim 14, further comprising:

updating the data structure, associated with the data flow, based on the incremented credit count as modified by the length of the packet and the current time; and

storing the updated data structure in the memory.

16. The method of claim 12, where generating the probability value further includes:

modifying the length of the packet based on a programmatically defined value.

17. The method of claim 16, where modifying the length of the packet further includes:

computing the modified length of the packet by multiplying the length corresponding to the packet by two raised to the programmatically defined value.

18. The method of claim 12, where sending the indication that the packet is outside the data flow specification further includes:

incrementing a quantity of out-of-specification packets, associated with the data flow,

updating the data structure, associated with the data flow, based on the incremented quantity of out-of-specification packets; and

storing the updated data structure in the memory.

19. The method of claim 12, further comprising:

determining that the credit count, as modified by the length of the packet and the information used to increment the credit count, is greater than a threshold; and

sending the indication that the packet is within the data flow specification based on the determination that the credit count, as modified by the length of the packet and the information used to increment the credit count, is greater than the threshold.

20. The method of claim 12, further comprising:

determining that the credit count, as modified by the length of the packet and the information used to increment the credit count, is less than a threshold; and

sending the indication that the packet is outside the data flow specification based on the determination that the credit count, as modified by the length of the packet and the information used to increment the credit count, is less than the threshold.