Mechanism for identifying and penalizing misbehaving flows in a network

• US 8,243,593 B2
• Filed: 12/22/2004
• Issued: 08/14/2012
• Est. Priority Date: 12/22/2004
• Status: Expired due to Fees

• Current Assignee: Sable Networks, Inc.
• Original Assignee: Sable Networks, Inc.
• Inventors: Natchu, Vishnu
• Primary Examiner(s): Wong, Xavier Szewai
• Application Number:
  US11/022,599
• Publication Number:
  US 20060133280A1
• Time in Patent Office: 2,792 Days
• Field of Search: 370229-236
• US Class Current: 370/229
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

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.

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.

6. The method of claim 1, wherein enforcing the penalty has an effect of correcting the flow'"'"'s behavior such that the flow exhibits less undesirable behavior.

7. The method of claim 1, wherein enforcing the penalty comprises:

imposing an increased drop rate on the flow such that the information packets belonging to the flow have a higher probability of being dropped than information packets belonging to other flows that do not exhibit undesirable behavior.

8. The method of claim 1, wherein the penalty is enforced when a congestion condition is encountered.

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.

10. The method of claim 9, wherein the badness factor also provides an indication of a degree to which the flow is behaving undesirably.

11. The method of claim 10, further comprising:

determining, based at least partially upon the badness factor, a penalty to impose on the flow.

12. The method of claim 11, further comprising:

enforcing the penalty on the flow.

13. The method of claim 12, wherein enforcing the penalty on the flow causes the flow to exhibit less undesirable behavior, thereby, causing the badness factor of the flow to improve.

14. The method of claim 12, wherein the penalty is enforced on the flow when a congestion condition is encountered.

15. The method of claim 12, wherein no penalty is enforced on the flow unless a congestion condition is encountered, regardless of how undesirably the flow is behaving.

16. The method of claim 12, wherein the penalty is determined and enforced on the flow even when no congestion condition is encountered.

17. The method of claim 12, wherein determining the penalty comprises:

determining an increased drop rate to impose on one or more information packets belonging to the flow.

18. The method of claim 17, wherein enforcing the penalty comprises:

imposing the increased drop rate on the flow such that the information packets belonging to the flow have a higher probability of being dropped than information packets belonging to other flows that do not exhibit undesirable behavior.

19. The method of claim 9, wherein the set of behavioral statistics comprises a measure T of how much total information has been contained in all of the information packets belonging to the flow that have been forwarded up to a current point in time.

20. The method of claim 9, wherein the set of behavioral statistics comprises a measure L of how long the flow has been in existence up to a current point in time.

21. The method of claim 20, wherein the set of behavioral statistics comprises a rate R of information transfer for the flow, wherein R is derived by dividing T by L.

22. The method of claim 9, wherein the set of behavioral statistics comprises an average size for the information packets belonging to the flow.

23. The method of claim 9, wherein maintaining the set of behavioral statistics comprises:

receiving a particular information packet belonging to the flow;

determining whether to forward the particular information packet to a destination; and

in response to a determination to forward the particular information packet to the destination, updating the set of behavioral statistics to reflect processing of the particular information packet.

24. The method of claim 9, wherein maintaining the set of behavioral statistics comprises:

receiving a particular information packet belonging to the flow; and

updating the set of behavioral statistics to reflect processing of the particular information packet, regardless of whether the particular information packet is discarded or forwarded to a destination.

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.

26. The MFM of claim 25, wherein enforcing the penalty has an effect of correcting the flow'"'"'s behavior such that the flow exhibits less undesirable behavior.

27. The MFM of claim 25, wherein the means for enforcing the penalty comprises:

means for imposing an increased drop rate on the flow such that the information packets belonging to the flow have a higher probability of being dropped than information packets belonging to other flows that do not exhibit undesirable behavior.

28. The MFM of claim 25, wherein the penalty is enforced when a congestion condition is encountered.

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.

30. The MFM of claim 29, wherein the badness factor also provides an indication of a degree to which the flow is behaving undesirably.

31. The MFM of claim 30, further comprising:

means for determining, based at least partially upon the badness factor, a penalty to impose on the flow.

32. The MFM of claim 31, further comprising:

means for enforcing the penalty on the flow.

33. The MFM of claim 32, wherein enforcing the penalty on the flow causes the flow to exhibit less undesirable behavior, thereby, causing the badness factor of the flow to improve.

34. The MFM of claim 32, wherein the penalty is enforced on the flow when a congestion condition is encountered.

35. The MFM of claim 32, wherein no penalty is enforced on the flow unless a congestion condition is encountered, regardless of how undesirably the flow is behaving.

36. The MFM of claim 32, wherein the penalty is determined and enforced on the flow even when no congestion condition is encountered.

37. The MFM of claim 32, wherein the means for determining the penalty comprises:

means for determining an increased drop rate to impose on one or more information packets belonging to the flow.

38. The MFM of claim 37, wherein the means for enforcing the penalty comprises:

means for imposing the increased drop rate on the flow such that the information packets belonging to the flow have a higher probability of being dropped than information packets belonging to other flows that do not exhibit undesirable behavior.

39. The MFM of claim 29, wherein the set of behavioral statistics comprises a measure T of how much total information has been contained in all of the information packets belonging to the flow that have been forwarded up to a current point in time.

40. The MFM of claim 29, wherein the set of behavioral statistics comprises a measure L of how long the flow has been in existence up to a current point in time.

41. The MFM of claim 40, wherein the set of behavioral statistics comprises a rate R of information transfer for the flow, wherein R is derived by dividing T by L.

42. The MFM of claim 29, wherein the set of behavioral statistics comprises an average size for the information packets belonging to the flow.

43. The MFM of claim 29, wherein the means for maintaining the set of behavioral statistics comprises:

means for receiving a particular information packet belonging to the flow;

means for determining whether to forward the particular information packet to a destination; and

means for updating, in response to a determination to forward the particular information packet to the destination, the set of behavioral statistics to reflect processing of the particular information packet.

44. The MFM of claim 29, wherein the means for maintaining the set of behavioral statistics comprises:

means for receiving a particular information packet belonging to the flow; and

means for updating the set of behavioral statistics to reflect processing of the particular information packet, regardless of whether the particular information packet is discarded or forwarded to a destination.