Mechanism for identifying and penalizing misbehaving flows in a network

• US 20060133280A1
• Filed: 12/22/2004
• Published: 06/22/2006
• Est. Priority Date: 12/22/2004
• Status: Active Grant

• Current Assignee: Sable Networks, Inc.
• Original Assignee: Sable Networks, Inc.
• Inventors: Natchu, Vishnu
• Granted Patent: US 8,243,593 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• 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 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 are updated as information packets belonging to the flow are processed;

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.

2. 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.

3. 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.

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

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 are updated as information packets belonging to the flow are processed; 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.

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

7. The method of claim 6, further comprising:

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

8. The method of claim 7, further comprising:

enforcing the penalty on the flow.

9. The method of claim 8, 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.

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

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

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

13. The method of claim 8, wherein determining the penalty comprises:

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

14. The method of claim 13, 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.

15. The method of claim 5, 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.

16. The method of claim 5, 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.

17. The method of claim 16, 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.

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

19. The method of claim 5, 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.

20. The method of claim 5, 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.

21. 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 are updated as information packets belonging to the flow are processed;

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.

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

23. The MFM of claim 21, 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.

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

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 are updated as information packets belonging to the flow are processed; 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.

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

27. The MFM of claim 26, further comprising:

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

28. The MFM of claim 27, further comprising:

means for enforcing the penalty on the flow.

29. The MFM of claim 28, 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.

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

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

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

33. The MFM of claim 28, 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.

34. The MFM of claim 33, 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.

35. The MFM of claim 25, 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.

36. The MFM of claim 25, 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.

37. The MFM of claim 36, 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.

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

39. The MFM of claim 25, 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.

40. The MFM of claim 25, 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.