Method and system for managing traffic within a data communication network

• US 7,274,666 B2
• Filed: 04/01/2003
• Issued: 09/25/2007
• Est. Priority Date: 04/01/2003
• Status: Expired due to Fees

• 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.
• Primary Examiner(s): Chan; Wing
• Assistant Examiner(s): Burrowes; Lawrence J
• Application Number:
  US10/405,673
• Publication Number:
  US 20040196790A1
• Time in Patent Office: 1,638 Days
• Field of Search: 370/232, 370/252, 370/429, 370/417, 370/412, 370/235, 370/229
• 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;

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);

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) 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 down to a minimum of 0;

j) else if 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.

2. 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;

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);

1) 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 ⅛

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/128for 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/32for high priority traffic and higher for lower priority traffic.