Managing traffic within a data communication network

• US 7,738,376 B2
• Filed: 06/21/2007
• Issued: 06/15/2010
• Est. Priority Date: 04/01/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nicholson, Larry W., Balakrishnan, Garesh, Nair, Jitesh R., Chalmers, John P., Jeffries, Clark D., Sabhikhi, Ravinder K., Singh, Raj K.
• Primary Examiner(s): Vu; Huy D
• Assistant Examiner(s): Duffy; James P
• Application Number:
  US11/766,190
• Publication Number:
  US 20070268826A1
• Time in Patent Office: 1,090 Days
• Field of Search: None
• US Class Current: 370/232
• 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
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A flow control method and system including an algorithm for deciding to transmit an arriving packet into a processing queue or to discard it, or, in the case of instructions or packets that must not be discarded, a similar method and system for deciding at a service event to transmit an instruction or packet into a processing queue or to skip the service event. The transmit probability is increased or decreased in consideration of minimum and maximum limits for each flow, aggregate limits for sets of flows, relative priority among flows, queue occupancy, and rate of change of queue occupancy. The effects include protection of flows below their minimum rates, correction of flows above their maximum rates, and, for flows between minimum and maximum rates, reduction of constituent flows of an aggregate that is above its aggregate maximum. Practice of the invention results in low queue occupancy during steady congestion.

Claims

1. A method to manage traffic in a system of a computer network, comprising:

configuring a processor in communication with a random number generator and a storage queue to set a transmit probability to a value between zero and one for receiving traffic from at least one flow of a plurality of flows ported into the processor by;

reading a present value of the transmit probability of the at least one flow;

determining at least one of if the present value is below a minimum value for the at least one flow, if the present value is above a maximum value for the at least one flow and if the at least one flow is a member of an aggregate of the plurality of flows wherein a recent aggregate transmitted rate of all flows in the aggregate is greater than an aggregate limit;

if the present value is below the minimum value or above the maximum value or the recent aggregate transmitted rate is greater than the aggregate limit, then setting the transmit probability to a sum of the present value and a first positive constant or to a product of the present value multiplied by a second constant, the second positive constant having a value less than one; and

if the present value is above the minimum value and below the maximum value and the recent aggregate transmitted rate is not greater than the aggregate limit, then;

determining if a present occupancy of the queue is less than a certain fractional value of a total capacity of the queue, and if the present occupancy of the queue is less than the certain fractional value, then setting the transmit probability to a sum of the present value and a third constant;

if the present queue occupancy is not less than the certain fractional value, then determining if the present queue occupancy is less than another fractional value of the total queue capacity larger than the certain fractional value and if the present queue occupancy is less than a previous queue occupancy, and if the present queue occupancy is less than the another fractional value and the present queue occupancy is less than the previous queue occupancy, then setting the transmit probability to a sum of the present value and a fourth constant; and

if the present queue occupancy is not less than the certain fraction value and if either of the present queue occupancy is not less than the another fraction or the present queue occupancy is not less than a previous queue occupancy, then setting the transmit probability to the present value less a value of a fourth constant multiplied by a current transmitted rate of the at least one flow and divided by a maximum possible send rate of the at least one flow;

wherein the processor is further configured to compare a random number generated by the random number generator with the set transmit probability and

make a transmit decision regarding said at least one flow based upon a result of the comparison.

2. The method of claim 1 wherein the traffic includes data packets, and the transmit decision comprises transmitting data packets from said at least one flow if the random number is less than or equal (≦

)to the set transmit probability.

3. The method of claim 1 wherein the traffic includes data packets, and the transmit decision comprises not transmitting traffic from said at least one flow if the random number is greater than (>

) the set transmit probability.

4. The method of claim 3 wherein the transmit decision of not transmitting traffic comprises discarding the traffic.

5. The method of claim 3 wherein the transmit decision of not transmitting traffic comprises delaying transmission of traffic.

6. The method of claim 1 further including configuring the processor to:

assign a value for the minimum flow rate and a value for the maximum flow rate for the at least one flow; and

use the assigned minimum flow rate and maximum flow rate for the setting of the transmission probability.

7. The method of claim 1 further including configuring the processor to set values of the third constant, the fourth constant and the certain fractional value of the total queue capacity as a function of a priority of the at least one flow relative to a priority of another flow of the plurality of flows ported into the processor.

8. The method of claim 7 wherein the at least one flow priority is a next-higher priority relative to the priority of the another flow;

wherein the third constant of the higher-priority at least one flow has a value double a value of the third constant of the another flow;

wherein the fourth constant of the higher-priority at least one flow has a value one-half of a value of the fourth constant of the another flow; and

wherein the certain fractional value of the total queue capacity of the higher-priority at least one flow is double a value of the certain fractional value of the total queue capacity of the another flow.

9. The method of claim 8 further including configuring the processor to set the transmit probability within a same time period used as the flow rate sample time period.

10. The method of claim 9 wherein a value of the flow rate sample time period is about equal to a product of one-eighth times the total queue capacity divided by the maximum total flow rate.

11. A network device, comprising:

a specialized processor implemented in hardware, the processor in communication with a random number generator and a storage queue;

wherein the processor is configured to manage traffic in a system of a computer network by setting a transmit probability for receiving traffic from at least one flow of a plurality of flows ported into the processor to a value between zero and one, by;

reading a present value of the transmit probability of the at least one flow;

determining at least one of if the present value is below a minimum value for the at least one flow, if the present value is above a maximum value for the at least one flow and if the at least one flow is a member of an aggregate of the plurality of flows wherein a recent aggregate transmitted rate of all flows in the aggregate is greater than an aggregate limit;

if the present value is below the minimum value or above the maximum value or the recent aggregate transmitted rate is greater than the aggregate limit, then setting the transmit probability to a sum of the present value and a first positive constant or to a product of the present value multiplied by a second constant, the second positive constant having a value less than one; and

if the present value is above the minimum value and below the maximum value and the recent aggregate transmitted rate is not greater than the aggregate limit, then;

determining if a present occupancy of the queue is less than a certain fractional value of a total capacity of the queue, and if the present occupancy of the queue is less than the certain fractional value then setting the transmit probability to a sum of the present value and a third constant;

if the present queue occupancy is not less than the certain fractional value, then determining if the present queue occupancy is less than another fractional value of the total queue capacity larger than the certain fractional value and if the present queue occupancy is less than a previous queue occupancy, and if the present queue occupancy is less than the another fractional value and the present queue occupancy is less than the previous queue occupancy, then setting the transmit probability to a sum of the present value and a fourth constant; and

if the present queue occupancy is not less than the certain fraction value and if either of the present queue occupancy is not less than the another fraction or the present queue occupancy is not less than a previous queue occupancy, then setting the transmit probability to the present value less a value of a fourth constant multiplied by a current transmitted rate of the at least one flow and divided by a maximum possible send rate of the at least one flow;

wherein the processor is further configured to compare a random number generated by the random number generator with the set transmit probability and make a transmit decision regarding said at least one flow based upon a result of the comparison.

12. The network device of claim 11 wherein the traffic includes data packets and the transmit decision comprises transmitting data packets from said at least one flow if the random number is less than or equal (≦

) to the set transmit probability.

13. The network device of claim 11 wherein the traffic includes data packets and the transmit decision comprises not transmitting traffic from said at least one flow if the random number is greater than (>

) the set transmit probability.

14. The network device of claim 13 wherein the transmit decision of not transmitting traffic comprises discarding the traffic.

15. The network device of claim 13 wherein the transmit decision of not transmitting traffic comprises delaying transmission of traffic.

16. The network device of claim 11 wherein the processor is further configured to:

assign a value for the minimum flow rate and a value for the maximum flow rate for the at least one flow; and

use the assigned minimum flow rate and maximum flow rate for the setting of the transmission probability.

17. The network device of claim 11 wherein the processor is further configured to set values of the third constant, the fourth constant and the certain fractional value of the total queue capacity as a function of a priority of the at least one flow relative to a priority of another flow of the plurality of flows ported into the processor.

18. The network device of claim 17 wherein the at least one flow priority is a next-higher priority relative to the priority of the another flow;

wherein the third constant of the higher-priority at least one flow has a value double a value of the third constant of the another flow;

wherein the fourth constant of the higher-priority at least one flow has a value one-half of a value of the fourth constant of the another flow; and

wherein the certain fractional value of the total queue capacity of the higher-priority at least one flow is double a value of the certain fractional value of the total queue capacity of the another flow.

19. The network device of claim 18 wherein the processor is further configured to set the transmit probability within a same time period used as the flow rate sample time period.

20. The network device of claim 19 wherein a value of the flow rate sample time period is about equal to a product of one-eighth times the total queue capacity divided by the maximum total flow rate.