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

• US 7,187,677 B2
• Filed: 05/23/2002
• Issued: 03/06/2007
• 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
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US10/152,986
• Publication Number:
  US 20030169741A1
• Time in Patent Office: 1,748 Days
• Field of Search: None
• 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 may be 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;

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;

receiving the missing data unit before the timer expires;

stopping the timer; and

removing the received data units having a sequence number less than the sequence number of the missing data unit,

the received missing data unit and the received data units each having a sequence number less than the sequence number of the received missing data unit are sent to a higher protocol layer for further processing.

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:

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

6. 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.

7. 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,

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, the method further comprising;

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

8. The method in claim 7, 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.

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

10. The method in claim 7, 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.

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

12. The method in claim 7, 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.

13. The method in claim 7, 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.

14. 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,

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

if a recently-received data unit is outside the receiving window, then 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.

15. The method in claim 14, 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 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.

16. The method in claim 15, further comprising:

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

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

18. The method in claim 14, 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.

19. The method in claim 14, 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.

20. The method in claim 14, further comprising:

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

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

22. The method in claim 14, 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.

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

24. The method in claim 14, 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.

25. The method in claim 24, 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.

26. 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

if the missing data unit is received before the timer expires, stop the timer, remove the received data units each having a sequence number less than the sequence number of the missing data unit, and send the received missing data unit and the received data units each having a sequence number less than the sequence number of the received missing data unit to a higher protocol layer for further processing.

27. The receiver in claim 26, 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.

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

29. The receiver in claim 26, 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.

30. The receiver in claim 26, 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.

31. 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,

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.

32. The transmitter in claim 31, 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.

33. The transmitter in claim 31, 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.

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

35. 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,

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, and

a buffer,

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.

36. The receiver in claim 35, further comprising:

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 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.

37. The receiver in claim 35, 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.

38. The receiver in claim 35, 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.

39. The receiver in claim 35, 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.

40. The receiver in claim 35, 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.

41. The receiver in claim 35, wherein the size of the receiver window is N/2.

42. The receiver in claim 35, 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.