Reliable Data Transfer Protocol (RDT/RDP) - αlphαrithms

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.

TL;DR: RDP guarantees reliable data delivery service across an unreliable channel. The most common implementation is TCP/IP protocol used for the majority of internet data transfer.

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.

Four Functions of Reliable Data Transfer

Implementing RDP as a transport layer service requires several moving parts amidst several checkpoints, so to speak. These “checkpoints” are points during data transmission where the following actions may occur:

receive data
encapsulate data prior to sending
un-encapsulate data upon receipt
send data

It’s important to note these four points of RDT function can be used to describe communications in either direction on a network. For example, from Host A sending a message to Host B:

1. Host A RDT receives data from layer above
2. Host A RDT encapsulates data
3. Host A RDT sends data to Host B
4. Host B RDT receives data from layer below
5. Host B RDT un-encapsulates data
6. Host B RDT passes data to layer above

By contrast, the same process would occur in reverse should Host B send a message to Host A (symmetrical process):

1. Host B RDT receives data from layer above
2. Host B RDT encapsulates data
3. Host B RDT sends data to Host A
4. Host A RDT receives data from layer below
5. Host A RDT un-encapsulates data
6. Host A RDT passes data to layer above

Features of Reliable Data Transfer Protocol

RDP/RDT utilizes several common features among varying implementations. These features help assure network engineers that the guarantees made by RDP/RDT standards are available and predictably available. Some of these features are basic while others involve much more technical complexity. Below are some of the most common features of RDP/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.

Congestion Control

Reliable Data Protocols operate in part by detecting degraded network conditions and acting accordingly. Timeout intervals help detect these types of conditions but don’t act to address them explicitly.

End-to-End: No explicit support is provided by the network layer; end systems must rely on inferred signals indicating congestion control such as packet loss or increasing RTT times.

Network Assisted: Network layer components such as routers provide direct feedback indicating current network conditions. This is usually implemented by direct link-to-end-system communication (choke packets) or by marking packet headers appropriately.

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 a 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 govern 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:

The minimum value is SEQ number from the last sent packet having not been ACKs. This is called the base number.
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:

Application data received from the above layer (Application process);
ACK received from the receiver;
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:

Data received from the application layer above, instructing transmission is required;
Timeouts experienced for already transmitted packets;
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:

Review

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.

Most modern programming languages like Java and Python offer standard networking libraries to help abstract away many of the technical details of reliable data protocols. These are incredibly useful and allow developers to focus on application-layer logic rather than mucking around with bitstreams.