Method and apparatus for discarding packets in a data network having automatic repeat request

• US 6,424,625 B1
• Filed: 10/28/1998
• Issued: 07/23/2002
• Est. Priority Date: 10/28/1998
• Status: Expired due to Term

• Current Assignee: Wi-Fi One, LLC (Inception Holdings, LLC)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Larsson, Mikael, Larsson, Peter
• Primary Examiner(s): YAO, KWANG BIN
• Application Number:
  US09/179,952
• Time in Patent Office: 1,364 Days
• Field of Search: 370/389, 370/394, 370/410, 370/426, 370/428, 370/429, 370/470, 370/471, 370/473, 370/236, 714/748, 714/749, 714/750
• US Class Current: 370/236
• CPC Class Codes: H04L 1/1806 Go-back-N protocols
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/1841 Resequencing
• CPC Class Codes: H04L 1/1877 for semi-reliable protocols, e.g. for less sensitive applications like streaming video buffer level management for video bitstream control arrangements H04N21/44004

Abstract

Techniques are provided for use with automatic repeat request (ARQ) schemes in a data network to minimize a bandwidth used by a receiver and a transmitter in the network to transfer data packets, by discarding outdated packets that have not yet been successfully transferred. In accordance with an embodiment of the invention, a bit is set in the ARQ packet header to force the receiver to accept packets subsequent to one or more erroneous or unreceived packets that have been discarded and not resent. In accordance with another embodiment of the invention, after data packets have been discarded, sequence numbers are reassigned to the non-discarded data packets that are yet to be sent to the receiver, so that a transmitted stream of the non-discarded packets will have consecutive sequence numbers.

Claims

1. A method for discarding packets in a data network employing a packet transfer protocol including an automatic repeat request scheme, comprising the steps of:

a transmitter in the data network commanding a receiver in the data network to a) receive at least one packet having a sequence number that is not consecutive with a sequence number of a previously received packet and b) release any expectation of receiving outstanding packets having sequence numbers prior to the at least one packet; and

the transmitter discarding all packets for which acknowledgment has not been received, and which have sequence numbers prior to the at least one packet.

2. The method of claim 1, wherein each of the at least one packet includes a receive enforcement bit, and the step of commanding comprises the steps of:

setting the receive enforcement bit for each of the at least one packet to a TRUE value; and

sending the at least one packet to the receiver.

3. The method of claim 1, wherein the step of commanding comprises the steps of:

setting a receive enforcement bit to a TRUE value for each at least one packet; and

sending the at least one receive enforcement bit set to TRUE together with identification of a transmitter sending the packets and the sequence numbers of the packets in a control message to the receiver.

4. The method of claim 1, wherein the method pertains to a go-back-n automatic repeat request scheme and further comprises the steps of:

defining a maximum top sequence number equal to a value (DSN+2<sup>k−

1</sup>), where DSN is a sequence number indicating that all packets having sequence numbers previous to DSN have been acknowledged by a receiver in the data network as having been received, and k is a number of bits in a sequence number field for a packet in the data network;

accepting a received packet when a receive enforcement bit for the received packet is set to TRUE and N(S)−

ESN<

2<sup>k−

1</sup>, where N(S) is a sequence number of the received packet and ESN is an expected sequence number of a next packet to be received; and

performing one of a) a restart of the automatic repeat request scheme and b) reporting a failure event to a management control system when the receive enforcement bit for the received packet is set to TRUE and N(S)−

ESN≧

2<sup>k−

1</sup>.

5. The method of claim 1, wherein the method pertains to a go-back-n automatic repeat request scheme and further comprises the steps of:

constraining a top sequence number TSN according to the rules (TSN≦

DSN−

1), (TSN≦

BSN+W) and (1≦

W≦

2<sup>k−

1</sup>), where k is a number of bits in a sequence number field for a packet in the data network, DSN is a sequence number indicating that all packets having sequence numbers previous to DSN have been acknowledged by a receiver in the data network as having been received, BSN is a bottom sequence number indicating a sequence number of an oldest packet stored in a transmit buffer of a transmitter in the data network, and W is a window size known to both the receiver and the transmitter, within which packets are tracked;

accepting a received packet when a receive enforcement bit for the received packet is set to TRUE and N(S)−

ESN<

2^k−

W, where N(S) is a sequence number of the received packet and ESN is an expected sequence number of a next packet to be received;

performing one of a) a restart of the automatic repeat request scheme and b) reporting a failure event to a management control system when the receive enforcement bit for the received packet is set to TRUE and N(S)−

ESN≧

2^k−

W; and

constraining BSN according to the rule (DSN≦

BSN≦

TSN).

6. The method of claim 1, wherein the method pertains to a selective repeat automatic repeat request scheme and further comprises the steps of:

constraining a bottom sequence number BSN indicating a sequence number of an oldest packet stored in a transmit buffer of a transmitter in the data network, and a top sequence number TSN according to the rules (DSN≦

BSN≦

TSN≦

TSN_MAX), where DSN is a sequence number indicating that all packets having sequence numbers previous to DSN have been acknowledged by a receiver in the data network as having been received, TSN_MAX is a maximum top sequence number, (TSN_MAX−

DSN=2<sup>k−

1</sup>), and k is a number of bits in a sequence number field for a packet in the data network;

accepting a received packet when a receive enforcement bit for the received packet is set to TRUE and N(S)−

ESN<

2<sup>k−

1</sup>, where N(S) is a sequence number of the received packet and ESN is an expected sequence number of a next packet to be received; and

performing one of a) a restart of the automatic repeat request scheme and b) reporting a failure event to a management control system when the receive enforcement bit for the received packet is set to TRUE and N(S)−

ESN≧

2<sup>k−

1</sup>.

7. The method of claim 6, further comprising the steps of:

when a) a first packet having a sequence number after DSN and before BSN is negatively acknowledged, b) a number of packets that are prior to the first packet and not positively acknowledged is less than a difference between BSN and the sequence number of the first packet, and c) TSN≠

BSN, setting a receive enforcement bit for the packet indicated by BSN and resending the packet indicated by BSN from the transmitter to the receiver.

8. The method of claim 6, further comprising the steps of:

when a) a first packet having a sequence number after DSN and before BSN is negatively acknowledged, b) a number of packets that are prior to the first packet and not positively acknowledged is less than a difference between BSN and the sequence number of the first packet, and c) TSN=BSN,

if a packet is pending for transmission, then setting a receive enforcement bit for the pending packet to TRUE and sending the pending packet from the transmitter to the receiver;

if no packets are pending for transmission, then performing one of a) waiting until a packet is received from a higher layer and b) informing the receiver that no packets are pending.

9. The method of claim 6, further comprising the steps of:

when a) a first packet having a sequence number after DSN and before BSN is negatively acknowledged, b) a number of packets that are prior to the first packet and not positively acknowledged is greater than a difference between BSN and the sequence number of the first packet, and c) TSN≠

BSN, setting a receive enforcement bit for a first outstanding packet after BSN and resending the first outstanding packet from the transmitter to the receiver.

10. The method of claim 6, further comprising the steps of:

when a) a first packet having a sequence number after DSN and before BSN is negatively acknowledged, b) a number of packets that are prior to the first packet and not positively acknowledged is greater than a difference between BSN and the sequence number of the first packet, c) at least one packet exists after the first packet, and d) there are no negatively acknowledged packets having sequence numbers after BSN, setting a receive enforcement bit for a first packet after BSN and resending the first packet after BSN from the transmitter to the receiver.

11. The method of claim 6, further comprising the steps of:

when a first packet having a sequence number after DSN and before BSN is negatively acknowledged, and all packets having sequence numbers greater than or equal to BSN and less than TSN have been positively acknowledged,

if a packet is pending for transmission, then setting a receive enforcement bit for the pending packet to TRUE and sending the pending packet from the transmitter to the receiver;

if no packets are pending for transmission, then performing one of a) waiting until a packet is received from a higher layer and b) informing the receiver that no packets are pending.

12. The method of claim 6, further comprising the steps of:

when a timer-initiated retransmission of a packet occurs, and ISN=BSN, setting a receive enforcement bit for the packet to TRUE; and

when a timer-initiated retransmission of the packet occurs, and ISN≠

BSN, setting the receive enforcement bit for the packet to FALSE;

wherein

ISN indicates a sequence number of a next packet to be sent.

13. The method of claim 6, further comprising the steps of:

when (ISN=BSN) and (BSN≠

DSN), setting a receive enforcement bit for the packet to TRUE, and otherwise setting the receive enforcement bit for the packet to FALSE, where ISN indicates a sequence number of a next packet to be sent.

14. A method for discarding packets in a data network employing a packet transfer protocol including a go-back-n automatic repeat request scheme, comprising the steps of:

discarding at least one packet from a transmitter;

receiving a NACK for the at least one packet from a receiver; and

assigning consecutive sequence numbers to non-discarded packets adjacent to the at least one packet.

15. A method for discarding packets in a data network employing a packet transfer protocol including a go-back-n automatic repeat request scheme, comprising the steps of:

a transmitter in the data network discarding at least one packet that has been sent by the transmitter but has not been acknowledged by a receiver in the data network as received;

after discarding the at least one packet, resynchronizing the transmitter and the receiver so that the last packet received by the receiver and the next packet to be transmitted by the transmitter have consecutive sequence numbers.

16. The method of claim 15, wherein the step of resynchronizing comprises the steps of:

determining what sequence number the receiver expects to receive next; and

when the expected sequence number is different from the sequence number of the packet to be sent next from the transmitter, assigning the expected sequence number to the packet to be sent next from the transmitter.

17. The method of claim 15, wherein the step of resynchronizing comprises the steps of:

determining what sequence number the receiver expects to receive next; and

when the expected sequence number is different from the sequence number of the packet to be sent next from the transmitter, commanding the receiver to expect a sequence number of a next packet to be sent from the transmitter to the receiver.

18. The method of claim 15, wherein the step of resynchronizing comprises the step of commanding the receiver to expect a sequence number of a next packet to be sent from the transmitter to the receiver.

19. A method for discarding packets in a data network employing a packet transfer protocol including a go-back-n automatic repeat request scheme, comprising the steps of:

a transmitter in the data network discarding at least one packet that has been sent by the transmitter but has not been acknowledged by a receiver in the data network as received;

after discarding the at least one packet, resynchronizing the receiver and the transmitter by determining what sequence number the receiver next expects, and consecutively renumbering packets pending at the transmitter starting with the expected sequence number.