Method and system for providing optimal discard fraction

• US 6,724,776 B1
• Filed: 11/23/1999
• Issued: 04/20/2004
• Est. Priority Date: 11/23/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Jeffries, Clark Debs
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): NGUYEN, VAN KIM T
• Application Number:
  US09/448,190
• Time in Patent Office: 1,610 Days
• Field of Search: 370/229, 370/230-238, 370/412-418, 370/428, 370/429, 370/465, 370/468, 709/227, 709/240
• US Class Current: 370/468
• 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 network includes a queue having a maximum queue level that is possible. 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 determining a virtual maximum queue level based on the queue level and the maximum queue level and controlling a transmission fraction of the plurality of packets to the queue, based on the queue level, the offered rate and the virtual maximum queue level.

Claims

1. A method for controlling a flow of a plurality of packets in a computer network including a queue having a maximum queue level that is possible, 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) determining a virtual maximum queue level based on the queue level and the maximum queue level;

wherein the virtual maximum queue level determining step further includes the steps of;

(c1) increasing the virtual maximum queue level to a maximum that is less than or equal to the maximum queue level if the queue level is above a first threshold; and

(c2) decreasing the virtual maximum queue level if the queue level is below a second threshold; and

(d) controlling a transmission fraction of the plurality of packets to the queue, based on the queue level, the offered rate and the virtual maximum queue level.

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

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

(d1) discarding a portion of the plurality of packets based on the transmission rate and a priority of each packet in the plurality of packets.

22. The method of claim 1 wherein congestion is determined based upon the queue level.

2. A method for controlling a flow of a plurality of packets in a computer network including a queue having a maximum queue level that is possible, 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) determining a virtual maximum queue level based on the queue level and the maximum queue level, wherein the virtual maximum queue level determining step (c) further includes the steps of

(c1) providing a multiplier for the maximum queue level, the multiplier being an exponentially weighted average which approaches a first level if the queue level is below a threshold and which approaches a second level if the queue level is above the threshold, the first level corresponding to the virtual queue level being a minimum virtual queue level and the second level corresponding to the virtual queue level being the maximum queue level;

(d) controlling a transmission fraction of the plurality of packets to the queue, based on the queue level, the offered rate and the virtual maximum queue level, and wherein the transmission fraction controlling step further includes the step of

(d1) controlling the transmission fraction based on the queue level, the offered rate, a previous transmission fraction, the multiplier and the maximum queue level.

3. The method of claim 2 wherein the multiplier providing step (c1) further includes the step of:

(c1i) setting the multiplier equal to a first constant multiplied by a previous multiplier plus a second constant if the queue level is below the threshold; and

(c1ii) setting the multiplier equal to the first constant multiplied by the previous multiplier plus a third constant if the queue level is above the threshold.

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

(d1i) controlling the transmission fraction to be one if the queue level is below a minimum queue level; and

(d1ii) controlling the transmission fraction to be the minimum of one and a second value, the second value being the maximum of a fourth constant and a third value, the third value being the previous transmission fraction plus a fourth value, the fourth value being a fifth value multiplied by a sixth value, the fifth value being a fifth constant multiplier by a previous multiplier multiplied by the offered rate multiplied by a time interval divided by the maximum queue level, the sixth value being a sixth constant minus a seventh constant multiplied by the previous transmission fraction minus an eighth constant multiplied by the previous multiplier multiplied by the queue level divided by the maximum queue level.

5. The method of claim 4 wherein the queue level is a previous queue level and the offered rate is a previous offered rate.

8. A computer-readable medium containing a program for controlling a flow of a plurality of packets in a computer network including a queue having a maximum queue level that is possible, 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) determining a virtual maximum queue level based on the queue level and the maximum queue level, wherein the virtual maximum queue level determining instructions (c) further includes instruction for;

(c1) increasing the virtual maximum queue level to a maximum that is less than or equal to the maximum queue level if the queue level is above a first threshold; and

(c2) decreasing the virtual maximum queue level if the queue level is below a second threshold; and

(d) controlling a transmission fraction of the plurality of packets to the queue, based on the queue level, the offered rate and the virtual maximum queue level.

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

14. The computer-readable medium of claim 8 wherein the transmission fraction controlling instructions (d) further includes instructions for:

(d1) discarding a portion of the plurality of packets based on the transmission rate and a priority of each packet in the plurality of packets.

9. A computer-readable medium containing a program for controlling a flow of a plurality of packets in a computer network including a queue having a maximum queue level that is possible, 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) determining a virtual maximum queue level based on the queue level and the maximum queue level, wherein the virtual maximum queue level determining instructions (c) further includes the steps of

(c1) providing a multiplier for the maximum queue level, the multiplier being an exponentially weighted average which approaches a first level if the queue level is below a threshold and which approaches a second level if the queue level is above the threshold, the first level corresponding to the virtual queue level being a minimum virtual queue level and the second level corresponding to the virtual queue level being the maximum queue level; and

(d) controlling a transmission fraction of the plurality of packets to the queue, based on the queue level, the offered rate and the virtual maximum queue level, wherein the transmission fraction controlling step further includes the step of

(d1) controlling the transmission fraction based on the queue level, the offered rate, a previous transmission fraction, the multiplier and the maximum queue level.

10. The computer-readable medium of claim 9 wherein the multiplier providing instructions (c1) further includes instructions for:

(c1i) setting the multiplier equal to a first constant multiplied by a previous multiplier plus a second constant if the queue level is below the threshold; and

(c1ii) setting the multiplier equal to the first constant multiplied by the previous multiplier plus a third constant if the queue level is above the threshold.

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

(d1i) controlling the transmission fraction to be one if the queue level is below a minimum queue level; and

(d1ii) controlling the transmission fraction to be the minimum of one and a second value, the second value being the maximum of a fourth constant and a third value, the third value being the previous transmission fraction plus a fourth value, the fourth value being a fifth value multiplied by a sixth value, the fifth value being a fifth constant multiplier by a previous multiplier multiplied by the offered rate multiplied by a time interval divided by the maximum queue level, the sixth value being a sixth constant minus a seventh constant multiplied by the previous transmission fraction minus an eighth constant multiplied by the previous multiplier multiplied by the queue level divided by the maximum queue level.

12. The computer-readable medium of claim 11 wherein the queue level is a previous queue level and the offered rate is a previous offered rate.

23. The computer-readable medium of claim 10 wherein congestion is determined based upon the queue level.

15. 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, the queue having a maximum queue level that is possible;

an enqueuing mechanism, coupled with the queue, for receiving an offered rate of the plurality of packets and for determining a virtual maximum queue level based on a queue level for the queue and the maximum queue level, the enqueuing mechanism also for controlling a transmission fraction of the plurality of packets to the queue, the transmission rate being controlled based on the queue level for the queue, the offered rate and the virtual maximum queue level wherein the enqueuing mechanism further increases the virtual maximum queue level to a maximum that is less than or equal to the maximum queue level if the queue level is above a first threshold and decreases the virtual maximum queue level if the queue level is below a second threshold.

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

21. The system of claim 15 wherein the enqueuing mechanism further discards a portion of the plurality of packets based on the transmission rate and a priority of each packet in the plurality of packets.

24. The system of claim 15 wherein congestion is determined based upon the queue level.

16. 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, the queue having a maximum queue level that is possible;

an enqueuing mechanism, coupled with the queue, for receiving an offered rate of the plurality of packets and for determining a virtual maximum queue level based on a queue level for the queue and the maximum queue level, the enqueuing mechanism also for controlling a transmission fraction of the plurality of packets to the queue, the transmission rate being controlled based on the queue level for the queue, the offered rate and the virtual maximum queue level wherein the enqueuing mechanism further provides a multiplier for the maximum queue level, the multiplier being an exponentially weighted average which approaches a first level if the queue level is below a threshold and which approaches a second level if the queue level is above the threshold, the first level corresponding to the virtual queue level being a minimum virtual queue level and the second level corresponding to the virtual queue level being the maximum queue level; and

wherein the enqueuing mechanism further controls the transmission fraction based on the queue level, the offered rate, a previous transmission fraction, the multiplier and the maximum queue level.

17. The system of claim 16 wherein the enqueuing mechanism further sets the multiplier equal to a first constant multiplied by a previous multiplier plus a second constant if the queue level is below the threshold and sets the multiplier equal to the first constant multiplied by the previous multiplier plus a third constant if the queue level is above the threshold.

18. The system of claim 17 wherein the enqueuing mechanism further controls the transmission fraction to be the minimum of one and a second value, the second value being the maximum of a fourth constant and a third value, the third value being the previous transmission fraction plus a fourth value, the fourth value being a fifth value multiplied by a sixth value, the fifth value being a fifth constant multiplier by a previous multiplier multiplied by the offered rate multiplied by a time interval divided by the maximum queue level, the sixth value being a sixth constant minus a seventh constant multiplied by the previous transmission fraction minus an eighth constant multiplied by the previous multiplier multiplied by the queue level divided by the maximum queue level.

19. The system of claim 18 wherein the queue level is a previous queue level and the offered rate is a previous offered rate.