TCP selective acknowledgements for communicating delivered and missed data packets

• US 7,630,305 B2
• Filed: 07/28/2004
• Issued: 12/08/2009
• Est. Priority Date: 07/29/2003
• Status: Active Grant

• Current Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Original Assignee: Orbital Data Corporation (Cloud Software Group)
• Inventors: Samuels, Allen R., Sutter, Paul G.
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): Weidner; Timothy J
• Application Number:
  US10/902,491
• Publication Number:
  US 20050063303A1
• Time in Patent Office: 1,959 Days
• Field of Search: None
• US Class Current: 370/229
• CPC Class Codes: H04L 1/16 in which the return channel carries supervisory signals, e.g. repetition request signals
• CPC Class Codes: H04L 1/1621 Group acknowledgement, i.e. the acknowledgement message defining a range of identifiers, e.g. of sequence numbers
• CPC Class Codes: H04L 1/1671 the supervisory signal being transmitted together with control information
• CPC Class Codes: H04L 1/1874 Buffer management
• CPC Class Codes: H04L 2001/0097 Relays
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 67/2876 Pairs of inter-processing entities at each side of the network, e.g. split proxies
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• 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/166 IP fragmentation; TCP segmentation

Abstract

One or more flow control modules, implemented on various types of network topologies, provide a number of functionalities for controlling the flow of IP packets (such as TCP/IP packets) over a network connection. The flow control modules may be implemented within a sender and/or receiver or may be deployed into a network as a separate device without requiring significant additional resources.

Claims

1. A method for determining between a sender and receiver a data packet from the sender to retransmit to the receiver, the method comprising:

transmitting, by a sender, a plurality of data packets to a receiver, the sender identifying each of the plurality of data packets by a sequence number and a transmit number different from the sequence number, the transmit number identifying an instance of transmission of the data packet;

maintaining, by a receiver, a sorted list comprising an index of consecutive sets of continuous ranges of transmit numbers identifying data packets received by the receiver;

generating, by the receiver, a selection acknowledgment (SACK) packet, responsive to a landing data packet and identifying a plurality of sets of continuous ranges of transmit numbers of data packets that had been received prior to receipt of the landing data packet, at least two but less than the plurality of the sets of continuous ranges identified in the SACK packet being consecutive in the sorted list to identify transmit numbers of one or more data packets between the consecutive ranges have not been received, and a continuous range that includes the landing data packet is not consecutive with the at least two of the plurality of sets of continuous ranges identified in the SACK packet;

identifying, by the sender, from the SACK packet received from the receiver, the transmit numbers of data packets not received by the receiver; and

transmitting, by the sender, the identified data packets.

2. The method of claim 1, wherein the consecutive sets of continuous ranges identified in a first SACK packet overlap the consecutive ranges identified in a next SACK packet.

3. The method of claim 1, wherein each SACK packet further identifies a range of received data packets that includes the landing data packet associated with the SACK packet.

4. The method of claim 1, further comprising:

maintaining a reference into the list of ranges of received data packets, wherein the consecutive sets of continuous ranges in the list identified in a generated SACK packet are chosen according to the reference; and

responsive to the generation of a SACK packet advancing the reference to a subsequent continuous range in the list.

5. The method of claim 4, wherein advancing the reference comprises wrapping to a beginning of the list upon reaching an end of the list.

6. The method of claim 4, wherein advancing the reference to a subsequent continuous range in the list further comprises advancing the reference at least two ranges.

7. The method of claim 1, wherein the method complies with TCP/IP.

8. The method of claim 1, wherein the method is performed in a proxy device coupled to a receiver,

9. A method for retransmitting packets based on acknowledgements received from a receiver over a network, the method comprising:

receiving, by a sender, a selection acknowledgement (SACK) packet from a receiver, the SACK packet identifying a plurality of sets of continuous ranges of transmit numbers of data packets that had been received by a receiver prior to receipt of a landing data packet, at least two but less than the plurality of the sets of continuous ranges identified in the SACK packet being consecutive in a sorted list maintained by the receiver to identify transmit numbers of one or more data packets between the consecutive ranges have not been received, each of the transmit numbers identifying an instance of transmission of a data packet and different from a sequence number of the data packet, and a continuous range that includes the landing data packet is not consecutive with the at least two of the plurality of sets of continuous ranges identified in the SACK packet;

identifying from the SACK packet transmit numbers of the one or more data packets between the consecutive ranges not received by the receiver; and

retransmitting the identified data packets.

10. The method of claim 9, wherein each SACK packet further identifies a range of received data packets that includes the landing data packet.

11. The method of claim 9, wherein the retransmitting comprises transmitting the one or more data packets between the consecutive ranges of transmit numbers of the SACK packet unless the one or more data packets were transmitted after the landing data packet.

12. The method of claim 9, further comprising:

adding unacknowledged data packets to a presumed lost list upon receiving an acknowledgement for a later-transmitted data packet;

wherein the retransmitting comprises retransmitting any data packets that are (1) in the presumed lost list, and (2) between the consecutive sets of continuous ranges of the SACK packet.

13. The method of claim 12, wherein the retransmitting a data packet further comprises waiting for a predetermined number of acknowledgements, and retransmitting the data packet only if the data packet has not been acknowledged.

14. The method of claim 9, wherein the method complies with TCP/IP.

15. The method of claim 9, wherein the method is performed in a proxy device coupled to a sender.

16. A method for identifying by a receiver a transmission of a data packet from a sender and not received by the receiver, the method comprising:

receiving, by a receiver, a plurality of data packets, each of the plurality of data packets identified by a transmit number, the transmit number identifying an instance of transmission, by a sender, of a data packet and different from a sequence number of the data packet;

maintaining a sorted list comprising an index of consecutive sets of continuous ranges of transmit numbers identifying data packets received by the receiver;

generating a selection acknowledgment (SACK) packet, responsive to a landing data packet, the SACK packet identifying a plurality of sets of continuous ranges of transmit numbers of data packets that bad been received prior to receipt of the landing data packet, at least two but less than the plurality of the sets of continuous ranges identified in the SACK packet being consecutive in the sorted list to identify transmit numbers of one or more data packets between the consecutive ranges have not been received, and a continuous range that includes the landing data packet is not consecutive with the at least two of the plurality of sets of continuous ranges identified in the SACK packet; and

transmitting the SACK packet to the sender.

17. A computer readable medium for communicating data packets from a sender to a. receiver over a network the computer readable medium comprising computer program code for performing the operations:

transmitting, by a sender, a plurality of data packets to a receiver, the sender identifying each of the plurality of data packets by a transmit number, the transmit number identifying an instance of transmission of a data packet and different from a sequence number of the data packet;

maintaining, by a receiver, a sorted list comprising an index of consecutive sets of continuous ranges of transmit numbers identifying data packets received by the receiver;

generating, by the receiver, a selection acknowledgment (SACK) packet, responsive to a landing data packet and identifying a plurality of sets of continuous ranges of transmit numbers of data packets that had been received prior to receipt of the landing data packet, at least two but less than the plurality of the ranges being consecutive in the sorted list to identify transmit numbers of one or more data packets between the consecutive ranges have not been received, and a continuous range that includes the landing data packet is not consecutive with the at least two of the plurality of sets of continuous ranges identified in the SACK packet;

identifying, by the sender, from the SACK packet received from the receiver, the transmit numbers of data packets not received by the receiver; and

transmitting, by the sender, the identified data packets.

18. The computer readable medium of claim 17, wherein the consecutive sets of continuous ranges identified in a first SACK packet overlap the consecutive ranges identified in a next SACK packet.

19. The computer readable medium of claim 17, wherein each SACK packet further identifies a range of received data packets that includes the landing data packet associated with the SACK packet.

20. The computer readable medium of claim 17, further comprising:

maintaining a reference into the list of ranges of received data packets, wherein the consecutive sets of continuous ranges identified in a generated SACK packet are chosen according to the reference; and

responsive to the generation of a SACK packet, advancing the reference to a subsequent continuous range in the list.

21. The computer readable medium of claim 20, wherein advancing the reference comprises wrapping to a beginning of the list upon reaching an end of the list.

22. A computer readable medium for retransmitting packets based on acknowledgements received from a receiver over a network, the computer readable medium comprising a computer program code for performing the operations:

receiving, by a sender, a selection acknowledgement (SACK) packet from a receiver, the SACK packet identifying a plurality of sets of continuous ranges of transmit numbers of data packets that had been received by a receiver prior to receipt of a landing data, at least two but less than the plurality of the sets of continuous ranges identified in the SACK packet being consecutive in a sorted list maintained by the receiver to identify transmit numbers of one or more data packets between the consecutive ranges have not been received, each of the transmit numbers identifying an instance of transmission of a data packet and different from a sequence number of the data packet, and a continuous range that includes the landing data packet is not consecutive with the at least two of the plurality of sets of continuous ranges identified in the SACK packet;

identifying from the SACK packet the transmit numbers of the one or more data packets between the consecutive ranges not received by the receiver; and

retransmitting the identified data packets.

23. The computer of claim 22, wherein each SACK packet further identifies a range of received data packets that includes the landing data packet.

24. The computer readable medium of claim 22, wherein the retransmitting comprises transmitting the one or more data packets between the consecutive ranges of transmit numbers of the SACK packet unless the one or more data packets were transmitted after the landing data packet.

25. The computer readable medium of claim 22, further comprising:

adding unacknowledged data packets to a presumed lost list upon receiving an acknowledgement for a later-transmitted data packet;

wherein the retransmitting comprises retransmitting any data packets that are (1) in the presumed lost fist, and (2) between the consecutive sets of continuous ranges of the SACK packet.

26. The computer readable medium of claim 25, wherein the retransmitting a data packet further comprises waiting for a predetermined number of acknowledgements, and retransmitting the data packet only if the data packet has not been acknowledged.

27. A network communications system comprising:

a receiver-side flow module configured to generate a SACK packet responsive to receiving a landing data packet at a receiver, the SACK packet including a plurality of sets of continuous ranges of transmit numbers of data packets received by the receiver, wherein;

at least two of the plurality of sets of continuous ranges are consecutive,

a continuous range that includes the landing data packet is not consecutive with the at least two of the plurality of sets of continuous ranges identified in the SACK packet,

a data packet with a transmit number between the at least two consecutive sets of continuous ranges of transmit numbers of data packets is not received by the receiver, and

each of the transmit numbers identify an instance of transmission of a data packet and are different from a sequence number of the data packet; and

a sender-side flow module configured to receive SACK packets from the receiver side flow module and, responsive to receiving a SACK packet, identify that the data packet with the transmit number between the two consecutive sets of continuous ranges of transmit numbers of data packets in the SACK packet had not been received by the receiver when the SACK packet was generated;

wherein a sender is coupled to the sender-side flow module for retransmitting data packets from the sender to the receiver based on the inferred lost packets.

28. The system of claim 27, wherein the sender-side flow control module is implemented within the sender.

29. The system of claim 27, wherein the receiver-side flow control module is implemented within a receiver.

30. A method for determining between a sender and receiver a data packet from the sender to retransmit to the receiver, the method comprising:

transmitting, by a sender, a plurality of data packets to a receiver, the sender identifying each of the plurality of data packets by a transmit number, the transmit number identifying an instance of transmission of the data packet and different from a sequence number of the data packet;

maintaining, by a receiver, a sorted list comprising an index of consecutive sets of continuous ranges of transmit numbers identifying data packets received by the receiver;

generating, by the receiver, a selection acknowledgment (SACK) packet, responsive to a landing data packet and identifying a plurality of ranges of transmit numbers of data packets that had been received prior to receipt of the landing data packet, at least two but less than the plurality of the sets of continuous ranges identified in the SACK packet being consecutive in the sorted list to identify transmit numbers of one or more data packets between the consecutive ranges have not been received, a continuous range that includes the landing data packet is not consecutive with the at least two of the plurality of sets of continuous ranges identified in the SACK packet, and the receiver advancing a left-off pointer past a transmit number in the sorted list to a previous point in the sorted list;

transmitting, by the receiver, the SACK packet, the SACK packet identifying the transmit number in the plurality of sets of continuous ranges of transmit numbers, the SACK packet not received by the sender;

generating, by the receiver, a second SACK packet identifying a second plurality of sets of continuous ranges of transmit numbers, the second SACK packet identifying the transmit number in the second plurality of sets of continuous ranges of transmit numbers based on the left-off pointer identifying one or more sets of continuous ranges of transmit numbers previously transmitted in the SACK packet;

identifying, by the sender, from the second SACK packet received from the receiver, that a data packet with a transmit number between two consecutive sets of continuous ranges of transmit numbers included in the second SACK packet was not received by the receiver; and

transmitting, by the sender, the data packet identified by the transmit number.