Enhanced random early discard for networked devices
Methods, apparatuses and systems directed to enhanced random early discard mechanisms implemented in various networked devices including end-systems such as servers and intermediate systems such as gateways and routers. In one implementation, the present invention enables a random early discard mechanism that intelligently biases the drop probabilities of select packets based on one or more application-aware and/or flow-aware metrics or state conditions.
1. A method, comprising:
monitoring the number of received packets stored in a buffer relative to a threshold value; and
if the number of received packets stored in the buffer exceeds the threshold value, then initiating a random early discard mechanism to randomly discard one or more of the received packets; and
biasing operation of the random early discard mechanism to alter drop probabilities corresponding to individual packets based on one or more attributes associated with the respective individual packets, wherein biasing operation of the random early discard mechanism for a given packet comprises:
maintaining a maximum drop probability value; and
based on one or more attributes associated with the given packet, identifying cached information associated with previous policy decisions made for previous packet flows;
calculating an adjusted drop probability value for the given packet based on the cached information associated with the previous policy decisions made for the previous packet flows; and
in response to determining that the adjusted drop probability is less than the maximum drop probability value, determining whether to discard the given packet based at least in part on the one or more attributes associated with the given packet.
2. The method of claim 1 wherein calculating the drop probability value for the given packet based on one or more attributes associated with the given packet comprises
maintaining a baseline drop probability value that varies with observed load;
computing an adjustment factor for the given packet; and
determining the drop probability value for the given packet by using the adjustment factor to modify the baseline drop probability value.
3. The method of claim 2 wherein the computing an adjustment factor comprises applying one or more rules that consider one or more flow state parameters of a data flow corresponding to the given packet.
4. The method of claim 2 wherein the computing an adjustment factor comprises applying one or more rules that consider an application type of a data flow corresponding to the given packet.
5. The method of claim 2 wherein the computing an adjustment factor comprises applying one or more rules that consider a message type of a plurality of message types corresponding to the given packet, wherein each of the message types corresponds to a transaction state of a plurality of transaction states.
6. The method of claim 5 wherein a first message type is a request message, and wherein a second message type of the plurality of message types is a response.
7. The method of claim 2 wherein the computing an adjustment factor comprises applying one or more rules that consider previous drop decisions for previous packets of a data flow corresponding to the given packet.
8. The method of claim 1 further comprising:
assigning a random value to the given packet;
comparing the random value to the drop probability value that is based on one or more attributes associated with the given packet; and
discarding the given packet in response to determining that the random value is less than the drop probability value.
9. An apparatus, comprising:
a system bus,
a processor connected to the system bus;
a system memory, connected to the system bus, wherein the system memory maintains a plurality of data structures, the plurality of data structures comprising
a packet buffer for storing packets;
at least one network interface receive ring for storing pointers to packets in the packet buffer; and
at least one receive queue for storing pointers to packets in the packet buffer;
at least one network interface, connected to the system bus, operative to
receive packets transmitted over a computer network;
read received packets into the packet buffer, and
maintain pointers to the received packets in a corresponding one of the network interface receive rings;
a random early discard mechanism operative to randomly discard packets in the packet buffer when an observed load crosses a threshold value; and
a biasing function operative to bias operation of the random early discard mechanism to alter drop probabilities corresponding to individual packets based on one or more attributes associated with the respective individual packets, wherein the biasing function is further operative:
maintain a maximum drop probability value;
based on one or more attributes associated with the given packet, identify cached information associated with previous policy decisions made for previous packet flows;
calculate an adjusted drop probability value for the given packet based on the cached information associated with the previous policy decisions made for the previous packet flows; and
in response to determining that the adjusted drop probability is less than the maximum drop probability value, determine whether to discard the given packet based at least in part on the one or more attributes associated with the given packet.
10. The apparatus of claim 9 wherein to calculate the drop probability value for the given packet based on one or more attributes associated with the given packet the biasing function is operative to
maintain a baseline drop probability value that varies with observed load;
compute an adjustment factor for the given packet; and
determine the drop probability value for the given packet by using the adjustment factor to modify the baseline drop probability value.
11. The apparatus of claim 10 wherein to compute an adjustment factor the biasing function is operative to apply one or more rules that consider one or more flow state parameters of a data flow corresponding to the given packet.
12. The apparatus of claim 10 wherein to compute an adjustment factor the biasing function is operative to apply one or more rules that consider an application type of a data flow corresponding to the given packet.
13. The apparatus of claim 10 wherein to compute an adjustment factor the biasing function is operative to apply one or more rules that consider a message type of a plurality of message types corresponding to the given packet, wherein each of the message types corresponds to a transaction state of a plurality of transaction states.
14. The apparatus of claim 13 wherein a first message type is a request message, and wherein a second message type of the plurality of message types is a response.
15. The apparatus of claim 10 wherein to compute an adjustment factor the biasing function is operative to apply one or more rules that consider previous drop decisions for previous packets of a data flow corresponding to the given packet.
16. The apparatus of claim 9 wherein the biasing function is further operative to:
assigning a random value to the given packet;
comparing the random value to the drop probability value that is based on one or more attributes associated with the given packet; and
discarding the given packet in response to determining that the random value is less than the drop probability value.
17. An apparatus, comprising:
a processor; and
a memory, wherein the memory maintains a plurality of data structures, the plurality of data structures comprising
a packet buffer for storing packets;
a first queue for storing pointers to packets in the packet buffer; and
a second queue for storing pointers to packets in the packet buffer;
a processing module operative to read pointers from the first queue to the second queue for further processing;
a random early discard mechanism operative to randomly discard packets in the packet buffer when an observed load crosses a threshold value; and
a biasing function operative to bias operation of the random early discard mechanism to alter drop probabilities corresponding to individual packets based on one or more attributes associated with the respective individual packets, wherein the biasing function is further operative to:
maintain a maximum drop probability value;
based on one or more attributes associated with the given packet, identify cached information associated with previous policy decisions made for previous packet flows;
calculate an adjusted drop probability value for the given packet based on the cached information associated with the previous policy decisions made for the previous packet flows; and
in response to determining that the adjusted drop probability is less than the maximum drop probability value, determine whether to discard the given packet based at least in part on the one or more attributes associated with the given packet.
18. The apparatus of claim 17 wherein to calculate the drop probability value for the given packet based on one or more attributes associated with the given packet the biasing function is operative to
maintain a baseline drop probability value that varies with observed load;
compute an adjustment factor for the given packet; and
determine the drop probability value for the given packet by using the adjustment factor to modify the baseline drop probability value.
19. The apparatus of claim 18 wherein to compute an adjustment factor the biasing function is operative to apply one or more rules that consider one or more flow state parameters of a data flow corresponding to the given packet.
20. The apparatus of claim 17 wherein to compute an adjustment factor the biasing function is operative to apply one or more rules that consider an application type of a data flow corresponding to the given packet.
21. The apparatus of claim 17 wherein to compute an adjustment factor the biasing function is operative to apply one or more rules that consider a message type of a plurality of message types corresponding to the given packet, wherein each of the message types corresponds to a transaction state of a plurality of transaction states.
22. The apparatus of claim 21 wherein a first message type is a request message, and wherein a second message type of the plurality of message types is a response.
23. The apparatus of claim 17 wherein to compute an adjustment factor the biasing function is operative to apply one or more rules that consider previous drop decisions for previous packets of a data flow corresponding to the given packet.
24. The apparatus of claim 17 wherein the biasing function is further operative to:
assigning a random value to the given packet;
comparing the random value to the drop probability value that is based on one or more attributes associated with the given packet; and
discarding the given packet in response to determining that the random value is less than the drop probability value.