Transmission order based selective repeat data transmission error recovery system and method

• US 5,754,754 A
• Filed: 07/26/1995
• Issued: 05/19/1998
• Est. Priority Date: 07/26/1995
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Dudley, John G., Peyravian, Mohammad
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Elmore, Stephen C.
• Application Number:
  US08/506,934
• Time in Patent Office: 1,028 Days
• Field of Search: 395/182.16, 395/200.13, 395/200.17, 395/856, 395/182.13, 364/204.8, 371/30, 371/32, 370/216, 370/218, 370/231, 370/242, 370/394, 370/912
• US Class Current: 714/18
• CPC Class Codes: G06F 11/1443 Transmit or communication errors
• 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/1635 Cumulative acknowledgement, i.e. the acknowledgement message applying to all previous messages
• 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 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/1832 Details of sliding window management
• CPC Class Codes: H04L 1/1841 Resequencing
• CPC Class Codes: H04L 1/187 Details of sliding window management
• CPC Class Codes: H04L 1/188 Time-out mechanisms

Abstract

An error recovery system and method for use in a data communication system in which a sender station transmits information packets with sequentially numbered information to a receiver station. The system includes selective retransmission of information packets which have had errors in transmission based on the order of transmission of information packets independent of the sequential (sequence) number of the information packets. A list, such as a linked list having a beginning and an end, is provided and, at the time of transmission of information packets, an identification of the transmitted information packet is placed at the end of the list. A status packet is provided by the receiver station to the sender station which identifies the sequential number of information packets which have been correctly received. Any information packets which have not been acknowledged as correctly received are retransmitted only if such packet was transmitted earlier in time than an information packet which has been acknowledged as correctly received as indicated by the position of the information packets in the list. The receiver station detects the presence of gaps and transmits a status packet to the sender station either responsive to a request from the sender station or responsive to detection of a gap.

Claims

1. An error recovery system for use in a data communication system in which a sender station transmits a plurality of information packets, each of the information packets having an associated sequential number to a receiver station, comprising:

means for transmitting said information packets;

means for detecting if said information packets have been transmitted without error;

means for determining an order in time of transmission of said information packets independent of the associated sequential numbers of said plurality of information packets;

retransmission control means, responsive to said means for detecting if said information packets have been transmitted without error and said means for determining an order in time of transmission of said information packets independent of the associated sequential numbers of said plurality of information packets, for identifying any of said information packets which have had an error in transmission and were transmitted by said means for transmitting information packets earlier in time than one of said information packets which has been transmitted without error and for providing any such information packet to said means for transmitting information packets for retransmission; and

wherein said means for determining an order in time of transmission of said information packets independent of the associated sequential numbers of said plurality of information packets comprises means for placing an identification of a transmitted information packet at an end of a list at the time of transmission of the transmitted information packet.

2. The error recovery system of claim 1 wherein said means for placing an identification of a transmitted information packet at an end of a list at the time of transmission of the transmitted information packet comprises:

a linked list having a beginning and an end; and

means for placing an identification of the transmitted information packet at the end of said linked list at the time of transmission of the information packet.

3. The error recovery system of claim 2 wherein said retransmission control means comprises:

means for providing to said means for transmitting said information packets for retransmission any information packet which has had an error in transmission which has a sequential number which was placed in said linked list before the associated sequential number of any information packet which has been transmitted without error; and

means for removing from said linked list the associated sequential number of any information packet which has been transmitted without error.

4. The error recovery system of claim 3 wherein said means for detecting if said information packets have been transmitted without error comprises:

means for detecting a gap in the associated sequential numbers of correctly received information packets; and

means for transmitting to said sender station a status packet containing acknowledgment of correctly received information packets responsive to said means for detecting a gap in the associated sequential numbers of correctly received information packets.

5. The error recovery system of claim 4 wherein said status packet contains the associated sequential number of a highest sequential number information packet which has been correctly received without any gaps in the associated sequential numbers of preceding correctly received information packets and further contains a start and stop sequence number of any spans of correctly received information packets having higher associated sequential numbers than the associated sequential number of the highest sequential number information packet which has been correctly received without any gaps in the associated sequential numbers of preceding correctly received information packets.

6. The error recovery system of claim 4 further comprising:

means for detecting if said status packet was received without error by said sender station and for providing to said means for transmitting to said sender station said status packet for retransmission if said status packet had an error in transmission.

7. The error recovery system of claim 6 wherein the data communication system defines a transmission window of the sender station further comprising:

means for determining if the transmission window of said sender station could close before a next status packet is received by said sender station; and

means responsive to said means for determining if the transmission window of said sender station could close for transmitting a request for a status packet to the receiver station.

8. A sender station for use in a data communication system in which the sender station transmits a plurality of information packets, each of the information packets having an associated sequential number to a receiver station, comprising:

a transmitter operatively connected to said data communication system;

a linked list having a beginning and an end;

means for placing in said linked list at said end thereof the associated sequential number of each information packet transmitted by said transmitter as each information packet is transmitted by said transmitter so that said link list provides a transmission order list of the associated sequential numbers of said information packets.

9. A sender station according to claim 8 further comprising:

a receiver operatively connected to said data communication system;

said receiver receiving from said receiver station a status packet; and

means operatively connected to said receiver and to said linked list for determining from said status packet which information packets have been correctly received by said receiver station and for determining based on position in said linked list any information packets which have not been correctly received by said receiver station which were transmitted earlier in time to one of said information packets which has been correctly received, and for providing any such information packets to said transmitter for retransmission.

10. An error recovery method for a data communication system in which a sender station transmits a plurality of information packets, each of the information packets having an associated sequential number, to a receiver station, comprising the steps of:

transmitting one of said plurality of information packets to the receiver station;

detecting if the transmitted information packet has been transmitted without error;

determining an order in time of transmission of the plurality of information packets independent of the associated sequential numbers of the information packets; and

retransmitting any information packets which have had an error in transmission which were transmitted earlier in time than an information packet which has been transmitted without error; and

wherein said step of detecting if the information packet has been transmitted without error comprises the steps of;

detecting a gap in the associated numbers of correctly received information packets; and

transmitting to the sender station a status packet containing acknowledgment of correctly received information packets responsive to said step of detecting a gap in the associated sequential numbers of correctly received information packets.

11. The error recovery method of claim 10 wherein the status packet contains the associated sequential number of a highest sequential number information packet which has been correctly received without any gaps in the associated sequential numbers of preceding correctly received information packets and further contains a start and stop sequence number of any spans of correctly received information packets.

12. The error recovery method of claim 10 wherein the following steps are performed after said step of transmitting to the sender station a status packet containing acknowledgment of correctly received information packets:

starting a timer when the status packet is transmitted;

checking the timer to determine if it has expired;

retransmitting the status packet if the timer has expired; and

, restarting the timer.

13. The error recovery method of claim 10 wherein said step of determining the order in time of transmission of the plurality of information packets independent of the associated sequential numbers of the information packets comprises the following step:

placing an identification of the transmitted information packet at a end of a list at the time of transmission of the information packet.

14. The error recovery method of claim 13 wherein said step of retransmitting any information packets which have had an error in transmission which were transmitted earlier in time than an information packet which has been transmitted without error comprises the step of:

identifying for retransmission any information packet which has not been acknowledged as received having a sequential number which is earlier in the list than a sequential number in the list of an acknowledged information packet.

15. The error recovery method of claim 14 wherein the data communication system defines a transmission window of the sender station further comprising the steps of:

determining if the sender station transmission window could close unless a new status packet is received; and

,

transmitting a request for a status packet to the receiver station if the transmission window of the sender station could close unless a new status packet is received.

16. The error recovery method of claim 14 further comprising the steps of:

starting a timer when a request for a status packet is transmitted;

checking the timer to determine if it has expired;

if the timer has expired, retransmitting the request for a status packet; and

restarting the timer.

17. The error recovery method of claim 10 further comprising the steps of:

determining if the information packet to be transmitted to the receiver station is a last information packet to be transmitted;

transmitting a request for a status packet to the receiver station if the information packet to be transmitted to the receiver station is the last information packet to be transmitted;

starting a timer when the request for a status packet is transmitted;

checking the timer to determine if it has expired;

if the timer has expired, retransmitting the request for a status packet; and

restarting the timer.