Apparatus and method for metering and marking data in a communication system

• US 7,664,028 B1
• Filed: 03/05/2002
• Issued: 02/16/2010
• Est. Priority Date: 03/05/2001
• Status: Expired due to Fees

• Current Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Original Assignee: Pmc-Sierra Limited (Microchip Technology Incorporated)
• Inventors: Reynolds, Scott, Gingras, Sylvain
• Primary Examiner(s): Trost, IV; William
• Assistant Examiner(s): Nguyen; Toan D
• Application Number:
  US10/093,092
• Time in Patent Office: 2,905 Days
• Field of Search: 370/253, 370/235.1, 370/229, 370/230, 370/231, 370/232, 370/235, 370/236, 370/450, 370/466, 370/467, 379/1.01, 379/24, 379/28, 379/32.01, 709/232
• US Class Current: 370/235
• CPC Class Codes: H04L 41/5022 by giving priorities, e.g. assigning classes of service
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits

Abstract

A system and/or method for metering and marking packets of data incoming into a communication system having in some embodiments primary and secondary meter selectors, primary and secondary metering processors and a pipeline and wrapper interface controller. Further methods involve measuring an incoming microflow against one or two specified temporal profiles using a two-level metering hierarchy.

Claims

1. A metering and marking processor (MMP) telecom system block apparatus comprising:

a metering processor measuring incoming digital data unit microflow against one or two specified temporal profiles using an at least two-level metering hierarchy;

a marking function using results of one and/or two metering operations to provide an action instruction for a downstream digital data unit handling device to perform an appropriate action on said corresponding digital data unit;

an action tag field of a context header record (CHR) specifying said action instruction;

one or more additional fields of said context header record in which said MMP provides other information for a downstream digital data unit handling device use;

and further comprising;

one or more primary digital data unit meters;

one or more secondary digital data unit meters

each said primary and secondary digital data unit meters including two token buckets; and

each said meter configurable to implement a metering algorithm using one or both of its token buckets.

2. The apparatus according to claim 1 further wherein said incoming digital data unit microflows are identified by a flow tag inserted in a context header record (CHR) by an upstream digital data unit handling component.

3. The apparatus according to claim 1 further wherein:

incoming digital data units are assigned to be metered by a particular primary meter using a flow tag of said incoming digital data units; and

said incoming digital data units are assigned to be metered by a particular secondary meter using results of an assigned primary meter.

4. The apparatus according to claim 1 further wherein the meters implement token-bucket-oriented metering algorithms and include a plurality of token buckets that can be configured for either plural or single bucket operation and further wherein said MMP implements three metering schemes:

Single Rate Dual-Bucket, Two Rate Dual-Bucket, and Single Bucket.

5. A metering and marking digital data unit handling module apparatus comprising:

a primary meter selector processor;

a primary metering processor;

a secondary metering processor;

said primary metering processor and said secondary metering processor providing a two-level metering hierarchy;

said primary metering processor performing microflow metering;

said secondary metering processor performing aggregate metering;

a metering algorithm processor;

a wrapper;

a pipeline and wrapper interface controller;

said primary and secondary metering processors including two token buckets; and

said primary and secondary metering processors configurable to implement a metering algorithm using one or both of its token buckets.

6. The apparatus according to claim 5 further comprising:

two pipeline schedules.

7. A method of managing incoming data transmissions comprising:

measuring an incoming digital data unit microflow against two specified temporal profiles using a two-level metering hierarchy; and

based on results of two metering operations, providing an action instruction for a downstream device to perform an appropriate action on said corresponding digital data unit;

wherein said two-level metering hierarchy includes two token buckets; and

wherein said two-level metering hierarchy is configurable to implement a metering algorithm using one or both of its token buckets;

further wherein said action instruction comprises an action code, action data, and an action mask and wherein said action code, said action data and said action mask are configurable by a user;

further wherein said incoming digital data unit microflows are identified by a flow tag inserted in a context header record (CHR) by an upstream component; and

providing said action instruction to said downstream device to perform said appropriate action on said corresponding data unit.

8. The method according to claim 7 further wherein said action data and said action mask can be used by said downstream device to perform a bit-selective modification of a type of service (ToS) field in said digital data unit.

9. The method according to claim 7 further comprising:

providing counter selection information for downstream statistics.

10. The method according to claim 7 further comprising:

using primary meters and secondary meters, each meter having at least two token buckets and configured to implement a specific metering algorithm using one or both of its token buckets and wherein said configuring is determined by data stored in a data structure and settable by an external management function.

11. The method according to claim 10 further comprising:

using a floating point number to indicate a bucket rate;

using a fixed point number to indicate a token count;

using a fixed point number to indicate a timestamp;

wherein use of a floating point rate provides a consistent percentage granularity in specification of a rate while reducing memory space needed;

wherein said fixed point token count and said timestamp provide byte-based granularity and simplified arithmetic.

12. The method according to claim 11 further wherein said token count is kept for each meter and wherein the result of a multiplication of the rate and elapsed time is always rounded up.

13. The method according to claim 11 further comprising:

setting a saturation flag in meter data structures to perform synchronous background updates.

14. The method according to claim 11 further comprising:

using a synchronous update process to provide a background refresh operation when using dynamic memory to implement meter tables in order to save bandwidth to memory and increase a digital data unit processing rate.

15. The method according to claim 11 further comprising:

using a 4-valued counter selector to provide counting for 6 distinct transitions between input color and conformance result.

16. The method according to claim 7 further wherein a metering structure identifying meters to be used for primary and secondary metering is specified through meter selectors that include a color to be input to a metering algorithm of a given meter.

17. The method according to claim 7 further wherein the action to be performed on a digital data unit based on a conformance level from a metering operation of the one or more metering operations is specified through an action selector.

18. The method according to claim 7 further wherein:

the action to be performed on the digital data unit based on a conformance level from said one or two metering operation is specified through an action selector;

wherein said action selector can indicate one of;

NO ACTION;

DISCARD;

REMARK.

19. The method according to claim 18 wherein said action selector further comprises:

a remarking data subfield; and

a remarking data mask subfield.

20. The method according to claim 7 further wherein:

the action to be performed on a digital data unit based on a conformance level from a metering operation of the one or more metering operations is specified through an action selector and wherein said action selector can indicate one of a several actions specified by a user.

21. The method according to claim 7 further comprising:

allowing separate actions to be defined for each possible outcome of each of a plurality of primary and secondary meters;

including in a secondary meter action selector a configuration indication to select whether the action to be applied to said digital data unit should be that associated with a primary metering operation or that associated with a secondary metering operation.

22. The method according to claim 21 further wherein said configuration indication further comprises:

a state indicating that a worst action from said primary meter and said secondary meter should be applied to a digital data unit.

23. The method according to claim 7 wherein a further configuration indication allows an action for a given metering result to be skipped if a conformance result corresponds to an input color of the digital data unit.

24. A network digital data unit router comprising:

one or more channel interfaces for sending and receiving digital data units on a data network;

one or more processors for processing said digital data units;

memory for temporarily storing said digital data units while determining processing of said digital data units;

a metering and marking function comprising;

a primary meter selector processor (pmsp);

a primary metering processor (pmp);

a secondary metering processor (smp); and

a metering algorithm processor (map) a wrapper; and

a pipeline and wrapper interface controller;

said primary metering processor and said secondary metering processor providing a two-level metering hierarchy;

said primary metering processor performing microflow metering;

said secondary metering processor performing aggregate metering;

wherein said two-level metering hierarchy includes two token buckets; and

wherein said two-level metering hierarchy is configurable to implement a metering algorithm using one or both of its token buckets.

25. A communications system comprising:

a plurality of routers, at least one router according to claim 24; and

a network communication media; and

a plurality of interfaces to destinations.

26. A computer readable medium containing computer interpretable instructions that when loaded into an appropriately configuration information processing device will cause said information processing device to embody all the network digital data unit router of claim 24.

27. A method of handling incoming data transmission in a communication system using a two-level metering hierarchy comprising:

performing a first metering operation; and

performing a second metering operation;

wherein a second meter identifier is determined by the result of the first metering operation; and

wherein an input color to said second metering operation is determined by the result of the first metering operation;

further wherein said first metering operation is performed using one of a large number of primary meters; and

said second metering operation is performed using one of a smaller number of secondary meters; and

providing results of said second metering operation to a downstream device to perform an appropriate action on the corresponding data transmission.

28. The method according to claim 27 wherein said smaller number of said secondary meters is about half said large number of said primary meters.

29. The method according to claim 27 wherein said smaller number of said secondary meters is about one order of magnitude less than said large number of said primary meters.

30. The method according to claim 27 further comprising:

reading a flow tag for an incoming data unit read from a context header record; and

selecting a first meter for said first metering operation using said flow tag.

31. The method according to claim 30 further comprising:

reading an input color for said incoming data unit read from the context header record; and

using said input color in said first metering operation.

32. The method according to claim 27 further comprising:

said first metering operation outputting an action instruction for a data unit.

33. The method according to claim 32 further wherein said action instruction comprises one or more of:

an action instruction code;

action instruction data; and

an action instruction mask.

34. The method according to claim 32 further comprising:

storing said action instruction in a record for said data so that a downstream component can read said action instruction to perform an appropriate action on said data unit.

35. The method according to claim 27 further comprising:

said second metering operation outputting an action instruction for a data unit.

36. The method according to claim 27 further comprising:

at said first metering operation, determining a color for an incoming digital data unit;

based on said color, selecting a second level meter from metering identifications stored in association with said first meter.

37. The method according to claim 36 further wherein:

if the first metering operation yields GREEN, selecting a first of said second level meter;

if the first metering operation yields YELLOW, selecting a second of said second level meter;

if the first metering operation yields RED, selecting a third of said second level meter.

38. The method according to claim 36 further comprising:

selecting a primary meter selector, comprising a pointer to a primary meter and a first input color code, based on a flow tag;

performing primary metering using a primary meter and first input color;

selecting a secondary meter selector, comprising a pointer to a secondary meter and a

second input color code, based on the primary metering result; and

performing the secondary metering using the secondary meter and the second input color.

39. The method according to claim 27 further wherein:

said first level metering is performed on a fine grain and said second level metering is performed on a coarse grain.

40. The method according to claim 27 further comprising:

providing said two-level metering hierarchy in an internet protocol digital data unit handling device, wherein said two-level metering provides microflow handling at a consumer edge of a network system and aggregate marking to allowing data to be handled as aggregate data in the core of the network system.