Congestion and delay handling in a packet data network

• US 20040218617A1
• Filed: 01/23/2004
• Published: 11/04/2004
• Est. Priority Date: 05/31/2001
• Status: Active Grant

• Current Assignee: Mats Sagfors
• Original Assignee: Mats Sagfors
• Inventors: Sagfors, Mats
• Granted Patent: US 7,664,017 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/5077 wherein the managed service relates to simple transport services, i.e. providing only network infrastructure
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• 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
• CPC Class Codes: H04W 28/0231 based on communication conditions dynamic wireless traffic scheduling definition based on channel quality criteria H04W72/54
• CPC Class Codes: H04W 28/0284 detecting congestion or overload during communication monitoring arrangements H04L43/00
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A method of managing a data packet queue in a buffer associated with the radio layers of a wireless network, the buffer storing packets prior to their transmission over the radio interface. The method comprises defining minimum and maximum threshold levels for the packet queue, and for a data packet received by the buffer 1) performing a congestion avoidance procedure if the buffer queue exceeds said maximum threshold level, or 2) not performing said procedure if the buffer queue is less than said minimum threshold level, or 3) if the buffer queue lies between said maximum and minimum thresholds, performing said congestion avoidance procedure for said packet, and not performing the procedure for at least one or more subsequent packets.

Claims

1-30. -30. (canceled).

31. A method of managing a data packet queue in a buffer associated with the radio layers of a wireless network, the buffer storing packets prior to their transmission over the radio interface, the method comprising:

defining minimum and maximum threshold levels for the packet queue; and

for a data packet received by the buffer,

1) performing a congestion avoidance procedure if the buffer queue exceeds said maximum threshold level;

or

2) not performing said procedure if the buffer queue is less than said minimum threshold level;

or

3) if the buffer queue lies between said maximum and minimum thresholds, performing said congestion avoidance procedure for said packet, and not performing the procedure for at least one or more subsequent packets.

32. A method according to claim 31, wherein steps 1) and 2) are carried out upon receipt of the packet at the buffer.

33. A method according to claim 31, wherein step 1) is carried out upon receipt of the packet at the buffer, and steps 2) and 3) are carried out when the packet reaches the front of the buffer queue.

34. A method according to claim 31, wherein in step 3) the number of subsequent packets for which said procedure is not performed is a predefined number of packets.

35. A method according to claim 31 and comprising predefining a fixed data volume and, in step 3), not performing said procedure on subsequent packets until at least that predefined volume of data has been received.

36. Apparatus for use in a wireless network and comprising:

a buffer for storing data packets for transmission over radio layers of the wireless network;

an input for receiving data packets;

a memory storing minimum and maximum threshold levels for the packet queue within the buffer; and

a controller arranged for each data packet received by the buffer to,

1) perform a congestion avoidance procedure if the buffer queue exceeds said maximum threshold level;

or

2) not perform said procedure if the buffer queue is less than said minimum threshold level;

or

3) if the buffer queue lies between said maximum and minimum thresholds, performing said congestion avoidance procedure for said packet, not performing the procedure for one or more subsequent packets, and for packets received thereafter performing steps 1) to

     3) as normal.

37. A method of managing a data packet queue at a radio link layer forming part of a packet transmission link, the method comprising:

measuring or estimating the round trip transmission time over said link, excluding the delay introduced by said queue;

setting a threshold value based upon the measured or estimated round trip transmission time;

for packets at the head of the queue, comparing the time spent in the queue with said threshold value; and

in the event that the time spent in the queue exceeds said threshold value, implementing a congestion or delay avoidance procedure.

38. A method according to claim 37, wherein said radio link is a WCDMA, WCDMA2000, or GPRS radio link.

39. A method according to claim 37, wherein said link comprises the Internet.

40. A method according to claim 37, wherein said data packets are TCP or UDP data packets.

41. A method according to claim 37, wherein said congestion or delay avoidance procedure comprises dropping the packet at the head of the queue or another packet in the queue.

42. A method according to claim 41, wherein said congestion or delay avoidance procedure comprises dropping one or more subsequent packets from the queue regardless of the time spent by these packets in the queue.

43. A method according to claim 41 and comprising defining a minimum queue threshold, T_min, in terms of data volume or number of packets, and for one or more subsequent packets, accepting and sending the packet regardless of the queue size and packet delay, and for the following packet determining whether the queue size exceeds the minimum threshold and the packet delay in the queue exceeds said threshold value and if so repeating the congestion avoidance procedure, otherwise terminating the congestion avoidance procedure.

44. A method according to claim 43, wherein n subsequent packets are accepted regardless of the queue size and packet delay, where n is an integer.

45. A method according to claim 37 and comprising defining a maximum queue threshold, T_max, in terms of data volume or number of packets, and for each packet arriving at the queue, comparing the queue size with said maximum threshold and if the queue size exceeds said maximum threshold, dropping the arriving packet or another packet from the queue.

46. Apparatus for managing a data packet queue forming part of a packet transmission link, the apparatus comprising:

means for storing and/or measuring or estimating the round trip transmission time over said link, excluding the delay introduced by said queue;

means for defining a threshold value based on said stored, measured or estimated round trip transmission time;

processing means arranged, for packets at the head of the queue, to compare the time spent in the queue with said threshold value and, in the event that the time spent in the queue exceeds said threshold value, to implement a congestion or delay avoidance procedure.

47. A method of controlling the entry of data packets into a buffer present in a packet transmission link, the method comprising:

defining a first fixed threshold level and a second variable threshold level for the packet queue size within the buffer; and

for each data packet arriving at the buffer, performing a congestion avoidance procedure if the current buffer queue size exceeds said first or second threshold level, and adjusting said second variable threshold level depending upon (a) whether or not a packet is dropped and (b) upon the relative values of the first and second thresholds and the queue size.

48. A method according to claim 47 and comprising initialising the second variable threshold level to a predetermined minimum threshold level which is less than said first fixed threshold level.

49. A method according to claim 47, wherein the second variable threshold level is adjusted by incrementing or decrementing the level by a fixed amount.

50. A method according to claim 47, wherein the amount by which the variable threshold is incremented is the same as the amount by which it is decremented.

51. A method according to claim 47, wherein the amount by which the variable threshold is incremented is greater than the amount by which it is decremented.

52. A method according to claim 47, wherein, when the variable threshold is incremented it is incremented by a fixed amount and, when the variable threshold is decremented, it is decremented to within some predetermined value in excess of the queue size so as to track the queue size.

53. A method according to claim 47, wherein the second variable threshold level is incremented following receipt of a packet if said congestion avoidance procedure is performed and the second variable threshold level does not exceed the first threshold level.

54. A method according to claim 52, wherein, if said congestion avoidance procedure is performed and the second variable threshold level does exceed the first threshold level, the second variable threshold level is not changed.

55. A method according to claim 47 and comprising decrementing the second variable threshold level following receipt of a packet if said congestion avoidance procedure is not performed, the queue size is less than the second variable threshold level by some predefined amount, and the second variable threshold level is greater than said minimum threshold level.

56. A method according to claim 55, wherein, if said congestion avoidance procedure is not performed and the queue size exceeds the second variable threshold less said predefined amount, or the second variable threshold level is less than said minimum threshold level, the second variable threshold level is not changed.

57. A method according to claim 47, wherein said congestion avoidance procedure comprises dropping the newly arrived packet or a packet already held in the buffer.

58. A method according to claim 47, wherein said congestion avoidance procedure comprises including in the packet a congestion marker.

59. A method according to claim 47, wherein the IP packets belong to a TCP/IP connection, with the packets arriving at the buffer being transmitted there by a TCP sender.

60. A method according to claim 47, wherein the buffer is be associated with a wireless communication network

61. Apparatus for buffering data packets in a packet transmission link, the apparatus comprising:

a buffer for containing a queue of data packets;

an input for receiving data packets;

a memory storing a first fixed threshold level and a second variable threshold level for the packet queue within the buffer; and

a controller arranged, for each data packet arriving at the buffer, to perform a congestion avoidance procedure if the current buffer queue exceeds said first or second threshold level, and to adjust said second variable threshold level depending upon (a) whether or not a packet is dropped, and (b) the relative values of the first and second thresholds and the queue size.