High performance probabilistic rate policer
First Claim
Patent Images
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
Specification