Method and system for a voiding unnecessary retransmissions using a selective rejection data link protocol

• US 5,664,091 A
• Filed: 08/31/1995
• Issued: 09/02/1997
• Est. Priority Date: 08/31/1995
• Status: Expired due to Term

• Current Assignee: NCR Corporation (NCR Voyix Corporation)
• Original Assignee: NCR Corporation (NCR Voyix Corporation)
• Inventors: Keen, Henry D.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Palys, Joseph E.
• Application Number:
  US08/524,021
• Time in Patent Office: 733 Days
• Field of Search: 395/182.16, 395/182.15, 395/182.14, 395/185.02, 371/32, 371/33, 371/34
• US Class Current: 714/18
• CPC Class Codes: G06F 11/1443 Transmit or communication errors
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/188 Time-out mechanisms
• CPC Class Codes: H04L 1/1887 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and system for controlling the retransmission of data packets which monitors the successive progression of cycles of round trips of message signal transmissions between a transmitter and at least one receiver for avoiding unnecessary retransmissions of data packets which are detected as incorrect during the transmission of sequentially numbered data packets of a data file. Data representative of the progress of cycles are included in the data fields of message signals transmitted to communication devices. Another copy of a data packet is not retransmitted pursuant to a request for retransmission unless the data values related to cycle progression indicate that the last transmitted copy of the data packet was not in transit to the communication device requesting the retransmission at the time the device issued the request. Unnecessary retransmissions in multicast communication sessions are prevented by monitoring the progression of cycles and delaying the retransmission of data packets scheduled for retransmission to compensate for the propagation delay to the receiving device furthest from the transmitting device.

Claims

1. A system for selectively retransmitting data packets detected as incorrect during a transmission of a data file from a transmitter to a receiver, said data file comprising a plurality of sequentially numbered data packets, the retransmission system comprising:

the transmitter comprising a processor connected to a memory, wherein said transmitter transmits and receives message signals, said transmitted message signals including data packets and requests for status (RQST), said received message signals including responses to the RQSTs,

wherein said transmitter originally transmits said data packets sequentially, and wherein said transmitter issues the RQSTS at a predetermined rate;

the receiver comprising a processor connected to a memory, wherein said receiver transmits and receives message signals, said received message signals including the data packets and the RQSTs, said transmitted message signals including the responses to the RQSTs, said responses including requests for retransmission of data packets detected as incorrect, said receiver processor being operable to detect incorrect data packets and determine the sequence number of said detected incorrect data packets,

wherein said transmitter processor and said receiver processor store in the transmitter memory and receiver memory, respectively, data indicating progress of cycles of round trips of message signal retransmission between the transmitter and the receiver, and

wherein each said RQST and response message signals includes a data field, each said data field including data representative of the progress of the cycles such that unnecessary retransmission of a data packet requested for retransmission in a response message signal is avoided while said requested data packet is in transit to said receiver.

2. The system of claim 1,

wherein the data stored in the transmitter memory further comprises

a first data word representation indicating progress of cycles as monitored at the transmitter,

counter data tracking the progress of cycles, and

data indicating the last time a copy of any sequentially numbered data packet was transmitted;

wherein the data stored in the receiver memory comprises a second data word representation indicating the next expected value of the first data word stored in the transmitter memory;

wherein the processor increments the counter data value each time a cycle is completed;

wherein said transmitter processor includes in the data field of the RQST message signals a data word representation of the latest value of the first data word stored in the transmitter memory;

wherein said receiver processor includes in the data field of the response message signals a data word representation of the latest value of the second data word stored in the receiver memory; and

,

wherein said transmitter processor is operable to determine the progress of cycles from the data words included in the data field of a response message signal.

3. The system of claim 2, wherein each of the second data word in the receiver memory, the first data word in the transmitter memory and the data word representations included in the data fields of message signals is a single data bit.

4. The system of claim 1, wherein the transmitter retransmits a copy of a sequentially numbered data packet requested for retransmission in a response message signal upon determination that a cycle corresponding to the last transmission of a copy of the data packet is complete.

5. The system of claim 1, wherein said transmitter processor further includes in each of said data packet message signals a data field, said data field of said data packet message signal including data representative of the progress of cycles.

6. The system of claim 5, wherein said transmitter processor further includes in the data field of the data packet message signals a data word representation of a latest value of a first data word stored in the transmitter memory.

7. The system of claim 6, wherein each of a second data word stored in the receiver memory, the first data word in the transmitter memory and the data word representations included in the data fields of message signals is a single data bit.

8. The system of claim 5, wherein said receiver issues unsolicited response message signals including requests for retransmission.

9. The system of claim 1, wherein the transmitter does not retransmit a copy of a data packet requested for retransmission in a response message signal where data in the transmitter memory indicates that a cycle corresponding to the last transmission of a copy of the data packet is not complete.

10. The system of claim 1, wherein the transmitter determines that the cycle data included in the data field of a response message signal do not indicate completion of a cycle, and

wherein the transmitter retransmits a copy of a data packet requested for retransmission in the response, wherein data in the transmitter memory indicates that the last transmission of a copy of the data packet did not occur during the current cycle.

11. A system for selectively retransmitting data packets detected as incorrect during transmission of a data file, said data file comprising a plurality of sequentially numbered data packets, the retransmission system comprising:

a transmitter comprising a processor connected to a memory, wherein said transmitter transmits and receives message signals, said transmitted message signals including data packets and requests for status (RQST), said received message signals including responses to the RQSTs,

wherein said transmitter originally transmits said data packets sequentially, and wherein said transmitter issues the RQSTs at a predetermined rate;

a plurality of receivers, each of said receivers comprising a processor connected to a memory, wherein each said receiver transmits and receives message signals, said received message signals including the data packets and the RQSTs, said transmitted message signals including the responses to the RQSTs, said responses including requests for retransmission of data packets detected as incorrect, said receiver processor being operable to detect incorrect data packets and determine the sequence number of the detected incorrect data packets,

wherein said transmitter processor and each of said receiver processors store in the transmitter memory and each of said receiver memories, respectively, data indicating progress of cycles of round trips of message signal transmissions between said transmitter and any of said plurality of receivers, and

wherein each of said RQST and response message signals transmitted between each of said plurality of receivers and said transmitter includes a data field, each said data field including data representative of the progress of cycles such that unnecessary retransmission of data packets requested for retransmission in a response message signal is avoided while said requested data packets are in transit to said plurality of receivers.

12. The system of claim 11,

wherein the data stored in the transmitter memory further comprises

a multiple bit first data word representation indicating progress of cycles as monitored at the transmitter,

counter data tracking the progress of cycles, and

data indicating the last time a copy of any sequentially numbered data packet was transmitted;

wherein the data stored in the receiver memory comprises a multiple bit second data word representation indicating acknowledgements of any received cycle indications of the first data word stored in the transmitter;

wherein said transmitter processor includes in the data field of the RQST message signals a multiple bit data word representation of the latest value of the first data word stored in the transmitter memory;

wherein said receiver processor includes in the data field of the response message signals a multiple bit data word representation of the latest value of the second data word stored in the receiver memory;

wherein each said receiver processor updates the value of the second data word stored in the receiver memory according to a predetermined modulus, wherein the modulus is defined by the number of bits allocated in the data field of the message signals for representing the latest values of the second data word stored in the receiver memory at each said receiver and the latest values of the first data word stored at the transmitter memory, wherein the number of bits allocated in the data field defines a compensating delay interval,

wherein said transmitter processor schedules for retransmission those data packets requested for retransmission in response message signals where the value of the data word representation included in the data field of these response message signals is equal to one greater than the current value of the first data word stored in the transmitter memory,

wherein the transmitter processor increments the value of the first data word stored in the transmitter memory by one each time a sequence of data packets is retransmitted, and

wherein the transmitter processor increments the value of the counter data by one for each retransmission of a sequence of data packets scheduled for retransmission such that incrementing the first data word stored in the transmitter memory provides the compensating delay interval required for compensating for the propagation delay to the receiver furthest from the transmitter for avoiding unnecessary retransmissions.

13. The system of claim 12, wherein each of the second data words stored in each of the plurality of receiver memories, respectively, the first data word stored in the transmitter memory and the data word representations included in the data fields of message signals is a two bit word.

14. The system of claim 12, wherein the transmitter retransmits a copy of a data packet requested for retransmission in a request message signal where the transmitter processor determines that the difference between the first data word stored in the transmitter memory and the value of the data word representation received in the message signal is less than the difference between the counter data value and the value of counter data at the last time a copy of the data packet was transmitted.

15. The system of claim 14, wherein the transmitter processor removes from the data packet retransmission schedule the data packet being retransmitted.

16. The system of claim 14, wherein the transmitter does not retransmit a copy of a data packet requested for retransmission in a request message signal where the transmitter determines that the difference between the value of the first data word stored in the transmitter memory and the value of the data word representation received in the message signal is not less than the difference between the value of the counter data and the value of the counter data at the last time a copy of the data packet was transmitted such that an unnecessary retransmission of the data packet is avoided.

17. The system of claim 11, wherein a copy of a data packet scheduled for retransmission is retransmitted from the transmitter when the last transmitted copy of the data packet is not in transit to the receiver requesting the retransmission.

18. The system of claim 11, wherein the processor of each said receiver discards data packets determined to be duplicate transmissions.

19. The system of claim 11, wherein a multiple bit data word representation of the progress of cycles is included in a data field of the data packet message signals, and

wherein the processor of each said receiver issues unsolicited response message signals including requests for data packet retransmission.

20. The system of claim 11, wherein the transmitter processor further includes a delay timer, wherein said delay timer times out a timer delay interval, said timer delay interval delaying the retransmission of data packets scheduled for retransmission by introducing an additional delay to compensate for the propagation delay to the receiver furthest from the transmitter.

21. The system of claim 20, wherein timing of the timer delay interval by the delay timer is restarted if the transmitter processor detects from the data word representation included in the data field of the currently received response message signal that data packet retransmission is occurring too quickly to allow for compensation of the propagation delay to the receiver issuing the currently received response message signal.

22. A method for selectively retransmitting data packets detected as incorrect during transmission of data file, said data file comprising a plurality of sequentially numbered data packets, the method comprising the steps of:

(a) transmitting message signals including data packets and requests for status (RQST) from a transmitter to a receiver, said transmitter comprising a processor connected to a memory and said receiver comprising a processor connected to a memory, wherein said transmitting step further comprises originally transmitting said data packets sequentially and issuing RQSTS at a predetermined rate;

(b) receiving at said receiver the transmitted message signals including the sequentially transmitted data packets and the issued RQSTs;

(c) detecting incorrect data packets at said receiver;

(d) determining the sequence numbers of any of the data packets detected as incorrect at said receiver;

(e) transmitting from said receiver message signals including a response to an issued RQST, said response message signal including a request for retransmission of a data packet detected as incorrect;

(f) storing data in the transmitter memory and the receiver memory indicating progress of cycles of round trips of message signal retransmissions between the transmitter and the receiver;

(g) including data representative of the progress of cycles in a data field in each said RQST and response message signal said data field usable to determine whether said request for retransmission is stale; and

,

(h) retransmitting, as a function of said determination a copy of a sequentially numbered data packet requested for retransmission in said response message signal to thereby avoid unnecessary retransmission of said data packet while in transit to said receiver.

23. The method of claim 22, wherein step (f) further comprises the steps of:

storing in the transmitter memory a first data word representation indicating progress of cycles, counter data tracking the progress of cycles, and data indicating the last time a copy of any sequentially numbered data packet was transmitted, and

storing in the receiver memory a second data word representation indicating the next expected value of the first data word stored in the transmitter memory;

wherein step (g) further comprises the steps of;

including in the data field of the RQST message signals a data word representation of the latest value of the first data word stored in the transmitter memory, and

including in the data field of the response message signals a data word representation of the latest value of the second data word stored in the receiver memory;

and wherein the method of claim 22 further comprises the steps of;

(i) incrementing the counter data value each time a cycle is completed; and

,

(j) comparing the latest values of the first data word stored in said transmitter memory and the latest value of the second data word included in the data field of a response message signal for determining whether a cycle corresponding to a data packet retransmission has been completed.

24. The method of claim 23, wherein each of the second data word in the receiver memory, the first data word in the transmitter memory and the data word representations included in the data fields of message signals is a single data bit.

25. The method of claim 23, wherein step (g) further comprises the step of including data representative of the progress of cycles in a data field of each said data packet message signal.

26. The method of claim 25, wherein step (g) further comprises the step of including in the data field of the data packet message signals a data word representation of the latest value of the first data word Stored in the transmitter memory.

27. The method of claim 26, wherein each of the second data word in the receiver memory, the first data word in the transmitter memory and the data word representations included in the data fields of message signals is a single data bit.

28. The method of claim 25, wherein step (e) further comprises the step of transmitting from the receiver unsolicited response message signals including requests for retransmission.

29. The method of claim 22, wherein step (h) further comprises the step of preventing retransmission of a copy of a data packet requested for retransmission in a response message signal where data in the transmitter memory indicates that a cycle corresponding to the last transmission of a copy of the data packet is not complete.

30. The method of claim 22, wherein step (h) further comprises the step of retransmitting a copy of a data packet requested for retransmission in a response message signal when the transmitter processor determines that the data included in the data field of a response message signal does not indicate completion of a cycle and when data in the transmitter memory indicates that the last transmission of a copy of the data packet did not occur during the current cycle indicated by a counter data value.

31. A method for selectively retransmitting data packets detected as incorrect during transmission of a data file, said data file comprising a plurality of sequentially numbered data packets, the method comprising the steps of:

(a) transmitting message signals including data packets and requests for status (RQST) from a transmitter to at least one receiver, said transmitter comprising a processor connected to a memory and said at least one receiver comprising a processor connected to a memory, wherein said transmitting step further comprises originally transmitting said data packets sequentially and issuing RQSTs at a predetermined rate;

(b) receiving at said at least one receiver the transmitted message signals including the sequentially transmitted data packets and the issued RQSTs;

(c) detecting incorrect data packets at said at least one receiver;

(d) determining the sequence numbers of any of the data packets detected as incorrect at said at least one receiver;

(e) transmitting from said at least one receiver message signals including a response to an issued RQST including a request for retransmission of a data packet detected as incorrect;

(f) storing data in the transmitter memory and the receiver memory of said at least one receiver indicating progress of cycles of round trips of message signal transmissions between said transmitter and said at least one receiver;

(g) including data representative of the progress of cycles in a data field of each of said RQST and response message signals transmitted between said at least one receiver and said transmitter, said data field usable to determine whether said request for retransmission is stale; and

,

(h) retransmitting, as a function of said determination, a copy of a sequentially numbered data packet requested for retransmission in said response message signal upon determination that propagation delay to the receiver furthest from the transmitter has been compensated and a cycle corresponding to the last transmission of a copy of the data packet is complete to thereby avoid unnecessary retransmission of said data packet while in transit to said at least one receiver.

32. The method of claim 31, wherein step (f) further comprises the steps of

storing in the transmitter memory a multiple bit first data word representation indicating progress of cycles, counter data tracking the progress of Cycles, and data indicating the last time a copy of any sequentially numbered data packet was transmitted, and

storing in said at least one receiver memory a multiple bit second data word representation indicating acknowledgements of any received cycle indications of the first data word stored in the transmitter;

wherein the step (g) further comprises the steps of;

including in the data field of the RQST message signals a multiple bit data word representation of the latest value of the first data word stored in the transmitter memory, and

including in the data field of the response message signals data a multiple bit data word representation of the latest value of the second data word stored in the said at least one receiver memory;

and wherein the method of claim 31 further comprises the steps of;

(i) updating the value of the second data word stored in the said at least one receiver memory according to a predetermined modulus, wherein the modulus is defined by the number of bits allocated in the data field of the message signals for representing the latest values of the second data word stored in the said at least one receiver memory and the latest values of the first data word stored at the transmitter memory, wherein the number of bits allocated in the data field defines a compensating delay interval;

(j) scheduling for retransmission those data packets requested for retransmission in response message signals where the value of the data word representation included in the data field of these response message signals is equal to one greater than the current value of the first data word stored in the transmitter memory;

(k) incrementing the value of the first data word stored in the transmitter memory by one each time a sequence of data packets is retransmitted; and

(l) incrementing the value of the counter data by one for each retransmission of a sequence of data packets scheduled for retransmission such that incrementing the first data word stored in the transmitter memory provides the compensating delay interval required for compensating for the propagation delay to the receiver furthest from the transmitter for avoiding unnecessary retransmissions.

33. The method of claim 32, wherein each of the second data word stored in said at least one receiver, the first data word stored in the transmitter memory and the data word representations included in the data fields of message signals is a two bit word.

34. The method of claim 32, wherein step (h) further comprises the step of:

retransmitting a copy of a data packet requested for retransmission in a request message signal where the transmitter determines that the difference between the first data word stored in the transmitter memory and the value of the data word representation received in the message signal is less than the difference between the counter data value and the value of counter data at the last time a copy of the data packet was transmitted.

35. The method of claim 34, wherein step (j) further comprises the step of:

removing from the data packet retransmission schedule the data packet being retransmitted.

36. The method of claim 31, wherein the step (h) further comprises the step of:

retransmitting a copy of a data packet scheduled for retransmission when the last copy of the data packet is not in transit to said at least one receiver requesting the retransmission.

37. The method of claim 36, further comprising the step of:

(m) discarding at said at least one receiver data packets determined to be duplicate transmissions.

38. The method of claim 31, wherein step (g) further comprises the step of including a multiple bit data word representation of the progress of cycles in a data field of the data packet message signals, and

wherein step (h) further comprises the step of transmitting from said at least one receiver unsolicited response message signals including requests for data packet retransmission.

39. The method of claim 31, further comprising the step of:

(m) timing out a timer delay interval at said transmitter for delaying the retransmission of data packets scheduled for retransmission for introducing an additional delay to compensate for the propagation delay to the receiver furthest from the transmitter.

40. The method of claim 39, wherein step (m) further comprises the step of restarting timing of the timer delay interval if the transmitter processor detects from the data word representation included in the data field of the currently received response message signal that data packet retransmission is occurring too quickly to allow for compensation of the propagation delay to said at least one receiver transmitting the currently received response message signal.

41. The method of claim 31, wherein step (h) further comprises the step of:

preventing the retransmission of a copy of a data packet requested for retransmission in a request message signal where the transmitter determines that the difference between the value of the first data word stored in the transmitter memory and the value of the data word representation received in the message signal is not less than the difference between the value of the counter data and the value of the counter data at the last time a copy of the data packet was transmitted such that an unnecessary retransmission of the data packet is avoided.

42. A system for communicating a plurality of data packets among a transmitter and at least one receiver, comprising:

said transmitter that transmits said plurality of data packets to said at least one receiver;

said at least one receiver, communicable with said transmitter, that receives said transmitted plurality of data packets from said transmitter and is capable of requesting retransmission of at least one of said transmitted plurality of data packets; and

circuitry, associated with at least one memory that stores retransmission cycle information, that uses said retransmission cycle information to avoid unnecessary retransmission of said requested at least one of said transmitted plurality of data packets among said transmitter and said receiver when said requested at least one of said transmitted plurality of data packets may be in transit to said receiver.

43. A method of operating a system for communicating a plurality of data packets among a transmitter and at least one receiver, comprising the steps of:

transmitting said plurality of data packets from said transmitter to said at least one receiver;

receiving said transmitted plurality of data packets at said at least one receiver from said transmitter, and selectively requesting retransmission of at least one of said transmitted plurality of data packets; and

avoiding unnecessary retransmission of said requested at least one of said transmitted plurality of data packets among said transmitter and said receiver in response to retransmission cycle information stored in at least one memory, said unnecessary retransmission avoided when said requested at least one of said transmitted plurality of data packets may be in transit to said receiver.