Enhanced acknowledgment pacing device and method for TCP connections

• US 6,215,769 B1
• Filed: 10/07/1998
• Issued: 04/10/2001
• Est. Priority Date: 10/07/1998
• Status: Expired due to Term

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Telecommunications Limited (Nokia Corporation)
• Inventors: Dixit, Sudhir Sharan, Ghani, Nasir
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/167,882
• Time in Patent Office: 916 Days
• Field of Search: 370/229, 370/231, 370/235, 370/236, 370/410, 370/249, 370/412, 709/232, 709/233, 709/234, 709/235
• US Class Current: 370/230
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/1854 Scheduling and prioritising arrangements
• 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/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/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/323 Discarding or blocking control packets, e.g. ACK packets
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

An enhanced acknowledgment pacing device and method for TCP connections is disclosed. The invention includes a link layer entity for receiving data packets from a source and forwarding the data packets to a forward data link, the link layer entity storing the received data packets in a data packet buffer until the data packets depart the link layer entity and are forwarded to the forward data link and an acknowledgment pacing device, coupled to the link layer entity, for pacing acknowledgment packets to be sent to the source in response to receiving the data packets from the source. The acknowledgment pacing device further includes an acknowledgment control unit for monitoring congestion at the link layer entity and generating a control signal for controlling the processing of acknowledgment packets based upon whether congestion is occurring at the link layer entity, an acknowledgment packet buffer, coupled to the acknowledgment control unit, for storing acknowledgment packets received from the acknowledgment control unit and a scheduler, coupled to the acknowledgment control unit and the acknowledgment buffer, the scheduler releasing acknowledgment packets to the source based upon the control signal generated by the acknowledgment control unit.

Claims

1. An acknowledgment pacing device for pacing acknowledgment packets to be sent to a source in response to receiving data packets from the source, comprising:

an acknowledgment control unit for monitoring loading of a network and generating a control signal for controlling the processing of acknowledgment packets based upon the loading of the network;

an acknowledgment packet buffer, coupled to the acknowledgment control unit, for storing acknowledgment packets received from the acknowledgment control unit; and

a scheduler, coupled to the acknowledgment control unit and the acknowledgment buffer, the scheduler releasing acknowledgment packets based upon the control signal generated by the acknowledgment control unit.

2. The acknowledgment pacing device of claim 1 where the scheduler chooses acknowledgment packets to release based upon a queuing strategy.

3. The acknowledgment pacing device of claim 2 wherein the queuing strategy comprises sending a head-of-line acknowledgment packet when aggregate acknowledgment packet buffering is used.

4. The acknowledgment pacing device of claim 2 wherein the queuing strategy comprises a weighted-round-robin (WRR) process for selecting an acknowledgment packet in the acknowledgment packet buffer for release when per-class or per-flow acknowledgment packet buffering is used.

5. The acknowledgment pacing device of claim 4 wherein the weighted-round-robin (WRR) process uses weights for weighting the selection of the acknowledgment packet for release inversely proportionally to a TCP maximum segment size (MSS) to the lessen a bias against smaller MSS flows.

6. The acknowledgment pacing device of claim 2 wherein the queuing strategy comprises a fair-queuing (FQ) process for selecting an acknowledgment packet in the acknowledgment packet buffer for release when per-class or per-flow acknowledgment packet buffering is used.

7. The acknowledgment pacing device of claim 1 wherein the acknowledgment control unit further comprises an acknowledgment packet pacing processor, the acknowledgment packet pacing processor generating the control signal for controlling the processing of acknowledgment packets using a acknowledgment packet arrival processor and a data packet departure processor.

8. The acknowledgment pacing device of claim 7 wherein the acknowledgment packet arrival processor controls the processing of acknowledgment packets to the acknowledgment packet buffer by checking a congestion level of the network and deciding whether to hold acknowledgment packets in the acknowledgment packet buffer or to send the acknowledgment packet directly to the source without buffering the acknowledgment packets in the acknowledgment packet buffer.

9. The acknowledgment pacing device of claim 7 wherein the acknowledgment packet arrival processor decides whether to hold acknowledgment packets in the acknowledgment packet buffer or to send the acknowledgment packet directly to the source without buffering the acknowledgment packets in the acknowledgment packet buffer by determining if the network is congested, determining if the acknowledgment packet buffer is empty, storing an acknowledgment packet in the buffer if the network is congested or the acknowledgment packet buffer is not empty, and forwarding the acknowledgment packet to the source if the acknowledgment packet buffer is empty and the network is not congested.

10. The acknowledgment pacing device of claim 9 wherein the acknowledgment packet is stored in the acknowledgment packet buffer and gated out by the scheduler if the acknowledgment packet is a first acknowledgment packet to be buffered in the acknowledgment packet buffer during congestion.

11. The acknowledgment pacing device of claim 10 wherein the acknowledgment control unit increases a spacing between acknowledgment packets gated from the acknowledgment packet buffer if the acknowledgment packet is the first acknowledgment packet to be buffered in the acknowledgment packet buffer during congestion.

12. The acknowledgment pacing device of claim 11 wherein the acknowledgment control unit increases the spacing between acknowledgment packets by setting a packet counter variable to a first predetermined value.

13. The acknowledgment pacing device of claim 12 wherein the packet counter variable is decremented as when a data packet departs from the network.

14. The acknowledgment pacing device of claim 13 wherein the scheduler releases a buffered acknowledgment packet when the pack et counter variable is decremented to zero and the acknowledgment control unit resets the packet counter variable.

15. The acknowledgment pacing device of claim 8 wherein the congestion level of the network is determined by analyzing a queue length representing a capacity for a data packet buffer.

16. The acknowledgment pacing device of claim 15 wherein the network is indicated as being non-congested when the queue length is less than a low threshold.

17. The acknowledgment pacing device of claim 15 wherein the network is indicated as being congested when the queue length is greater than a high threshold.

18. The acknowledgment pacing device of claim 7 wherein the data packet departure processor controls the release of acknowledgment packets from the acknowledgment packet buffer by monitoring congestion levels of the network and deciding when to gate acknowledgment packets from the acknowledgment buffer to the source.

19. The acknowledgment pacing device of claim 18 wherein the data packet departure processor decides when to gate acknowledgment packets from the acknowledgment buffer to the source by checking if acknowledgment packets are in the acknowledgment packet buffer awaiting transmission and if a packet counter variable set by the acknowledgment control unit has a value of zero, and releasing a buffered acknowledgment packet in the acknowledgment packet buffer to the source when the packet counter variable has a value of zero.

20. The acknowledgment pacing device of claim 19 wherein the data packet departure processor increases the spacing between the release of acknowledgment packets from the acknowledgment packet buffer if congestion still exists in the network.

21. The acknowledgment pacing device of claim 20 wherein the spacing a between the release of acknowledgment packets is increased by resetting the packet counter variable to a first predetermined value.

22. The acknowledgment pacing device of claim 21 wherein the data packet departure processor decrementing the packet counter variable if the value of the packet counter variable is non-zero.

23. The acknowledgment pacing device of claim 22 wherein the data packet departure processor resets the packet counter variable to the second predetermined value to prevent bandwidth under-utilization after congestion periods if the packet counter variable is larger than the second predetermined value.

24. The acknowledgment pacing device of claim 19 wherein the data packet departure processor decreases a spacing between the release of acknowledgment packets from the acknowledgment packet buffer if congestion in the network has abated.

25. The acknowledgment pacing device of claim 24 wherein the data packet departure processor decreases a spacing between the release of acknowledgment packets by resetting the packet counter variable to a second predetermined value, the second predetermined value being less than the first predetermined value.

26. The acknowledgment pacing device of claim 25 wherein the data packet departure processor decrementing the packet counter variable if the value of the packet counter variable is non-zero.

27. The acknowledgment pacing device of claim 26 wherein the data packet departure processor resets the packet counter variable to the second predetermined value to prevent bandwidth under-utilization after congestion periods if the packet counter variable is larger than the second predetermined value.

28. The acknowledgment pacing device of claim 19 wherein the congestion level of the network is determined by analyzing a queue length representing a capacity for a data packet buffer.

29. The acknowledgment pacing device of claim 28 wherein the network is indicated as being non-congested when the queue length is less than a low threshold.

30. The acknowledgment pacing device of claim 28 wherein the network is indicated as being congested when the queue length is greater than a high threshold.

31. The acknowledgment pacing device of claim 1 wherein the acknowledgment packet buffer buffers acknowledgment packets on an aggregate basis.

32. The acknowledgment pacing device of claim 1 wherein the acknowledgment packet buffer buffers acknowledgment packets by flow type, and wherein the scheduler releases the acknowledgment packets in the acknowledgment buffer taking into account the type of flows for the buffered acknowledgment packets.

33. An access node device, comprising;

a link layer entity for receiving data packets from a source and forwarding the data packets to a forward data link, the link layer entity storing the received data packets in a data packet buffer until the data packets depart the link layer entity and are forwarded to the forward data link; and

an acknowledgment pacing device, coupled to the link layer entity, for pacing acknowledgment packets to be sent to the source in response to receiving the data packets from the source, the acknowledgment pacing device further comprising;

an acknowledgment control unit for monitoring congestion at the link layer entity and generating a control signal for controlling the processing of acknowledgment packets based upon whether congestion is occurring at the link layer entity;

an acknowledgment packet buffer, coupled to the acknowledgment control unit, for storing acknowledgment packets received from the acknowledgment control unit; and

a scheduler, coupled to the acknowledgment control unit and the acknowledgment buffer, the scheduler releasing acknowledgment packets to the source based upon the control signal generated by the acknowledgment control unit.

34. The access node device of claim 33 where the scheduler chooses acknowledgment packets to be released based upon a queuing strategy.

35. The access node device of claim 34 wherein the queuing strategy comprises sending a head-of-line acknowledgment packet when aggregate acknowledgment packet buffering is used.

36. The access node device of claim 34 wherein the queuing strategy comprises a weighted-round-robin (WRR) process for selecting an acknowledgment packet in the acknowledgment packet buffer for release when per-class or per-flow acknowledgment packet buffering is used.

37. The access node device of claim 36 wherein the weighted-round-robin (WRR) process uses weights for weighting the selection of the acknowledgment packet for release inversely proportionally to a TCP maximum segment size (MSS) to the lessen a bias against smaller MSS flows.

38. The access node device of claim 34 wherein the queuing strategy comprises a fair-queuing (FQ) process for selecting an acknowledgment packet in the acknowledgment packet buffer for release when per-class or per-flow acknowledgment packet buffering is used.

39. The access node device of claim 33 wherein the acknowledgment control unit further comprises an acknowledgment packet pacing processor, the acknowledgment packet pacing processor generating the control signal for controlling the processing of acknowledgment packets using a acknowledgment packet arrival processor and a data packet departure processor.

40. The access node device of claim 39 wherein the acknowledgment packet arrival processor controls the processing of acknowledgment packets to the acknowledgment packet buffer by checking the congestion at the link layer entity and deciding whether to hold acknowledgment packets in the acknowledgment packet buffer or to send the acknowledgment packet directly to the source without buffering the acknowledgment packets in the acknowledgment packet buffer.

41. The access node device of claim 39 wherein the acknowledgment packet arrival processor decides whether to hold acknowledgment packets in the acknowledgment packet buffer or to send the acknowledgment packet directly to the source without buffering the acknowledgment packets in the acknowledgment packet buffer by determining if the link layer entity is congested, determining if the acknowledgment packet buffer is empty, storing an acknowledgment packet in the buffer if the link layer entity is congested or the acknowledgment packet buffer is not empty, and forwarding the acknowledgment packet to the source if the acknowledgment packet buffer is empty and the link layer entity is not congested.

42. The access node device of claim 41 wherein the acknowledgment packet is stored in the acknowledgment packet buffer and gated out by the scheduler if the acknowledgment packet is a first acknowledgment packet to be buffered in the acknowledgment packet buffer during congestion.

43. The access node device of claim 42 wherein the acknowledgment control unit increases a spacing between acknowledgment packets gated from the acknowledgment packet buffer if the acknowledgment packet is the first acknowledgment packet to be buffered in the acknowledgment packet buffer during congestion.

44. The access node device of claim 39 wherein the data packet departure processor decreases a spacing between the release of acknowledgment packets from the acknowledgment packet buffer if congestion in the link layer entity has abated.

45. A method for providing acknowledgment pacing for acknowledgment packets to be sent to a source in response to receiving data packets from the source, comprising:

monitoring loading of a network;

generating a control signal for controlling the processing of acknowledgment packets based upon the loading of the network;

storing acknowledgment packets received from the acknowledgment control unit in an acknowledgment packet buffer; and

releasing acknowledgment packets based upon the control signal.

46. The method of claim 45 wherein the releasing further comprises choosing acknowledgment packets to release based upon a queuing strategy.

47. The method of claim 46 wherein the queuing strategy comprises sending a head-of-line acknowledgment packet when aggregate acknowledgment packet buffering is used.

48. The method of claim 46 wherein the queuing strategy comprises a weighted-round-robin (WRR) process for selecting an acknowledgment packet in the acknowledgment packet buffer for release when per-class or per-flow acknowledgment packet buffering is used.

49. The method of claim 48 wherein the weighted-round-robin (WRR) process uses weights for weighting the selection of the acknowledgment packet for release inversely proportionally to a TCP maximum segment size (MSS) to the lessen a bias against smaller MSS flows.

50. The method of claim 46 wherein the queuing strategy comprises a fair-queuing (FQ) process for selecting an acknowledgment packet in the acknowledgment packet buffer for release when per-class or per-flow acknowledgment packet buffering is used.

51. The method of claim 45 wherein the generating the control signal for controlling the processing of acknowledgment packets comprises a acknowledgment packet arrival processes and a data packet departure process.

52. The method of claim 51 wherein the acknowledgment packet arrival process controls the processing of acknowledgment packets to the acknowledgment packet buffer by checking a congestion level of the network and deciding whether to hold acknowledgment packets in the acknowledgment packet buffer or to send the acknowledgment packet directly to the source without buffering the acknowledgment packets in the acknowledgment packet buffer.

53. The method of claim 51 wherein the deciding whether to hold acknowledgment packets in the acknowledgment packet buffer or to send the acknowledgment packet directly to the source without buffering the acknowledgment packets in the acknowledgment packet buffer further comprises determining if the network is congested, determining if the acknowledgment packet buffer is empty, storing an acknowledgment packet in the buffer if the network is congested or the acknowledgment packet is not empty, and forwarding the acknowledgment packet to the source if the acknowledgment packet buffer is empty and the network is not congested.

54. The method of claim 53 wherein the acknowledgment packet is stored in the acknowledgment packet buffer and gated out if the acknowledgment packet is a first acknowledgment packet to be buffered in the acknowledgment packet buffer.

55. The method of claim 54 further comprising increasing a spacing between acknowledgment packets gated from the acknowledgment packet buffer if the acknowledgment packet is the first acknowledgment packet to be buffered in the acknowledgment packet buffer.

56. The method of claim 55 wherein increasing the spacing further comprises setting a packet counter variable to a first predetermined value.

57. The method of claim 56 further comprising decrementing the packet counter variable when a data packet departs from the network.

58. The method of claim 57 further comprising releasing a buffered acknowledgment packet when the packet counter variable is decremented to zero and resetting the packet counter variable.

59. The method of claim 52 wherein the congestion level of the network is determined by analyzing a queue length representing a capacity for a data packet buffer.

60. The method of claim 59 further comprising indicating the network is not congested when the queue length is less than a low threshold.

61. The method of claim 59 further comprising indicating the network is congested when the queue length is greater than a high threshold.

62. The method of claim 51 wherein the releasing further comprises monitoring congestion levels of the network and deciding when to gate acknowledgment packets from the acknowledgment buffer to the source.

63. The method of claim 62 wherein the deciding further comprises checking if acknowledgment packets are in the acknowledgment packet buffer awaiting transmission and if a packet counter variable set by the acknowledgment control unit has a value of zero, and releasing a buffered acknowledgment packet in the acknowledgment packet buffer to the source when the packet counter variable has a value of zero.

64. The method of claim 63 wherein the data packet departure process further comprises increasing the spacing between the release of acknowledgment packets from the acknowledgment packet buffer if congestion still exists in the network.

65. The method of claim 64 wherein the increasing further comprises resetting the packet counter variable to a first predetermined value.

66. The method of claim 65 wherein the data packet departure process further comprises decrementing the packet counter variable if the value of the packet counter variable is non-zero.

67. The method of claim 66 wherein the data packet departure process further comprises resetting the packet counter variable to the second predetermined value to prevent bandwidth under-utilization after congestion periods if the packet counter variable is larger than the second predetermined value.

68. The method of claim 63 wherein the data packet departure process further comprises decreasing a spacing between the release of acknowledgment packets from the acknowledgment packet buffer if congestion in the network has abated.

69. The method of claim 68 wherein the data packet departure process further comprises decreasing a spacing between the release of acknowledgment packets by resetting the packet counter variable to a second predetermined value, the second predetermined value being less than the first predetermined value.

70. The method of claim 69 wherein the data packet departure process further comprises decrementing the packet counter variable if the value of the packet counter variable is non-zero.

71. The method of claim 70 wherein the data packet departure process further comprises resetting the packet counter variable to the second predetermined value to prevent bandwidth under-utilization after congestion periods if the packet counter variable is larger than the second predetermined value.

72. The method of claim 63 wherein the determining of the congestion level of the network further comprises analyzing a queue length representing a capacity for a data packet buffer.

73. The method of claim 72 further comprising indicating the network is not congested when the queue length is less than a low threshold.

74. The method of claim 72 further comprising indicating the network is congested when the queue length is greater than a high threshold.

75. The method of claim 45 wherein the storing further comprises buffering acknowledgment packets on an aggregate basis.

76. The method of claim 45 wherein the storing further comprises buffering acknowledgment packets by flow type, and wherein the releasing further comprises scheduling the release of acknowledgment packets in the acknowledgment buffer by taking into account the type of flows for the buffered acknowledgment packets.