Source-based congestion detection and control

• US 8,824,294 B2
• Filed: 06/08/2011
• Issued: 09/02/2014
• Est. Priority Date: 08/29/2008
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Inventors: Halabi, Mitri, Wong, Yuen Fai, Colvin, Robert, Yang, Frank S.
• Primary Examiner(s): Cho, Un C
• Assistant Examiner(s): Liu, Siming
• Application Number:
  US13/156,145
• Publication Number:
  US 20110235518A1
• Time in Patent Office: 1,182 Days
• Field of Search: 370/229, 370/230, 370/235, 370/236, 370/414, 370/418
• US Class Current: 370/235
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes

Abstract

Congestion control techniques based upon resource utilization information stored by a network device. According to an embodiment of the present invention, a network device is configured to identify a data source causing congestion based upon information stored by the network device identifying a set of data sources, and for each data source, information identifying the amount of a resource of the network device being used for processing data received by the network device from the data source.

Claims

1. A method comprising:

receiving, at a network device, a packet that was forwarded to the network device by an intermediate device that is separate from a source device from which the packet originated;

augmenting a forwarding table, used by the network device to route packets through a network, with a resource utilization value that is associated with the source device and that tracks an amount of a resource of the network device being used to process data originating at the source device;

determining, by the network device, that the resource utilization value equals or exceeds a first threshold;

responsive to the determining, sending, by the network device, through one or more hops in between the network device and the source device, a first message to the source device to either pause or slow down transmission of a first type of data;

determining, by the network device, that the resource utilization value associated with the source device does not exceed the first threshold; and

responsive to the determining that the resource utilization value associated with the source device does not exceed the first threshold, sending, by the network device, through one or more hops in between the network device and the source device, a second message addressed to the source device to resume transmission of the first type of data;

wherein the source device did not receive the packet from any other device.

2. The method of claim 1 further comprising:

determining, by the network device, that the resource utilization value associated with the source device equals or exceeds a second threshold; and

responsive to determining that the resource utilization value associated with the source device equals or exceeds the second threshold, sending, by the network device, a third message to the source device to pause, slow down, or resume transmission of a second type of data, the second type of data being different from the first type of data.

3. The method of claim 2 wherein the first type of data corresponds to data associated with a first priority and the second type of data corresponds to data associated with a second priority different from the first priority.

4. The method of claim 1 further comprising:

determining, by the network device, the source device based upon a source device MAC address extracted from the received packet;

determining an amount of memory needed for processing the packet; and

determining the resource utilization value based upon the amount of memory determined for processing the packet;

wherein determining that the resource utilization value associated with the source device equals or exceeds the first threshold comprises determining that a resource utilization value associated with the MAC address equals or exceeds the first threshold;

wherein sending the second message to the source device comprises sending a message that specifies the MAC address as a destination.

5. The method of claim 4 further comprising associating a tag with the packet, the tag comprising information usable for determining the source device.

6. A network device comprising:

a memory configured to store a first threshold; and

a congestion controller configured to;

receive a packet that was forwarded to the network device by an intermediate device that is separate from a source device from which the packet originated;

augment a forwarding table, used by the network device to route packets through a network, with a resource utilization value that is associated with the source device and that tracks an amount of a resource of the network device being used to process data originating at the source device;

determine that the resource utilization value equals or exceeds the first threshold;

responsive to the determining, send, through one or more hops in between the network device and the source device, a first message to the source device to either pause or slow down transmission of a first type of data;

determine that the resource utilization value associated with the source device does not exceed the first threshold; and

responsive to the determining that the resource utilization value associated with the source device does not exceed the first threshold, sending, through one or more hops in between the network device and the source device, a second message addressed to the source device to resume transmission of the first type of data;

wherein the source device did not receive the packet from any other device.

7. The network device of claim 6 wherein:

the memory is configured to store a second threshold; and

the congestion controller is configured to;

determine that the resource utilization value associated with the source device equals or exceeds the second threshold; and

responsive to determining that the resource utilization value associated with the source device equals or exceeds the second threshold, send a third message to the source device to pause, slow down, or resume transmission of a second type of data, the second type of data being different from the first type of data.

8. The system of claim 7 wherein the first type of data corresponds to data associated with a first priority and the second type of data corresponds to data associated with a second priority different from the first priority.

9. The network device of claim 6 wherein:

the resource is the memory; and

the congestion controller is configured to;

determine the source device based upon a source device MAC address extracted from the packet that originated from the source device;

determine an amount of the memory needed for processing the packet;

determine the resource utilization value based upon the amount of memory determined for processing the packet; and

store the resource utilization value in association with the source device MAC address.

10. The network device of claim 9 wherein the congestion controller is configured to associate a tag with the packet, the tag comprising information usable for determining the source device.

11. A network device comprising:

a memory configured to store a plurality of thresholds; and

a congestion controller configured to;

receive a packet that was forwarded to the network device by an intermediate device that is separate from a source device from which the packet originated;

augment a forwarding table, used by the network device to route packets through a network, with a resource utilization value that is associated with the source device and that tracks an amount of a resource of the network device being used to process data originating at the source device;

determine that the resource utilization value associated with the source device and stored in the forwarding table equals or exceeds each of the plurality of thresholds;

responsive to the determining, for each threshold in the plurality of thresholds, send, through one or more hops in between the network device and the source device, a message addressed to the source device to either pause, slow down, or resume transmission of a type of data associated with the threshold;

determine that the resource utilization value associated with the source device does not exceed a particular threshold of the plurality of thresholds; and

responsive to the determining that the resource utilization value associated with the source device does not exceed the particular threshold, sending, through one or more hops in between the network device and the source device, a second message addressed to the source device to resume transmission of a type of data associated with the particular threshold;

wherein the source device did not receive the packet from any other device.

12. The network device of claim 11 wherein the resource is the memory.