Discard mechanism for selective repeat automatic repeat request

• US 6,621,796 B1
• Filed: 03/22/1999
• Issued: 09/16/2003
• Est. Priority Date: 03/22/1999
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Miklós, György
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Phan, Tri H.
• Application Number:
  US09/273,259
• Time in Patent Office: 1,639 Days
• Field of Search: 370/235, 370/236, 370/410, 370/231, 370/252, 370/389, 370/390, 370/392, 370/394, 714/746, 714/751, 714/814, 714/815, 714/748, 714/749, 714/750, 714/18, 714/55, 713/600
• US Class Current: 370/236
• 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/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/1832 Details of sliding window management
• CPC Class Codes: H04L 1/1838 for semi-reliable protocols, e.g. for less sensitive applications such as streaming video buffer level management for video bitstream receiver H04N21/44004
• CPC Class Codes: H04L 1/1848 Time-out mechanisms

Abstract

A more effective discard mechanism for Selective Repeat ARQ is achievable, where the discard mechanism exhibits a sender-initiated discard signaling scheme. The discard mechanism is also more effective where it takes into consideration the segmentation and reassembly of upper layer data packets, if such is being employed, and where it is able to notify the receiver when data units have been discarded at the sender, regardless whether explicit discard signaling from the sender to the receiver is feasible.

Claims

1. A method for discarding data units for Selective Repeat ARQ, said method comprising the steps of:

transmitting a first data unit from a sender to a receiver;

initiating a first timer in connection with said step of transmitting the first data unit;

transmitting a second data unit from the sender to the receiver;

initiating a second timer in connection with the second data unit being received;

at the sender, discarding the first data unit if a time period corresponding to the first timer expires before the sender receives an acknowledgment from the receiver that the first data unit was received; and

performing a purge operation at the receiver as a function of the second data unit, if a time period corresponding to the second timer expires before the first data unit is received.

6. The method of claim 1, wherein the time period corresponding to the second timer is greater than or equal to the time period corresponding to the first timer.

7. The method of claim 1, wherein said step of performing a purge operation at the receiver as a function of the second data unit, if a time period corresponding to the second timer expires before the first data unit is received, comprises the step of:

releasing buffer space at the receiver allocated for the first data unit.

8. The method of claim 1, wherein said first data unit and said second data unit are protocol data units.

24. The method of claim 6 further comprising the steps of:

maintaining a first variable equal to a first sequence number of a first received discard-signaling data unit, wherein the first sequence number indicates that the first discard-signaling data unit was transmitted before any other discard-signaling data unit;

maintaining a second variable equal to a second sequence number associated with a second discard-signaling data unit which has a start bit in its header portion set, wherein the second sequence number indicates that the second discard-signaling data unit was transmitted after the first discard-signaling data unit;

maintaining a third variable equal to a third sequence number associated with a third discard-signaling data unit which has a stop bit in its header portion set, wherein the third sequence number indicates that the third discard-signaling data unit was transmitted after the first discard-signaling data unit,

wherein said step of discarding a received data unit associated with a non-completely received data packet is accomplished as a function of the first, second and third variables.

25. The method of claim 6 further comprising the step of:

upon receiving any of the one or more discard-signaling data units, releasing buffer space at the receiver allocated for a data unit that has not been received, if the data unit that has not yet been received has a sequence number indicating that it was transmitted before any of the one or more discard-signaling data units.

26. The method of claim 6 further comprising the step of:

upon receiving any of the one or more discard-signaling data units, transporting a group of one or more data units associated with a completely received data packet to a higher network layer.

28. The method of claim 7, wherein said step of performing a purge operation at the receiver as a function of the sequence number associated with the discard-signaling data unit, comprises the step of:

discarding a received data unit that has a sequence number indicating that the received data unit was transmitted before the discard-signaling data unit.

29. The method of claim 7, wherein said step of performing a purge operation at the receiver as a function of the sequence number associated with the discard-signaling data unit, comprises the step of:

releasing buffer space at the receiver allocated for a data unit that has not yet been received, if the data unit that has not yet been received has a sequence number indicating that it was transmitted before the discard-signaling data unit.

2. A method for discarding data units for Selective Repeat ARQ, said method comprising the steps of:

transmitting, from a sender to a receiver, a plurality of data units, wherein each of said plurality of data units is associated with a common data packet, and wherein each of said plurality of data units is assigned a sequence number representing the order in which the corresponding data unit is transmitted;

initiating a first timer in connection with the transmission of a first of said plurality of data units;

initiating a second timer if a second of said plurality of data units is received when the receiver is expecting to receive at least one data unit having a sequence number indicating that the at least one data unit was transmitted before the second of said plurality of data units;

at the sender, discarding each of said plurality of data units associated with the common data packet if any one of said plurality of data units has not been acknowledged as being received before a time period associated with the first timer expires; and

at the receiver, performing a purge operation as a function of the second of said plurality of data units, if a time period associated with the second timer expires and the receiver is expecting to receive at least one data unit having a sequence number indicating that the at least one data unit was transmitted before the second of said plurality data units.

9. The method of claim 2, wherein the at least one data unit having a sequence number indicating that the at least one data unit was transmitted before the second of said plurality of data units is one of said plurality of data units.

10. The method of claim 2, wherein said time period associated with the second timer is greater than or equal to the time period associated with the first timer.

11. The method of claim 2, wherein said step of performing a purge operation as a function of a second of said plurality of data units comprises the step of:

discarding a received data unit if it is associated with a non-completely received data packet, and if it has a sequence number indicating that it was transmitted before any of the plurality of data units associated with the common data packet.

12. The method of claim 2, wherein said step of performing a purge operation as a function of the second of said plurality of data units comprises the step of:

releasing buffer space allocated to any data unit that the receiver is expecting to

receive, if the data unit has a sequence number indicating that it was transmitted before any of the plurality of data units associated with the common data unit.

13. The method of claim 2, wherein said step of performing a purge operation as a function of the second of said plurality of data units comprises the step of:

transporting a group of received data units that are associated with a completed received data packet, wherein each of the data units associated with the group have a sequence number indicating that they were transmitted before any of the plurality of data units associated with the common data packet.

3. A method for discarding data units for Selective Repeat ARQ, said method comprising the steps of:

transmitting a plurality of data units from a sender to a receiver, wherein a first timer is maintained at the sender and a second timer is maintained at the receiver, wherein each of the plurality of data units is assigned a sequence number representing the order in which the corresponding data unit is transmitted, and wherein a higher sequence number reflects a later transmission and a lower sequence number reflects an earlier transmission;

at the sender, maintaining a variable HSS which has a value that represents the highest sequence number of any data unit that has been transmitted at a given point during a present cycle of the first timer;

at the receiver, maintaining two variables, HSR1 and HSR2, wherein HSR1 has a value that represents the highest sequence number of any data unit received at a given point during a present cycle of the second timer, and wherein HSR2 which has a value that represents the highest sequence number of any data unit received at a same point during a previous cycle of the second timer;

at the given point during each cycle of the first timer, discarding any data unit at the sender that has a sequence number that is less than the value of the variable HSS and, thereafter, updating the value of the variable HSS; and

at the given point during each cycle of the second timer, purging any data unit having a sequence number that is less than the value of the variable HSR2 and, thereafter, updating the value of the variables HSR1 and HSR2.

14. The method of claim 3, wherein said step of purging any data unit having a sequence number that is less than the value of the variable HSR2 and, thereafter, updating the value of the variables HSR1 and HSR2, comprises a step of:

setting the value of the variable HSR2 equal to the value of the variable HSR1 and, thereafter, setting the value of the variable HSR1 equal to the highest sequence number of any data unit received thus far.

15. The method of claim 14, wherein said step of purging any data unit having a sequence number that is less that the value of the variable HSR2 and, thereafter, updating the value of the variables HSR1 and HSR2, comprises the step of:

discharging any data unit having a sequence number that is less that the value of the variable HSR2.

16. The method of claim 14, wherein said step of purging any data unit having a sequence number that is less than the value of the variable HSR2 and, thereafter, updating the value of the variables HSR1 and HSR2, comprises the step of:

releasing buffer space at the receiver allocated to any missing data unit having a sequence number that is less than the value of the variable HSR2.

4. A method for discarding data units for selective Repeat ARQ, wherein said method comprises the steps of:

defining a transmission window, wherein the transmission window represents a sequence of K number of data units which are eligible for transmission from a sender to a receiver, wherein each data unit is assigned a sequence number which represents the order of transmission associated with the corresponding data unit;

at the sender, discarding one or more data units that are currently within the transmission window, wherein the one or more data units have sequence numbers that indicate the one or more data units were transmitted prior to all other data units currently in the transmission window;

advancing the transmission window forward as a function of the one or more discarded data units;

defining a receiving window, wherein the receiving window represents a sequence of data units which have been received or are expected to be received; and

if a data unit having a sequence number S is received, wherein the sequence number S is above the receiving window, performing a purge operation at the receiver as a function of the sequence number S-K+1.

17. The method of claim 4, wherein said step of performing a purge operation at the receiver as a function of the sequence number S-K+1, comprises the step of:

discarding a received data unit having a sequence number that is less than S-K+1.

18. The method of claim 4, wherein said step of performing a purge operation at the receiver as a function of sequence number S-K+1, comprises the step of:

releasing a missing data unit that has a sequence number that is less than S-K +1.

19. The method of claim 4, wherein said step of advancing the transmission window forward as a function of the one of more discarded data units, comprises the step of:

advancing the transmission window forward as a function of the number of said one or more discarded data units.

5. A method for discarding data units for Selective Repeat ARQ, said method comprising the steps of:

transmitting a plurality of data units from a sender to a receiver, wherein said plurality of data units are associated with data packets, and wherein each data packet may be associated with one or more data units;

at the sender, storing a first data unit associated with a data packet until the receiver completely acknowledges the data packet;

discarding one or more data units, at the sender, which have a sequence number indicating that they were transmitted before said first data unit;

generating a discard-signaling data unit by setting a discard-bit in a header portion of said first data unit;

transmitting said discard-signaling data unit to the receiver, so as to notify the receiver that the one or more data units have been discarded at the sender; and

performing a purge operation at the receiver as a function of a sequence number associated with said discard-signaling data unit.

20. The method of claim 5, wherein the data packet associated with the first data unit is further associated with a plurality of data units, and wherein the first data unit has a sequence number indicating that is was transmitted before any of the other of said plurality of said data units.

21. The method of claim 5, wherein said step of performing a purge operation at the receiver as a function of a sequence number associated with said discard-signaling data unit, comprises the step of:

discarding a received data unit that has a sequencing number indicating that the received data unit was transmitted before the first data unit.

22. The method of claim 5, wherein said step of performing a purge operation at the receiver as a function of a sequence number associated with said discard-signaling unit, comprises the step of:

releasing buffer space allocated to a data unit that the receiver is expecting to receive, wherein the data unit that the receiver is expecting to receive has a sequence number indicating that is was transmitted before the first data unit.

23. A method of discarding data units for Selective Repeat ARQ, said method comprising the steps of:

transmitting a plurality of data units from a sender to a receiver, wherein said plurality of data units are associated with data packets such that each data packet may comprise one or more data units, and wherein each of said plurality of data units are assigned a sequence number indicating the order of transmission for the corresponding data unit;

discarding a data unit at the sender;

generating one or more discard-signaling data units by setting a discard bit in a header portion of each data unit at the sender associated with a next available data packet at the sender, wherein the next available data packet at the sender comprises one or more data units that have not been discarded or acknowledged by the receiver as being received, and wherein each of the one or more data units have a sequence number indicating that the one or more data units associated with the next available data packet were transmitted after the discarded data unit;

transmitting the one or more discard-signaling data units; and

upon receiving any of the one or more discard-signaling data units, discarding a received data unit associated with a non-completely received data packet, if the received data unit has a sequence number indicating that it was transmitted before any of the one or more discard-signaling data units.

27. A method of discarding data units for Selective Repeat ARQ, said method comprising the steps of:

transmitting a plurality of data units from a sender to a receiver, wherein each of said plurality of data units are assigned a sequence number indicating the order of transmission for each of said plurality of data units;

discarding a data unit at the sender;

generating a discard-signaling data unit as a function of a first undischarged data unit following the discarded data unit, wherein a discard-signaling data unit has a discard bit in a header portion of the data unit set and a data valid bit in the header portion of the data unit reset;

transmitting the discard-signaling data unit to the receiver; and

performing a purge operation at the receiver as a function of the sequence number associated with the discard-signaling data unit.

30. A method for discarding data units for Selective Repeat ARQ, said method comprising steps of:

transmitting a plurality of data units from a sender to a receiver, wherein said plurality of data units are associated with data packets, and wherein each data packet may be associated with one or more data units, and wherein each of said plurality of data units are assigned a sequence number indicating the order of transmission for the corresponding data unit;

at the sender, storing a first data unit associated with a data packet at least until the receiver completely acknowledges the data packet;

discarding one or more data units, at the sender, which have a sequence number indicating that they were transmitted or sequence number which indicate that they would have been transmitted before said first data unit;

generating a discard-indication message including the corresponding sequence number of first said data unit;

transmitting said discard-indicating message to the receiver, so as to notify the receiver that one or more data units have been discarded at the sender; and

performing a purge operation at the receiver as a function of the sequence number conveyed in the discard-indicating message.

31. The method of claim 30, wherein the data packet associated with the first data unit is further associated with a plurality of data units, and wherein the first data unit has a sequence number indicating that is was transmitted before any of the other of said plurality of said data units.

32. The meted of claim 30, wherein said step of performing a purge operation at the receiver as a function of a sequence number conveyed in said discard-indicating message, comprises abe step of:

discarding a received data unit that has a sequencing number indicating that the received data unit was transmitted before the first data unit.

33. The method of claim 30, wherein said step of performing a purge operation at the receiver as a function at a sequence number conveyed in said discard-indicating message, comprises the step of:

releasing buffer space allocated to a data unit that the receiver is expecting to receive, wherein the data unit that the receiver is expecting to receive has a sequence number indicating that is was transmitted before the first data unit.

34. A method for discarding data units for Selective Repeat ARQ, said method comprising steps of:

transmitting a plurality of data units from a sender to a receiver, wherein said plurality of data units are associated with data packets, and wherein each data packet may be associated with one or more data units, and wherein each of said plurality of data units are assigned a sequence number indicating the order of transmission for the corresponding data unit;

discarding one or more data units at the sender;

generating one or more discard-indication messages including the corresponding sequence number associated with a next available data packet at the sender, wherein the next available data packet at the sender comprise one or more data units that have not been discarded or acknowledged by the receiver as being received;

transmitting the one or more discard-indication messages;

and upon receiving any of the one or more discard-indication messages, discarding a received data unit associated with a non-completely received data packet, if the received data unit has a sequence number indicating that it was transmitted before the sequence number conveyed in any of the one or more discard-indication messages.