Priority-based hierarchical bandwidth sharing

• US 8,315,168 B2
• Filed: 04/13/2010
• Issued: 11/20/2012
• Est. Priority Date: 10/28/2009
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Davari, Shahram
• Primary Examiner(s): Chou, Albert T
• Application Number:
  US12/759,471
• Publication Number:
  US 20110096666A1
• Time in Patent Office: 952 Days
• Field of Search: 370/235.1, 370/230, 370/232, 370/233, 370/230.1
• US Class Current: 370/235
• 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/29 using a combination of thresholds
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/41 by acting on aggregated flows or links

Abstract

Methods and apparatus for communicating data are disclosed. The example method includes allocating tokens to a first token bucket of a first two-rate, three-color meter (trTCM) at a first rate and allocating tokens to a second token bucket of the first trTCM at a second rate. The example method further includes allocating tokens to a first token bucket of a second trTCM at a third rate and allocating tokens to a second token bucket of the second trTCM at a fourth rate. The example method also includes reallocating tokens allocated to the first token bucket of the first trTCM to the first token bucket of the second trTCM when a token count of the first token bucket of the first trTCM exceeds a first capacity and reallocating tokens allocated to the second token bucket of the first trTCM to the second token bucket of the second trTCM when a token count of the second token bucket of the first trTCM exceeds a second capacity.

Claims

1. A data communication apparatus comprising:

a processor;

a non-transitory machine readable medium having instructions stored therein, the instructions, when executed by the processor, result in the data communication apparatus;

metering a first data traffic flow with a first two-rate, three-color meter (trTCM), wherein a first token bucket of the first trTCM has a first token capacity and a second token bucket of the first trTCM has a second token capacity;

allocating tokens to the first token bucket of the first trTCM at a first rate and allocating tokens to the second token bucket of the first trTCM at a second rate;

metering a second data traffic flow with a second trTCM, wherein a first token bucket of the second trTCM has a third token capacity and a second token bucket of the second trTCM has a fourth token capacity;

allocating tokens to the first token bucket of the second trTCM at a third rate and allocating tokens to the second token bucket of the second trTCM at a fourth rate;

reallocating tokens allocated to the first token bucket of the first trTCM to the first token bucket of the second trTCM when a token count of the first token bucket of the first trTCM exceeds the first capacity; and

reallocating tokens allocated to the second token bucket of the first trTCM to the second token bucket of the second trTCM when a token count of the second token bucket of the first trTCM exceeds the second capacity.

2. The data communication apparatus of claim 1, wherein the first data traffic flow is assigned a higher priority than the second data traffic flow.

3. The data communication apparatus of claim 1, wherein the instructions, when executed by the processor, further result in the data communication apparatus:

reallocating tokens allocated to the first token bucket of the second trTCM to the first token bucket of the first trTCM when a token count of the first token bucket of the second trTCM exceeds the third capacity; and

reallocating tokens allocated to the second token bucket of the second trTCM to the second token bucket of the first trTCM when a token count of the second token bucket of the second trTCM exceeds the fourth capacity.

4. The data communication apparatus of claim 3, wherein:

reallocating tokens allocated to the first token bucket of the second trTCM to the first token bucket of the first trTCM comprises at least one of;

reallocating at least a portion of the tokens allocated to the first token bucket of the second trTCM at the third rate; and

reallocating at least a portion of the tokens reallocated from the first token bucket of the first trTCM to the first token bucket of the second trTCM; and

reallocating tokens allocated to the second token bucket of the second trTCM to the second token bucket of the first trTCM comprises at least one of;

reallocating at least a portion of the tokens allocated to the second token bucket of the second trTCM at the third rate; and

reallocating at least a portion of the tokens reallocated from the second token bucket of the second trTCM to the second token bucket of the second trTCM.

5. The data communication apparatus of claim 1, wherein the instructions, when executed by the processor, further result in the data communication apparatus reallocating tokens allocated to the first token bucket of the second trTCM to the second token bucket of the first trTCM when a token count of the first token bucket of the second trTCM exceeds the third capacity.

6. The data communication apparatus of claim 5, wherein the instructions, when executed by the processor, further result in the data communication apparatus reallocating tokens allocated to the second token bucket of the second trTCM to the second token bucket of the first trTCM when a token count of the second token bucket of the second trTCM exceeds the fourth capacity.

7. The data communication apparatus of claim 1, wherein the instructions, when executed by the processor, further result in the data communication apparatus:

processing a third data traffic flow in parallel with the first data traffic flow and the second data traffic flow, the third data traffic flow having a lower priority than the first data traffic flow and a higher priority than the second data traffic flow;

metering the third data traffic flow with a third trTCM, wherein a first token bucket of the third trTCM has a fifth token capacity and a second token bucket of the third trTCM has a sixth token capacity;

allocating tokens to the first token bucket of the third trTCM at a fifth rate;

allocating tokens to the second token bucket of the third trTCM at a sixth rate; and

reallocating tokens allocated to the first token bucket of the third trTCM to the second token bucket of the third trTCM when a token count of the first token bucket of the third trTCM exceeds the fifth capacity.

8. The data communication apparatus of claim 7, wherein:

reallocating tokens allocated to the first token bucket of the first trTCM to the first token bucket of the second trTCM is done in response to a first flag being set, the first flag being associated with the first token bucket of the first trTCM;

reallocating tokens allocated to the second token bucket of the first trTCM to the second token bucket of the second trTCM is done in response to a second flag being set, the second flag being associated with the second token bucket of the first trTCM; and

reallocating tokens allocated to the first token bucket of the third trTCM to the second token bucket of the third trTCM is done in response to a third flag being cleared and a fourth flag being set, the third flag being associated with the first token bucket of the third trTCM being and the fourth flag being associated with the third trTCM.

9. The data communication apparatus of claim 1, wherein the instructions, when executed by the processor, further result in the data communication apparatus:

processing a third data traffic flow in parallel with the first data traffic flow and the second data traffic flow, the third data traffic flow having a lower priority than the first data traffic flow and the second data traffic flow;

metering the third data traffic flow with a third trTCM, wherein a first token bucket of the third trTCM has a fifth token capacity and a second token bucket of the third trTCM has a sixth token capacity;

allocating tokens to the first token bucket of the third trTCM at a fifth rate;

allocating tokens to the second token bucket of the third trTCM at a sixth rate;

reallocating tokens allocated to the first token bucket of the second trTCM to the first token bucket of the third trTCM when a token count of the first token bucket of the second trTCM exceeds the third capacity; and

reallocating tokens allocated to the second token bucket of the second trTCM to the second token bucket of the third trTCM when a token count of the second token bucket of the second trTCM exceeds the fourth capacity.

10. The data communication apparatus of claim 9, wherein the instructions, when executed by the processor, further result in the data communication apparatus:

reallocating tokens allocated to the first token bucket of the third trTCM to the first token bucket of the first trTCM when a token count of the first token bucket of the third trTCM exceeds the fifth capacity; and

reallocating tokens allocated to the second token bucket of the third trTCM to the second token bucket of the first trTCM when a token count of the second token bucket of the third trTCM exceeds the sixth capacity.

11. The data communication apparatus of claim 1, wherein:

the first rate comprises a committed information rate (CIR) of the first data traffic flow;

the second rate comprises an excess information rate (EIR) of the first data traffic flow;

the third rate comprises a CIR of the second data traffic flow; and

the fourth rate comprises an EIR of the second data traffic flow.

12. The data communication apparatus of claim 1, wherein the instructions, when executed by the processor, further result in the data communication apparatus:

in response to a flag associated with the first token bucket of the second trTCM being cleared, discarding tokens reallocated to the first token bucket of the second trTCM when a token count of the first token bucket of the second trTCM exceeds the third capacity; and

in response to a flag associated with the second token bucket of the second trTCM being cleared, discarding tokens reallocated to the second token bucket of the second trTCM when a token count of the second token bucket of the second trTCM exceeds the fourth capacity.

13. The data communication apparatus of claim 1, wherein:

reallocating tokens allocated to the first token bucket of the first trTCM to the first token bucket of the second trTCM comprises reallocating tokens allocated to the first token bucket of the first trTCM to the first token bucket of the second trTCM based on an index of the first token bucket of the second trTCM; and

reallocating tokens allocated to the second token bucket of the first trTCM to the second token bucket of the second trTCM comprises reallocating tokens allocated to the second token bucket of the first trTCM to the second token bucket of the second trTCM based on an index of the second token bucket of the second trTCM.

14. A network device comprising:

a first two-rate, three-color meter (trTCM) configured to meter a first data traffic flow, the first trTCM comprising;

a first token bucket having a first capacity; and

a second token bucket having a second capacity;

a second trTCM configured to meter a second data traffic flow, the second trTCM comprising;

a first token bucket having a third capacity; and

a second token bucket having a fourth capacity,

wherein;

the first token bucket of the first trTCM is configured to reallocate tokens allocated to the first token bucket of the first trTCM to the first token bucket of the second trTCM when a token count of the first token bucket of the first trTCM exceeds the first capacity; and

the second token bucket of the first trTCM is configured to reallocate tokens allocated to the second token bucket of the first trTCM to the second token bucket of the second trTCM when a token count of the second token bucket of the first trTCM exceeds the second capacity.

15. The network device of claim 14, further comprising:

a third trTCM configured to meter a third data traffic flow, the third trTCM comprising;

a first token bucket having a fifth capacity; and

a second token bucket having a sixth capacity,

wherein;

the third data traffic flow has a lower priority than the first data traffic flow and a higher priority than the second data traffic flow; and

the first token bucket of the third trTCM is configured to reallocate tokens allocated to the first token bucket of the third trTCM to the second token bucket of the third trTCM when a token count of the first token bucket of the third trTCM exceeds the fifth capacity.

16. The network device of claim 14, wherein the first token bucket of the second trTCM is configured to reallocate tokens allocated to the first token bucket of the second trTCM to the second token bucket of the first trTCM when a token count of the first token bucket of the second trTCM exceeds the third capacity.

17. The network device of claim 14;

a third trTCM configured to meter a third data traffic flow, the third trTCM comprising;

a first token bucket having a fifth capacity; and

a second token bucket having a sixth capacity,

wherein;

the third data traffic flow has a lower priority than the first data traffic flow and a lower priority than the second data traffic flow; and

the first token bucket of the third trTCM is configured to reallocate tokens allocated to it to the second token bucket of the first trTCM when a token count of the first token bucket of the third trTCM exceeds the fifth capacity.

18. The network device of claim 17, wherein the tokens allocated to the first token bucket of the third trTCM comprise:

tokens allocated to the first token bucket of the third trTCM by the third trTCM; and

tokens reallocated to the first token bucket of the third trTCM by a token bucket of a trTCM that is configured to process a data traffic flow with a higher priority than the third data traffic flow and a lower priority of the first data traffic flow.

19. The network device of claim 14, wherein:

the first token bucket of the second trTCM is configured to reallocate tokens allocated to it to a token bucket of a trTCM that is configured to process a data traffic flow having a higher priority than the second data traffic flow when a token count of the first token bucket of the second trTCM exceeds the third capacity; and

the second token bucket of the second trTCM is configured to discard tokens allocated to it when a token count of the second token bucket of the second trTCM exceeds the fourth capacity.

20. A network device comprising:

a first two-rate, three-color meter (trTCM) comprising a first token bucket having a first capacity and a second token bucket having a second capacity, wherein the first trTCM is configured to meter a first data traffic flow; and

a second trTCM comprising a first token bucket and a second token bucket, wherein the second trTCM is configured to meter a second data traffic flow,

wherein;

the first token bucket of the first trTCM is configured to reallocate tokens allocated to it to the first token bucket of the second trTCM when a token count of the first token bucket of the first trTCM exceeds the first capacity; and

the second token bucket of the first trTCM is configured to reallocate tokens allocated to it to the second token bucket of the second trTCM when a token count of the second token bucket of the first trTCM exceeds the second capacity.