High performance probabilistic rate policer

• US 7,715,315 B1
• Filed: 04/27/2007
• Issued: 05/11/2010
• Est. Priority Date: 03/18/2002
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Stewart, John W. III, Ferguson, Dennis C., Washburn, James, Zimmer, Jeffrey R., Chen, Devereaux C.
• Primary Examiner(s): Ahmed; Salman
• Assistant Examiner(s): Haliyur; Venkatesh
• Application Number:
  US11/741,363
• Time in Patent Office: 1,110 Days
• Field of Search: 370230-238, 370389-467
• 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 data flow policing device comprising:

a policer to receive a policing request that includes an indication of a packet belonging to a data flow and to determine whether the packet is within specification using a function that implements a probabilistic function that compares a probability value based on a credit count associated with the data flow to a random number, the policer further comprising;

a credit increment component to calculate an amount to increment the credit count, and

a decision component to receive the amount to increment the credit count and generate the determination of whether the packet is within specification, using the probabilistic function, based on the credit count, as modified by a length of the packet and the amount to increment the credit count; and

a memory to store a data structure corresponding to the data flow, the data structure including at least the credit count of the data flow.

2. The data flow policing device of claim 1, further comprising:

a route lookup engine to transmit the policing request to the policer and to drop the packet when the policer determines that the packet is not within specification.

3. The data flow policing device of claim 1, where the credit increment component and the decision component are implemented as application specific integrated circuits.

4. The data flow policing device of claim 1, where the memory is to store a plurality of data structures corresponding to a plurality of data flows.

5. The data flow policing device of claim 1, where each data structure in the memory further includes:

a field that stores an indication of the last time that the data structure was modified, and

an indication of a maximum credit value for the credit count.

15. The data flow policing device of claim 1, where the credit increment component and the decision component are implemented as application specific integrated circuits.

6. A network device comprising:

a physical interface to receive packets from and transmit packets to a network; and

a processing unit to store the received packets and determine a destination device for the packets, the processing unit including a route lookup unit that comprises;

a plurality of route lookup engines,

a policer to receive a policing request for a packet associated with a data flow from one of the plurality of route lookup engines and determine whether the packet is within specification based on information contained in a data structure associated with the data flow, the data structure including at least a credit count of the data flow, the policer determining whether the packet is within specification using a probabilistic function that compares a probability value based on the credit count to a random number, the policer further comprising;

a credit increment component to calculate an amount to increment the credit count, and

a decision component to receive the amount to increment the credit count and generate the determination of whether the packet is within specification using the probabilistic function based on the credit count, as modified based on a length of the packet and the amount to increment the credit count, and

a memory to store the data structure associated with the data flow.

7. The network device of claim 6, where the one route lookup engine drops the packet when the policer determines that the packet is not within specification.

8. The network device of claim 6, where the credit increment component and the decision component are implemented as application specific integrated circuits.

9. The network device of claim 6, where the memory is to store a plurality of data structures corresponding to a plurality of data flows.

10. The network device of claim 6, where the network device is a router.

11. A device comprising:

means for initiating a credit based flow control operation in response to a request identifying at least a length of a data packet and a flow to which the data packet belongs;

means for reading a data structure corresponding to the identified flow from memory, the data structure including at least a credit count associated with the indentified flow;

means for determining whether the data packet is within specification using a probabilistic function that compares a probability value based on the credit count to a random number;

means for calculating an amount to increment the credit count; and

means for receiving the amount to increment the credit count,

where the means for determining whether the data packet is within specification is further for determining whether the packet is within specification using the probabilistic function based on the credit count, as modified based on a length of the data packet and the amount to increment the credit count.

12. The device of claim 11, further comprising:

means for writing an updated version of the data structure to the memory.

13. A data flow policing device comprising:

a memory to store data structures corresponding to a plurality of data flows, the data structures including at least a credit count associated with the data flows; and

a policer to;

receive a policing request that includes an indication of a data unit belonging to at least one of the data flows,

read the data structure corresponding to the data flow from the memory, in response to the request,

calculate an amount to increment the credit count,

determine whether the data unit is within specification based on evaluation of a probabilistic function, in which a probability value is derived from the credit count, as modified based on a length of the data unit and the amount to increment the credit count, associated with the data flow, and the derived probability value is compared to a random number, and

update the read data structure in the memory.

14. The data flow policing device of claim 13, further comprising:

a route lookup engine to transmit the policing request to the policer and drop the data unit when the policer determines that the packet is not within specification.