System and method for a negative acknowledgement-based transmission control protocol

• US 7,035,214 B1
• Filed: 09/28/1999
• Issued: 04/25/2006
• Est. Priority Date: 09/28/1999
• Status: Expired due to Fees

• Current Assignee: Avaya Incorporated
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Nandy, Biswajit B., Seddigh, Nabil N., Hadi Salim, Jamal
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): MEHRA, INDER P
• Application Number:
  US09/406,837
• Time in Patent Office: 2,401 Days
• Field of Search: 370/236, 370/389, 370/474, 370229-232, 370/235, 370/390, 370/394, 370/466, 370/216, 370/223, 714/748, 714/749, 714/746, 714/18, 714/51, 714/55
• US Class Current: 370/231
• CPC Class Codes: H04L 1/1635 Cumulative acknowledgement, i.e. the acknowledgement message applying to all previous messages
• 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/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/326 in the transport layer [OSI layer 4] H04L69/16 takes precedence
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A system and method for transmitting data in a data communications network, using a transmission control protocol, to provide reduced acknowledgment control traffic, error recovery and congestion control. A communications link is established between a transmitter and a receiver. Setting the communications link includes setting a network congestion window to an initial length. A sequence, or stream, of data packets is sent from the transmitter to the receiver. The receiver detects any missing packets, by examining the sequence numbers of the incoming packets, and sends negative acknowledgments, generally no more than four, to the transmitter identifying the missing data packet. When the transmitter receives a negative acknowledgment, it decreases the length of the congestion window, and re-transmits the missing packet. Detection and use of round-trip time, re-transmission time-out are provided.

Claims

1. A method of transmitting data in a data communications network, comprising the steps of:

(i) establishing a connection-oriented communications link between a transmitter and a receiver through a Transmission Control Protocol (TCP) handshake, the communications link having a congestion window set to an initial length;

(ii) transmitting data packets in TCP from the transmitter to the receiver;

(iii) sending periodically a keep-alive request from the transmitter to the receiver, whereupon a re-transmission time-out timer is set,

(iv) determining, at the transmitter, if an acknowledgment to the keep-alive request is not received before expiry of the re-transmission time-out timer, whereupon the transmitter backs off for a predetermined period;

(v) detecting a missing data packet at the receiver;

(vi) sending a negative acknowledgment from the receiver to the transmitter for the missing data packet, the receiver being unresponsive to any packets from the transmitter unless the receiver detects the missing data packet;

(vii) decreasing, at the transmitter, the length of the congestion window in response to receipt of the negative acknowledgment; and

(viii) re-transmitting the missing data packet.

2. The method according to claim 1, wherein up to four duplicate negative acknowledgments are sent from the receiver.

3. The method according to claim 1, wherein the congestion window is halved at step (vii).

4. The method according to claim 1, further including a step of setting a round-trip timer at the transmitter upon transmitting the data packet, and a step of increasing the congestion window in response to the expiry of the round-trip timer.

5. The method according to claim 4, wherein the step of increasing the congestion window increases the congestion window if no negative acknowledgement is received upon expiry of the round-trip timer.

6. The method according to claim 5, wherein the congestion window is doubled.

7. The method according to claim 1, further comprising a step of generating, at the receiver, an acknowledgement in response to the keep-alive request, the receiver being responsive only to the missing data packet and the keep-alive request.

8. The method according to claim 1, wherein the congestion window is decreased in response to three duplicate negative acknowledgments.

9. The method according to claim 1, wherein the data communications network in an internet.

10. A method for error recovery in a data communications network where data is transmitted in Transmission Control Protocol (TCP) as a sequence of data packets sent from a transmitter to a receiver, comprising the steps of:

establishing a connection-oriented communication link between the transmitter and the receiver being established through a TCP handshake;

sending periodically a keep-alive request from the transmitter to the receiver, whereupon a re-transmission time-out timer is set,

determining, at the transmitter, if an acknowledgment to the keep-alive request is not received before expiry of the re-transmission time-out timer, whereupon the transmitter backs off for a predetermined period;

detecting a missing data packet at the receiver;

sending a negative acknowledgment from the receiver to the transmitter for the missing data packet, the receiver being unresponsive to any packets from the transmitter unless the receiver detects the missing data packet;

setting a missing-packet timer at the receiver upon sending the negative acknowledgment; and

where the missing data packet is not received at the receiver in response to the negative acknowledgment before expiry of the missing-packet timer, sending a further negative acknowledgment.

11. The error recovery method according to claim 10, wherein the step of detecting a missing data packet includes the step of detecting a missing data packet according to a gap in sequence numbers of the stream of data packets, the step of setting a missing-packet timer settings a missing data packet timer when the gap is detected.

12. The error recovery method according to claim 10, wherein up to four negative acknowledgments are sent from the receiver to the transmitter before expiry of the missing-packet timer.

13. The error recovery method according to claim 10, wherein the missing-packet timer is cleared upon receipt of the missing data packet at the receiver.

14. A method for congestion control in a data communications network where data is transmitted as a sequence of data packets from a transmitter to a receiver, comprising the steps of:

establishing a connection-oriented communication link between the transmitter and the receiver being established through a Transmission Control Protocol (TCP) handshake;

setting a congestion window to an initial size, the congestion window relating to a transmission rate over the network;

transmitting a data packet in TCP from the transmitter to the receiver;

setting a round-trip timer at the transmitter upon sending the packet;

sending a negative acknowledgement for a missing data packet from the receiver to the transmitter, the receiver being unresponsive to any packets from the transmitter unless the receiver detects the missing data packet;

increasing the congestion window if no negative acknowledgment for the missing data packet is received before expiry of the round-trip timer; and

decreasing the congestion window if the negative acknowledgment for the missing data packet is received at the transmitter, wherein the congestion window is doubled, and an interval between transmission of subsequent data packets is decreased, upon expiry of the round-trip timer.

15. The congestion control method according to claim 14, further including a step of empirically determining the round-trip time.

16. The congestion control method according to claim 15, further comprising the step of sending a round-trip time update request to the receiver, the receiver being responsive only to the missing data packet and the round-trip time update request.

17. The congestion control method according to claim 14, wherein the step of increasing the congestion window includes the step of multiplicatively increasing the congestion window if no negative acknowledgement for the missing data packet is received before expiry of the round-trip timer.

18. The congestion control method according to claim 14, further including steps of sending a keep-alive request from the transmitter to the receiver, and setting a re-transmission timeout timer to detect a re-transmission timeout, the receiver being responsive only to the missing data packet and the keep-alive request.

19. The congestion control method according to claim 18, wherein the congestion window is set to one for a back-off period if no acknowledgment is received in response to the keep-alive request, before expiry of the re-transmission time-out timer.

20. A data communications system employing transmission control protocol for providing error recovery and congestion control on a data communications network, comprising:

a transmitter for sending a sequence of data packets in Transmission Control Protocol (TCP), the transmitter having a round-trip timer that is set upon sending each data packet;

a receiver for receiving the sequence of data packets, a connection-oriented communication link between the transmitter and the receiver being established through a TCP handshake, the receiver detecting a missing data packet in the sequence of data packets, and returning a negative acknowledgment for the missing data packet to the transmitter to cause re-transmission of the missing data packet, the receiver being unresponsive to any packets from the transmitter unless the receiver detects the missing data packet; and

means for increasing the congestion window if no negative acknowledgment for the missing data packet is received before expiry of the round-trip timer, and decreasing the congestion window if the negative acknowledgment for the missing data packet is received at the transmitter, wherein the congestion window is doubled, and an interval between transmission of subsequent data packets is decreased, upon expiry of the round-trip timer.

21. The system according to claim 20, further including a missing-packet timer at the receiver upon expiry of which a final negative acknowledgment is sent to the transmitter.

22. The system according to claim 20, further including a re-transmission time-out timer at the transmitter, the means for adjusting responding to expiry of the re-transmission time-out timer.

23. The system according to claim 20, wherein the transmitter includes means for setting a congestion window to an initial size, the congestion window relating to a transmission rate over the network, the adjusting means including means for increasing the congestion window if no negative acknowledgment for the missing data packet is received before expiry of the round-trip timer, and means for decreasing the congestion window if the negative acknowledgment for the missing data packet is received.

24. A method for congestion control in a data communications network where data is transmitted as a sequence of data packets from a transmitter to a receiver, comprising the steps of:

setting a congestion window to an initial size, the congestion window relating to a transmission rate over the network;

transmitting a data packet in Transmission Control Protocol (TCP) from the transmitter to the receiver;

setting a round-trip timer at the transmitter upon sending the packet;

increasing the congestion window if no negative acknowledgment for the data packet is received before expiry of the round-trip timer; and

decreasing the congestion window if a negative acknowledgment for the data packet is received at the transmitter

wherein the congestion window is doubled, and an interval between transmission of subsequent data packets is decreased, upon expiry of the round-trip timer.

25. A system for transmitting data in a data communications network, comprising:

a receiver; and

a transmitter,

a communications link between the transmitter and the receiver being established through a Transmission Control Protocol (TCP) handshake, the communications link having a congestion window set to an initial length;

the transmitter including means for transmitting data packets in TCP to the receiver;

the receiver including means for detecting a missing data packet, means for sending a negative acknowledgment to the transmitter for the missing data packet, the receiver being unresponsive to any packets from the transmitter unless the receiver detects the missing data packet,

the transmitter further including means for decreasing the congestion window in response to receipt of the negative acknowledgment, and means for re-transmitting the missing data packet,

the transmitter further including means for increasing the congestion window if no negative acknowledgment for the missing data packet is received before expiry of the round-trip timer; and

means for decreasing the congestion window if the negative acknowledgment for the missing data packet is received at the transmitter, wherein the congestion window is doubled, and an interval between transmission of subsequent data packets is decreased, upon expiry of the round-trip timer.

26. The system according to claim 25, wherein the receiver further includes means for setting a missing-packet timer upon sending the negative acknowledgment, and means for sending a further negative acknowledgment when the missing data packet is not received in response to the negative acknowledgment before expiry of the missing-packet timer.