QUEUE MANAGEMENT SYSTEM AND METHODS

• US 20100202469A1
• Filed: 02/10/2009
• Published: 08/12/2010
• Est. Priority Date: 02/10/2009
• Status: Active Grant

• Current Assignee: Optis Wireless Technology, LLC (Brevet Capital)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: ISAKSSON, Martin, LJUNGBERG, Malin, EKSTROM, Hannes
• Granted Patent: US 8,565,249 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/127 by using congestion prediction
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• 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

Abstract

A system and method are provided for managing a queue of packets transmitted from a sender to a receiver across a communications network. The sender has a plurality of sender states and a queue manager situated in between the sender and receiver may have a corresponding plurality of queue manager states. The queue manager has one or more queue management parameters which may have distinct predetermined values for each of the queue manager states. When the queue manager detects an event that is indicative of a change in the sender'"'"'s state, the queue manager may change its state correspondingly.

Claims

1. A queue management method, comprising:

initializing a queue for queuing packets transmitted from a communication device, wherein the step of initializing the queue comprises setting a queue management parameter equal to a first value;

while the queue management parameter is equal to the first value, using the queue management parameter in a queue management process for managing the queue;

in response to the detection of a first predetermined event, setting the queue management parameter equal to a second value, wherein the step of detecting the first predetermined event comprises one or more of;

(a) detecting that a packet transmission process executing in the communication device has transitioned from a first state to a second state,

(b) detecting an event that suggests the packet transmission process has transitioned from the first state to the second state,

(c) detecting that the packet transmission process will transition from a first state to a second state, and

(d) detecting an event that suggests the packet transmission process will transition from a first state to a second state; and

while the queue management parameter is equal to the second value, using the queue management parameter in the queue management process for managing the queue.

2. The queue management method of claim 1, wherein the second value is greater than the first value.

3. The queue management method of claim 1, wherein the second value is two times greater or about two times greater than the first value.

4. The queue management method of claim 1, wherein the step of detecting an event that suggests the packet transmission process will transition from the first state to the second state comprises determining whether a packet has been dropped from the queue.

5. The queue management method of claim 1, wherein the step of detecting an event that suggests the packet transmission process has transitioned from the first state to the second state comprises determining whether the rate at which packets are arriving at the queue is increasing linearly.

6. The queue management method of claim 1, further comprising:

in response to the detection of a second predetermined event, setting the queue management parameter equal to the first value; and

after the detection of the second predetermined event and while the queue management parameter is equal to the first value, using the queue management parameter in the queue management process.

7. The queue management method of claim 6, wherein the step of detecting the second predetermined event comprises one or more of:

(a) detecting that the packet transmission process has transitioned back to the first state;

(b) detecting an event that suggests the packet transmission process has transitioned back to the first state;

(c) detecting that the packet transmission process will transition back to the first state; and

(d) detecting an event that suggests the packet transmission process will transition back to the first state.

8. The queue management method of claim 7, wherein the step of detecting an event that suggests the packet transmission process has transitioned back to the first state comprises detecting a certain amount of queue inactivity.

9. The queue management method of claim 7, wherein the step of detecting an event that suggests the packet transmission process has transitioned back to the first state comprises determining whether the rate at which packets are arriving at the queue is increasing exponentially.

10. The queue management method of claim 1, wherein the step of using the queue management parameter in the queue management process comprises using the queue management parameter in deciding whether a packet in the queue should be dropped from the queue.

11. The queue management method of claim 10, wherein the step of using the queue management parameter in deciding whether a packet in the queue should be dropped from the queue comprises:

(i) determining a time value representing the length of time the packet has been in the queue and (ii) comparing the time value to the value of the queue management parameter.

12. The queue management method of claim 11, further comprising dropping the packet from the queue in response to the result of the comparing step indicating that the time value is greater than the value of the queue management parameter.

13. The queue management method of claim 1, wherein

the step of initializing the queue further comprises (i) setting a second queue management parameter equal to a third value and (ii) setting a third queue management parameter equal to a fourth value, and

the method further comprises

while the first queue management parameter is equal to the first value, the second queue management parameter is equal to the third value, and the third queue management parameter is equal to the fourth value, using the first, second and third queue management parameters in deciding whether a packet in the queue should be dropped from the queue;

in response to the detection of the first predetermined event, setting the second queue management parameter equal to a fifth value and setting the third queue management parameter equal to a sixth value; and

while the first queue management parameter is equal to the second value, the second queue management parameter is equal to the fifth value, and the third queue management parameter is equal to the sixth value, using the first, second and third queue management parameters in deciding whether a packet in the queue should be dropped from the queue.

14. The queue management method of claim 1, wherein the packets transmitted from a communication device are transmission control protocol (TCP) packets.

15. The queue management method of claim 1, further comprising:

in response to the detection of a second predetermined event, setting the queue management parameter equal to a third value; and

after the detection of the second predetermined event and while the queue management parameter is equal to the third value, using the queue management parameter in the queue management process.

16. The queue management method of claim 15, wherein the step of detecting the second predetermined event comprises one or more of:

(a) detecting that the packet transmission process has transitioned from the second state to a third state,

(b) detecting an event that suggests the packet transmission process has transitioned from the second state to a third state,

(c) detecting that the packet transmission process will transition from the second state to a third state, and

(d) detecting an event that suggests the packet transmission process will transition from the second state to a third state.

17. A network node for queuing packets received from a communication device, comprising:

a packet queue for storing packets; and

a queue manager configured to manage the queue,

wherein the queue manager is configured to;

(a) initialize the queue, wherein as part of initializing the queue the queue manager is configured to set a queue management parameter equal to a first predetermined value;

(b) use the queue management parameter in a queue management process for managing the queue while the queue management parameter is equal to the first value;

(c) set the queue management parameter equal to a second predetermined value in response to the detection of a first predetermined event, wherein the queue manager is configured to detect the first predetermined event by;

(1) detecting that a packet transmission process executing in the communication device has transitioned from a first state to a second state,

(2) detecting an event that suggests the packet transmission process has transitioned from the first state to the second state,

(3) detecting that the packet transmission process will transition from a first state to a second state, and/or

(4) detecting an event that suggests the packet transmission process will transition from the first state to the second state; and

(d) use the queue management parameter in the queue management process while the queue management parameter is equal to the second value.

18. The network node of claim 17, wherein the second value is greater than the first value.

19. The network node of claim 17, wherein the second value is two times greater or about two times greater than the first value.

20. The network node of claim 17, wherein the queue manager is configured to detect an event that suggests the packet transmission process will transition from the first state to the second state by determining whether a packet has been dropped from the queue.

21. The network node of claim 17, wherein the queue manager is further configured to:

set the queue management parameter equal to the first value in response to the detection of a second predetermined event; and

use the queue management parameter in the queue management process after the detection of the second predetermined event and while the queue management parameter is equal to the first value.

22. The network node of claim 21, wherein the queue manager is configured to detect the second predetermined event by:

(a) detecting that the packet transmission process has transitioned back to the first state,

(b) detecting an event that suggests the packet transmission process has transitioned back to the first state,

(c) detecting that the packet transmission process will transition back to the first state, and/or

(d) detecting an event that suggests the packet transmission process will transition back to the first state.

23. The network node of claim 22, wherein the queue manager is configured to detect an event that suggests the packet transmission process has transitioned back to the first state by detecting a predetermined amount of queue inactivity.

24. The network node of claim 17, wherein the queue manager is configured to use the queue management parameter in the queue management process by using the queue management parameter in deciding whether a packet in the queue should be dropped from the queue.

25. The network node of claim 24, wherein the queue manager is configured to use the queue management parameter in deciding whether a packet in the queue should be dropped from the queue by:

(i) determining a time value representing the length of time the packet has been in the queue and (ii) comparing the time value to the value of the queue management parameter.

26. The network node of claim 25, wherein the queue manager is further configured to drop the packet from the queue in response to the result of the comparing step indicating that the time value is greater than the value of the queue management parameter.

27. The network node of claim 17, wherein

the queue manager is configured to (i) set a second queue management parameter equal to a third value and (ii) set a third queue management parameter equal to a fourth value as part of the queue initialization process, and

the queue manager is further configured to:

use the first, second and third queue management parameters in deciding whether a packet in the queue should be dropped from the queue while the first queue management parameter is equal to the first value, the second queue management parameter is equal to the third value, and the third queue management parameter is equal to the fourth value;

set the second queue management parameter equal to a fifth value and set the third queue management parameter equal to a sixth value in response to the detection of the first predetermined event; and

use the first, second and third queue management parameters in deciding whether a packet in the queue should be dropped from the queue while the first queue management parameter is equal to the second value, the second queue management parameter is equal to the fifth value, and the third queue management parameter is equal to the sixth value.

28. The network node of claim 17, wherein the packets transmitted from a communication device are transmission control protocol (TCP) packets.

29. The network node of claim 17, wherein the queue manager is further configured to:

set the queue management parameter equal to a third value in response to the detection of a second predetermined event; and

use the queue management parameter in the queue management process after the detection of the second predetermined event and while the queue management parameter is equal to the third value.

30. The network node of claim 29, wherein the queue manager is configured to detect the second predetermined event by:

(a) detecting that the packet transmission process has transitioned from the second state to a third state,

(b) detecting an event that suggests the packet transmission process has transitioned from the second state to a third state,

(c) detecting that the packet transmission process will transition from the second state to a third state, and/or

(d) detecting an event that suggests the packet transmission process will transition from the second state to a third state.

31. A computer program product comprising a computer usable medium having a computer readable program code embodied therein, said computer readable program code adapted to be executed to implement a method for managing a queue, said method comprising:

initializing a queue for queuing packets transmitted from a communication device, wherein the step of initializing the queue comprises setting a queue management parameter equal to a first value;

while the queue management parameter is equal to the first value, using the queue management parameter in a queue management process for managing the queue;

in response to the detection of a first predetermined event, setting the queue management parameter equal to a second value, wherein detecting the first predetermined event comprises one or more of;

(a) detecting that a packet transmission process executing in the communication device has transitioned from a first state to a second state, p2 (b) detecting an event that suggests the packet transmission process has transitioned from the first state to the second state,

(c) detecting that the packet transmission process will transition from a first state to a second state, and

(d) detecting an event that suggests the packet transmission process will transition from a first state to a second state; and

while the queue management parameter is equal to the second value, using the queue management parameter in the queue management process for managing the queue.

32. The computer program product of claim 31, wherein the second value is greater than the first value.

33. The computer program product of claim 31, wherein the second value is two times greater or about two times greater than the first value.

34. The computer program product of claim 31, wherein the step of detecting an event that suggests the packet transmission process will transition from the first state to the second state comprises determining whether a packet has been dropped from the queue.

35. The computer program product of claim 31, wherein the method further comprises:

setting the queue management parameter equal to the first value in response to the detection of a second predetermined event; and

using the queue management parameter in the queue management process after the detection of the second predetermined event and while the queue management parameter is equal to the first value.

36. The computer program product of claim 35, wherein the step of detecting the second predetermined event comprises one or more of:

(a) detecting that the packet transmission process has transitioned back to the first state,

(b) detecting an event that suggests the packet transmission process has transitioned back to the first state,

(c) detecting that the packet transmission process will transition back to the first state, and

(d) detecting an event that suggests the packet transmission process will transition back to the first state.

37. The computer program product of claim 36, wherein the step of detecting an event that suggests the packet transmission process has transitioned from the second state to the first state comprises detecting a certain amount of queue inactivity.

38. The computer program product of claim 33, wherein the step of using the queue management parameter in the queue management process comprises using the queue management parameter in deciding whether a packet in the queue should be dropped from the queue.

39. The computer program product of claim 38, wherein the step of using the queue management parameter in deciding whether a packet in the queue should be dropped from the queue comprises:

(i) determining a time value representing the length of time the packet has been in the queue and (ii) comparing the time value to the value of the queue management parameter.

40. The computer program product of claim 39, wherein the method further comprises dropping the packet from the queue in response to the result of the comparing step indicating that the time value is greater than the value of the queue management parameter.

41. The computer program product of claim 31, wherein

the step of initializing the queue further comprises (i) setting a second queue management parameter equal to a third value and (ii) setting a third queue management parameter equal to a fourth value, and

the method further comprises

using the first, second and third queue management parameters in deciding whether a packet in the queue should be dropped from the queue while the first queue management parameter is equal to the first value, the second queue management parameter is equal to the third value, and the third queue management parameter is equal to the fourth value;

setting the second queue management parameter equal to a fifth value and setting the third queue management parameter equal to a sixth value in response to the detection of the first predetermined event; and

using the first, second and third queue management parameters in deciding whether a packet in the queue should be dropped from the queue while the first queue management parameter is equal to the second value, the second queue management parameter is equal to the fifth value, and the third queue management parameter is equal to the sixth value.

42. The computer program product of claim 31, further comprising:

in response to the detection of a second predetermined event, setting the queue management parameter equal to a third value; and

after the detection of the second predetermined event and while the queue management parameter is equal to the third value, using the queue management parameter in the queue management process.

43. The computer program product of claim 42, wherein the step of detecting the second predetermined event comprises one or more of:

(a) detecting that the packet transmission process has transitioned from the second state to a third state,

(b) detecting an event that suggests the packet transmission process has transitioned from the second state to a third state,

(c) detecting that the packet transmission process will transition from the second state to a third state, and

(d) detecting an event that suggests the packet transmission process will transition from the second state to a third state.