Bandwidth allocation in accordance with shared queue output limit

• US 20030007452A1
• Filed: 06/07/2001
• Published: 01/09/2003
• Est. Priority Date: 06/07/2001
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Jeffries, Clark Debs, Gorti, Brahmanand Kumar, Siegel, Michael Steven, Hwang, Dongming, Sudeep, Kartik
• Granted Patent: US 6,701,389 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• 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
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method for dynamically adjusting the flow rate of a plurality of logical pipes that share a common output queue. In accordance with the method of the present invention, a minimum flow rate and a maximum flow rate are set for each of the pipes. Next a determination is made of whether or not excess queue bandwidth exists in accordance with the output flow rate of the shared queue. The determination of whether or not excess bandwidth exists comprises comparing the output flow rate of the shared queue with a pre-determined threshold queue output value. An instantaneous excess bandwidth signal has a value of 1 if there is excess bandwidth and is otherwise 0 if there is no excess bandwidth. In an alternate embodiment, the instantaneous excess bandwidth signal for a particular pipe is logically ANDed with one or more additional excess bandwidth signals to form a composite instantaneous excess bandwidth signal. In response to the existence of excess queue bandwidth, a flow rate of a pipe is linearly increased while in response to a lack of excess queue bandwidth, the flow rate of the pipe is exponentially decreased.

Claims

1. A method for dynamically adjusting the flow rate of a plurality of pipes that feed into a shared queue, said method comprising:

setting a minimum flow and a maximum flow for each of said plurality of pipes;

determining whether or not excess queue bandwidth exists in accordance with a queue output flow rate;

in response to the existence of excess queue bandwidth, linearly increasing a flow rate of a pipe; and

in response to a lack of excess queue bandwidth, exponentially decreasing a flow rate of a pipe.

2. The method of claim 1, wherein said step of determining whether or not excess bandwidth exists comprises comparing said queue output flow rate with a pre-determined threshold queue output value.

3. The method of claim 2, wherein said step of determining whether or not excess bandwidth exists further comprises setting an instantaneous bandwidth signal in accordance with a single comparison of said queue output flow rate with said pre-determined threshold queue output value.

4. The method of claim 3, wherein said step of determining whether or not excess bandwidth exists further comprises setting an excess bandwidth signal to be an exponentially weighted average of said instantaneous excess bandwidth signal.

5. The method of claim 1, wherein the flow rate for a pipe among said plurality of pipes is evaluated as being equal to an offered rate multiplied by a transmit fraction.

6. The method of claim 5, wherein said step of linearly increasing a flow rate of a pipe further comprises setting said transmit fraction for said pipe in accordance with the relation:

T_i(t+Dt)=T_i(t)+C_i*E(t),

wherein T_i(t+Dt) represents the transmit fraction for a current epoch, T_i(t) represents the transmit fraction for a previous epoch, C_i represents a constant for increasing the flow rate, and E(t) represents an excess bandwidth value for said shared queue.

7. The method of claim 6, wherein C_i is determined in accordance with the relation:

8. The method of claim 5, wherein said step of exponentially decreasing a flow rate of a pipe further comprises setting a transmit fraction for said pipe in accordance with the relation:

T_i(t+Δ

t)=T_i−

D_i*f_i(t),

wherein T_i(t+Dt) represents a transmit fraction for a current epoch, T_i(t) represents a transmit fraction for a previous epoch, D_i represents a constant for decreasing the flow rate, and E(t) represents an excess bandwidth value for said shared queue.

9. The method of claim 8, wherein D_i is determined in accordance with the relation:

D_i=(W_i/W)*(S−

f_imin)/(2*S),

wherein W_i represents the weight for the i^th pipe, which is preferably in the range (0, 1], W represents the sum of the weights of all pipes feeding into said shared queue, and f_imin represents the minimum flow for the i^th pipe, and S represents the maximum send rate of said shared queue.

10. The method of claim 5, wherein said plurality of pipes forms a hierarchy of pipes and subpipes wherein if a subpipe offers traffic at or below its guaranteed minimum rate then it is fully transmitted.

11. The method of claim 10, wherein said plurality of pipes may be divided into a plurality of behavior aggregate flows.

12. The method of claim 11, wherein each of said plurality of behavior aggregate flows comprises a plurality of subpipes, and wherein said method further comprises in response to the sum of offered rates of said plurality of subpipes being at or below the sum of the guaranteed minimum rates of said plurality of subpipes, fully transmitting each of said plurality of subpipes.

14. The system of claim 13, further comprising processing means for comparing said queue output flow rate with a pre-determined threshold queue output value.

15. The system of claim 14, further comprising processing means for setting an instantaneous bandwidth signal in accordance with a single comparison of said queue output flow rate with said pre-determined threshold queue output value.

16. The system of claim 15, further comprising processing means for setting an excess bandwidth signal to be an exponentially weighted average of said instantaneous excess bandwidth signal.

17. The system of claim 15, further comprising processing means for setting an excess bandwidth signal to be an exponentially weighted average of said instantaneous excess bandwidth signal.

18. The system of claim 17, further comprising processing means for setting said transmit fraction for said pipe in accordance with the relation:

T_i(t+Dt)=T_i(t)+C_i*E(t),

wherein T_i(t+Dt) represents the transmit fraction for a current epoch, T_i(t) represents the transmit fraction for a previous epoch, C_i represents a constant for increasing the flow rate, and E(t) represents an excess bandwidth value for said shared queue.

19. The system of claim 18, further comprising processing means for determining C_i in accordance with the relation:

20. The system of claim 17, further comprising processing means for setting a transmit fraction for said pipe in accordance with the relation:

T_i(t+Δ

t)=T_i−

D_i*f_i(t),

wherein T_i(t+Dt) represents a transmit fraction for a current epoch, T_i(t) represents a transmit fraction for a previous epoch, D_i represents a constant for decreasing the flow rate, and E(t) represents an excess bandwidth value for said shared queue.

21. The system of claim 20, further comprising processing means for determining D_i in accordance with the relation:

D_i=(W_i/W)*(S−

f_imin)/(2*S),

wherein W_i represents the weight for the i^th pipe, which is preferably in the range (0, 1], W represents the sum of the weights of all pipes feeding into said shared queue, and f_imin represents the minimum flow for the i^th pipe, and S represents the maximum send rate of said shared queue.

22. The system of claim 17, wherein said plurality of pipes forms a hierarchy of pipes and subpipes, said system further comprising processing means for responsive to a subpipe offering traffic at or below its guaranteed minimum rate for fully transmitting said subpipe.

23. The system of claim 22, wherein said plurality of pipes may be divided into a plurality of behavior aggregate flows.

24. The system of claim 23, wherein each of said plurality of behavior aggregate flows comprises a plurality of subpipes, and wherein said system further comprises processing means responsive to the sum of offered rates of said plurality of subpipes being at or below the sum of the guaranteed minimum rates of said plurality of subpipes, for fully transmitting each of said plurality of subpipes.

26. The computer program product of claim 25, further comprising instruction means for comparing said queue output flow rate with a pre-determined threshold queue output value.

27. The computer program product of claim 26, further comprising instruction means for setting an instantaneous bandwidth signal in accordance with a single comparison of said queue output flow rate with said pre-determined threshold queue output value.

28. The computer program product of claim 27, further comprising instruction means for setting an excess bandwidth signal to be an exponentially weighted average of said instantaneous excess bandwidth signal.

29. The computer program product of claim 27, wherein the flow rate for a pipe among said plurality of pipes is evaluated as being equal to an offered rate multiplied by a transmit fraction.

30. The computer program product of claim 29, further comprising instruction means for setting said transmit fraction for said pipe in accordance with the relation:

T_i(t+Dt)=T_i(t)+C_i*E(t),

wherein T_i(t+Dt) represents the transmit fraction for a current epoch, T_i(t) represents the transmit fraction for a previous epoch, C_i represents a constant for increasing the flow rate, and E(t) represents an excess bandwidth value for said shared queue.

31. The computer program product of claim 30, further comprising instruction means for determining C_i in accordance with the relation:

32. The computer program product of claim 29, further comprising instruction means for setting a transmit fraction for said pipe in accordance with the relation:

T_i(t+Δ

t)=T_i−

D_i*f_i(t),

wherein T_i(t+Dt) represents a transmit fraction for a current epoch, T_i(t) represents a transmit fraction for a previous epoch, D_i represents a constant for decreasing the flow rate, and E(t) represents an excess bandwidth value for said shared queue.

33. The computer program product of claim 32, further comprising instruction means for determining D_i in accordance with the relation:

D_i=(W_i/W)*(S−

f_imin)/(2*S),

wherein W_i represents the weight for the i^th pipe, which is preferably in the range (0, 1], W represents the sum of the weights of all pipes feeding into said shared queue, and f_imin represents the minimum flow for the i^th pipe, and S represents the maximum send rate of said shared queue.

34. The computer program product of claim 29, wherein said plurality of pipes forms a hierarchy of pipes and subpipes, said computer program product further comprising instruction means for responsive to a subpipe offering traffic at or below its guaranteed minimum rate for fully transmitting said subpipe.

35. The computer program product of claim 34, wherein said plurality of pipes may be divided into a plurality of behavior aggregate flows.

36. The computer program product of claim 35, wherein each of said plurality of behavior aggregate flows comprises a plurality of subpipes, and wherein said computer program product further comprises instruction means responsive to the sum of offered rates of said plurality of subpipes being at or below the sum of the guaranteed minimum rates of said plurality of subpipes, for fully transmitting each of said plurality of subpipes.

13. A system for dynamically adjusting the flow rate of a plurality of pipes that feed into a shared queue, said system comprising:

processing means for setting a minimum flow and a maximum flow for each of said plurality of pipes;

processing means for determining whether or not excess queue bandwidth exists in accordance with a queue output flow rate;

processing means responsive to the existence of excess queue bandwidth for linearly increasing a flow rate of a pipe; and

processing means responsive to a lack of excess queue bandwidth for exponentially decreasing a flow rate of a pipe.

25. A computer program product for dynamically adjusting the flow rate of a plurality of pipes that feed into a shared queue, said computer program product comprising:

instruction means for setting a minimum flow and a maximum flow for each of said plurality of pipes;

instruction means for determining whether or not excess queue bandwidth exists in accordance with a queue output flow rate;

instruction means responsive to the existence of excess queue bandwidth for linearly increasing a flow rate of a pipe; and

instruction means responsive to a lack of excess queue bandwidth for exponentially decreasing a flow rate of a pipe.