Method and apparatus to minimize congestion in a packet switched network

• US 6,970,424 B2
• Filed: 11/10/1998
• Issued: 11/29/2005
• Est. Priority Date: 11/10/1998
• Status: Expired due to Term

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Walrand, Jean, Fawaz, Ayman
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): TRAN, PHUC H
• Application Number:
  US09/189,819
• Publication Number:
  US 20030133406A1
• Time in Patent Office: 2,576 Days
• Field of Search: 370/351, 370/354, 370/357, 370/395.1, 370/395.21, 370/395.4, 370/395.43, 370/229, 370/230, 370/230.1, 370/231, 370/232, 370/235, 370/237, 301/235.1, 301/236, 301/236.1, 301/236.2, 301/237
• US Class Current: 370/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2425 for supporting services specification, e.g. SLA
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A packet-switched communication network in accordance with the invention provides a guaranteed minimum bandwidth between pairs of Packet Switches by defining Service Level Agreements (SLAs). An SLA is defined by at least a source identifier, a destination identifier, and a minimum data rate although other information can also be used. Upon arrival at certain networked nodes, packets are classified according to an SLA by reading the source and destination addresses in the packet. Once classified, the packets are placed in a queue and scheduled for transmission. A scheduler ensures that packets are transmitted at the minimum defined data rate for the SLA. The scheduler may use a statistical multiplexing method, such as deficit round robin, or deficit golden ratio, which is part of the present invention. The deficit golden ratio method assures a minimum rate to packets for a particular SLA, but minimizes jitter and delay. Further, the present invention implements congestion control that does not require nodes to be entirely turned off in congested conditions.

Claims

1. A method for controlling congestion in a network having a plurality of switching points, comprising:

maintaining a plurality of service level agreements (SLAs) at a first switching point, each SLA having a corresponding minimum data rate;

transmitting data packets received at the first switching point corresponding to each SLA at or above the minimum data rate in accordance with the respective SLA;

receiving a message from a second switching point at the first switching point to indicate that traffic between a source and a destination is congested; and

adjusting a data rate at which packets corresponding to an SLA, destined for the destination, are output from the first switching point in response to receiving the message to reduce the congestion.

2. The method of claim 1 wherein adjusting the data rate for packets corresponding to the SLA to reduce the congestion includes reducing the data rate to the minimum data rate for the SLA.

3. The method of claim 1 wherein adjusting the data rate for packets corresponding to the SLA to reduce the congestion includes reducing the data rate below the minimum data rate.

4. The method of claim 1 wherein maintaining SLAs further comprises separating the data packets into different queues corresponding to each different SLA.

5. An article of manufacture comprising a machine-accessible medium that includes content that when accessed provides instructions to cause a machine to:

maintain a plurality of service level agreements (SLAs) at a first switching point, each SLA having a corresponding minimum data rate;

transmit data packets received at the first switching point corresponding to each SLA at or above the minimum data rate in accordance with the respective SLA;

receive a message from a second switching point to indicate that traffic between a source and a destination is congested; and

adjust a data rate at which packets corresponding to an SLA, destined for the destination, are transmitted in response to receiving the message to reduce the congestion.

6. The article of manufacture of claim 5 wherein the content to provide instructions to cause the machine to adjust the data rate for an SLA to reduce the congestion includes the content providing instructions to cause the machine to reduce the data rate to the minimum data rate for the SLA.

7. The article of manufacture of the claim 5 wherein the content to provide instructions to cause the machine to adjust the data rate for an SLA to reduce the congestion includes the content providing instructions to cause the machine to reduce the data rate below the minimum data rate for the SLA.

8. The article of manufacture of claim 5 wherein the content to provide instructions to cause the machine to maintain SLAs further comprises the content providing instructions to cause the machine to separate the data packets into different queues corresponding to each different SLA.

9. A method of controlling congestion among a plurality of switching points, comprising:

managing a plurality of service level agreements (SLAs) specifying a minimum data rate of transmission for packets corresponding to each SLA, at each switching point;

sending a message from a downstream switching point to an upstream switching point to cause the upstream switching point to reduce a data rate at which packets associated with a specific SLA to be forwarded by the upstream switching point are output from the upstream switching point to a device downstream from the downstream switching point; and

sending a message from the downstream switching point to the upstream switching point to cause the upstream switching point to increase the data rate at which packets associated with the specific SLA are output from the upstream switching point to the device downstream from the downstream switching point.

10. A system comprising:

a first switching point to receive data packets, transmit the data packets to another switching point, manage service level agreements (SLAs) specifying a minimum data rate for packets corresponding to the SLA, and send a message to indicate that traffic between a source and a destination is congested; and

a second switching point coupled with the first switching point to manage SLAs specifying a minimum data rate for packets corresponding to the SLA, transmit packets from the second switching point in accordance with the SLA, receive the message from the first switching point, and reduce a data rate at which packets corresponding to an SLA indicated in the message, destined for the destination, are output from the second switching device in response to receiving the message.

11. The system of claim 10 wherein the second switching point reducing the data rate includes the second switching point to reduce the data rate to the minimum data rate specified by the corresponding SLA.

12. The system of claim 10 wherein the second switching point reducing the data rate includes the second switching point to reduce the data rate to below the minimum data rate specified by the corresponding SLA.

13. A method for controlling congestion in a network having a plurality of switching points, comprising:

maintaining a plurality of service level agreements (SLAs) at a switching point, each SLA having a corresponding minimum data rate;

receiving data packets corresponding to at least one of the SLAs;

detecting congestion for data packets corresponding to the at least one of the SLAs; and

sending a message from the switching point to indicate the congestion to an upstream switching point, the upstream switching point to route packets received from further upstream, to cause the upstream switching point to adjust a data rate at which packets corresponding to the at least one of the SLAs are output from the upstream switching point in response to the message.

14. The method of claim 13 wherein sending a message to indicate congestion to an upstream switching point comprises sending a message to indicate to the upstream switching point to reduce the data rate to a rate at or below the minimum data rate for the SLA.

15. The method of claim 13 further comprising:

sending a message from the switching point to an upstream switching point to cause the upstream switching point to increase the data rate when congestion is no longer detected for data packets corresponding to the at least one SLA.