Multi-flow multi-level leaky bucket policer
View Patent ↗The invention provides a method and apparatus for policing a traffic flow in which a first stage of policing is performed on the traffic flow to produce a first stage conforming flow and a first stage violating flow. These two flows are then policed again in a second stage of policing, such that the first stage conforming flow can take advantage of a capacity allowed for the first stage violating flow which is unused by the first stage violating flow. In some embodiments, performing a first stage of policing involves associating each packet of the traffic flow with one of a plurality of sub-flows, policing at least one of the plurality of sub-flows individually to produce for each sub-flow a respective conforming sub-flow and a respective violating sub-flow. The conforming sub-flow(s) collectively are the first stage conforming flow. The violating sub-flows collectively are the first stage violating flow.
1. A method of policing a traffic flow comprising:
performing a first stage of policing on the traffic flow to produce a first stage conforming flow and a first stage violating flow;
policing the first stage violating flow;
policing the first stage conforming flow in a manner which allows the first stage conforming flow to take advantage of a capacity allowed for the first stage violating flow which is unused by the first stage violating flow;
wherein policing the first stage conforming flow and policing the first stage violating flow comprises:
maintaining a credit count for the first stage conforming flow in combination with the first stage violating flow;
enforcing a first burst parameter on the first stage conforming flow and enforcing a second burst parameter on the first stage violating flow, the second burst parameter being smaller than the first burst parameter, to produce a second stage conforming flow and a second stage violating flow.
2. A method according to claim 1 wherein maintaining a credit count for the first stage conforming flow in combination with the first stage violating flow comprises:
periodically subtracting from the credit count in accordance with a rate parameter of the second stage policer;
adding to the credit count for each packet in the second stage conforming flow.
3. A method according to claim 2 wherein enforcing the first burst parameter on the first stage conforming flow and enforcing the second burst parameter on the first stage violating flow, comprises:
for each packet in the first stage conforming flow, determining if a sum of the credit count plus an added amount for the packet does not exceed the first burst parameter and if so adding the packet to the second stage conforming flow;
for each packet in the first stage violating flow, determining if a sum of the credit count plus an added amount for the packet does not exceed the second burst parameter and if so adding the packet to the second stage conforming flow.
4. A method according to claim 2 wherein enforcing the first burst parameter on the first stage conforming flow and enforcing the second burst parameter on the first stage violating flow, comprises:
for each packet in the first stage conforming flow, if the credit count does not exceed the first burst parameter, adding the packet to the second stage conforming flow;
for each packet in the first stage violating flow, if the credit count does not exceed the second burst parameter, adding the packet to the second stage conforming flow.
5. A method according to claim 2 further comprising:
marking packets of the first stage conforming flow not added to the second stage conforming flow.
6. A method according to claim 2 further comprising:
discarding packets of the first stage conforming flow not added to the second stage conforming flow.
7. A method according to claim 2 further comprising marking or discarding packets of the first stage violating flow not added to the second stage conforming flow.
8. An apparatus comprising:
a machine readable medium storing program instructions executable by a processor of the apparatus, said program instructions comprising:
a first policing function for performing a first stage of policing on each packet to produce a policed packet which is either a conforming packet or a violating packet;
a second policing function for performing a second stage of policing on each policed packet in a manner which allows conforming packets to take advantage of a capacity allowed for violating packets which is unused by violating packets;
a packet classifier function for classifying each packet of a packet flow into one of a plurality of classifications;
wherein the first policing function performs a first stage of policing on each packet to produce a policed packet which is either a conforming packet or a violating packet according to policing parameters associated with the classification of the packet;
wherein the second policing function:
maintains a credit count; and
enforces a first burst parameter on the policed packet if it is a conforming packet and enforces a second burst parameter on the policed packet if it is a violation packet, the second burst parameter being smaller than the first burst parameter.
9. An apparatus according to claim 8 wherein:
for each policed packet if a sum of the credit count plus an added amount for the packet does not exceed the first burst parameter the policed packet is a conforming packet of the second policing function and otherwise the policed packet is a violating packet of the second policing function.
10. An apparatus according to claim 8 wherein:
for each policed packet, if the credit count does not exceed the first burst parameter, the policed packet is a conforming packet of the second policing function and otherwise the packet is a violating packet of the policing function.