Reliable Data Transfer Protocols (RDT): The Reliability Guarantee that Keeps the Internet Running Smoothly

The Internet is a messy place connected by presumably unreliable infrastructure — but we make it work! How can an unreliable network provide a reliable communications platform? Reliable Data Transfer Protocols help make it happen and understanding their core functions is essential to understanding computer networks.

Image from Overcoded

Reliable data transfer protocols (RDT, RDP) are algorithmic measures to provide assurances of the reliable transfer of data across a network that may be subject to data loss and/or corruption. RDT involves sender-side and receiver-side sequences and variables to validate, acknowledge, and retransmit data when necessary.

The goal of RDT protocols is to provide network and link layer service such that application and transport layer services can make guarantees about data delivery.

Introduction

Reliable Data Transfer Protocols must address the two primary concerns of data loss and data corruption. In network communications, these types of errors generally occur on the physical network hardware during buffering, propagation, and transmission actions.

To address these concerns, senders and receivers need a way to communicate indirectly with respect to the receipt and validation of data being transmitted. In such cases where data has been lost or corrupted, RDT protocols dictate that data should be re-transmitted. At the most basic level, this introduces another concern of duplicate data into the mix.

Data loss and corruption are the two primary concerns RDT seeks to address. The concern of duplicate data only arises through actions taken to address these first two concerns. As such, considering the issues of loss and corruption is a sensible place to begin considering the underlying function of RDT.

Acknowledgment (ACK)

When a network system sends data to another network system, RDT suggests that some measures be taken to ensure that data arrived successfully. One basic approach to accomplish this is to incorporate a system of acknowledgment such that a receiver can inform the sender “yes, I received your message.”

How does one send such an acknowledgment though? The addition of an extra bit in the data segment being transmitted accomplishes just this. A receiver can send the sender a message, now with an

1

indicating positive acknowledgment (“message received, send next message”) or

0

indicating negative acknowledgment (“the last message was corrupt, please re-send.”)

Protocols such as Transmission Control Protocol (TCP) encapsulate data integrated with headers, with one header field being reserved specifically for these types of acknowledgments (ACKs). The ACK system informs a sender of data loss or corruption when a negative ACK (NAK) is received, or duplicate ACKs are received.

Timeouts

What happens is a receiver never receives a packet to ACK or NAK? Such could be the case resulting from packet loss across the network. In this scenario, a sender may be stuck waiting indefinitely for an ACK/NAK that will never come.

To mitigate this case, RDT requires the introduction of a sender-side timer variable. When a sender transmits a data segment it starts a timer. If the timer reaches a threshold before an ACK/NAK is received, the sender retransmits the data.

The addition of a timer variable helps deal with data loss but there’s still one very limiting factor: a sender is limited to sending one data segment, waiting on an ACK/NAK/timeout, and then sending or retransmitting another data segment.

To better utilize available network bandwidth there needs to be a system of sending multiple data segments while keeping track of which ones are received, corrupted, or lost along the way.

Sequence Numbers (SEQ)

As senders transmit data across the network, awaiting ACK feedback from receivers, there becomes another issue: how is a sender to know which data an ACK is referencing? For example, let’s say 3 data segments were transmitted and the sender received 2 ACKs and 1 NAK. Which segment would need to be retransmitted?

In a protocol limited to simple ACK/NAK there would be no way to no unless a sender was limited to sending a single data segment at a time. This approach was used in early network communications and is known as a stop-and-wait protocol. Certainly, stop-and-wait protocols are better than nothing but they can significantly limit network throughput when implemented haphazardly.

One approach to address this limiting factor is to introduce a new variable into the data segment: the sequence number (SEQ). This variable, now included as a 1-bit field in TCP headers, can allow a sender to transmit multiple segments and await ACKs for each.

One approach, known as alternating bit protocol, suggests the sender simply alternate between 0 and 1 for each segment transmitted across the network. The receiver will, in turn, respond with an ACK and a SEQ value or 0 or 1 indicating the last valid sequence received.

This acknowledgment system is known as an Automatic Repeat Request (ARQ). The sender is able to detect which packets need to be re-sent and automatically do so. The alternating bit protocol is a very simplified approach to ARQ that creates a more capable RDT system but has some serious limitations.

For example, if only two unique values for a SEQ number can be used, how can more than two segments ever be transmitted simultaneously? This concern broaches a topic known as pipelining by which RDT transmits multiple packets at a time, handles multiple ACKS, and retransmits in varying ways.

Pipelining

Pipelining is an ARQ protocol that allows for significant expansion of transmission rates. In modern protocols like TCP, the range of sequence numbers available are 232 (0 -4,294,967,295 unsigned integers). However, there are still several approaches as to how retransmission of corrupt or lost data segments should be handled.

Consider the following scenario: a sender transmits 5 packets labeled SEQ0-SEQ4 and awaits ACKs from the receiver. The receiver responds with an ACK for SEQ0, SEQ1, and SEQ4 indicating that SEQ2, and SEQ3 had issues. What should happen at this point?

One option would be to re-transmit only SEQ2 and SEQ3. Another option would be to retransmit the entire SEQ0-SEQ4 range. These approaches are characteristic for specific types of ARQ known as Go-Back-N and Selective Repeat. Each of these governs how sequences are accounted for and how/when data should be retransmitted.

Go-Back-N (GBN)

Go-Back-N is a sliding window protocol by which a sender maintains a window of packets that can be sent across the network. For example, if the sender has 30 total packets ranging in SEQ numbers from 0–29, a transmission window of size 5 may only include SEQ5-SEQ9 at a particular time.

To better understand the concept of the window as it’s used here, consider the boundary definitions:

1. The minimum value is SEQ number from the last sent packet having not been ACKs. This is called the base number.
2. The maximum value is the SEQ of the base + N for an n-sized window. In our example above, a window size of 5 would result in a maximum of base+5. This represents the SEQ number of the last packet authorized for transmission.

GBN protocol dictates that a sender should respond to 3 unique events:

1. Application data received from the above layer;
2. ACK received from the receiver;
3. Timeout event for a previously transmitted packet

The mechanics of GB are somewhat simple: a sender transmits a number of packets and waits on ACKs from the receiver. The ACKs include a SEQ number indicating the last packet received. As the sender receives ACKs, the base value (representing the window minimum) slides forward thus “authorizing” incremented SEQ numbered-segments.

On the receiver side, packets that are received out-of-order are simply discarded. This represents a significant waste of network resources in many cases. The main advantage of this approach is to eliminate the need of storing out-of-sequence packets in some form of receiver-side buffer. This reduces receiver-side resource usage and simplifies implementation.

For a better illustration of the dynamics of Go-Back-N consider this video from Neso Academy:

Selective Repeat (SR)

Selective repeat is similar to GBN but addresses the issue of redundant network transmissions. For example, where GBN receivers discard out-of-sequence packets and signal retransmission of entire sequence ranges, SR can request specific packets to be retransmitted.

This approach obvious benefits but comes with some drawbacks such as added complexity and resource consumption. One such added complexity is the necessity of the receiver to keep track and acknowledge, individual packets whether they are received in order or not.

This requires the buffering of out-of-sequence packets until such time packets with SEQ numbers prior to those are received.

Similarly to GBN, Selective Repeat dictates that a sender take action following these events:

1. Data received from the application layer above, instructing transmission is required;
2. Timeouts experienced for already transmitted packets;
3. ACK received for already transmitted packets

In general, SR is fairly complex — at least with respect to implications resource use, data loss, and transmission rates are concerned. To better illustrate SR, consider the following video from Neso Academy:

Discussion

Reliable data protocols support transport layer services necessary for many modern network communications. The use of acknowledgments, timers, sequence numbers, buffers, and clever algorithms all help ensure messages from senders arrive at receivers around the world.

The basics of RDT can be provided by so-called stop-and-wait approaches utilizing such designs as alternating bit protocols. While valid in concept; these approaches don’t address the need for robust throughput available on many modern networks. Go-back-N and Selective repeat offer solutions for these concerns, though still require a diligent implementation to ensure optimal performance within a given domain of network conditions/requirements.

The article Reliable Data Transfer Protocols (RDT) was originally published on the Overcoded website and has been re-published here with permission.