TCP SELECTION ACKNOWLEDGEMENTS FOR COMMUNICATING DELIVERED AND MISSING DATA PACKETS

• US 20100050040A1
• Filed: 10/28/2009
• Published: 02/25/2010
• Est. Priority Date: 10/30/2002
• 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.
• Granted Patent: US 8,411,560 B2
• Time in Patent Office: Days
• US Class Current: 714/749
• 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:

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

generating, by the receiver responsive to receiving a landing data packet, a selective acknowledgment (SACK) packet identifying;

(i) a first continuous range of sequence numbers and a second continuous range of sequence numbers, the second continuous range subsequent to the first continuous range in the sorted list and one or more sequence numbers between the first continuous range and the second continuous range identifying one or more data packets that have not been received, and

(ii) a third continuous range of sequence numbers, the third continuous range including the sequence number of the landing data packet, and not subsequent to the first continuous range or second continuous range in the sorted list.

2. The method of claim 1, further comprising:

maintaining a reference in the sorted list, such that the first continuous range is 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.

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

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

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

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

receiving, by a sender, a selective acknowledgement (SACK) packet from a receiver, the SACK packet identifying;

(i) a first continuous range of sequence numbers and a second continuous range of sequence numbers, with one or more sequence numbers between the first continuous range and the second continuous range identifying one or more data packets that have not been received, and

(ii) a third continuous range of sequence numbers, the third continuous range including the sequence number of the landing data packet, and not consecutive with the first continuous range or second continuous range; and

identifying as not received by the receiver, from the SACK packet, the one or more data packets with sequence numbers between the first and second continuous ranges.

7. The method of claim 6, further comprising retransmitting the identified data packets.

8. The method of claim 6, further comprising:

designating the identified data packets as presumed lost data packets;

maintaining a counter of received SACK packets since the identified data packets were designated as presumed lost data packets; and

retransmitting the presumed lost data packets, responsive to the counter exceeding a threshold set responsive to an observed or expected packet reordering in the network.

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

transmitting, by a flow control module configured on a device, a first data packet from a sender to a remote system, the transmitted first data packet including a transport layer sequence number and a first internet layer internet protocol identifier (IP ID) field, the first IP ID field comprising a first unique value;

transmitting, by the flow control module, one or more additional data packets from the sender to the remote system;

retransmitting, by the flow control module, the first data packet to the remote system after transmitting the one or more additional data packets, the retransmitted first data packet including the transport layer sequence number and a second IP ID field, the second IP ID field comprising a second unique value different than the first unique value;

receiving, by the flow control module, a selective acknowledgment (SACK) packet sent by the remote system generated responsive to receipt of the retransmitted first data packet, the SACK packet;

including the transport layer sequence number and a third IP ID field, the third IP ID field comprising a third value set to a function of the second unique value to identify the retransmitted first data packet as the packet triggering the SACK packet, and

the SACK packet identifying;

(i) a first continuous range of sequence numbers and a second continuous range of sequence numbers, with one or more sequence numbers between the first continuous range and the second continuous range identifying one or more data packets that have not been received, and

(ii) a third continuous range of sequence numbers, the third continuous range including the sequence number of the landing data packet, and not consecutive with the first continuous range or second continuous range; and

presuming lost, by the flow control module, the one or more additional data packets sent prior to retransmitting the data packet, responsive to;

(i) determining that the received acknowledgement packet acknowledges receipt by the remote system of the retransmission of the first data packet, and (ii) the one or more additional data packets having sequence numbers between the first continuous range and second continuous range.

10. The method of claim 9, further comprising:

maintaining a counter of received SACK packets since presuming lost the one or more additional data packets; and

retransmitting the presumed lost data packets, responsive to the counter exceeding a threshold set responsive to an observed or expected packet reordering in the network.

11. A network communication systems comprising:

a receiver-side sorted list comprising an index of continuous ranges of sequence numbers identifying data packets received by a receiver;

a receiver-side flow module configured to generate a SACK packet responsive to receiving a landing data packet at the receiver, the SACK packet identifying;

(i) a first continuous range of sequence numbers and a second continuous range of sequence numbers, the second continuous range subsequent to the first continuous range in the sorted list and one or more sequence numbers between the first continuous range and the second continuous range identifying one or more data packets that have not been received, and

(ii) a third continuous range of sequence numbers, the third continuous range including the sequence number of the landing data packet, and not subsequent to the first continuous range or second continuous range in the sorted list; 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 one or more data packets with sequence numbers between the first and second continuous ranges had not been received by the receiver when the SACK packet was generated.

12. The system of claim 11, wherein the receiver-side flow module is further configured to:

maintain a reference in the sorted list, such that the first continuous range is chosen according to the reference; and

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

13. The system of claim 12, wherein advancing the reference comprises wrapping to a beginning of the list upon reaching an end of the list.

14. The system of claim 12, wherein advancing the reference to a subsequent continuous range in the list further comprises advancing the reference at least two ranges.

15. The system of claim 11, further comprising a proxy device coupled to the receiver, and wherein the receiver-side flow module is installed on the proxy device.

16. A system for retransmitting packets based on acknowledgements received from a receiver over a network, the system comprising

a receiver, configured to generate and transmit a selective acknowledgement (SACK) packet, the SACK packet identifying:

(i) a first continuous range of sequence numbers and a second continuous range of sequence numbers, with one or more sequence numbers between the first continuous range and the second continuous range identifying one or more data packets that have not been received, and

(ii) a third continuous range of sequence numbers, the third continuous range including the sequence number of the landing data packet, and not consecutive with the first continuous range or second continuous range; and

a sender, configured to receive the SACK packet and identify as not received by the receiver the one or more data packets with sequence numbers between the first and second continuous ranges.

17. The system of claim 16, wherein the sender is further configured to retransmit the identified data packets.

18. The system of claim 16, wherein the sender is further configured to:

designate the identified data packets as presumed lost data packets;

maintain a counter of received SACK packets since the identified data packets were designated as presumed lost data packets; and

retransmit the presumed lost data packets, responsive to the counter exceeding a threshold set responsive to an observed or expected packet reordering in the network.

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

a network interface on a device configured to;

transmit a first data packet from a sender to a remote system, the transmitted first data packet including a transport layer sequence number and a first internet layer internet protocol identifier (IP ID) field, the first IP ID field comprising a first unique value;

transmit one or more additional data packets from the sender to the remote system;

retransmit the first data packet to the remote system after transmitting the one or more additional data packets, the retransmitted first data packet including the transport layer sequence number and a second IP ID field, the second IP ID field comprising a second unique value different than the first unique value;

receive a selective acknowledgment (SACK) packet sent by the remote system generated responsive to receipt of the retransmitted first data packet, the SACK packet;

including the transport layer sequence number and a third IP ID field, the third IP ID field comprising a third value set to a function of the second unique value to identify the retransmitted first data packet as the packet triggering the SACK packet, and

the SACK packet identifying;

(i) a first continuous range of sequence numbers and a second continuous range of sequence numbers, with one or more sequence numbers between the first continuous range and the second continuous range identifying one or more data packets that have not been received, and

(ii) a third continuous range of sequence numbers, the third continuous range including the sequence number of the landing data packet, and not consecutive with the first continuous range or second continuous range; and

a flow control module on the device configured to;

presume lost the one or more additional data packets sent prior to retransmitting the data packet, responsive to;

(i) determining that the received acknowledgement packet acknowledges receipt by the remote system of the retransmission of the first data packet, and (ii) the one or more additional data packets having sequence numbers between the first continuous range and second continuous range.

20. The system of claim 19, wherein:

the flow control module is further configured to maintain a counter of received SACK packets since presuming lost the one or more additional data packets; and

the network interface is further configured to retransmit the presumed lost data packets, responsive to the counter exceeding a threshold set responsive to an observed or expected packet reordering in the network.