Fabric load balancing

• US 8,958,329 B2
• Filed: 11/20/2012
• Issued: 02/17/2015
• Est. Priority Date: 11/20/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Morandin, Guglielmo
• Primary Examiner(s): Pham, Brenda H
• Application Number:
  US13/681,607
• Publication Number:
  US 20140140212A1
• Time in Patent Office: 819 Days
• Field of Search: 370/229, 370/231, 370/230.1, 370/232, 370/234, 370/235, 370/332, 370/252
• US Class Current: 370/252
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/505 Corrective measures
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

In one implementation, a series of nodes in a network or a fabric communicate congestion values upstream against the flow of data packets. A current node determines average data intensity for each of a set of outputs. The average data intensity is based on recent data packet transmissions respectively to each of the set of outputs. The current node receives an output congestion value from each of the set of outputs and calculates an effective congestion value for each of the plurality of outputs as a function of the output congestion value and the average data intensity. The current node performs a comparison of the effective congestion values for the plurality of outputs and selects an output based on the comparison.

Claims

1. A method comprising:

determining an average data intensity for each of a plurality of outputs, wherein the average data intensity is based on recent data packet transmissions respectively to each of the plurality of outputs;

receiving an output congestion value from each of the plurality of outputs;

calculating, by a processor, an effective congestion value for each of the plurality of outputs, wherein the effective congestion value is a function of the output congestion value and the average data intensity;

performing, by the processor, a comparison of the effective congestion values for the plurality of outputs; and

selecting an output based on the comparison,

wherein the output congestion value is calculated based on at least one of a shadow queue value of the output or an arbiter value,

wherein when the output congestion value is calculated based on the shadow queue value of the output, the shadow queue value of the output is a virtual queue size for the output, and

wherein when the output congestion value is calculated based on the arbiter value, the arbiter value reflects packets with a pending arbiter request.

2. The method of claim 1, wherein the output is selected by a round robin algorithm from a set of allowable outputs, wherein the set of allowable outputs is a subset of the plurality of outputs defined by an allowable range for the output congestion value.

3. The method of claim 1, wherein the output congestion value is based on data received from a downstream node.

4. A method comprising:

determining an average data intensity for each of a plurality of outputs, wherein the average data intensity is based on recent data packet transmissions respectively to each of the plurality of outputs;

receiving an output congestion value from each of the plurality of outputs;

calculating, by a processor, an effective congestion value for each of the plurality of outputs, wherein the effective congestion value is a function of the output congestion value and the average data intensity;

performing, by the processor, a comparison of the effective congestion values for the plurality of outputs; and

selecting an output based on the comparison, wherein the output congestion value is calculated based on a second effective congestion value received from a downstream node.

5. The method of claim 4, further comprising:

forwarding a data packet to the selected output.

6. The method of claim 5, further comprising:

updating the average data intensity based on the forwarded data packet.

7. The method of claim 5, further comprising:

identifying the plurality of outputs based on an address in the data packet.

8. A method comprising:

determining an average data intensity for each of a plurality of outputs, wherein the average data intensity is based on recent data packet transmissions respectively to each of the plurality of outputs;

receiving an output congestion value from each of the plurality of outputs;

calculating, by a processor, an effective congestion value for each of the plurality of outputs, wherein the effective congestion value is a function of the output congestion value and the average data intensity;

performing, by the processor, a comparison of the effective congestion values for the plurality of outputs;

selecting an output based on the comparison, and

calculating a current congestion value for an input based on a weighted average of a past congestion value for the input and the effective congestion value of the selected output.

9. The method of claim 8, further comprising:

sending the current congestion value for the input to an upstream node as an effective congestion value.

10. A network device comprising:

an input communication interface configured to receive an output congestion value from each of a plurality of eligible outputs; and

a processor configured to calculate a first effective congestion value for each of the plurality of eligible outputs as a function of the output congestion value and an average data intensity, wherein the average data intensity is based on recent data packet transmissions respectively to each of the plurality of eligible outputs;

wherein the processor selects one of the plurality of eligible outputs based on a comparison of the first effective congestion values for the plurality of eligible outputs,

wherein the output congestion value is calculated based on a second effective congestion value received from a node downstream of the network device.

11. The network device of claim 10, wherein the processor selects the one of the plurality of eligible outputs from a narrowed set of eligible outputs that falls within an allowable range.

12. The network device of claim 11, wherein the processor is configured select from the narrowed set of eligible outputs based on a round robin algorithm.

13. The network device of claim 11, wherein the processor is configured to increment the average data intensity according to incoming packets and decrement the average data intensity according to time.

14. A non-transitory computer readable medium containing instructions that when executed are configured to:

determine an average data intensity for each of a plurality of outputs available to a current node, wherein the average data intensity is based on recent data packet transmissions respectively to each of the plurality of outputs;

receive an output congestion value from a plurality of downstream nodes;

calculate an effective congestion value for each of the plurality of outputs, wherein the effective congestion value is a function of the output congestion value and the average data intensity;

select a lowest of the effective congestion values for the plurality of outputs; and

forward an indication of the lowest of the effective congestion values to an upstream node,

wherein the output congestion value is calculated based on a downstream effective congestion value received from a node downstream of the current node.

15. The non-transitory computer readable medium of claim 14, the instructions further configured to:

select an output that corresponds to a lowest of the effective congestion values; and

forward a packet to one of the plurality of downstream nodes coupled to the output that corresponds to the lowest of the effective congestion values.

16. The non-transitory computer readable medium of claim 14, wherein the output congestion value is calculated based on a shadow queue value that lags a queue of the output.