METER-BASED HIERARCHICAL BANDWIDTH SHARING

• US 20110002222A1
• Filed: 09/14/2010
• Published: 01/06/2011
• Est. Priority Date: 08/26/2008
• Status: Active Grant

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Kwan, Bruce, Agarwal, Puneet
• Granted Patent: US 8,446,831 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/215 using token-bucket
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits

Abstract

Example methods and apparatus for hierarchical bandwidth management are disclosed. An example method includes, receiving a data packet included in a first data traffic flow having a first rate of traffic. The example method further includes marking the data packet with a first marker type if the first rate of traffic is less than or equal to a first threshold, otherwise marking the data packet with a second marker type. The example method also includes combining the first data traffic flow with a second data traffic flow having a second rate of traffic to produce a third data traffic flow having a third rate of traffic. The example method still further includes, if the data packet is marked with the first marker type, forwarding the data packet in the third data flow. The example method yet further includes, if the data packet is marked with the second marker type and the third rate of traffic is less than or equal to a second threshold, forwarding the data packet in the third data flow, otherwise, discarding the packet.

Claims

1. A method for communicating data comprising:

receiving a data packet included in a first data traffic flow having a first rate of traffic;

marking the data packet with a first marker type if the first rate of traffic is less than or equal to a first threshold, otherwise marking the data packet with a second marker type;

combining the first data traffic flow with a second data traffic flow having a second rate of traffic to produce a third data traffic flow having a third rate of traffic;

if the data packet is marked with the first marker type, forwarding the data packet in the third data flow; and

if the data packet is marked with the second marker type and the third rate of traffic is less than or equal to a second threshold, forwarding the data packet in the third data flow, otherwise, discarding the packet.

2. The method of claim 1, wherein if the data packet is marked with the second marker type and the third rate of traffic is less than or equal to the second threshold, the method further comprises changing the second marker type to the first marker type.

3. The method of claim 1, wherein:

the first marker type designates the data packet as green; and

the second marker type designates the data packet as red.

4. The method of claim 1, wherein:

the first marker type designates the data packet as green; and

the second marker type designates the data packet as yellow.

5. The method of claim 1, further comprising:

combining the third traffic flow with a fourth data traffic flow having a fourth rate of traffic to produce a fifth data traffic flow having a fifth rate of traffic; and

determining whether to discard the data packet or forward the data packet in the fifth data traffic flow based on the data packet'"'"'s marker type, the fifth rate of traffic and a third threshold.

6. The method of claim 1, further comprising discarding the data packet if the first rate of traffic is greater than a third threshold, the third threshold being greater than the first threshold.

7. The method of claim 1, further comprising marking the data packet with a third marker type in place of marking the packet with the second marker type and discarding the data packet from the third data flow if the first rate of traffic is greater than a third threshold, the third threshold being greater than the first threshold.

8. The method of claim 7, wherein:

the first marker type designates the packet as green;

the second marker type designates the packet as yellow; and

the third marker type designates the packet as red.

9. The method of claim 1, wherein:

determining whether the first rate of traffic is less than or equal to the first threshold comprises determining whether a positive token count is present in a single token bucket meter associated with the first data traffic flow; and

determining whether the third rate of traffic is less than or equal to the second threshold comprises determining whether a positive token count is present in a single token bucket meter associated with the third data traffic flow.

10. The method of claim 9, wherein if the token count of the single token bucket meter associated with the first data traffic flow is positive, forwarding the data packet in the third data traffic flow comprises:

decrementing the token count of the single token bucket meter associated with the first data traffic flow by an amount of tokens proportional to a size of the data packet; and

decrementing the token count of the single token bucket meter associated with the third data traffic flow by the amount of tokens proportional to the size of the data packet.

11. The method of claim 1, wherein:

determining whether the first rate of traffic is less than or equal to the first threshold comprises determining whether a positive token count is present in a first token bucket of a two-rate three-color meter (trTCM) associated with the first data traffic flow; and

determining whether the third rate of traffic is less than or equal to the second threshold comprises determining whether a positive token count is present in a single token bucket meter associated with the third data traffic flow.

12. The method of claim 11, wherein if the token count of the first token bucket is positive, forwarding the data packet in the third data flow comprises:

decrementing the token count of the first token bucket by an amount of tokens proportional to a size of the data packet; and

decrementing the token count of the single token bucket meter associated with the third data traffic flow by the amount of tokens proportional to the size of the data packet.

13. The method of claim 1, further comprising:

periodically adding tokens to a first single token bucket meter associated with the first data traffic flow, wherein;

the first single token bucket meter is configured to determine whether the first traffic rate is less than or equal to the first threshold based on a token count of the first single token bucket meter; and

tokens are added to the first token bucket meter at a rate proportional to the first threshold and up to an amount corresponding with a depth of the first token bucket meter; and

periodically adding tokens to a second single token bucket meter associated with the third data traffic flow, wherein;

the second single token bucket meter is configured to determine whether the third traffic rate is less than or equal to the second threshold based on a token count of the second single token bucket meter; and

tokens are added to the second token bucket meter at a rate proportional to the second threshold up to an amount corresponding with a depth of the second token bucket meter.

14. The method of claim 1, further comprising:

periodically adding tokens to a first token bucket of a two-rate three-color meter (trTCM) associated with the first data traffic flow, wherein;

the trTCM is configured to determine whether the first traffic rate is less than or equal to the first threshold based on a token count of the first token bucket; and

tokens are added to the first token bucket at a rate proportional to the first threshold and up to an amount corresponding with a depth of the first token bucket;

periodically adding tokens to a second token bucket of the trTCM, wherein;

the trTCM is configured to determine whether the first traffic rate is less than or equal to a third threshold based on a token count of the second token bucket, the third threshold being greater than the second threshold; and

tokens are added to the second token bucket at a rate proportional to the third threshold minus the first threshold and up to an amount corresponding with a depth of the second token bucket; and

periodically adding tokens to a single token bucket meter associated with the third data traffic flow, wherein;

the single token bucket meter is configured to determine whether the third traffic rate is less than or equal to the second threshold based on a token count of the single token bucket meter; and

tokens are added to the single token bucket meter at a rate proportional to the second threshold up to an amount corresponding with a depth of the single token bucket meter.

15. A method for communicating data comprising:

receiving a data packet included in a first data traffic flow having a first rate of traffic;

marking the data packet with a first marker type if the first rate of traffic is less than or equal to a first threshold, otherwise marking the data packet with a second marker type;

combining the first data traffic flow with a second data traffic flow having a second rate of traffic to produce a third data traffic flow having a third rate of traffic;

if the data packet is marked with the second marker type and the third rate of traffic is less than or equal to a second threshold, changing the second marker type to the first marker type;

providing the third data traffic flow to a data queue having a first admission threshold and a second admission threshold, the second admission threshold being greater than the first admission threshold;

if the data packet is marked with the second marker type;

forwarding the data packet to a destination of the packet if an amount of data in the data queue is less than or equal to the first admission threshold, otherwise, discarding the packet; and

if the data packet is marked with the first marker type;

forwarding the data packet to a destination of the packet if an amount of data in the data queue is less than or equal to the second admission threshold, otherwise, discarding the packet.

16. The method of claim 15, wherein:

the first marker type designates the data packet as green; and

the second marker type designates the data packet as red.

17. The method of claim 15, wherein:

determining whether the first rate of traffic is less than or equal to the first threshold comprises determining whether a positive token count is present in a single token bucket meter associated with the first data traffic flow; and

determining whether the third rate of traffic is less than or equal to the second threshold comprises determining whether a positive token count is present in a single token bucket meter associated with the third data traffic flow.

18. The method of claim 17, wherein if the token count of the single token bucket meter associated with the first data traffic flow is positive, providing the data packet to the data queue in the third data traffic flow comprises:

decrementing the token count of the single token bucket meter associated with the first data traffic flow by an amount of tokens proportional to a size of the data packet; and

decrementing the token count of the single token bucket meter associated with the third data traffic flow by the amount of tokens proportional to the size of the data packet.

19. The method of claim 15, wherein in the event the data packet marker is changed from the second marker type to the first marker type, providing the data packet to the data queue comprises decrementing a token count of a single token bucket meter associated with the third data traffic flow by an amount of tokens proportional to a size of the data packet.

20. An apparatus comprising:

a first data traffic meter configured to;

receive a data packet included in a first data traffic flow having a first rate of traffic; and

mark the data packet with a first marker type if the first rate of traffic is less than or equal to a first threshold, otherwise mark the data packet with a second marker type;

a scheduler coupled with the first data traffic meter, the scheduler being configured to;

receive the first data traffic flow from the first data traffic meter; and

combine the first data traffic flow with a second data traffic flow having a second traffic rate to produce a third data traffic flow having a third rate of traffic; and

a second data traffic meter coupled with the scheduler, the second data traffic meter being configured to;

received the third data traffic flow from the scheduler;

if the data packet is marked with the first marker type, forward the data packet in the third data flow; and

if the data packet is marked with the second marker type and the third rate of traffic is less than or equal to a second threshold, forward the data packet in the third data flow, otherwise, discard the packet.