Meter-based hierarchical bandwidth sharing

• US 8,416,689 B2
• Filed: 04/23/2010
• Issued: 04/09/2013
• Est. Priority Date: 08/26/2008
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Kwan, Bruce, Agarwal, Puneet, Davari, Shahram
• Primary Examiner(s): HOANG, THAI D
• Application Number:
  US12/766,518
• Publication Number:
  US 20100271946A1
• Time in Patent Office: 1,082 Days
• Field of Search: 370229-240, 370252-253, 709223-226, 709231-235, 709/239
• US Class Current: 370/232
• 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, using dual-token bucket meters (two-rate three-color meters) to meter bandwidth usage by individual microflows and associated macroflows (combinations of microflows). The dual-token bucket meters are used to locally and finally mark the packets using a three-color marking approach. In the example method, forwarding and discard decisions for packets processed using such techniques are made based on the final marking.

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;

based on the first rate of traffic of the first data traffic flow, marking the data packet with a first marker using a first two-rate three-color meter (trTCM);

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;

based on the third rate of traffic of the third data traffic flow, marking the data packet with a second marker using a second two-rate three-color meter (trTCM);

finally marking the data packet with a final marker based on the first marker and the second marker; and

processing the data packet based on the final marker.

2. The method of claim 1, wherein marking the data packet with the first marker comprises:

determining if the first rate of traffic is less than or equal to a first threshold;

in the event the first rate of traffic is less than or equal to the first threshold, assigning a first marker type to the first marker;

in the event the first rate of traffic is greater than the first threshold;

determining whether the first rate of traffic is greater than a second threshold, the second threshold being greater than the first threshold;

in the event the first rate of traffic is less than or equal to the second threshold, assigning a second marker type to the first marker; and

in the event the first of rate traffic is greater than the second threshold, assigning a third marker type to the first marker.

3. The method of claim 2, 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 committed information rate token bucket of the first trTCM.

4. The method of claim 2, wherein determining whether the first rate of traffic is greater than the second threshold comprises determining whether a positive token count is present in an excess information rate token bucket of the first trTCM.

5. The method of claim 2, wherein:

the first marker type designates the data packet as green;

the second marker type designates the data packet as yellow; and

the third marker type designates the data packet as red.

6. The method of claim 2, wherein:

marking the data packet with the second marker comprises;

determining whether the third rate of traffic is less than or equal to a third threshold;

in the event the third rate of traffic is less than or equal to the third threshold, assigning the first marker type to the second marker;

in the event the third rate of traffic is greater than the third threshold;

determining whether the third rate of traffic is greater than a fourth threshold, the fourth threshold being greater than the third threshold;

in the event the third rate of traffic is less than or equal to the fourth threshold, assigning the second marker type to the second marker; and

in the event the third rate of traffic is greater than the fourth threshold, assigning the third marker type to the second marker; and

finally marking the data packet with a final marker based on the first marker and the second marker comprises;

in the event the first marker is assigned the first marker type, assigning the first marker type to the final marker;

in the event the first marker is assigned the third marker type, assigning the third marker type to the final marker;

in the event the first marker is assigned the second marker type and the second marker is assigned the first marker type, assigning the first marker type to the final marker;

in the event the first marker type is assigned the second marker type and the second marker is assigned the second marker type, assigning the second marker type to the final marker; and

in the event the first marker type is assigned the second marker type and the second marker is assigned the third marker type, assigning the third marker type to the final marker.

7. The method of claim 6, wherein determining whether the third rate of traffic is less than or equal to the third threshold comprises determining whether a positive token count is present in a committed information rate token bucket of the second trTCM.

8. The method of claim 6, wherein determining whether the third rate of traffic is greater than the fourth threshold comprises determining whether a positive token count is present in an excess information rate token bucket of the second trTCM.

9. The method of claim 6, wherein:

the first marker type designates the data packet as green;

the second marker type designates the data packet as yellow; and

the third marker type designates the data packet as red.

10. The method of claim 6, wherein:

in the event the final marker is assigned one of the first marker type and the second marker type, forwarding the data packet to a destination associated with the packet; and

in the event the final marker is assigned the third marker type, discarding the packet.

11. The method of claim 10, wherein in the event the first marker is assigned the first marker type, forwarding the data packet to the destination associated with the packet comprises:

decrementing a token count of a committed information rate token bucket of the first trTCM by an amount corresponding with a size of the data packet; and

decrementing a token count of a committed information rate token bucket of the second trTCM by the amount corresponding with the size of the data packet.

12. The method of claim 10, wherein in the event the first marker is assigned the second marker type and the final marker is assigned the first marker type, forwarding the data packet the destination associated with the packet comprises:

decrementing a token count of an excess information rate token bucket of the first trTCM by an amount corresponding with a size of the data packet; and

decrementing a token count of a committed information rate token bucket of the second trTCM by the amount corresponding with the size of the data packet.

13. The method of claim 10, wherein in the event the first marker is assigned the second marker type and the final marker is assigned the second marker type, forwarding the data packet to the destination associated with the packet comprises:

decrementing a token count of an excess information rate token bucket of the first trTCM by an amount corresponding with a size of the data packet; and

decrementing a token count of an excess information rate token bucket of the second trTCM by the amount corresponding with the size of the data packet.

14. A network device comprising:

a first two-rate three-color meter (trTCM) configured to;

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

based on the first rate of traffic of the first data traffic flow, mark the data packet with a first marker using a first two-rate three-color meter (trTCM);

a scheduler configured to combine 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;

a second trTCM configured to;

receive the third data traffic flow; and

based on the third rate of traffic of the third data traffic flow, mark the data packet with a second marker using a second two-rate three-color meter (trTCM); and

a data queue comprising an admission control module, the data queue being configured to;

finally mark the data packet with a final marker based on the first marker and the second marker; and

process the data packet based on the final marker.

15. The network device of claim 14, wherein the first trTCM comprises:

a committed information rate token bucket for metering a committed information rate for the first data traffic flow; and

an excess information rate token bucket for metering an excess information rate for the first data traffic flow.

16. The network device of claim 14, wherein the second trTCM comprises:

a committed information rate token bucket for metering a committed information rate for the third data traffic flow; and

an excess information rate token bucket for metering an excess information rate for the third data traffic flow.

17. The method of claim 14, wherein data queue is further configured to:

forward the data packet to a destination associated with the data packet if the final marker type is one of a first marker type and a second marker type; and

discard the data packet if the final marker type is a third marker type.

18. The network device of claim 17, wherein:

the first marker type designates the data packet as green;

the second marker type designates the data packet as yellow; and

the third marker type designates the data packet as red.

19. A method for communicating data comprising:

receiving a data packet included in a first data traffic flow;

determining if a first rate of traffic of the first data traffic flow is less than or equal to a first threshold;

in the event the first rate of traffic is less than or equal to the first threshold, locally and finally marking the data packet with a first marker type;

in the event the first rate of traffic is greater than the first threshold;

determining whether the first rate of traffic is greater than a second threshold, the second threshold being greater than the first threshold;

in the event the first rate of traffic is less than or equal to the second threshold, locally marking the data packet with a second marker type; and

in the event the first of rate traffic is greater than the second threshold, locally and finally marking the data packet with a third marker type;

receiving a second data traffic flow having a second rate of traffic;

combining the first data traffic flow and the second data traffic flow to produce a third data traffic flow;

determining whether a third rate of traffic of the third data traffic flow is less than or equal to a third threshold;

in the event the data packet is locally marked with the second marker type and the third rate of traffic is less than or equal to the third threshold, finally marking the packet with the first marker type;

in the event the data packet is locally marked with the second marker type and the third rate of traffic is greater than the third threshold;

determining whether the third rate of traffic is greater than a fourth threshold, the fourth threshold being greater than the third threshold;

in the event the third rate of traffic is less than or equal to the fourth threshold, finally marking the packet with the second marker type; and

in the event the third rate of traffic is greater than the fourth threshold, finally marking the packet with the third marker type; and

in the event the packet is finally marked with the first marker type, forwarding the packet to a destination associated with the packet;

in the event the packet is finally marked with one of the second marker type and the third marker type, performing one of;

processing the packet to determine whether to forward or discard the packet, and forwarding or discarding the packet in accordance with the determination; and

forwarding the packet for processing to determine whether to retain or discard the packet.