System and method for hierarchical policing of flows and subflows of a data stream

• US 7,042,848 B2
• Filed: 05/04/2001
• Issued: 05/09/2006
• Est. Priority Date: 05/04/2001
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: SLT Logic LLC
• Inventors: Santiago, Rodolfo A., Sarkinen, Scott A.
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US09/849,810
• Publication Number:
  US 20020186661A1
• Time in Patent Office: 1,831 Days
• Field of Search: 370/232, 370/235, 370/252, 370/253, 370/392, 370/412, 370/468, 370/469, 370/230.1, 711/104, 709/238
• US Class Current: 370/253
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]

Abstract

A system and method for policing individual flows and subflows of a data stream. Data traffic streams are classified into separate traffic flows, which in turn can be further classified into subflows, thereby providing for different priority levels of subsets of the flow. The subflows may be still further classified into additional subflows, creating a hierarchical, layered prioritization that can be metered at each vertical and horizontal level of the hierarchy. A packet flow rate of each of the subflows is compared to a predefined rate limit to allow subflows of a flow to have different priorities therebetween.

Claims

1. A method for policing communications packets, comprising:

classifying the data stream into at least one traffic flow using information other than a Peak Information Rate (PIR) or a Committed Information Rate (CIR) to distinguish traffic flows;

classifying at least one of the traffic flows into a plurality of first level subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold; and

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows.

2. The method of claim 1, further comprising:

assigning a rate limit to each of the first level subflows; and

comparing each first level subflow to its corresponding rate limit.

3. The method of claim 2, wherein marking the packets comprises marking the packets based on whether the measured rate of each first level subflow exceeds its respective rate limit.

4. The method of claim 1, further comprising monitoring each of the traffic flows to determine whether each respective traffic flow has reached the predetermined bandwidth threshold.

5. The method of claim 4, wherein monitoring each of the traffic flows comprises monitoring for a triggering token level in a credit-token metering methodology.

6. The method of claim 1, further comprising adding a flow ID corresponding to the classified flow to a local header, and identifying a traffic flow to meter based on the flow ID.

7. The method of claim 1, further comprising adding a subflow ID corresponding to the classified subflow to a local header, and identifying the first level subflow in which its rate is to be measured based on the subflow ID.

8. The method of claim 1, wherein classifying the data stream based on layer-3 information comprises classifying the data stream based on at least one of a source address and a destination address.

9. The method of claim 1, wherein classifying at least one of the traffic flows into a plurality of first level subflows comprises classifying the traffic flow based on protocol layer information.

10. The method of claim 1, wherein measuring a rate of each of the first level subflows comprises metering each of the first level subflows using a credit-token methodology.

11. The method of claim 1, wherein measuring a rate of each of the first level subflows comprises metering each of the first level subflows using a color-based methodology.

12. The method of claim 1, wherein measuring a rate of each of the first level subflows comprises metering each of the first level subflows using an Frame Based Generic Cell Rate Algorithm (F-GCRA) methodology.

13. The method of claim 1, further comprising discarding packets of a non-conforming subflow which are marked with a conformance indicator indicating that the corresponding packets of the non-conforming subflow should be discarded.

14. The method of claim 13, further comprising forwarding packets of a conforming subflow which are marked with a conformance indicator indicating that the corresponding packets of the conforming subflow should not be discarded.

15. The method of claim 1, further comprising assigning a rate limit to each of the first level subflows, and wherein marking the packets comprises marking the packets associated with a subflow as non-conforming where the rate of the subflow exceeds its respective rate limit.

16. A method for policing communications packets, comprising:

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first subflows, classifying at least one of the first level subflows into a plurality of second level subflows,

measuring a rate of each of the first level subflows and second level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold; and

marking the packets associated with each of the first level subflows and the second level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows and second level subflows.

17. The method for policing communications packets, comprising:

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows, classifying at least one of the first level subflows into further levels of subflows to an n^th level of subflows;

measuring a rate of the first level subflows and n^th level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold; and

marking the packets associated with each of the first level subflows and the n^th level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows and the n^th level subflows.

18. A method for policing communications packets, comprising:

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows, classifying at least one of the first level subflows into further levels of subflows to an n^th level of subflows;

measuring a rate of each of the first level subflows and n^th level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold;

marking the packets associated with each of the first level subflows and the n^th level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows and the n^th level subflows;

assigning a rate limit to each of the n^th level subflows; and

comparing each n^th level subflow to its corresponding rate limit.

19. A method for policing communications packets comprising:

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows, classifying at least one of the first level subflows into further levels of subflows to an n^th level of subflows;

measuring a rate of each of the first level subflows and n^th level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold; and

marking the packets associated with each of the first level subflows and the n^th level subflows with one of a plurality of conformance indicators based on whether the measured rate of the respective first level subflows and the n^th level subflows exceed their respective rate limit.

20. A method for policing communications packets, comprising:

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows;

classifying at least one of the first level subflows into further levels of subflows to an n^th level of subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold;

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows;

measuring a rate of each of the n^th level subflows associated with its parent subflow; and

marking the packets associated with each of the n^th level subflows with one of a plurality of conformance indicators based on the measured rate of the respective n^th level subflow.

21. A method for policing communications packets comprising:

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold;

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows; and

assigning a priority level to each of the first level subflows, wherein at least two of the priority levels are different so that at least one of the first level subflows has priority over another of the first level subflows.

22. A method for policing communications packets comprising:

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold;

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows; and

assigning a priority level to each of the first level subflows, wherein at least two of the priority levels are different so that at least one of the first level subflows has priority over another of the first level subflows wherein the priority levels are effected by associating a rate limit with each of the subflows, and wherein marking the packets based on the measured rate comprises marking the packets based on whether the rate limit is exceeded for the corresponding subflow.

23. A method for policing communications packets, comprising;

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows based on layer-4 protocol layer information;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold; and

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows wherein classifying at least one of the traffic flows into a plurality of first level subflows comprises classifying the traffic flow based on protocol layer information.

24. A method for policing communications packets, comprising:

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows based on layer-4 protocol layer information, and based on at least a port number;

measuring a rate of each of the first level subflow associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold; and

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows wherein classifying at least one of the traffic flows into a plurality of first level subflows comprises classifying the traffic flow based on protocol layer information.

25. A method for policing communications packets, comprising:

classifying a data stream into at least one traffic flow;

classifying the at least one of the traffic flows into a plurality of first level subflows;

wherein classifying the data stream and classifying the at least one of the traffic flows into a plurality of first level subflows comprises classifying the data stream and traffic flows based on any predetermined one or more fields in any embedded header of each packet;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold; and

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows.

26. A method for policing communication packets comprising:

classifying a data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold;

assigning a rate limit to each of the first level subflows; and

marking the packets associated with each of the first level subflow with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows wherein marking the packets comprises marking the packets associated with a subflow as conforming where the rate of the subflow exceeds its respective rate limit but remains within the predetermined bandwidth threshold of the traffic flow.

27. A method for policing communications packets comprising:

classifying at least one of the traffic flows into a plurality of first level subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold;

assigning a rate limit to each of the first level subflows; and

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows wherein marking the packets comprises;

marking the packets associated with a subflow as conforming where the rate of the sub flow exceeds its respective rate limit but remains within the predetermined bandwidth threshold of the traffic flow; and

marking the packets associated with the subflow as non-conforming where the rate of the subflow exceeds both its respective rate limit and the predetermined bandwidth threshold of the traffic flow.

28. A method for policing communications packets comprising:

classifying the data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold;

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows; and

allocating substantially all of the available bandwidth of the traffic flow to one of the subflows where the traffic flow has reached the predetermined bandwidth threshold and the other subflow are not utilizing bandwidth.

29. A method for policing communications packets comprising:

classifying the data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold;

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows wherein marking the packets further comprises;

marking the packets associated with the one subflow as conforming where the rate of the subflow exceeds its respective rate limit but remains within the predetermined bandwidth threshold of the traffic flow; and

marking the packets associated with the subflow as non-conforming where the rate of the subflow exceeds both its respective rate limit and the predetermined bandwidth threshold of the traffic flow; and

allocating substantially all of the available bandwidth of the traffic flow to one of the subflows where the traffic flow has reached the predetermined bandwidth threshold and the other subflows are not utilizing bandwidth.

30. A method for policing communications packets comprising:

classifying the data stream into at least one traffic flow;

classifying at least one of the traffic flows into a plurality of first level subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold;

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflows; and

assigning a rate limit to each of the first level subflows and allocating the available bandwidth of the traffic flow to a plurality of the subflows if the traffic flow has reached the predetermined bandwidth threshold, wherein the available bandwidth of the traffic flow is allocated to the plurality of subflows based on their respective rate limits and demand for bandwidth.

31. A method for providing layered policing of packets of a data stream, comprising:

parsing a data stream into a plurality of flows;

for any of the flows, identifying at least one characteristic other than a Peak Information Rate (PIR) or a Committed Information Rate (CIR) common to a first subset of the flow;

associating a first drop probability with each of the packets of the first subset having the common characteristic, and associating a second drop probability to at least one other subset of the flow, thereby providing different drop probabilities for different subsets of the flow.

32. The method of claim 31, wherein the first drop probability indicates that the packets of the first subset are to be dropped.

33. The method of claim 32, wherein the second drop probability indicates that the packets of the at least one other subset are not to be dropped.

34. The method of claim 31, wherein the first drop probability indicates that the packets of the first subset have a greater likelihood of being dropped prior to the at least one other subset of the flow.

35. The method of claim 31, wherein parsing the data stream comprises respectively grouping the packets having predetermined common characteristics into the flows.

36. The method of claim 35, wherein grouping the packets having predetermined common characteristics comprises grouping those packets having predetermined information in one or more header fields embedded in the packet.

37. The method of claim 36, wherein the one or more header fields comprise header fields of a network layer header.

38. The method of claim 37, wherein the header fields of the network layer header comprises at least one of a source address and a destination address.

39. The method of claim 31, wherein identifying at least one characteristic common to the first subset of the flow comprises identifying common information in one or more header fields embedded in the packets to distinguish the first subset from the other subsets of the flow.

40. The method of claim 39, wherein the one or more header fields comprise header fields of a transport layer header.

41. The method of claim 40, wherein the header fields of the transport layer header comprises a port number.

42. The method of claim 31:

further comprising identifying at least one characteristic common to a second subset of the flow; and

wherein associating a second drop probability to at least one other subset of the flow comprises associating the second drop probability with each of the packets of the second subset of the flow.

43. The method of claim 42, wherein the first arid second drop probabilities are equivalent.

44. The method of claim 42, wherein the first and second drop probabilities are different.

45. The method of claim 31, wherein one of the subsets of the flow comprises all packets otherwise not associated with a subset defined by having common characteristics.

46. A method for providing layered policing of packets of a data stream comprising:

parsing the data stream into a plurality of flows;

for any of the flows, identifying at least a first characteristic common to a first subset of the flow;

associating a first drop probability with each of the packets of the first subset having the first characteristic in common;

identifying at least a second characteristic common to a second subset of the flow;

associating a second drop probability with each of the packets of the second substrate of the flow; and

identifying at least one characteristic common to an n^th subset of the flow; and

associating the second drop probability with each of the packets of the n^th subset of the flow.

47. A packet policing system for providing layered policing of packets of a data stream, comprising:

means for classifying the data stream into at least one traffic flow using information other than a Peak Information Rate (PIR) or a Committed Information Rate (CIR) to distinguish the traffic flows;

means for classifying at least one of the traffic flows into a plurality of first level subflows;

means for measuring the packet rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold; and

means for marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured packet rate of the respective first level subflow.

48. A packet policing apparatus for providing layered policing of packets of a data stream, comprising:

means for parsing the data stream into a plurality of flows using information other than a Peak Information Rate (PIR) or a Committed Information Rate (CIR) to distinguish the traffic flows;

for any of the flows, means for identifying at least one characteristic common to a first subset of the flaw;

means for associating a first drop probability with each of the packets of the first subset having the common characteristic, and means for associating a second drop probability to at least one other subset of the flow, thereby providing different drop probabilities for different subsets of the flow.

49. A computer-readable medium having computer-executable instructions for policing communications packets, the computer-executable instructions performing steps comprising:

classifying the data stream into at least one traffic flow using information other than a Peak Information Rate (PIR) or a Committed Information Rate (CIR) to distinguish the traffic flows;

classifying at least one of the traffic flows into a plurality of first level subflows;

measuring a rate of each of the first level subflows associated with the traffic flow when the traffic flow reaches a predetermined bandwidth threshold; and

marking the packets associated with each of the first level subflows with one of a plurality of conformance indicators based on the measured rate of the respective first level subflow.