Go-Back-N ARQ

Last updated

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. It can transmit N frames to the peer before requiring an ACK.

Contents

The receiver process keeps track of the sequence number of the next frame it expects to receive. It will discard any frame that does not have the exact sequence number it expects (either a duplicate frame it already acknowledged, or an out-of-order frame it expects to receive later) and will send an ACK for the last correct in-order frame. [1] 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 the 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 send window (even if they were received without error) will be re-sent. To avoid this, Selective Repeat ARQ can be used. [2]

Pseudocode

These examples assume an infinite number of sequence and request numbers. [1] 

N  := window size Rn := request number Sn := sequence number Sb := sequence base Sm := sequence max   function receiver isRn := 0     Do the following forever:         if the packet received = Rn and the packet is error free then             Accept the packet and send it to a higher layer             Rn := Rn + 1         else             Refuse packet         Send a Request for Rnfunction sender isSb := 0     Sm := N + 1     Repeat the following steps forever:         if you receive a request number where Rn > SbthenSm := (Sm − Sb) + RnSb := Rnif no packet is in transmission then             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) [ clarification needed ] to verify transmission in cases of any packet (any data or ACK packet) being dropped. [2]
  3. Given the bounds presented in (1) and (2), choose N to be the largest number possible. [3] [ failed verification ]

Related Research Articles

The Transmission Control Protocol (TCP) is one of the main protocols of the Internet protocol suite. It originated in the initial network implementation in which it complemented the Internet Protocol (IP). Therefore, the entire suite is commonly referred to as TCP/IP. TCP provides reliable, ordered, and error-checked delivery of a stream of octets (bytes) between applications running on hosts communicating via an IP network. Major internet applications such as the World Wide Web, email, remote administration, and file transfer rely on TCP, which is part of the transport layer of the TCP/IP suite. SSL/TLS often runs on top of TCP.

Automatic repeat request (ARQ), also known as automatic repeat query, is an error-control method for data transmission that uses acknowledgements and timeouts to achieve reliable data transmission over an unreliable communication channel. ARQ is appropriate if the communication channel has varying or unknown capacity. If the sender does not receive an acknowledgment before the timeout, it re-transmits the message until it receives an acknowledgment or exceeds a predefined number of retransmissions.

Alternating bit protocol (ABP) is a simple network protocol operating at the data link layer that retransmits lost or corrupted messages using FIFO semantics. It can be seen as a special case of a sliding window protocol where a simple timer restricts the order of messages to ensure receivers send messages in turn while using a window of 1 bit.

High-Level Data Link Control (HDLC) is a communication protocol used for transmitting data between devices in telecommunication and networking. Developed by the International Organization for Standardization (ISO), it is defined in the standard ISO/IEC 13239:2002.

<span class="mw-page-title-main">LAPB</span>

Link Access Procedure, Balanced (LAPB) implements the data link layer as defined in the X.25 protocol suite. LAPB is a bit-oriented protocol derived from HDLC that ensures that frames are error free and in the correct sequence. LAPB is specified in ITU-T Recommendation X.25 and ISO/IEC 7776. It implements the connection-mode data link service in the OSI Reference Model as defined by ITU-T Recommendation X.222.

<span class="mw-page-title-main">Stop-and-wait ARQ</span> Basic automatic repeat-request (ARQ) data transmission and error detection protocol

Stop-and-wait ARQ, also referred to as alternating bit protocol, is a method 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 automatic repeat-request (ARQ) mechanism. A stop-and-wait ARQ sender sends one frame at a time; it is a special case of the general sliding window protocol with transmit and receive window sizes equal to one in both cases. After sending each frame, the sender doesn't send any further frames until it receives an acknowledgement (ACK) signal. After receiving a valid frame, the receiver sends an ACK. If the ACK does not reach the sender before a certain time, known as the timeout, the sender sends the same frame again. The timeout countdown is reset after each frame transmission. The above behavior is a basic example of Stop-and-Wait. However, real-life implementations vary to address certain issues of design.

ZMODEM is an inline file transfer protocol developed by Chuck Forsberg in 1986, in a project funded by Telenet in order to improve file transfers on their X.25 network. In addition to dramatically improved performance compared to older protocols, ZMODEM offered restartable transfers, auto-start by the sender, an expanded 32-bit CRC, and control character quoting supporting 8-bit clean transfers, allowing it to be used on networks that would not pass control characters.

XMODEM is a simple file transfer protocol developed as a quick hack by Ward Christensen for use in his 1977 MODEM.ASM terminal program. It allowed users to transmit files between their computers when both sides used MODEM. Keith Petersen made a minor update to always turn on "quiet mode", and called the result XMODEM.

In data communications, flow control is the process of managing the rate of data transmission between two nodes to prevent a fast sender from overwhelming a slow receiver. Flow control should be distinguished from congestion control, which is used for controlling the flow of data when congestion has actually occurred. Flow control mechanisms can be classified by whether or not the receiving node sends feedback to the sending node.

Selective Repeat ARQ or Selective Reject ARQ is a specific instance of the automatic repeat request (ARQ) protocol used to manage sequence numbers and retransmissions in reliable communications.

Radio Link Protocol (RLP) is an automatic repeat request (ARQ) fragmentation protocol used over a wireless air interface. Most wireless air interfaces are tuned to provide 1% packet loss, and most Vocoders are mutually tuned to sacrifice very little voice quality at 1% packet loss. However, 1% packet loss is intolerable to all variants of TCP, and so something must be done to improve reliability for voice networks carrying TCP/IP data.

In two-way communication, whenever a frame is received, the receiver waits and does not send the control frame back to the sender immediately. The receiver waits until its network layer passes in the next data packet. The delayed acknowledgment is then attached to this outgoing data frame. This technique of temporarily delaying the acknowledgment so that it can be hooked with next outgoing data frame is known as piggybacking.

Protocol spoofing is used in data communications to improve performance in situations where an existing protocol is inadequate, for example due to long delays or high error rates.

SEAlink is a file transfer protocol that is backward compatible with XMODEM but features a sliding window system for improved throughput. SEAlink was written in 1986 as a part of the SEAdog FidoNet mailer written by System Enhancement Associates, creators of the famous ARC program. It was licensed with a simple "give credit" requirement, but nevertheless was not very widely used except in FidoNet mailers. SEAlink, and most other XMODEM enhancements, were quickly displaced following the introduction of ZMODEM.

The Stream Control Transmission Protocol (SCTP) has a simpler basic packet structure than TCP. Each consists of two basic sections:

  1. The common header, which occupies the first 12 bytes. In the adjacent diagram, this header is highlighted in blue.
  2. The data chunks, which form the remaining portion of the packet. In the diagram, the first chunk is highlighted in green and the last of N chunks (Chunk N) is highlighted in red. There are several types, including payload data and different control messages.

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. They are also used to improve efficiency when the channel may include high latency.

A reliable byte stream is a common service paradigm in computer networking; it refers to a byte stream in which the bytes which emerge from the communication channel at the recipient are exactly the same, and in exactly the same order, as they were when the sender inserted them into the channel.

In data networking, telecommunications, and computer buses, an acknowledgement (ACK) is a signal that is passed between communicating processes, computers, or devices to signify acknowledgment, or receipt of message, as part of a communications protocol. Correspondingly a negative-acknowledgement is a signal that is sent to reject a previously received message or to indicate some kind of error. Acknowledgments and negative acknowledgments inform a sender of the receiver's state so that it can adjust its own state accordingly.

NACK-Oriented Reliable Multicast (NORM) is a transport layer Internet protocol designed to provide reliable transport in multicast groups in data networks. It is formally defined by the Internet Engineering Task Force (IETF) in Request for Comments (RFC) 5740, which was published in November 2009.

Reliable Data Transfer is a topic in computer networking concerning the transfer of data across unreliable channels. Unreliability is one of the drawbacks of packet switched networks such as the modern internet, as packet loss can occur for a variety of reasons, and delivery of packets is not guaranteed to happen in the order that the packets were sent. Therefore, in order to create long-term data streams over the internet, techniques have been developed to provide reliability, which are generally implemented in the Transport layer of the internet protocol suite.

References

  1. 1 2 Kurose, James F.; Keith W. Ross. Computer Networking: A Top-Down Approach. ISBN   0-321-49770-8.
  2. 1 2 Tanenbaum, Andrew S. (2003). Computer Networks (4th ed.). Prentice Hall. ISBN   0-13-066102-3.
  3. ↑ Marbach, Peter. "ARQ Protocols" (PDF). Retrieved August 24, 2013.

See also

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.