Principles of Reliable Data Transfer (RDT)

A reliable channel guarantees that data is delivered:

• Without corruption (no bit errors).
• Without loss (no missing packets).
• In order as it was sent.

This is challenging because the underlying network layer (IP) is unreliable, it can lose, corrupt, or reorder packets.

Reliable Data Transfer (RDT) protocols are designed to detect and recover from these errors and to provide the illusion of a perfectly reliable channel to upper-layer applications, even when the underlying network is unreliable.

This is a critical problem in networking, addressed by protocols like TCP.

How RDT Protocols are Designed

RDT protocols are typically developed incrementally, assuming that the lower layer is an unreliable point-to-point channel, then starting with simple assumptions to ensure reliability and adding mechanisms to handle more complex failures like loss, corruption missing order of packets.

The general framework involves two sides:

• Sender Side: Takes data from the upper layer and sends it as packets over the unreliable channel.

• Receiver Side: Receives packets and, after validating them, passes the correct data up to its application layer.

To achieve reliability, communication must be bidirectional. While data primarily flows from the sender to the receiver, essential control information (like acknowledgments or retransmission requests) flows from the receiver back to the sender.

This feedback loop allows the sender to detect and correct errors, ensuring the application sees a flawless connection.

Building a Reliable Data Transfer Protocol

To build a reliable data transfer (RDT) protocol step-by-step, we start with a simple case and incrementally add mechanisms to handle real-world network problems.

rdt1.0: Transfer Over a Perfectly Reliable Channel

• Assumption: The underlying channel is perfectly reliable, will never corrupt, reorder or loss packets.

• Mechanism: None needed. This protocol is extremely simple.

  • The sender simply takes data from the application, creates a packet, and sends it.

  • The receiver simply receives the packet, extracts the data, and passes it to its upper layer application.

No feedback or control information (acknowledgments) is required to be sent because nothing can go wrong.

Both sender and receiver are finite state machines with only a single state, no need to handle different conditions.

The protocol also assumes the receiver can always keep up with the sender, eliminating any need for flow control or back-pressure.

---

rdt2.0: Handling Bit Errors

• Assumption: The channel can corrupt packets through bit errors, but it will not lose them and delivered in order.

• ARQ (Automatic Repeat reQuest) protocols are used to recover from errors through re-transmission.

  1. Error Detection: A checksum is added to each packet so the receiver can detect bit errors.

  2. Receiver Feedback: The receiver sends control messages back to the sender:

     • ACK (Positive Acknowledgment): Sent if the packet is received correctly.

     • NAK (Negative Acknowledgment): Sent if the packet is corrupted.

This protocol uses a stop-and-wait method. The sender sends one packet, then waits for an ACK or NAK. If it receives a NAK, it retransmits the packet. It will not send a new piece of data until the current one is successfully acknowledged.

This handles bit error, prevents overload and maintains synchronization.

• The Flaw: This protocol assumes the ACK/NAK packets themselves can't be corrupted. If an ACK/NAK is corrupted, the sender won't know what to do next.

---

rdt3.0: Handling Packet Loss and Bit Errors

• The channel is a realistic one that can both corrupt and lose packets (both data packets and ACKs).

• This version builds on rdt2.0 (ACK/NAK feedback and Retransmission) by adding two key features to handle packet loss.

  1. Countdown Timer: The sender starts a timer after sending a packet. If the timer expires before a valid ACK is received, it assumes the packet or its ACK was lost or delay was too long and retransmits the packet. Timer is stopped If valid ACK is received.

  2. Sequence Numbers: Retransmissions can create duplicate packets. To handle this, packets are tagged with a sequence number (0 or 1). This allows the receiver to identify and discard any duplicate packets it receives.

This is also a stop-and-wait protocol, ensuring sender does not transmit a new packet until it is confirmed that the previous one was delivered successfully.

By combining checksums, ACKs, sequence numbers, and a timeout timer, rdt3.0 becomes a functionally complete, reliable data transfer protocol handling both corruption and loss of packet.

Pipelined Reliable Data Transfer Protocols

The stop-and-wait protocol (rdt3.0) ensures reliability but suffers from poor performance. The sender transmits a single packet and then sits idle while waiting for an acknowledgment (ACK), leading to very low channel utilization over high-bandwidth links.

• Link Bandwidth (R): 1 Gbps (109 bits/sec)

• Round-Trip Time (RTT): 30 ms (0.03 sec)

• Packet Size (L): 1 KB (8000 bits)

Time it takes to transmit the packet: Transmission Time: L/R ​= 8000 bits / 10^9 bits per sec ​= 0.008 ms

The sender utilization (the fraction of time it's busy sending) is:

Total time for one packet (RTT + transmission time): ≈ 30.008 ms

Utilization=L/R / RTT+L/R ​​≈0.00027

This means the 1 Gbps link is used only 0.027% of the time, resulting in a dismal effective throughput of about 267 kbps. The sender spends almost all its time waiting.

Pipelining

Pipelining is a technique that allows the sender to transmit multiple packets before receiving an acknowledgment for the first one. By having many "in-flight" packets, the sender can keep the channel busy, much like an assembly line, dramatically increasing throughput and efficiency. Making better use of available bandwidth.

Pipelining introduces new complexities as Design Implications:

• Expanded Sequence Numbers: A larger range of sequence numbers is needed to distinguish between all the in-transit packets.

• Buffering: The sender must buffer all unacknowledged packets for potential retransmission. The receiver may also need to buffer correctly-received but out-of-order packets.

Two main strategies are used to recover from errors in pipelined protocols:

1. Go-Back-N (GBN): A simpler approach where the sender retransmits all packets starting from the one that was lost or corrupted.

2. Selective Repeat (SR): Sender retransmits only the specific packets that were lost. A more efficient but complex approach.

Pipelined protocols significantly enhance performance and utilization compared to stop-and-wait, but they introduce additional complexity in terms of buffering, sequencing, and error recovery.