Active queue management with flow proportional buffering

• US 6,901,593 B2
• Filed: 05/08/2001
• Issued: 05/31/2005
• Est. Priority Date: 05/08/2001
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Aweya, James, Ouellette, Michel, Montuno, Delfin Y.
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US09/850,057
• Publication Number:
  US 20020188648A1
• Time in Patent Office: 1,484 Days
• Field of Search: 718/104, 718/100, 370/230, 370/235, 370/236, 370/249, 370/352, 370/396, 370/400, 709/226, 709/228
• US Class Current: 718/104
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• 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
• CPC Class Codes: H04L 49/9078 using an external memory or storage device

Abstract

A technique for an improved active queue management scheme which dynamically changes its threshold settings as the number of connections (and system load) changes is disclosed. Using this technique, network devices can effectively control packet losses and TCP timeouts while maintaining high link utilization. The technique also allows a network to support a larger number of connections during congestion periods.

Claims

1. A method for dynamically allocating a buffer, the method comprising:

estimating a number of active connections;

adjusting a queue threshold for a queue by setting the queue threshold (T(n)) according to the relation;

$T<br><br>\left(n\right)=\max <br><br>\left\{\frac{P}{2<br><br>\hat{N}<br><br>\left(n\right)-1},\mathrm{\gamma <br><br>}<br><br>\hat{N}<br><br>\left(n\right)\right\},$

where P is a bandwidth-delay product, {circumflex over (N)}(n) is an estimated number of active connections at measurement time n, and γ

is a predetermined parameter that represents a minimum number of packets buffered per connection to avoid a TCP timeout;

computing a drop probability based, at least in part, on the adjusted threshold and a measured queue size;

executing a packet drop routine based upon the drop probability.

2. The method of claim 1 wherein the step of estimating a number of active connections further comprises:

filtering the estimated number of active connections.

3. The method of claim 1 wherein the step of computing a drop probability further comprises:

sampling the queue size q(n) at a time n;

calculating an error signal e(n), at time n according to the relation e(n)=q(n)−

T(n), where T(n) is the queue threshold at time n; and

calculating a drop probability p_d(n) at time n according to the relation $p_d<br><br>\left(n\right)=\min <br><br>\left\{\max <br><br>\left[p_d<br><br>\left(n-1\right)+\mathrm{\alpha <br><br>}<br><br>\frac{e<br><br>\left(n\right)}{2<br><br>T<br><br>\left(n\right)},0\right],\mathrm{\theta <br><br>}\right\},$

 

where α

is a control gain parameter and θ

is a predetermined upper limit on the drop probability.

4. The method of claim 3 wherein the step of calculating an error signal e(n) further comprises:

filtering the error signal e(n) according to the relation;

(1−

β

)ê

(n−

1)+β

e(n), where β

is a filter gain parameter and ê

(n−

1) is the filtered error signal at time n−

1.

5. The method of claim 1 wherein the step of executing a packet drop routine further comprises:

dropping packets according to a random number generator drop scheme.

6. The method of claim 1 wherein the step of executing a packet drop routine further comprises:

dropping packets according to an inter-drop interval count routine.

7. An apparatus for dynamically allocating a buffer, the apparatus comprising:

an active connection estimator for estimating a number of active connections;

a queue threshold adjuster for adjusting a queue threshold for a queue, the queue threshold adjuster further comprising a module for setting the queue threshold (T(n)) according to the relation;

$T<br><br>\left(n\right)=\max <br><br>\left\{\frac{P}{2<br><br>\hat{N}<br><br>\left(n\right)-1},\mathrm{\gamma <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{N}<br><br>\left(n\right)\right\},$

where P is a bandwidth-delay product, {circumflex over (N)}(n) is an estimated number of active connections at measurement time n, and γ

is a predetermined parameter that represents a minimum number of packets buffered per connection to avoid a TCP timeout;

a drop probability calculator for computing a drop probability based, at least in part, on the adjusted threshold and a sampled queue size; and

a packet drop module for executing a packet drop routine based upon the drop probability.

8. The apparatus of claim 7 wherein the active connection estimator further comprises:

a filter for filtering the estimated number of active connections.

9. The apparatus of claim 7 wherein the drop probability calculator further comprises:

a queue size sampler for sampling the queue size q(n) at a time n;

an error signal calculator for calculating an error signal e(n), at time n according to the relation e(n)=q(n)−

T(n), where T(n) is the queue threshold at time n; and

a module for calculating a drop probability p_d(n), at time n according to the relation $P_d<br><br>\left(n\right)=\min <br><br>\left\{\max <br><br>\left[p_d<br><br>\left(n-1\right)+\mathrm{\alpha <br><br>}<br><br>\frac{e<br><br>\left(n\right)}{2<br><br>T<br><br>\left(n\right)},0\right],\mathrm{\theta <br><br>}\right\},$

 

where α

is a control gain parameter and θ

is a predetermined upper limit on the drop probability.

10. The apparatus of claim 9 wherein the error signal calculator further comprises:

a filter for filtering the error signal e(n) according to the relation;

(1−

β

)ê

(n−

1)+β

e(n), where β

is a filter gain parameter and ê

(n−

1) is the filtered error signal at time n−

1.

11. The apparatus of claim 7 wherein the packet drop module further comprises:

a random number generator drop scheme module.

12. The apparatus of claim 7 wherein the packet drop module further comprises:

an inter-drop interval count routine module.

13. An article of manufacture for dynamically allocating a buffer, the article of manufacture comprising:

at least one processor readable carrier; and

instructions carried on the at least one carrier;

wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to;

estimate a number of active connections;

adjust a queue threshold for a queque by setting the queue threshold (T(n)) according to the relation;

$T<br><br>\left(n\right)=\max <br><br>\left\{\frac{P}{2<br><br>\hat{N}<br><br>\left(n\right)-1},\mathrm{\gamma <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{N}<br><br>\left(n\right)\right\},$

where P is a bandwidth-delay product, {circumflex over (N)}(n) is an estimated number of active connections at measurement time n, and γ

is a predetermined parameter that represents a minimum number of packets buffered per connection to avoid a TCP timeout;

compute a drop probability based, at least in part, on the adjusted threshold and a measured queue size;

execute a packet drop routine based upon the drop probability.

14. A signal embodied in a carrier wave and representing sequences of instructions which, when executed by at least one processor, cause the at least one processor to dynamically allocate a buffer by performing the steps of:

estimating a number of active connections;

adjusting a queue threshold for a queue by setting the queue threshold (T(n)) according to the relation;

$T<br><br>\left(n\right)=\max <br><br>\left\{\frac{P}{2<br><br>\hat{N}<br><br>\left(n\right)-1},\mathrm{\gamma <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\hat{N}<br><br>\left(n\right)\right\},$

where P is a bandwidth-delay product, {circumflex over (N)}(n) is an estimated number of active connections at measurement time n, and γ

is a predetermined parameter that represents a minimum number of packets buffered per connection to avoid a TCP timeout;

computing a drop probability based, at least in part, on the adjusted threshold and a measured queue size;

executing a packet drop routine based upon the drop probability.