Principles of Reliable Data Transfer

• Reliable data transfer is one of the top problems in networking.
• The problem of implementing reliable data transfer occurs at not just the transport layer, but the link layer and application layer too.
• A reliable channel is one where no transferred data bits are corrupted or lost, and all are delivered in the order in which they were sent. This is the service offered by TCP.
• But while TCP may be a reliable data transfer protocol, it’s implemented on top of an unreliable (IP) end-to-end network layer.
  • So, TCP masks all network messiness so it looks like data is flowing through a clean, flawless, perfectly ordered pipe, when it’s actually very chaotic (packets frequently get lost, delayed, corrupted, etc).

Building a Reliable Data Transfer Protocol

Reliable Data Transfer over a Perfectly Reliable Channel (rdt1.0)

• Imagine a 100% perfect network channel – a fantasy scenario where packets are never lost, corrupted, delayed, or delivered out of order. Let’s call this imaginary protocol rdt1.0 (reliable data transfer 1.0).
• We can use a finite state machine (FSM) to map out the ‘brain’ of the protocol. In this case, one FSM for the sender and one FSM for the receiver.

• Here the green circles are the “states”. For the sender, its only state is “wait for the call from above” (i.e. wait for the app to give it data). For the receiver, its only state is “wait for the call from below” (i.e. wait for the network to hand it a packet).
• The arrow show the rules. They tell the system what to do when a specific event happens and what state to go to nextt.
  • Because rdt1.0 assumes the network never makes a mistake, the system never needs to change modes, which is why when a sender makes a packet and sends it the arrow loops right back to the same circle.
  • In other words, if you’re a sender in rdt1.0, you don’t need a “waiting for receipt” state or a “resending lost packet” state. You only need one single mode of waiting to send the next message.

Reliable Data Transfer over a Channel with Bit Errors (rdt2.0)

• A more realistic model is where bits in a packet get corrupted – so the receiver might get the packet, but the contents are scrambled gibberish.

Phone Call Analogy

• If you’re on the phone with someone and they read a long number for you, you might say ‘ok’ if you heard the number clearly or ‘please repeat that’ if you didn’t hear it clearly.
• Saying ‘ok’ is Positive Acknowledgement (ACK).
• Saying ‘please repeat that’ is Negative Acknowledgment (NAK) and the person would stop and repeat the exact same numbers again.

• In computer networking, protocols using the ‘please repeat that’ strategy mentioned in the phone call analogy are called ARQ (Automatic Repeat reQuest).
• To make this work, rtd2.0 uses three new features that the simple rdt1.0 didn’t need:
  1. Error Detection (checksums): a mathematical way for the receiver to realise the data is corrupted (as we saw with the UDP checksum).
  2. Receiver Feedback: the receiver must be able to send short messages back to the sender (ACK for OK, NAK for repeat).
  3. Retransmission: the sender must be ready to resend the exact same packet if it receives a NAK.

The Sender (Left Side)

• Because the sender now has to wait for receipts, it requires two states (the green circles) to keep track of what it is doing:
  1. State 1 (“Wait for call from above”): the sender rests here waiting for a new message from the application. When a message arrives, it attaches a checksum, sends the packet, and immediately moves to State 2.
  2. State 2 (“Wait for ACK or NAK”): this is a “lockdown” mode. The sender refuses to accept any new data from the application until the current packet is resolved. (This lockdown behaviour is called a stop-and-wait protocol)
     • If a NAK arrives (isNAK), the sender resends the exact same packet and stays in this lockdown circle
     • If an ACK arrives (isACK) the sender knows the packet arrived safely, so it follows the bottom arrow back to State 1 waiting for the next message. (The Λ symbol on the bottom arrow just means it doesn’t need to do any extra actions before moving back).

The Receiver (Right Side)

• The receiver still only needs one state because it just sits and reacts to whatever arrives.
  • If the packet is scrambled (corrupt), it creates a NAK message and fires it back to the sender.
  • If the packet is clean (notcorrupt), it extracts the data, hands it up to the application, and fires an ACK message back to the sender

---

• The fatal flaw in all of this is that the ACK and NAK messages themselves may get corrupted, so the sender has no idea if the receiver said “ok” or “repeat that”.
• There are three possibilities for handling corrupted ACKs or NAKs:
  1. Ask again: the sender could ask the receiver again for their NAK/ACK response. But if that response is continually garbled/corrupted then we end up in a loop we can’t get out of.
  2. Auto-correct: The sender can fix the broken method themselves, by getting the receiver to send more checksum bits for every ACK/NAK it sends. E.g. if you got a text saying “Yxs, I gxt thx pXcket!”, you’d be able to work out what it says even though several letters (bits) are corrupted. This is called Forward Error Correction (FEC).
  3. Resend original message: the sender could resend the original data message to get a new ACK/NAK response. But this introduces duplicate messages into the sender-to-receiver channel, and the receiver won’t know whether the ACK/NAK it last sent was received correctly. So it won’t know if an arriving packet contains new data or is a retransmission.
• One solution is to this third possibility is to add a new field to the data packet and have the sender assigning a number to each data packet it sends. That way the receiver knows if the packet they’re receiving is a retransmission. This is the idea behind the imaginary protocol rdt2.1:

• So, the rdt2.1 protocol (above) solves the flaw of rdt2.0 by introducing sequence numbers (to keep this simple, rdt2.1 only uses two sequence numbers – 0 and 1 – and the protocol alternates between them)
• We can see that both the sender and receiver now have twice as many states (the circles) because the protocol has to do two things that mirror each other (except for the number stamped on the packet):
  • Half handles sending/receiving Packet 0 (the top state for the sender and left state for the receiver)
  • The other half handles ending/receiving Packet 1 (the bottom state for the sender and right state for the receiver)

The Sender (Left Side)

• The sender moves through each state in a continuous loop:
  1. Send 0: it starts in the top-left (“wait for call 0”). It wraps the data in an envelope marked with a 0, sends it, and move to the top-right to wait for a receipt.
  2. Wait for receipt: if it gets a NAK (or if the receipt itself is corrupted) it spins in a loop, resending packet 0 to the receiver.
  3. Move to 1: once it gets a clean ACK, it drops down to the bottom-right (“wait for call 1”).
  4. Send 1: when the next message is ready, it puts it in an envelope marked with a 1, sends it, and moves to the bottom-left to wait for receipt. Once it gets a clean ACK, it loops all the way back to the start.

The Receiver (Right Side)

• The receiver has two states, effectively playing ping-pong between expecting a 0 and expecting a 1.
  1. Expecting 0 (left circle): it sits waiting for Packet 0. If a corrupted packet arrives, it sends a NAK and stays put. If a perfect Pack 0 arrives (has_seq0), it extracts the data, sends an ACK, and moves to the right circle.
  2. Expecting 1 (right circle): it now sits waiting for Packet 1. It does the exact same checks, and when a perfect Packet 1 arrives, it pings back to the left side.

• This also means that instead of having two different types of receipts (ACK and NAK), we don’t need to use NAKs at all.
  • If the receiver gets a corrupted packet, instead of saying ‘repeat that’ it can simply say “I successfully received packet 0”
  • If the sender is trying to send Packet 1 and receives a receipt saying “I successfully received packet 0” it realises they’re acknowledging the previous packet and that their latest packet must have been corrupted.
  • This double-receipt (Duplicate ACK) triggers the sender to resend the data without ever needing a NAK.

Reliable Data Transfer over a Lossy Channel with Bit Errors (rdt3.0)

• Let’s suppose the underlying channel doesn’t just corrupt bits but loses packets too.
• How do we detect packet loss? And what do we do when packet loss occurs?
• The second question can be answered using checksumming, sequence numbers, ACK packets, and retransmissions already discussed above.
• Handling the first question (detecting packet loss) requires adding a new protocol mechanism.

How do we detect packet loss?

• There are many approaches to dealing with packet loss. Here, we’ll put the burden of detecting and recovering from lost packets on the sender.
• Let’s say a sender transmits a data packet and that packet (or the receiver’s ACK of that packet) gets lost. In either case, no reply is going to come from the receiver to the sender.
• If the sender is willing to wait long enough so it can be certain the packet has been lost, it could just retransmit the data packet. But how long should the sender wait?
  • The sender must clearly wait for as long as a round-trip delay between the sender and receiver plus whatever time is needed to process the packet at a receiver. But the worst-case max delay here is hard to estimate and the protocol should recover from the packet loss as soon as possible.
• In practice, the sender waits for just about long enough that packet loss is likely to have happened (although not guaranteed).
  • If an ACK is not received within this time, the packet is retransmitted.
  • This does mean, however, that there could just be a large delay and nothing is actually lost, which introduces the possibility of duplicate data packets in the sender-to-receive channel. Happily, the duplicate ACK protocol above has enough functionality (that is, sequence numbers) to handle the case of duplicate packets.

---

• From the sender’s perspective, retransmission is the perfect solution (regardless of whether the data packet was lost, an ACK was lost or if the packet/ACK was overly delayed).
• All we need is (1) a countdown timer that starts each time a packet is sent, (2) be able to respond to a timer interrupt and (3) stop the timer.

• Because packet sequence numbers alternate between 0 and 1, protocol rdt3.0 is sometimes known as the alternating-bit protocol.

Pipelined Reliable Data Transfer Protocols

• Although rtd3.0 works, its main performance problem is that it’s a stop-and-wait protocol, which is practically useless in the real world – it’s incredibly slow because it wastes time waiting.

• The solution to this is pipelining.

• With pipelining, rather than operate in a stop-and-wait manner, the sender is allowed to send multiple packets without waiting for acknowledgement.
• Thus, if the sender can send three data packets without waiting for acknowledgment, the utilisation of the sender is essentially tripled.
• Pipelining has the following consequences for reliable data transfer protocols:
  1. The range of sequence numbers must be increased as there are more packets being sent and each needs a unique sequence number.
  2. The sender and receiver sides of the protocols may have to buffer more than one packet (i.e. temporarily store more data in the compute memory until processed, sent or delivered).
  3. The range of sequence numbers and buffering requirements will depend on the manner in which a data transfer protocol responds to lost, corrupted, and overly delayed packets. The two basic approaches towards pipelined error recover are discussed below: Go-Back-N and selective repeat.

Go-Back-N (GBN)

• In a Go-Back-N (GBN) protocol, the sender can send multiple packets without waiting for an acknowledgment, but can’t send more than a certain number (N) of unacknowledged packets into the pipeline.
• The name says exactly what it does: if a packet gets lost in the middle of a convoy, the sender must go back N steps and resend that lost packet, along with every single packet that was sent after it.

The ‘Strict Listener’ Analogy

• Imagine you are reading a sequence of numbered instructions to a very strict friend over the phone.
  1. You read instructions #1, #2, #3, #4, and #5 without pausing.
  2. Your friend hears #1 and #2 perfectly.
  3. Static scrambles instruction #3.
  4. Your friend still hears #4 and #5 perfectly.
• Because your friend is strict, they refuse to remember anything out of order. They completely ignore #4 and #5 and throw them in the trash. When your timer runs out because you never got a receipt for #3, you must go back and resend #3, #4, and #5 all over again.
• In GBN, the receiver is “dumb” and lazy – it buffers absolutely nothing if it arrives out of order. The sender does all the hard work of buffering the packets and resending the whole batch if one drops.

• If you send millions of packets before getting a receipt, a single lost packet would mean resending millions of packets, which would crash the network.
• To prevent this, GBN limits the sender to a maximum number of un-receipted packets in the air at once. This limit is called N (the window size).

• Imagine a massive row of packets lined up (as above):
  • Blue (Left of window): Packets you already sent and got receipts (ACKs) for. You are done with these.
  • Green (Inside window): Packets you just sent, but are still waiting for receipts for. (You must keep these buffered in memory just in case you have to go back and resend them).
  • Shaded (Inside window): Empty slots in your allowed quota. You are allowed to send these packets immediately if the app gives you data.
  • White (Right of window): Locked packets. You cannot send these yet because your window is full. If the application tries to send more data, the sender will reject it and tell the app to try again later.
• When the sender finally gets an ACK for the oldest green packet on the left side of the window, the entire window slides one slot to the right. This opens up a brand new white slot on the right side, allowing the sender to fire off the next packet in line. Because of this mechanical frame-shifting action, GBN is known as a sliding-window protocol

Selective Repeat (SR)

• Selective Repeat (SR) fixes the inefficiency of GBN by making the receiver smarter.
• Instead of throwing away perfectly good data just because it arrived out of order, the receiver keeps it. This means the sender only has to repeat the specific packets that actually got lost, rather than re-sending the entire convoy.

The ‘Smart Listener’ Analogy (again)

• Imagine reading five numbered instructions over the phone to a friend.
  • You read #1, #2, #3, #4, and #5 without pausing.
  • Your friend hears #1 and #2.
  • Static scrambles #3.
  • Your friend hears #4 and #5.
• In Go-Back-N, your strict friend threw away #4 and #5.
• In Selective Repeat, your friend writes #4 and #5 on a notepad and says, “I got 1, 2, 4, and 5. I am just missing 3.” When your timer for #3 runs out, you only repeat #3. You do not waste time repeating #4 and #5.

• To make this work, the protocol upgrades three main components:
  • Individual Receipts (ACKs): in GBN, an ACK for packet 5 meant “I have successfully received all packets up to5.” In SR, an ACK strictly means “I received this exact packet.”
  • Receiver Buffering: the receiver now has its own memory buffer. When packets arrive out of order, it stores them safely in its window until the missing pieces arrive to fill the gaps.
  • Individual Timers: The sender no longer relies on one master timer. It attaches a separate countdown timer to every single packet in the air. If a specific packet’s timer hits zero, only that packet is dropped back into the channel.