Methods and systems for reliable data transmission using selective retransmission

• US 7,664,026 B2
• Filed: 06/12/2007
• Issued: 02/16/2010
• Est. Priority Date: 06/19/2006
• Status: Expired due to Fees

• Current Assignee: Liquid Computing Corporation, Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Liquid Computing Corporation
• Inventors: Munter, Ernst, Kemp, Michael F., Huang, Kaiyuan
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US11/761,804
• Publication Number:
  US 20070291778A1
• Time in Patent Office: 980 Days
• Field of Search: 370/231, 370/394, 709/238
• US Class Current: 370/231
• CPC Class Codes: G06F 15/173 using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
• CPC Class Codes: H04L 1/1614 using bitmaps
• CPC Class Codes: H04L 1/1685 the supervisory signal being transmitted in response to a specific request, e.g. to a polling signal
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/35 by embedding flow control information in regular packets, e.g. piggybacking
• CPC Class Codes: H04L 47/746 Reaction triggered by a failure

Abstract

A reliable method for inter-computer packet transport in multi-process and multi-computer environments includes acknowledgments of received packets. To enhance the reliability and fast recovery of lost packets, a bit-mapped message is used for selective acknowledgments by which individual messages may be selected for retransmission. Further functionalities cover the cases where packets may have been received out-of-order, or an acknowledgment was lost.

Claims

1. A method of sending data packets between a first node and a second node of a computer system, comprising steps of:

sending data packets numbered with consecutive source sequence numbers from the first node to the second node;

retaining a copy of each sent data packet in a retransmission job queue of the first node;

receiving the data packets in the second node;

tracking the source sequence numbers of the data packets received in the second node;

including a current highest tracked source sequence number in a data packet sent from the second node to the first node for which all data packets sent from the first node that are numbered with source sequence numbers no larger than the highest tracked source sequence number have been received in the second node; and

sending, from the second node to the first node, a packet reception bitmap message that indicates a reception status at the second node of a consecutive range of data packets that starts with a data packet numbered with a lowest source sequence number that was not received at the second node and that ends with a data packet with the highest source sequence number that was received at the second node.

2. The method of claim 1, wherein the including step is effective to acknowledge all data packets that have been received by the second node that are numbered with source sequence numbers no larger than the highest tracked source sequence number.

3. The method of claim 1, wherein the packet reception bitmap sending step is carried out when a number of data packets numbered between the lowest source sequence number whose data packet has not been received by the second node and the highest tracked source sequence number whose data packet has been received by the second node inclusive, exceeds a first threshold.

4. The method of claim 1, wherein the packet reception bitmap sending step is carried out when a time period between a time at which a data packet numbered with a next higher source sequence number is received at the second node and a time at which a last data packet was received at the second node, exceeds a second threshold.

5. The method of claim 1, wherein the packet reception bitmap message sending step is carried out at a request of the first node.

6. The method of claim 1, further comprising a step of generating the packet reception bitmap message when a difference between a last source sequence number received from the second node and an earliest source sequence number sent by the first node and not received by the second node exceeds a predetermined first threshold.

7. The method of claim 1, further comprising a step of generating the packet reception bitmap message when a difference between a time when a last sequential source sequence number was received and a time when a last data packet was received exceeds a predetermined second threshold.

8. The method of claim 1, wherein the tracking step includes receiving the source sequence number in the second node and storing the received source sequence number as a destination sequence number in the second node, the stored destination sequence number being updated only when a data packet numbered with a next higher source sequence number is received at the second node.

9. The method of claim 1, further including a step of the first node receiving the packet reception bitmap message and selectively resending data packets identified by the packet reception bitmap message from the retransmission job queue to the second node.

10. The method of claim 1, further including a step of removing data packets from the retransmission job queue of the first node, the removing step being carried out only upon receipt of a corresponding included current highest tracked source sequence number from the second node or when the packet reception bitmap message received from the second node indicates receipt of the data packet by the second node.

11. The method of claim 1, further including a step of re-sending a first and subsequent data packets queued in the retransmission job queue, the re-sending step being carried out when a predetermined time period has elapsed without the first node having received a corresponding included current highest tracked source sequence number from the second node or when the packet reception bitmap message received from the second node indicates receipt of the queued first and subsequent data packets by the second node.

12. A computer readable medium having data stored thereon representing sequences of instructions which, when executed by a computer system having a first and a second node, causes the computer system to send data packets between the first and second nodes by performing the steps of:

sending data packets numbered with consecutive source sequence numbers from the first node to the second node;

retaining a copy of each sent data packet in a retransmission job queue of the first node;

receiving the data packets in the second node;

tracking the source sequence numbers of the data packets received in the second node;

including a current highest tracked source sequence number in a data packet sent from the second node to the first node for which all data packets sent from the first node that are numbered with source sequence numbers no larger than the highest tracked source sequence number have been received in the second node, and

sending, from the second node to the first node, a packet reception bitmap message that indicates a reception status at the second node of a consecutive range of data packets that starts with a data packet numbered with a lowest source sequence number that was not received at the second node and that ends with a data packet with the highest source sequence number that was received at the second node.

13. The medium of claim 12, wherein the including step is effective to acknowledge all data packets that have been received by the second node that are numbered with source sequence numbers no larger than the highest tracked source sequence number.

14. The medium of claim 12, wherein the packet reception bitmap sending step is carried out when a number of data packets numbered between the lowest source sequence number whose data packet has not been received by the second node and the highest tracked source sequence number whose data packet has been received by the second node inclusive, exceeds a first threshold.

15. The medium of claim 12, wherein the packet reception bitmap sending step is carried out when a time period between a time at which a data packet numbered with a next higher source sequence number is received at the second node and a time at which a last data packet was received at the second node, exceeds a second threshold.

16. The medium of claim 12, wherein the packet reception bitmap message sending step is carried out at a request of the first node.

17. The medium of claim 12, further comprising a step of generating the packet reception bitmap message when a difference between a last source sequence number received from the second node and an earliest source sequence number sent by the first node and not received by the second node exceeds a predetermined first threshold.

18. The medium of claim 12, further comprising a step of generating the packet reception bitmap message when a difference between a time when a last sequential source sequence number was received and a time when a last data packet was received exceeds a predetermined second threshold.

19. The medium of claim 12, wherein the tracking step includes receiving the source sequence number in the second node and storing the received source sequence number as a destination sequence number in the second node, the stored destination sequence number being updated only when a data packet numbered with a next higher source sequence number is received at the second node.

20. The medium of claim 12, further including a step of the first node receiving the packet reception bitmap message and selectively resending data packets identified by the packet reception bitmap message from the retransmission job queue to the second node.

21. The medium of claim 12, further including a step of removing data packets from the retransmission job queue of the first node, the removing step being carried out only upon receipt of a corresponding included current highest tracked source sequence number from the second node or when the packet reception bitmap message received from the second node indicates receipt of the data packet by the second node.

22. The medium of claim 12, further including a step of re-sending a first and subsequent data packets queued in the retransmission job queue, the re-sending step being carried out when a predetermined time period has elapsed without the first node having received a corresponding included current highest tracked source sequence number from the second node or when the packet reception bitmap message received from the second node indicates receipt of the queued first and subsequent data packets by the second node.

23. A method of transmitting data packets between a first node and a second node of a computer system, comprising steps of:

associating a source sequence number with each data packet transmitted from one of the first and the second nodes and storing the associated source sequence number, the stored source sequence number being incremented each time one of the first and second nodes transmits a new data packet to the other one of the first and second nodes;

storing a destination sequence number at one of the first and the second nodes, each destination sequence number being a copy of a last consecutively numbered source sequence number associated with a data packet received by one of the first and second nodes from the other one of the first and second nodes;

maintaining a local copy of each data packet transmitted from one of the first and the second nodes to the other one of the first and second nodes;

receiving destination sequence numbers included in data packets sent from one of the first and the second nodes to the other one of the first and second nodes, the received destination sequence numbers being indicative of safe receipt of at least one transmitted data packet;

generating and transmitting a packet reception bitmap message from one of the first and the second nodes to the other one of the first and second nodes, the packet reception bitmap message identifying a plurality of data packets which have not been timely received; and

upon receipt by one of the first and second nodes of a packet reception bitmap message, re-transmitting the data packets identified in the received packet reception bitmap message as not being safely received using the corresponding local copies of the data packets.

24. The method of claim 23, wherein the local copy of each data packet is discarded only upon receipt of a destination sequence number that indicates safe receipt of the locally copied data packet or when a received packet reception bitmap message indicates safe receipt of the locally copied data packet.

25. The method of claim 23, wherein the received destination sequence numbers are effective to acknowledge receipt of transmitted data packets that are numbered with source sequence numbers no larger than a highest source sequence number whose associated data packet has been received.

26. The method of claim 23, wherein the packet reception bitmap message transmitting step is carried out when a number of data packets associated with source sequence numbers between a lowest source sequence number whose data packet has not been received and a highest source sequence number whose data packet has been received, exceeds a first threshold.

27. The method of claim 23, wherein the packet reception bitmap message transmitting step is carried out when a time period between a time at which a data packet associated with a next higher source sequence number is received and a time at which a last data packet was received, exceeds a second threshold.

28. The method of claim 23, wherein the packet reception bitmap message transmitting step is carried out by one of the first and second nodes at a request of the other one of the first and second nodes.

29. The method of claim 23, wherein the packet reception bitmap message generating step is carried out when a difference between a last destination sequence number received and an earliest source sequence number sent by one of the first and second nodes and not received by the other one of the first and second nodes exceeds a predetermined first threshold.

30. The method of claim 23, wherein the packet reception bitmap message generating step is carried out when a difference between a time when a last sequential destination sequence number was received and a time when a last data packet was received exceeds a predetermined second threshold.

31. A computer readable medium having data stored thereon representing sequences of instructions which, when executed by a computer system having a first and a second node, causes the computer system to transmit data packets between the first node and the second node by performing the steps of:

associating a source sequence number with each data packet transmitted from one of the first and the second nodes and storing the associated source sequence number, the stored source sequence number being incremented each time one of the first and second nodes transmits a new data packet to the other one of the first and second nodes;

storing a destination sequence number at one of the first and the second nodes, each destination sequence number being a copy of a last consecutively numbered source sequence number associated with a data packet received by one of the first and second nodes from the other one of the first and second nodes;

maintaining a local copy of each data packet transmitted from one of the first and the second nodes to the other one of the first and second nodes;

receiving destination sequence numbers included in data packets sent from one of the first and the second nodes to the other one of the first and second nodes, the received destination sequence numbers being indicative of safe receipt of at least one transmitted data packet;

generating and transmitting a packet reception bitmap message from one of the first and the second nodes to the other one of the first and second nodes, the packet reception bitmap message identifying a plurality of data packets which have not been timely received; and

upon receipt by one of the first and second nodes of a packet reception bitmap message, re-transmitting the data packets identified in the received packet reception bitmap message as not being safely received using the corresponding local copies of the data packets.

32. The medium of claim 31, wherein the local copy of each data packet is discarded only upon receipt of a destination sequence number that indicates safe receipt of the locally copied data packet or when a received packet reception bitmap message indicates safe receipt of the locally copied data packet.

33. The medium of claim 31, wherein the received destination sequence numbers are effective to acknowledge receipt of transmitted data packets that are numbered with source sequence numbers no larger than a highest source sequence number whose associated data packet has been received.

34. The medium of claim 31, wherein the packet reception bitmap message transmitting step is carried out when a number of data packets associated with source sequence numbers between a lowest source sequence number whose data packet has not been received and a highest source sequence number whose data packet has been received, exceeds a first threshold.

35. The medium of claim 31, wherein the packet reception bitmap message transmitting step is carried out when a time period between a time at which a data packet associated with a next higher source sequence number is received and a time at which a last data packet was received, exceeds a second threshold.

36. The medium of claim 31, wherein the packet reception bitmap message transmitting step is carried out by one of the first and second nodes at a request of the other one of the first and second nodes.

37. The medium of claim 31, wherein the packet reception bitmap message generating step is carried out when a difference between a last destination sequence number received and an earliest source sequence number sent by one of the first and second nodes and not received by the other one of the first and second nodes exceeds a predetermined first threshold.

38. The medium of claim 31, wherein the packet reception bitmap message generating step is carried out when a difference between a time when a last sequential destination sequence number was received and a time when a last data packet was received exceeds a predetermined second threshold.