Avoiding stall conditions and sequence number ambiguity in an automatic repeat request protocol

• US 20030169741A1
• Filed: 05/23/2002
• Published: 09/11/2003
• Est. Priority Date: 10/19/2001
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Peisa, Janne, Torsner, Per Johan
• Granted Patent: US 7,187,677 B2
• Time in Patent Office: Days
• US Class Current: 370/394
• CPC Class Codes: H04L 1/1819 with retransmission of additional or different redundancy
• CPC Class Codes: H04L 1/1832 Details of sliding window management
• CPC Class Codes: H04L 1/1848 Time-out mechanisms
• CPC Class Codes: H04L 1/187 Details of sliding window management

Abstract

The present invention provides a stall avoidance mechanism that maybe used alone or in conjunction with an ambiguity avoidance mechanism in an ARQ protocol. Both mechanisms decrease data delays and increase data throughput rates. Stall avoidance is accomplished by determining whether a stall condition exists with respect to receiving a missing data unit. In one example, only a single timer is needed to avoid stalls. Retransmission ambiguities may be avoided using a retransmission window in the transmitter and/or a receive window in the receiver. Although each mechanism may be used independently of the other, a preferred example embodiment uses a stall avoidance timer, a retransmission window in the transmitter, and a receive window in the receiver.

Claims

1. A method for use in data unit transmissions between a transmitter and a receiver implemented in the receiver, comprising:

detecting a sequence number of data units received by the receiver;

storing the received data units in a buffer;

identifying a missing data unit in the sequence;

starting a timer if a data unit is received having a sequence number greater than a sequence number of the missing data unit; and

if the timer expires before the missing data unit is received, removing from the buffer the received data units having sequence numbers less than the sequence number of the missing data unit.

2. The method in claim 1, wherein a missing data unit includes a data unit that has not been received, a data unit that is incorrectly received, or a received data unit that can not be corrected.

3. The method in claim 1, wherein a missing data unit includes a data unit that the receiver requests the transmitter to retransmit.

4. The method in claim 1, wherein the received data units having sequence numbers less than the sequence number of the missing data unit are sent to a higher protocol layer for further processing.

5. The method in claim 1, further comprising:

receiving the missing data unit before the timer expires;

stopping the timer;

removing the received data units having sequence numbers less than the sequence number of the missing data unit.

6. The method in claim 5, wherein the missing data unit and the received data units having sequence numbers less than the sequence number of the missing data unit are sent to a higher protocol layer for further processing.

7. The method in claim 1, further comprising:

using a retransmission window at the transmitter to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

8. The method in claim 1, further comprising:

using a receiving window at the receiver to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

9. A method for use in data unit transmissions between a transmitter and a receiver implemented in the receiver, comprising:

detecting a sequence number of data units received by the receiver;

storing the received data units in a buffer;

identifying a missing data unit in the sequence;

determining whether a stall condition exists with respect to receiving the missing data unit; and

when the stall condition exists, removing from the buffer the received data units having sequence numbers less than the sequence number of the missing data unit.

10. The method in claim 9, further comprising:

starting a timer if a data unit is received having a sequence number greater than a sequence number of the missing data unit,

wherein if the timer expires before the missing data unit is received, removing from the buffer the received data units having sequence numbers less than the sequence number of the missing data unit.

11. The method in claim 10, wherein the received data units having sequence numbers less than the sequence number of the missing data unit are sent to a higher protocol layer for further processing.

12. The method in claim 9, wherein a missing data unit includes a data unit that has not been received, a data unit that is incorrectly received, or a received data unit that can not be corrected.

13. The method in claim 9, wherein a missing data unit includes a data unit that the receiver requests the transmitter to retransmit.

14. The method in claim 9, further comprising:

using a retransmission window at the transmitter to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

15. The method in claim 9, further comprising:

using a receiving window at the receiver to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

16. A method for use in data unit transmissions between a transmitter and a receiver implemented in the transmitter, where each data unit includes a corresponding sequence number, comprising:

transmitting data units in sequence modulo-N, N being a largest sequence number;

establishing a retransmission window having a size corresponding to a number of data units less than N; and

using the retransmission window to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

17. The method in claim 16, further comprising:

only permitting retransmission of one or more data units having a sequence number within a current position of the retransmission window in the sequence.

18. The method in claim 16, wherein an upper end of the window is positioned at a sequence number that is less than or equal to a difference between a highest sequence number most recently transmitted and the window size.

19. The method in claim 18, further comprising:

moving the retransmission window to a next sequence number position in the modulo-N sequence after each data unit is transmitted.

20. The method in claim 16, wherein the size of the retransmission window is N/2.

21. The method in claim 16, wherein a missing data unit includes a data unit that has not been received, a data unit that is incorrectly received, or a received data unit that can not be corrected.

22. The method in claim 16, wherein a missing data unit includes a data unit that the receiver requests the transmitter to retransmit.

23. The method in claim 16, further comprising:

identifying a missing data unit in the sequence;

starting a timer if a data unit is received having a sequence number greater than a sequence number of the missing data unit; and

if the timer expires before the missing data unit is received, removing from the buffer the received data units having sequence numbers less than the sequence number of the missing data unit.

24. The method in claim 16, further comprising:

using a receiving window at the receiver to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

25. A method for use in data unit transmissions between a transmitter and a receiver implemented in the receiver, where each data unit includes a corresponding sequence number and is transmitted by the transmitter in sequence modulo-N, N being a largest sequence number, comprising:

a receiving window corresponding to a number of data units less than N, and

using the receiving window to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

26. The method in claim 25, further comprising:

storing in a buffer a received data unit having a sequence number within a current position of the receiving window in the sequence, where an upper end of the receiving window is positioned at a sequence number that is less than or equal to a difference between a highest sequence number most recently transmitted and the window size,

wherein the received data unit is stored at location in the buffer corresponding to the sequence number of the received data unit.

27. The method in claim 26, further comprising:

determining whether a recently-received data unit inside the receiving window was previously received, and if so, discarding the recently-received data unit.

28. The method in claim 26, wherein if a recently-received data unit inside the receiving window was not previously received, storing the recently-received data unit in the buffer in a position corresponding to the recently-received data unit sequence number.

29. The method in claim 26, wherein if a recently-received data unit is outside the receiving window, storing the recently-received data unit in the buffer at a position corresponding to the recently-received data unit sequence number, and

advancing the receiver window so that the sequence number of the recently-received data unit forms the upper end.

30. The method in claim 29, further comprising:

removing from the buffer any data units having a sequence number less than thea lower end of the receiver window.

31. The method in claim 26, further comprising:

removing from the buffer all received data units with consecutive sequence numbers up to a first missing data unit.

32. The method in claim 31, wherein the removed data units are provided to a higher protocol layer.

33. The method in claim 25, wherein the size of the receiver window is N/2.

34. The method in claim 25, wherein a missing data unit includes a data unit that has not been received, a data unit that is incorrectly received, or a received data unit that can not be corrected.

35. The method in claim 25, wherein a missing data unit includes a data unit that the receiver requests the transmitter to retransmit.

36. The method in claim 25, further comprising:

identifying a missing data unit in the sequence;

starting a timer if a data unit is received having a sequence number greater than a sequence number of the missing data unit; and

if the timer expires before the missing data unit is received, removing from the buffer the received data units having sequence numbers less than the sequence number of the missing data unit.

37. The method in claim 36, further comprising:

using a retransmission window at the transmitter to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

38. A receiver for receiving data units transmitted from a transmitter, comprising:

a detector for detecting a sequence number of data units received by the receiver;

a buffer for storing the received data units in a buffer;

a timer; and

electronic circuitry configured to;

identify a missing data unit in the sequence;

start the timer if a data unit is received having a sequence number greater than a sequence number of the missing data unit; and

if the timer expires before the missing data unit is received, remove from the buffer the received data units having sequence numbers less than the sequence number of the missing data unit.

39. The receiver in claim 38, wherein a missing data unit includes a data unit that has not been received, a data unit that is incorrectly received, or a received data unit that can not be corrected.

40. The receiver in claim 38, wherein a missing data unit includes a data unit that the receiver requests the transmitter to retransmit.

41. The receiver in claim 38, wherein the electronic circuitry is configured to send received data units having sequence numbers less than the sequence number of the missing data unit to a higher protocol layer for further processing.

42. The receiver in claim 38, wherein if the missing data unit is received before the timer expires, the electronic circuitry is configured to stop the timer and remove the received data units having sequence numbers less than the sequence number of the missing data unit.

43. The receiver in claim 38, wherein the electronic circuitry is configured to use a receiving window to avoid sequence number ambiguity between originally-transmitted data units and retransmitted data units.

44. A receiver for receiving data units transmitted from a transmitter, comprising:

a detector for detecting a sequence number of data units received by the receiver;

a buffer for storing the received data units in a buffer;

electronic circuitry configured to determine that a stall condition exists with respect to receiving the missing data unit and remove from the buffer the received data units having sequence numbers less than the sequence number of the missing data unit.

45. The receiver in claim 44, further comprising:

a timer,

wherein if a data unit is received having a sequence number greater than a sequence number of the missing data unit and the timer expires before the missing data unit is received, the electronic circuitry is configured to remove from the buffer the received data units having sequence numbers less than the sequence number of the missing data unit.

46. The receiver in claim 44, wherein the electronic circuitry is configured to send received data units having sequence numbers less than the sequence number of the missing data unit to a higher protocol layer for further processing.

47. The receiver in claim 44, further comprising:

a receiving window,

wherein the electronic circuitry is configured to use the receiving window to avoid sequence number ambiguity between originally-transmitted data units and retransmitted data units.

48. A transmitter for use in transmitting data units to a receiver, where each data unit includes a corresponding sequence number, comprising:

a transmitter for transmitting data units in sequence modulo-N, N being a largest sequence number;

a retransmission window having a size corresponding to a number of data units less than N; and

a controller configured to use the retransmission window to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

49. The transmitter in claim 48, wherein the controller is configured to only permit retransmission of one or more data units having a sequence number within a current position of the retransmission window in the sequence.

50. The transmitter in claim 48, wherein the controller is configured to position an upper end of the window at a sequence number that is less than or equal to a difference between a highest sequence number most recently transmitted and the window size.

51. The transmitter in claim 50, wherein the controller is configured to move the retransmission window to a next sequence number position in the modulo-N sequence after each data unit is transmitted.

52. The transmitter in claim 48, wherein the size of the retransmission window is N/2.

53. A receiver for use in data unit transmissions between a transmitter and the receiver, where each data unit includes a corresponding sequence number and is transmitted by the transmitter in sequence modulo-N, N being a largest sequence number, comprising:

a receiving window corresponding to a number of data units less than N, and

a controller configured to use the receiving window to avoid sequence number ambiguity in the receiver between originally-transmitted data units and retransmitted data units.

54. The receiver in claim 53, further comprising:

a buffer,

wherein the controller is configured to store in the buffer a received data unit having a sequence number within a current position of the receiving window in the sequence, where an upper end of the receiving window is positioned at a sequence number that is less than or equal to a difference between a highest sequence number most recently transmitted and the window size,

wherein the received data unit is stored at location in the buffer corresponding to the sequence number of the received data unit.

55. The receiver in claim 54, wherein the controller is configured to determine whether a recently-received data unit inside the receiving window was previously received, and if so, discard the recently-received data unit.

56. The receiver in claim 54, wherein if a recently-received data unit inside the receiving window was not previously received, the controller is configured to store the recently-received data unit in the buffer in a position corresponding to the recently-received data unit sequence number.

57. The receiver in claim 54, wherein if a recently-received data unit is outside the receiving window, the controller is configured to store the recently-received data unit in the buffer at a position corresponding to the recently-received data unit sequence number and advance the receiver window so that the sequence number of the recently-received data unit forms the upper end.

58. The receiver in claim 57, wherein the controller is configured to remove from the buffer any data units having a sequence number less than the lower end of the receiver window.

59. The receiver in claim 53, wherein the controller is configured to remove from the buffer all received data units with consecutive sequence numbers up to a first missing data unit.

60. The receiver in claim 53, wherein the size of the receiver window is N/2.

61. The receiver in claim 53, further comprising:

a timer,

wherein the controller is configured to;

identify a missing data unit in the sequence;

start the timer if a data unit is received having a sequence number greater than a sequence number of the missing data unit; and

if the timer expires before the missing data unit is received, remove from the buffer the received data units having sequence numbers less than the sequence number of the missing data unit.