Method and system for managing traffic within a data communication network

• US 20040196790A1
• Filed: 04/01/2003
• Published: 10/07/2004
• Est. Priority Date: 04/01/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Balakrishnan, Ganesh, Jeffries, Clark D., Sabhikhi, Ravinder K., Singh, Raj K., Nicholson, Larry W., Nair, Jitesh R., Chalmers, John P.
• Granted Patent: US 7,274,666 B2
• Time in Patent Office: Days
• 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 including acts of:

a) providing N flows in which the traffic are placed, N greater than 1;

b) calculating a transmit probability Ti for at least one flow wherein said Ti is in part based upon at least one flow being a member of an aggregate of flows;

c) generating a random number for the at least one flow;

d) comparing the random number with Ti; and

e) making a 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.

3. The method of claim 1 wherein the traffic includes instructions.

4. The method of claims 1 or 2 wherein making the decision step (e) further includes the act of transmitting data packets from said at least one flow, if the random number is less than or equal (≦

) to the Ti.

5. The method of claims 1 or 2 wherein making the decision step (e) further includes the act of not transmitting traffic from said at least one flow if the random number is greater than (>

) Ti.

6. The method of claims 2 or 3 further including the acts of providing a storage queue to receive traffic from said at least one flow Ti.

7. The method of claim 5 wherein the act of not transmitting traffic further includes the act of discarding the traffic.

8. The method of claim 5 wherein the act of not transmitting traffic delays transmission of traffic.

9. The method of claim 1 further including acts of (f) assigning minimum (min) flow rate and maximum (max) flow rate for the at least one flow;

(f1) using assigned min and max to calculate transmission probability Ti.

10. The method of claim 9 wherein the act of calculating transmission probability Ti further includes acts of:

g) if current traffic in the at least one flow is below its flow minimum mini, then Ti should increase up to a maximum of 1;

h) else if the current traffic in the at least one flow is above its flow maximum maxi, then Ti should decrease down to a minimum of 0;

i) elseif the flow is in any aggregate j in which the current aggregate flow is above the maximum aggi max, then Ti should decrease down to a minimum of 0;

j) elseif the system is declared not to be congested, the value of Ti should increase up to a maximum of 1;

k) else Ti should decrease toward a minimum of 0.

11. The method according to claim 9, wherein the act of calculating the transmit probability Ti(t) further includes the acts of:

l) if the current traffic in the at least one flow is below its flow minimum mini, then Ti should increase by adding a constant, such as 1/16, up to a maximum value of 1;

m) else if the current traffic in the at least one flow is above its flow maximum maxi, then Ti should decrease by multiplying it by a constant positive value<

1, such as 31/32;

n) else if the flow is in any aggregate j in which the current aggregate flow is above the maximum aggj max, then Ti should decrease by multiplying it by a constant positive value<

1, such as 31/32;

o) else if the fraction Q of queue occupancy of a buffer relative to full capacity satisfies

Q<

a low threshold fraction Thi of Queue capacity, the value of Thi being for example 1/8 for high priority traffic and lower for lower priority traffic

OR {if Q<

a larger but still low threshold such as 2*Thi of Queue capacity AND Queue occupancy is decreasing}

then Ti should increase by adding a constant, such as Ci, up to a maximum value of 1, the value of Ci being for example 1/128 for high priority traffic and lower for lower priority traffic;

p) else Ti should decrease toward a minimum of 0 by subtracting the product of a constant Di times flow rate i divided by maximum processor sending capacity S, the value of Di being for example 1/32 for high priority traffic and higher for lower priority traffic.

13. The method of claim 1 further including acts of determining length of a queue within a buffer;

and

using said length of queue to calculate Ti.

12. A method to manage traffic in a computer network comprising the acts of:

a) providing N flows, N>

1;

b) aggregating selected ones of the N flows into at least one set;

c) assigning an aggregate maximum flow rate for said at least one set;

d) measuring the actual flow rate for the at least one set;

e) comparing the measured actual flow rate with assigned aggregate maximum flow rate; and

f) adjusting individual flow, within the selected one of said N flows until the actual maximum flow of said at least one set of said N flows is within the assigned aggregate maximum flow rate, if the measured actual maximum flow rate exceeds the assigned aggregate maximum flow rate.