Method and system for controlling transmission of packets in computer networks

• US 6,771,652 B1
• Filed: 11/23/1999
• Issued: 08/03/2004
• Est. Priority Date: 11/23/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jeffries, Clark Debs, Aydemir, Metin, Siegel, Michael Steven, Gallo, Anthony Matteo, Bass, Brian Mitchell, Rovner, Sonia Kiang
• Primary Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US09/448,380
• Time in Patent Office: 1,715 Days
• Field of Search: 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/428, 370/429, 370/229, 370/230, 370/230.1, 370/232, 370/233-235, 370/235.1, 370/236, 370/236.1, 370/236.2, 370/252, 370/253, 370/352, 370/353, 370/356, 370/389, 370/395.1, 370/395.21, 370/395.4, 370/395.7, 370/395.71, 370/395.72, 370/400, 370/401
• US Class Current: 370/412
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes

Abstract

A method and system for controlling a flow of a plurality of packets in a computer network is disclosed. The computer network includes a queue. The method and system include determining a queue level for the queue and determining an offered rate of the plurality of packets to the queue. The method and system also include controlling a transmission fraction of the plurality of packets to the queue, based on the queue level, the offered rate and a previous value of the transmission fraction so that the transmission fraction and the queue level are critically damped if the queue level is between at least a first queue level and a second queue level.

Claims

1. A method for controlling a flow of a plurality of packets in a computer network including a queue, the method comprising the steps of

(a) determining a queue level for the queue;

(b) determining an offered rate of the plurality of packets to the queue;

(c) controlling a transmission fraction of the plurality of packets to the queue, based on the queue level and the offered rate, so that the transmission fraction and the queue level are damped if the queue level is between at least a first queue level and a second queue level, wherein the transmission fraction is controlled after each of a plurality of epochs and wherein the transmission fraction controlling step (c) further includes the step of;

(c1) controlling the transmission fraction for an epoch of the plurality of epochs based on the queue level for a previous epoch, the offered rate for the previous epoch and the transmission fraction for the previous epoch such that the transmission fraction for the epoch and the queue level for the previous epoch would be damped.

2. The method of claim 1 wherein the transmissions fraction controlling step (c1) further includes the step of:

(c1) controlling the transmission fraction such that the queue level is critically damped.

3. The method of claim 1 wherein the queue further includes a hardware memory resource.

4. The method of claim 1 wherein the transmission fraction controlling step (c) further includes the step of:

(c2) dropping a portion of the plurality of packets based on the transmission fraction and a priority of each packet in the plurality of packets.

5. The method of claim 1 wherein the transmission fraction controlling step (c) further includes the steps of:

(c2) controlling the transmission fraction such that each packet of the plurality of packets is transmitted if the queue level is below a minimum threshold;

(c3) controlling the transmission fraction such that no packet or a small fraction of the plurality of packets is transmitted if the queue level is above a maximum threshold; and

(c4) controlling the transmission fraction such that the transmission fraction and the queue level are critically damped if the queue level is between the minimum threshold and the maximum threshold.

6. A method for controlling a flow of a plurality of packets in a computer network including a queue, the method comprising the steps of

(a) determining a queue level for the queue;

(b) determining an offered rate of the plurality of packets to the queue;

(c) controlling a transmission fraction of the plurality of packets to the queue, based on the queue level and the offered rate, so that the transmission fraction and the queue level are damped if the queue level is between at least a first queue level and a second queue level, wherein the transmission fraction controlling step (c) further includes the steps of;

(c1) setting a change in the transmission fraction with respect to time equal to a first quantity multiplied by a second quantity, the first quantity being dependent upon time, the second quantity being a first constant minus a second constant multiplied by the transmission fraction minus the queue level divided by a maximum possible queue level.

7. A computer-readable medium containing a program for controlling a flow of a plurality of packets in a computer network including a queue, the program including instructions for

(a) determining a queue level for the queue;

(b) determining an offered rate of the plurality of packets to the queue;

(c) controlling a transmission fraction of the plurality of packets to the queue, based on the queue level and the offered rate, so that the transmission fraction and the queue level are damped if the queue level is between at least a first queue level and a second queue level, wherein the transmission fraction is controlled after each of a plurality of epochs and wherein the transmission fraction controlling instructions (c) further includes instructions for;

(c1) controlling the transmission fraction for an epoch of the plurality of epochs based on the queue level for a previous epoch, the offered rate for the previous epoch and the transmission fraction for the previous epoch such that the transmission fraction for the epoch and the queue level for the previous epoch would be damped.

8. The computer-readable medium of claim 7 wherein the transmissions fraction controlling instructions (c1) further includes instructions for:

(c1) controlling the transmission fraction such that the queue level is critically damped.

9. The computer-readable medium of claim 7 wherein the queue further includes a hardware memory resource.

10. The computer-readable medium of claim 7 wherein the transmission fraction controlling instructions (c) further includes instructions for:

(c2) dropping a portion of the plurality of packets based on the transmission fraction and a priority of each packet in the plurality of packets.

11. The computer-readable medium of claim 7 wherein the transmission fraction controlling instructions (c) further includes instructions for:

(c2) controlling the transmission fraction such that each packet of the plurality of packets is transmitted if the queue level is below a minimum threshold;

(c3) controlling the transmission fraction such that no packet of the plurality of packets is transmitted if the queue level is above a maximum threshold; and

(c4) controlling the transmission fraction such that the transmission fraction and the queue level are critically damped if the queue level is between the minimum threshold and the maximum threshold.

12. A computer-readable medium containing a program for controlling a flow of a plurality of packets in a computer network including a queue, the program including instructions for

(a) determining a queue level for the queue;

(b) determining an offered rate of the plurality of packets to the queue;

(c) controlling a transmission fraction of the plurality of packets to the queue, based on the queue level and the offered rate, so that the transmission fraction and the queue level are damped if the queue level is between at least a first queue level and a second queue level, wherein the transmission fraction controlling instructions (c) further includes instructions for;

(c1) setting a change in the transmission fraction with respect to time equal to a first quantity multiplied by a second quantity, the first quantity being dependent upon time, the second to quantity being a first constant minus a second constant multiplied by the transmission fraction minus the queue level divided by a maximum possible queue level.

13. A system for controlling a flow of a plurality of packets in a computer network, the system comprising:

a queue for storing a portion of the plurality of packets;

an enqueuing mechanism, coupled with the queue, for receiving an offered rate of the plurality of packets and for controlling a transmission fraction of the plurality of packets to the queue, the transmission fraction being controlled based on a queue level for the queue and the offered rate so that the transmission fraction and the queue level are damped if the queue level is between at least a first queue level and a second queue level;

wherein the enqueuing mechanism controls the transmission fraction after each of a plurality of epochs and wherein the enqueuing mechanism controls the transmission fraction for an epoch of the plurality of epochs based on the queue level for a previous epoch, the offered rate for the previous epoch and the transmission fraction for the previous epoch such that the transmission fraction for the epoch and the queue level for the previous epoch would be damped.

14. The system of claim 13 wherein the transmission fraction is controlled to allow the queue level to be critically damped.

15. The system of claim 13 wherein the queue further includes a hardware memory resource.

16. The system of claim 13 wherein the enqueuing mechanism further drops a portion of the plurality of packets based on the transmission fraction and a priority of each packet in the plurality of packets.

17. The system of claim 13 wherein the enqueuing mechanism further controls the transmission fraction such that each packet of the plurality of packets is transmitted if the queue level is below a minimum threshold, no packet of the plurality of packets is transmitted if the queue level is above a maximum threshold, and the transmission fraction and the queue level are critically damped if the queue level is between the minimum threshold and the maximum threshold.

18. A system for controlling a flow of a plurality of packets in a computer network, the system comprising:

a queue for storing a portion of the plurality of packets;

an enqueuing mechanism, coupled with the queue, for receiving an offered rate of the plurality of packets and for controlling a transmission fraction of the plurality of packets to the queue, the transmission fraction being controlled based on a queue level for the queue and the offered rate so that the transmission fraction and the queue level are damped if the queue level is between at least a first queue level and a second queue level;

wherein the enqueuing mechanism further controls the transmission fraction by setting a change in the transmission fraction with respect to time equal to a first quantity multiplied by a second quantity, the first quantity being dependent upon time, the second quantity being a first constant minus a second constant multiplied by the transmission fraction minus the queue level divided by a maximum possible queue level.