Back to results
US 8,897,132 B2Granted
Enhanced random early discard for networked devices
AssigneeBlue Coat Systems, Inc.
InventorsAzeem Feroz, Suresh Babu Muppala, Jon Eric Okholm
Life of this patent
Estimating the term…
Abstract
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.
Claims24
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.
8 more elements
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.
16 more elements
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.
13 more elements
Dependencies are inferred from the claim text.