Methods and devices for backward congestion notification

• US 8,792,352 B2
• Filed: 05/05/2011
• Issued: 07/29/2014
• Est. Priority Date: 10/11/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bergamasco, Davide, Baldini, Andrea, Alaria, Valentina, Bonomi, Flavio, Pan, Rong
• Primary Examiner(s): Chriss, Andrew
• Assistant Examiner(s): Cehic, Kenan
• Application Number:
  US13/101,870
• Publication Number:
  US 20110273983A1
• Time in Patent Office: 1,181 Days
• Field of Search: 3702301-236, 370/468, 370236-2362, 709/225, 709232-235, 709/229
• US Class Current: 370/236
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• 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

The present invention provides improved methods and devices for managing network congestion. Preferred implementations of the invention allow congestion to be pushed from congestion points in the core of a network to reaction points, which may be edge devices, host devices or components thereof. Preferably, rate limiters shape individual flows of the reaction points that are causing congestion. Parameters of these rate limiters are preferably tuned based on feedback from congestion points, e.g., in the form of backward congestion notification (“BCN”) messages. In some implementations, such BCN messages include congestion change information and at least one instantaneous measure of congestion. The instantaneous measure(s) of congestion may be relative to a threshold of a particular queue and/or relative to a threshold of a buffer that includes a plurality of queues.

Claims

1. A method of controlling a rate of traffic injected into a network, the method comprising:

receiving a first feedback message from a congestion point of a network, the first feedback message comprising an Ethernet frame having embedded therein;

an instantaneous congestion value in a first field of the Ethernet frame;

a congestion change value in a second field of the Ethernet frame, the second field being separate from the first field; and

a congestion point identifier associated with the congestion point;

calculating a rate control value based, at least in part, on the instantaneous congestion value and the congestion change value; and

adjusting a flow rate of traffic addressed to the congestion point according to the rate control value.

2. The method of claim 1, wherein the Ethernet frame includes an EtherType field value that identifies the Ethernet frame as a backwards congestion notification message.

3. The method of claim 1, wherein the Ethernet frame includes first and second congestion condition bits, wherein the first congestion condition bit indicates whether mild congestion is present, and the second congestion condition bit indicates whether severe congestion is present.

4. The method of claim 1, wherein the first feedback message further comprises an indication that an occupancy of a buffer of the congestion point is above a buffer congestion threshold, wherein calculating the rate control value comprises calculating a maximum negative value of the rate control value.

5. The method of claim 1, further comprising adding a tag to frames sent to the congestion point, the tag including data responsive to the first feedback message.

14. The method of claim 1, wherein the congestion change value is associated with a change in length of a queue.

15. The method of claim 1, wherein the congestion change value indicates a change in a level of congestion since a previous time.

16. The method of claim 1, further comprising adding data responsive to the first feedback message to frames sent to the congestion point.

6. An apparatus for controlling a rate of traffic injected into a network, comprising:

a processor; and

a memory, at least one of the processor or the memory being configured for;

receiving a first feedback message from a congestion point of a network, the first feedback message comprising an Ethernet frame having embedded therein;

an instantaneous congestion value in a first field of the Ethernet frame;

a congestion change value in a second field of the Ethernet frame, the second field being separate from the first field, the congestion change value indicating a change in an amount of congestion at the congestion point; and

a congestion point identifier associated with the congestion point;

calculating a rate control value based, at least in part, on the instantaneous congestion value and the congestion change value; and

adjusting a flow rate of traffic addressed to the congestion point according to the rate control value.

7. The apparatus of claim 6, wherein the first feedback message identifies a network flow.

8. The apparatus of claim 6, wherein the first feedback message further comprises an indication that an occupancy of a buffer of the congestion point is above a buffer congestion threshold, wherein said calculating step the rate control value comprises calculating a maximum negative value of the rate control value.

9. The apparatus of claim 6, at least one of the processor or the memory being further configured for adding a tag to frames sent to the congestion point, the tag including data responsive to the first feedback message.

10. A device for controlling a rate of traffic injected into a network, the device comprising:

means for receiving a first feedback message from a congestion point of a network, the first feedback message comprising an Ethernet frame having embedded therein;

an instantaneous congestion value in a first field of the Ethernet frame;

a congestion change value in a second field of the Ethernet frame, the second field being separate from the first field; and

a congestion point identifier associated with the congestion point;

means for calculating a rate control value based, at least in part, on the instantaneous congestion value and the congestion change value;

means for adjusting a flow rate of traffic addressed to the congestion point according to the rate control value; and

means for adding data responsive to the first feedback message to frames sent to the congestion point.

11. The device of claim 10, wherein the device comprises an ingress port of an edge switch.

12. The device of claim 10, wherein the device comprises an egress port of a host device.

13. A congestion management method, comprising:

detecting network congestion at a first congestion point of a network

identifying a first congested entity of the network;

determining a current queue level of the congested entity;

sending a first feedback message to a first reaction point of the network, the first reaction point being associated with one or more traffic flows at least partly causing the congestion, the first feedback message comprising an Ethernet frame having embedded therein;

an instantaneous congestion value in a first field of the Ethernet frame;

a congestion change value in a second field of the Ethernet frame, the second field being separate from the first field; and

a congestion point identifier associated with the congested; and

determining whether the congestion change value exceeds a predetermined threshold;

wherein the predetermined threshold decreases as a number of active virtual output queues (“

VOQs”

) in a buffer of the first congestion point increases and wherein the predetermined threshold increases as the number of active VOQs in the buffer decreases.