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. If the sender does not receive an acknowledgment before the timeout, it re-transmits the packet until it receives an acknowledgment or exceeds a predefined number of retransmissions.

Trivial File Transfer Protocol (TFTP) is a simple lockstep File Transfer Protocol which allows a client to get a file from or put a file onto a remote host. One of its primary uses is in the early stages of nodes booting from a local area network. TFTP has been used for this application because it is very simple to implement.

High-Level Data Link Control (HDLC) is a bit-oriented code-transparent synchronous data link layer protocol developed by the International Organization for Standardization (ISO). The standard for HDLC is ISO/IEC 13239:2002.

RTS/CTS is the optional mechanism used by the 802.11 wireless networking protocol to reduce frame collisions introduced by the hidden node problem. Originally the protocol fixed the exposed node problem as well, but modern RTS/CTS includes ACKs and does not solve the exposed node problem.

LAPB

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.

Stop-and-wait ARQ 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.

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. It provides a mechanism for the receiver to control the transmission speed, so that the receiving node is not overwhelmed with data from transmitting node. 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.

Transmission Control Protocol (TCP) uses a network congestion-avoidance algorithm that includes various aspects of an additive increase/multiplicative decrease (AIMD) scheme, along with other schemes including slow start and congestion window (CWND), to achieve congestion avoidance. The TCP congestion-avoidance algorithm is the primary basis for congestion control in the Internet. Per the end-to-end principle, congestion control is largely a function of internet hosts, not the network itself. There are several variations and versions of the algorithm implemented in protocol stacks of operating systems of computers that connect to the Internet.

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

Nagle's algorithm is a means of improving the efficiency of TCP/IP networks by reducing the number of packets that need to be sent over the network. It was defined by John Nagle while working for Ford Aerospace. It was published in 1984 as a Request for Comments (RFC) with title Congestion Control in IP/TCP Internetworks in RFC 896.

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.

Retransmission, essentially identical with automatic repeat request (ARQ), is the resending of packets which have been either damaged or lost. Retransmission is one of the basic mechanisms used by protocols operating over a packet switched computer network to provide reliable communication.

Binary Synchronous Communication is an IBM character-oriented, half-duplex link protocol, announced in 1967 after the introduction of System/360. It replaced the synchronous transmit-receive (STR) protocol used with second generation computers. The intent was that common link management rules could be used with three different character encodings for messages. Six-bit Transcode looked backwards to older systems; USASCII with 128 characters and EBCDIC with 256 characters looked forward. Transcode disappeared very quickly but the EBCDIC and USASCII dialects of Bisync continued in use.

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

In data networking, telecommunications, and computer buses, an acknowledgment (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. The negative-acknowledgment 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 technique and algorithm in computer networking. It aims to transfer data in a reliable way under unreliable data channel. It is consider one of most important networking topics.

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. Computer Networks (4th ed.). 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.