Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-10-28
2002-07-23
Yao, Kwang B. (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S410000
Reexamination Certificate
active
06424625
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to Automatic Repeat Request (ARQ) techniques for transferring data in fixed/wireless data networks.
BACKGROUND OF THE INVENTION
ARQ techniques are commonly used in data networks to ensure reliable data transfer and to protect data sequence integrity. Data packets are encoded with an error detecting code, so that when a transmitter in the data network sends or transfers data packets to a receiver in the data network, the receiver receiving the data packets can detect corrupted, erroneous or lost packets and thereby request that the transmitter retransmit the affected data packets. The integrity of a data sequence is normally protected by sequentially numbering packets and applying certain transmission rules.
There are three main ARQ schemes: Stop-and-Wait; Go-Back-N; and Selective Reject (sometimes referred to as Selective Repeat). All three methods provide mechanisms for transferring packets to a receiver in a data network in an appropriate order. In terms of throughput efficiency as a function of the signal to noise ratio, generally Selective Reject is most efficient, Stop-and-Wait is least efficient, and Go-Back-N is intermediate. Also, various mixtures of the Selective Reject and Go-Back-N techniques exist, and fall between pure Selective Reject and pure Go-Back-N techniques in both efficiency and complexity.
With respect to Go-Back-N, several different variants exist which differ in terms of how they use positive acknowledgments (PACKs), negative acknowledgments (NACKs), retransmission timers, polling schemes, etc.
One type of Go-Back-N technique uses both PACKs and NACKs that have the following characteristics:
A PACK for a data packet having a sequence number N(R) gives a cumulative positive acknowledgment for data packets having sequence numbers before N(R), but does not positively acknowledge the data packet having the sequence number N(R), as shown for example in FIG.
1
A.
The NACK positively acknowledges all data packets before the data packet it negatively acknowledges. The data packet which the NACK negatively acknowledges is indicated by N(R), as shown for example in FIG.
1
B.
FIG. 2
shows a simplified ARQ transmitter window, in which five variables are used to keep track of a transmitter state. The five variables include: a bottom sequence number, BSN; a top sequence number, TSN; a maximum top sequence number, TSN
MAX
; an instant sequence number, ISN; and an expected sequence number, ESN.
BSN denotes the oldest packet in the transmitter buffer, and can also indicate that all packets before the BSN packet have been acknowledged or discarded. Packets prior to the packet indicated by TSN have been sent. ESN denotes the expected sequence number of a packet to be received. ISN indicates the sequence number of the next packet to be sent. When a packet is sent for the first time, TSN and ISN will be identical. However, when a retransmission is performed, ISN will start over from the first retransmitted packet and progress in consecutive order, one packet at a time, up to TSN. TSN cannot exceed TSN
MAX
, which is defined by the window size W. Assuming that a sequence number field has k bits, 2
k
different sequence numbers can be created. Thus, the maximum size W of the window shown in
FIG. 2
is 2
k
−1.
Operation of the Go-Back-N technique using both PACKs and NACKs can be envisioned by imagining a clockwise consecutive modulo 2
k
sequence numbering superimposed upon the circumference of the circles shown in
FIGS. 3A-3D
.
FIG. 3A
shows a circle indicating a state where no packets have yet been sent, and TSN, ESN, BSN and ISN all have the same value, i.e., point to the same packet. The circle shown in
FIG. 3B
indicates that (TSN-BSN) packets have been sent and also received, since ESN=TSN. An erroneous or lost packet causes ESN to stop progressing forward, although more packets have been sent. For example, in
FIG. 3C
packets up to the packet indicated by TSN and ISN have been sent, but ESN indicates a prior packet which was not received. After a packet is lost or an erroneous packet is received, the ARQ receiver sends a NACK to the ARQ transmitter to inform the ARQ transmitter about the lost or erroneous packet. The NACK includes a returned sequence number N(R) that is set equal to ESN, thereby acknowledging that all previous packets were correctly received. BSN and ISN are set equal to ESN (and N(R)) so that BSN moves forward and ISN moves backward to the sequence number representing the lost or erroneous packet. Thereafter, as shown in
FIG. 3D
, ISN and ESN move forward together as the lost or erroneous packet is retransmitted, and as the succeeding packets are also retransmitted.
FIGS. 4A-4D
illustrate use of a PACK. For example,
FIG. 4A
shows a state where nothing has yet been sent, and TSN=ISN=BSN=ESN.
FIG. 4B
shows a situation where all sent packets have been correctly received.
FIG. 4C
shows that a timer-initiated PACK is sent, conveying the sequence number N(R) of a packet between BSN and TSN=ESN=ISN. As shown in
FIG. 4D
, after the PACK is sent, BSN is set to N(R).
Sending PACKs ensures that sequence number starvation does not occur. Since TSN may not pass BSN, if the transmitter does not receive PACKs, it may continue to send data packets up to TSN
MAX
. However, if data packets up to TSN
MAX
are sent but no PACKs are received, then TSN
MAX
cannot progress and sequence number starvation occurs. The transmitter must wait until it receives a PACK, which will allow BSN and thus TSN
MAX
to progress.
FIG. 5
shows a general example of an ARQ data packet
510
. The packet
510
typically includes an ARQ header
512
and a data portion
516
. The header
512
contains a k-bit sequence number
514
, and can be located at the front of the packet
510
as shown in
FIG. 5
, or at any predefined position within the packet
510
.
FIG. 6
shows an exemplary ACK message
610
, with an identifier field
612
that identifies the responding terminal sending the ACK message
610
, a NACK/PACK type indicator
614
indicating whether a PACK or a NACK is being sent, and finally a sequence number field N(R)
616
that indicates for which sequence number the ACK message
610
is valid.
In a Selective Reject scheme, a sender window having a size of 2
k−1
or less is normally used in order to avoid certain ambiguities which appear in conjunction with an automatic (timer-initiated) retransmission. The receiver window size in a Selective Reject scheme can include up to 2
k−1
positions, instead of just one position as in a Go-Back-N scheme. In Selective Reject a range of packets can be received since the receiver window can include up to 2
k−1
positions.
As long as packets are received correctly, they are sent or forwarded to the next higher layer. When an outstanding packet is detected, i.e., a packet that has been sent but not received or not correctly received, the sending of subsequent packets up to the higher layer is halted and a list of correct and missing packets is built up. A NACK is used to initiate a request for a retransmission of the outstanding packet or of a multitude of outstanding packets. When the first detected outstanding packet is correctly received, that packet and all subsequent packets are sent to the higher layer, until the next outstanding packet is detected and the process repeats with respect to the new outstanding packet.
FIG. 7A
, for example, shows a situation wherein three packets are outstanding. The outstanding packets are denoted by ESN
1
, ESN
2
and ESN
3
. The receiver sends one or several NACKs indicating the sequence number of these outstanding packets. In
FIGS. 7B and 7C
, the transmitter has received the one or several NACKs and in response retransmits the outstanding packets. The transmission of new packets can proceed to the TSN
MAX
limit, which of course can also occur when no NACKs are received. In particular,
FIG. 7B
shows a situation where ESN
1
has been retransmitted and correctly received,
Larsson Mikael
Larsson Peter
Burns Doane Swecker & Mathis L.L.P.
Telefonaktiebolaget LM Ericsson (publ)
Yao Kwang B.
LandOfFree
Method and apparatus for discarding packets in a data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for discarding packets in a data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for discarding packets in a data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2890357