Mechanism for identifying and penalizing misbehaving flows in a network
DC CAFCFirst Claim
1. A machine-implemented method for processing a single flow, the flow comprising a plurality of packets, and the method comprising:
- creating a flow block as the first packet of a flow is processed by a single router;
said flow block being configured to store payload-content-agnostic behavioral statistics pertaining to said flow, regardless of the presence or absence of congestion;
said router updating said flow block with the payload-content-agnostic behavioral statistics of each packet belonging to said flow, as each packet belonging to said flow is processed by said router, regardless of the presence or absence of congestion;
said router heuristically determining whether said flow exhibits undesirable behavior by comparing at least one of said payload-content-agnostic behavioral statistics to at least one pre-determined threshold value; and
upon determination by said router that said flow exhibits undesirable behavior, enforcing, relative to at least one packet, a penalty;
wherein the preceding steps are performed on said router without requiring use of inter-router data.
5 Assignments
Litigations
3 Petitions
Accused Products
Abstract
A mechanism is disclosed for identifying and penalizing misbehaving flows in a network. In one implementation, a set of behavioral statistics are maintained for each flow. These behavioral statistics are updated as information packets belonging to a flow are processed. Based upon these behavioral statistics, a determination is made as to whether a flow is exhibiting undesirable behavior. If so, a penalty is imposed on the flow. In one implementation, this penalty causes packets belonging to the flow to have a higher probability of being dropped than packets belonging to other flows that do not exhibit undesirable behavior. In one implementation, in addition to penalizing the flow, this penalty also has the effect of correcting the flow'"'"'s behavior such that the flow exhibits less undesirable behavior after the penalty than before. By correcting the flow'"'"'s behavior, the penalty makes it possible for the flow to become a non-misbehaving flow.
-
Citations
44 Claims
-
1. A machine-implemented method for processing a single flow, the flow comprising a plurality of packets, and the method comprising:
-
creating a flow block as the first packet of a flow is processed by a single router; said flow block being configured to store payload-content-agnostic behavioral statistics pertaining to said flow, regardless of the presence or absence of congestion; said router updating said flow block with the payload-content-agnostic behavioral statistics of each packet belonging to said flow, as each packet belonging to said flow is processed by said router, regardless of the presence or absence of congestion; said router heuristically determining whether said flow exhibits undesirable behavior by comparing at least one of said payload-content-agnostic behavioral statistics to at least one pre-determined threshold value; and upon determination by said router that said flow exhibits undesirable behavior, enforcing, relative to at least one packet, a penalty; wherein the preceding steps are performed on said router without requiring use of inter-router data. - View Dependent Claims (6, 7, 8)
-
-
2. A non-transitory computer-readable medium having computer-executable instructions for performing a method to process a single flow, the flow comprising a plurality of packets, and the method comprising:
-
creating a flow block as the first packet of a flow is processed by a single router; said flow block being configured to store payload-content agnostic behavioral statistics about said flow, regardless of the presence or absence of congestion; said router updating said flow block with the flow'"'"'s behavioral statistics of each packet belonging to said flow, as each packet belonging to said flow is processed by said router, regardless of the presence or absence of congestion; said router heuristically determining whether said flow is exhibiting undesirable behavior by comparing at least one of said behavioral statistics to at least one pre-determined threshold value; and upon determination by said router that said flow is exhibiting undesirable behavior, enforcing, relative to at least one packet belonging to said flow, a penalty; wherein the preceding steps are performed on said router without requiring use of inter-router data.
-
-
3. An article of manufacture comprising:
-
a non-transitory computer-readable medium having stored thereon a data structure; a first field containing data representing a flow block; a second field containing data representing payload-content-agnostic behavioral statistics about dropped and non-dropped packets of a flow; a third field containing data representing pre-determined behavior threshold values; a fourth field containing data representing the results of a heuristic determination of whether said flow exhibits undesirable behavior determined by comparing said behavioral statistics to said pre-determined threshold values; a fifth field containing data representing at least one penalty to be enforced against at least one packet upon determination that said flow exhibits undesirable behavior.
-
-
4. A machine implemented method for processing a flow, the flow comprising a series of information packets, the method comprising:
-
maintaining a set of behavioral statistics for the flow, wherein the set of behavioral statistics is updated based on each information packet belonging to the flow, as each information packet belonging to the flow is processed; determining, based at least partially upon the set of behavioral statistics, whether the flow is exhibiting undesirable behavior, regardless of the presence or absence of congestion; and in response to a determination that the flow is exhibiting undesirable behavior, enforcing a penalty on the flow.
-
-
5. A machine implemented method for processing a flow, the flow comprising a series of information packets, the method comprising:
-
maintaining a set of behavioral statistics for the flow, wherein the set of behavioral statistics is updated based on each information packet belonging to the flow, as each information packet belonging to the flow is processed, regardless of the presence or absence of congestion; determining, based at least partially upon the set of behavioral statistics, whether the flow is exhibiting undesirable behavior; and in response to a determination that the flow is exhibiting undesirable behavior, enforcing a penalty on the flow.
-
-
9. A machine implemented method for processing a flow, the flow comprising a series of information packets, the method comprising:
-
maintaining a set of behavioral statistics for the flow, wherein the set of behavioral statistics is updated based on each information packet belonging to the flow, as each information packet belonging to the flow is processed, regardless of the presence or absence of congestion; and computing, based at least partially upon the set of behavioral statistics, a badness factor for the flow, wherein the badness factor provides an indication of whether the flow is exhibiting undesirable behavior. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A misbehaving flow manager (MFM) for processing a flow, the flow comprising a series of information packets, the MFM comprising:
-
means for maintaining a set of behavioral statistics for the flow, wherein the set of behavioral statistics is updated based on each information packet belonging to the flow, as each information packet belonging to the flow is processed, regardless of the presence or absence of congestion; means for determining, based at least partially upon the set of behavioral statistics, whether the flow is exhibiting undesirable behavior; and means for enforcing, in response to a determination that the flow is exhibiting undesirable behavior, a penalty on the flow. - View Dependent Claims (26, 27, 28)
-
-
29. A misbehaving flow manager (MFM) for processing a flow, the flow comprising a series of information packets, the MFM comprising:
-
means for maintaining a set of behavioral statistics for the flow, wherein the set of behavioral statistics is updated based on each information packet belonging to the flow, as each information packet belonging to the flow is processed, regardless of the presence or absence of congestion; and means for computing, based at least partially upon the set of behavioral statistics, a badness factor for the flow, wherein the badness factor provides an indication of whether the flow is exhibiting undesirable behavior. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44)
-
Specification