Modification of policing methods to make them more TCP-friendly
Various improvements are provided for prior art policing methods, including token bucket methods and virtual time policing methods. Some preferred methods of the invention involve assigning a non-zero drop probability even when the packet would otherwise have been transmitted according to a prior art policing method. For example, a non-zero drop probability may be assigned even when there are sufficient tokens in a token bucket to allow transmission of the packet. A non-zero drop probability may be assigned, for example, when a token bucket level is at or below a predetermined threshold or according to a rate at which a token bucket is being emptied. Some implementations involve treating a token bucket as a virtual queue wherein the number of free elements in the virtual queue is proportional to the number of remaining tokens in the token bucket. Such implementations may involve predicting a future virtual queue size according to a previous virtual queue size and using this predicted value to calculate a drop probability.
1. A method of controlling a network device, comprising:
receiving a packet in the network device;
determining that there are sufficient tokens in a token bucket to allow transmission of the packet; and
applying a control method to determine whether to drop the packet, wherein the control method comprises treating a difference between a token bucket capacity and a token bucket level as a virtual queue, wherein a determination of whether to drop packets is based in part on a virtual queue size.
2. The method of claim 1 , wherein the control method comprises:
predicting a future virtual queue size based on a present virtual queue size; and
calculating a drop probability according to a predicted future virtual queue size.
3. A method of controlling a network device, comprising:
receiving a packet in the network device;
determining that there are sufficient tokens in a token bucket to allow transmission of the packet; and
applying a control method to determine whether to drop the packet, wherein the control method comprises determining a predicted token bucket level;
wherein the control method further comprises assigning a zero probability that the packet will be dropped when the predicted token bucket level exceeds a predetermined level.
4. The method of claim 3 , wherein the control method further comprises determining a token bucket level.
5. The method of claim 4 , wherein the token bucket level comprises an instantaneous level or an average level.
6. The method of claim 3 , wherein the control method further comprises determining a rate at which a token bucket level is being changed, wherein the predicted token bucket level is based on a current level and on a rate at which a token bucket level is being changed.
7. A method of controlling a network device, comprising:
receiving a packet in the network device;
determining that there are sufficient tokens in a token bucket to allow transmission of the packet; and
applying a control method to determine whether to drop the packet, wherein the control method comprises determining a predicted token bucket level;
wherein the control method further comprises assigning a non-zero probability that the packet will be dropped when the predicted token bucket level is below a predetermined level.
8. The method of claim 7 , wherein the predicted token bucket level is based on a current level and on a rate at which a token bucket level is being changed.
9. The method of claim 7 , wherein the predicted token bucket level is based on an instantaneous level or an average level.
10. The method of claim 7 , wherein the control method further comprises determining a token bucket level.
11. The method of claim 10 , wherein the token bucket level comprises an instantaneous level or an average level.
12. The method of claim 7 , wherein the non-zero probability varies according to a rate at which the token bucket level is being changed.
13. The method of claim 7 , wherein the non-zero probability varies according to an extent by which the token bucket level is below a predetermined level.
14. A network device including a processor and a memory, comprising:
means for receiving a packet;
means for determining that there are sufficient tokens in a token bucket to allow transmission of the packet; and
means for applying a control procedure to determine whether to drop the packet, wherein the control procedure comprises determining a predicted token bucket level, determining a token bucket level, and assigning a non-zero probability that the packet will be dropped when the token bucket level is below a predetermined level.
15. A non-transitory computer-readable medium storing thereon computer-readable instructions for controlling a network device to perform the following steps:
receiving a packet;
determining that there are sufficient tokens in a token bucket to allow transmission of the packet; and
applying a control procedure to determine whether to drop the packet, wherein the control procedure comprises determining a predicted token bucket level, wherein the control method further comprises assigning a non-zero probability that the packet will be dropped when the predicted token bucket level is below a predetermined level.
16. A line card for a network device, comprising:
an interface configured for receiving packets; and
a logic device configured to perform the following steps:
determining that there are sufficient tokens in a token bucket to allow transmission of a packet; and
applying a control procedure to determine whether to drop the packet, wherein the control procedure comprises determining a predicted token bucket level, wherein the control method further comprises assigning a non-zero probability that the packet will be dropped when the predicted token bucket level is below a predetermined level.
17. A method of controlling a network device, comprising:
receiving a packet in the network device;
determining that a policing method would allow transmission of the packet by comparing packet size of the packet with a predicted level of a token bucket, each token of the token bucket corresponding to an authorization for transmitting a predetermined unit of data;
applying a control procedure to determine whether to drop the packet, the control procedure generating a probability based on the predicted level of the token bucket, the probability being greater than zero and less than one; and
subsequently dropping or transmitting the packet based on the probability.