Efficient traffic management

• US 10,432,429 B1
• Filed: 10/11/2016
• Issued: 10/01/2019
• Est. Priority Date: 02/16/2016
• Status: Active Grant

• Current Assignee: Innovium, Inc. (Marvell Technology Group Limited)
• Original Assignee: Innovium, Inc. (Marvell Technology Group Limited)
• Inventors: Matthews, William Brad, Kim, Paul, Kwan, Bruce, Agarwal, Puneet
• Primary Examiner(s): Henson, Jamaal
• Application Number:
  US15/290,769
• Time in Patent Office: 1,085 Days
• Field of Search: None
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

A token bucket or leaky bucket is maintained at least partially through the use of two separate counters. A full counter, is maintained in relatively lower cost memory, and indicates the amount of tokens within the bucket on a potentially delayed basis. An intermediate counter is stored in a relatively higher cost memory that supports high access rates, and indicates the amount of tokens assigned (or unassigned) to the bucket since the full counter was last updated. Various adjustment processes remove (or add) tokens as needed for performing tasks. A background process updates the full counter from the corresponding intermediate counter on a periodic, scheduled, or other basis. The buckets are replenished (or deleted) with tokens periodically at assigned rates. Traffic management or other decisions are based on the bucket'"'"'s current status, as determined from the full counter during the background process and then stored in the higher cost memory.

Claims

1. A networking apparatus comprising:

communication interfaces coupled to one or more networks;

a message handling subsystem configured to process messages received over the communication interfaces;

a traffic management subsystem configured to apply traffic shaping or traffic policing logic to specific messages of the messages selected based on status indicators associated with traffic action control groups to which the specific messages are assigned;

one or more first memories configured to store full counters associated with the traffic action control groups;

one or more second memories configured to store intermediate counters associated with the traffic action control groups, the one or more second memories being different than the one or more first memories, each of the intermediate counters corresponding to a different one of the full counters;

an intermediate counting subsystem configured to adjust particular intermediate counters for particular traffic action control groups by amounts corresponding to particular messages sent over the communication interfaces in association with the particular traffic action control groups;

a full count update subsystem configured to update the full counters based on respectively corresponding intermediate counters, and to reset the corresponding intermediate counters;

a replenishment subsystem configured to update the intermediate counters or to update the full counters, based on replenishment amounts determined from replenishment rates associated with the traffic action control groups;

a status update subsystem configured to update the status indicators by comparing the full counters to one or more applicable thresholds.

2. The apparatus of claim 1, further comprising an update scheduler configured to identify times for the full count update subsystem to update specific full counters of the full counters and for the status update subsystems to update specific status indicators of the status indicators, the update scheduler configured to identify the times based on one or more of the replenishment rates and/or magnitudes of the intermediate counters.

3. The apparatus of claim 1, wherein the full count update subsystem is configured to only update a limited number of the full counters in a given set of one or more clock cycles, wherein the intermediate counting subsystem is not restricted to updating the limited number of the intermediate counters in the given set of one or more clock cycles.

4. The apparatus of claim 1,

wherein a given full counter, of the full counters, represents a token bucket for a given traffic action control group, of the traffic action control groups, that is associated with the given full counter;

wherein adjusting a given intermediate counter, of the intermediate counters, that corresponds to the given full counter comprises decrementing the given full counter by amounts of tokens needed to send given messages associated with the given traffic action control group;

wherein updating the given full counter based on the given intermediate counter comprises adding the given intermediate counter to the given full counter and resetting the given intermediate counter;

wherein updating the given intermediate counter or the given full counter by a given replenishment amount determined based on a given replenishment rate that is associated with the given traffic action control group comprises incrementing the given intermediate counter or the given full counter based on the given replenishment amount.

5. The apparatus of claim 1,

wherein a given full counter, of the full counters, represents a leaky bucket for a given traffic action control group, of the traffic action control groups, that is associated with the given full counter;

wherein adjusting a given intermediate counter, of the intermediate counters, that corresponds to the given full counter comprises incrementing the given intermediate counter by amounts of tokens needed to send given messages associated with the given traffic action control group;

wherein updating the given full counter based on the given intermediate counter comprises adding the given intermediate counter to the given full counter and resetting the given intermediate counter;

wherein updating the given intermediate counter or the given full counter by a given replenishment amount determined based on a given replenishment rate that is associated with the given traffic action control group comprises decrementing the given intermediate counter or the given full counter based on the given replenishment amount.

6. The apparatus of claim 1,

wherein the one or more second memories are further configured to store the status indicators;

wherein the one or more first memories are single-ported memories;

wherein the one or more second memories are registers.

7. A method comprising:

storing full counters in one or more first memories;

storing intermediate counters in one or more second memories;

identifying traffic action control groups associated with messages being processed within a networking device, each of the traffic action control groups assigned to at least a different one of the intermediate counters and at least a different one of the full counters;

when particular messages, associated with corresponding groups of the traffic action control groups, are forwarded to one or more next components, adjusting respectively assigned intermediate counters;

recurrently updating the full counters by combining full counts of the full counters with intermediate counts of the respectively assigned intermediate counters, and resetting the respectively assigned intermediate counters;

based on replenishment rates assigned to the traffic action control groups, recurrently replenishing the full counters or recurrently replenishing the intermediate counters;

determining when to enforce a network traffic management rule or policy against a given group, of the traffic action control groups, based at least on a current value of a given full counter, of the full counters, that is assigned to the given group.

8. The method of claim 7, further comprising:

storing status indicators for the traffic action control groups in the one or more second memories, each of the traffic action control groups assigned to at least a different one of the status indicators;

recurrently updating the status indicators for the traffic action control groups based on comparing the respectively assigned full counters for the traffic action control groups to one or more thresholds for corresponding status indicators;

wherein determining when to enforce the network traffic management rule or policy comprises determining when to enforce the network traffic management rule or policy based on a given status indicator, of the status indicators, that is assigned to the given group.

9. The method of claim 8, wherein updating the full counters and updating the status indicators are both performed less frequently than the particular messages are forwarded.

10. The method of claim 8, wherein updating the status indicators comprises updating the given status indicator responsive to updating the given full counter.

11. The method of claim 8, further comprising updating the full counters and updating the status indicators asynchronously relative to the forwarding the particular messages.

12. The method of claim 8, wherein the one or more thresholds include a first threshold for a first full counter of the full counters and a second threshold for a second full counter of the full counters, the first threshold being different than the second threshold.

13. The method of claim 12, further comprising storing the one or more thresholds in the one or more first memories.

14. The method of claim 7, wherein the one or more second memories support higher access rates than the one or more first memories.

15. The method of claim 7,

wherein adjusting the respectively assigned intermediate counters comprises, for a particular message, decrementing a particular intermediate counter associated with the particular message based on an amount of tokens associated with the particular message;

wherein replenishing the full counters or replenishing the intermediate counters comprises adding amounts of tokens to the full counters or the intermediate counters based on the replenishment rates;

wherein determining when to enforce the network traffic management rule or policy comprises determining to enforce the network traffic management rule or policy after the given full counter falls below a given threshold value.

16. The method of claim 7,

wherein adjusting the respectively assigned intermediate counters comprises, for a particular message, incrementing a particular intermediate counter associated with the particular message based on an amount of tokens associated with the particular message;

wherein replenishing at least one of the full counters or the intermediate counters comprises removing amounts of tokens from the at least one of the full counters or the intermediate counters based on the replenishment rates;

wherein determining when to enforce the network traffic management rule or policy comprises determining to enforce the network traffic management rule or policy after the given full counter rises above a given threshold value.

17. The method of claim 7, wherein the method further comprises:

determining when to enforce multiple network traffic management rules or policies against the given group;

wherein multiple full counters, of the full counters, and multiple intermediate counters, of the intermediate counters, are assigned to the given group, each of the multiple full counters having a different replenishment rate, of the replenishment rates;

wherein each of the multiple network traffic control rules or policies is associated with a different one of the multiple full counters assigned to the given group.

18. The method of claim 7, wherein the replenishment rates correspond to at least one of:

a minimum bandwidth guarantee, a maximum bandwidth limit, or a bandwidth throttling threshold.

19. The method of claim 7, wherein the traffic action control groups are groupings of messages selected based on one or more of:

incoming ports, outgoing ports, traffic classes, protocols, incoming addresses, outgoing addresses, traffic flow identifiers, or message queues.

20. The method of claim 7, wherein enforcing the network traffic control rule or policy comprises one or more of:

delaying a message, dropping a message, flagging a message, or changing a service class of a message.

21. One or more non-transitory computer-readable media storing instructions that, when executed by one or more computer devices, cause:

storing full counters in one or more first memories;

storing intermediate counters in one or more second memories;

identifying traffic action control groups associated with messages being processed within a networking device, each of the traffic action control groups assigned to at least a different one of the intermediate counters and at least a different one of the full counters;

when particular messages, associated with corresponding groups of the traffic action control groups, are forwarded to one or more next components, adjusting respectively assigned intermediate counters;

recurrently updating the full counters by combining full counts of the full counters with intermediate counts of the respectively assigned intermediate counters, and resetting the respectively assigned intermediate counters;

based on replenishment rates assigned to the traffic action control groups, recurrently replenishing the full counters or recurrently replenishing the intermediate counters;

determining when to enforce a network traffic management rule or policy against a given group, of the traffic action control groups, based at least on a current value of a given full counter, of the full counters, that is assigned to the given group.