Methods and devices for backward congestion notification

• US 20070081454A1
• Filed: 10/11/2005
• Published: 04/12/2007
• 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, Bonomi, Flavio, Pan, Rong, Alaria, Valentina, Baldini, Andrea
• Granted Patent: US 7,961,621 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• 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 congestion management method, comprising:

detecting network congestion at a first congestion point of a network;

identifying a first congested entity of the network;

calculating feedback information regarding a congestion level of the congested entity; and

sending a first feedback message to a first reaction point of the network, the reaction point being associated with one or more traffic flows causing the congestion, at least in part, the feedback message including the feedback information and identity data for the congested entity.

2. The method of claim 1, wherein the feedback information comprises an instantaneous measure of congestion and congestion change information.

3. The method of claim 1, wherein the first feedback message comprises one of an indication to slow down a traffic flow, an indication to speed up a traffic flow and an indication to stop a traffic flow.

4. The method of claim 1, wherein the first feedback message identifies a particular flow.

5. The method of claim 1, wherein the congested entity comprises a queue.

6. The method of claim 1, wherein the detecting step comprises:

sampling a frame; and

determining whether a sampled frame includes responsive data that is responsive to a feedback message.

7. The method of claim 2, wherein the instantaneous measure of congestion and the congestion change information are determined with reference to a predetermined threshold of a queue.

8. The method of claim 6, wherein it is determined that the sampled frame includes responsive data, further comprising:

determining that the responsive data identify the first congested entity;

determining that the occupancy of a queue to which the sampled frame will be added is currently above a first predetermined threshold; and

sending a second feedback message to a source address of the sampled frame, the second feedback message comprising an indication to slow down a traffic flow.

9. The method of claim 6, wherein it is determined that the sampled frame does not include responsive data, further comprising:

determining that the occupancy of a queue to which the sampled frame will be added is currently below a first predetermined threshold; and

determining not to send a second feedback message to a source address of the sampled frame.

10. The method of claim 6, wherein it is determined that the sampled frame includes responsive data, further comprising:

determining that the responsive data identify the first congested entity;

determining that the occupancy of a queue to which the sampled frame will be added is currently above a second predetermined threshold; and

sending a second feedback message to a source address of the sampled frame, the second feedback message comprising an indication to stop a traffic flow.

11. The method of claim 6, wherein it is determined that the sampled frame includes responsive data, further comprising:

determining that the responsive data identify the first congested entity;

determining that the occupancy of a buffer of the congestion point is above a buffer congestion threshold; and

sending a second feedback message to a source address of the sampled frame, the second feedback message comprising an indication that the occupancy of the buffer is above the buffer congestion threshold.

12. The method of claim 7, wherein the predetermined threshold decreases as a number of active virtual output queues (“

VOQs”

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

13. A network device, comprising:

means for detecting network congestion at a first congestion point of a network;

means for identifying a first congested entity of the network;

means for calculating feedback information regarding a congestion level of the congested entity; and

means for sending a first feedback message to a first reaction point of the network, the reaction point being associated with one or more traffic flows causing the congestion, at least in part, the feedback message including the feedback information and identity data for the congested entity.

14. 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 instantaneous measure of congestion for the congestion point, congestion change information for the congestion point and identity data for the congestion point;

calculating a feedback signal based, at least in part, on information in the first feedback message; and

adjusting a flow rate of traffic addressed to the congestion point according to the feedback signal.

15. The method of claim 14, wherein the first feedback message identifies a particular flow.

16. The method of claim 14, wherein the congested entity comprises a queue.

17. The method of claim 14, wherein the calculating step comprises calculating the feedback signal based on the instantaneous measure of congestion and the congestion change information for the congestion point.

18. The method of claim 14, wherein the first feedback message further comprises an indication that the occupancy of a buffer of the congestion point is above a buffer congestion threshold, wherein the calculating step comprises calculating the maximum negative value of the feedback signal.

19. The method of claim 14, further comprising the step of adding a tag to each frame sent to the congestion point, the tag including data responsive to the first feedback message.

22. The device of claim 19, wherein the device comprises an egress port of a host device.

20. 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 instantaneous measure of congestion for the congestion point, congestion change information for the congestion point and identity data for the congestion point;

means for calculating a feedback signal based, at least in part, on information in the first feedback message; and

means for adjusting a flow rate of traffic addressed to the congestion point according to the feedback signal.

21. The device of claim 20, wherein the device comprises an ingress port of an edge switch.