Go-Back-N ARQ
Encyclopedia
Go-Back-N ARQ is a specific instance of the automatic repeat request (ARQ) protocol, in which the sending process continues to send a number of frames
specified by a window size even without receiving an acknowledgement
(ACK) packet from the receiver. It is a special case of the general sliding window protocol
with the transmit window size of N and receive window size of 1.
The receiver process keeps track of the sequence number of the next frame it expects to receive, and sends that number with every ACK it sends. The receiver will ignore any frame that does not have the exact sequence number it expects – whether that frame is a "past" duplicate of a frame it has already ACK'ed
or whether that frame is a "future" frame past the last packet it is waiting for. Once the sender has sent all of the frames in its window, it will detect that all of the frames since the first lost frame are outstanding, and will go back to sequence number of the last ACK it received from the receiver process and fill its window starting with that frame and continue the process over again.
Go-Back-N ARQ is a more efficient use of a connection than Stop-and-wait ARQ
, since unlike waiting for an acknowledgement for each packet, the connection is still being utilized as packets are being sent. In other words, during the time that would otherwise be spent waiting, more packets are being sent. However, this method also results in sending frames multiple times – if any frame was lost or damaged, or the ACK acknowledging them was lost or damaged, then that frame and all following frames in the window (even if they were received without error) will be re-sent. To avoid this, Selective Repeat ARQ
can be used.
1: The sender must not transmit too fast. N should be bounded by the receiver’s ability to process packets.
2: N must be smaller than the number of sequence numbers (if they are numbered from zero to N) to verify transmission in cases of any packet (any data or ACK packet) being dropped.
3: Given the bounds presented in (1) and (2), choose N to be the largest number possible.
Data frame
In computer networking and telecommunication, a frame is a digital data transmission unit or data packet that includes frame synchronization, i.e. a sequence of bits or symbols making it possible for the receiver to detect the beginning and end of the packet in the stream of symbols or bits...
specified by a window size even without receiving an acknowledgement
Acknowledgement (data networks)
In data networking, an acknowledgment is a signal passed between communicating processes or computers to signify acknowledgment, or receipt of response, as part of a communications protocol...
(ACK) packet from the receiver. It is a special case of the general sliding window protocol
Sliding Window Protocol
A sliding window protocol is a feature of packet-based data transmission protocols. Sliding window protocols are used where reliable in-order delivery of packets is required, such as in the Data Link Layer as well as in the Transmission Control Protocol .Conceptually, each portion of the...
with the transmit window size of N and receive window size of 1.
The receiver process keeps track of the sequence number of the next frame it expects to receive, and sends that number with every ACK it sends. The receiver will ignore any frame that does not have the exact sequence number it expects – whether that frame is a "past" duplicate of a frame it has already ACK'ed
or whether that frame is a "future" frame past the last packet it is waiting for. Once the sender has sent all of the frames in its window, it will detect that all of the frames since the first lost frame are outstanding, and will go back to sequence number of the last ACK it received from the receiver process and fill its window starting with that frame and continue the process over again.
Go-Back-N ARQ is a more efficient use of a connection than Stop-and-wait ARQ
Stop-and-wait ARQ
Stop-and-wait ARQ is a method used in telecommunications to send information between two connected devices. It ensures that information is not lost due to dropped packets and that packets are received in the correct order. It is the simplest kind of automatic repeat-request method...
, since unlike waiting for an acknowledgement for each packet, the connection is still being utilized as packets are being sent. In other words, during the time that would otherwise be spent waiting, more packets are being sent. However, this method also results in sending frames multiple times – if any frame was lost or damaged, or the ACK acknowledging them was lost or damaged, then that frame and all following frames in the window (even if they were received without error) will be re-sent. To avoid this, Selective Repeat ARQ
Selective Repeat ARQ
Selective Repeat ARQ / Selective Reject ARQ is a specific instance of the Automatic Repeat-Request protocol used for communications.-Concept:...
can be used.
Pseudocode
These examples assume an infinite number of sequence and request numbers.
N = window size
Rn = request number
Sn = sequence number
Sb = sequence base
Sm = sequence max
Receiver:
Rn = 0
Do the following forever:
If the packet received = Rn && the packet is error free
Accept the packet and send it to a higher layer
Rn = Rn + 1
Send a Request for Rn
Else
Refuse packet
Send a Request for Rn
Sender:
Sb = 0
Sm = N – 1
Repeat the following steps forever:
1. If you receive a request number where Rn > Sb
Sm = Sm + (Rn – Sb)
Sb = Rn
2. If no packet is in transmission,
Transmit a packet where Sb <= Sn <= Sm.
Packets are transmitted in order.
Choosing a Window size(N)
There are a few things to keep in mind when choosing a value for N.1: The sender must not transmit too fast. N should be bounded by the receiver’s ability to process packets.
2: N must be smaller than the number of sequence numbers (if they are numbered from zero to N) to verify transmission in cases of any packet (any data or ACK packet) being dropped.
3: Given the bounds presented in (1) and (2), choose N to be the largest number possible.