This post is based on the textbook Computer Networking: A Top-Down Approach (6th Edition) by James Kurose and Keith Ross.

1. What Is Reliable Data Transfer

The goal is to provide reliable transfer to upper layers even though the underlying channel (network layer) is unreliable.

Application layer: "My data will definitely arrive"
                 ^v Reliable channel (abstraction)
Transport layer (rdt): Implements protocol that guarantees reliability
                 ^v Unreliable channel (reality)
Network layer:    Packet loss and bit errors can occur

1.1 Interface

Sender side:
  rdt_send(data)     <- Upper layer delivers data
  udt_send(packet)   <- Send packet over unreliable channel

Receiver side:
  rdt_rcv(packet)    <- Receive packet from unreliable channel
  deliver_data(data) <- Deliver data to upper layer

2. Building the Protocol Step by Step

2.1 rdt 1.0: Reliable Transfer Over a Perfect Channel

Assumption: The underlying channel is perfect (no bit errors, no packet loss)

Sender FSM:
  [Wait] --rdt_send(data)-->
    packet = make_pkt(data)
    udt_send(packet)
  -->[Wait]

Receiver FSM:
  [Wait] --rdt_rcv(packet)-->
    data = extract(packet)
    deliver_data(data)
  -->[Wait]

No additional mechanisms are needed. In reality, such channels do not exist.

2.2 rdt 2.0: Channel with Bit Errors

Assumption: Bit errors possible, no packet loss

Required Mechanisms

1. Error detection: Discover bit errors via checksum
2. Feedback: Receiver informs sender of the result
   - ACK (Acknowledgment): "Received correctly"
   - NAK (Negative Acknowledgment): "Error occurred"
3. Retransmission: Retransmit packet upon receiving NAK

Such protocols are called ARQ (Automatic Repeat reQuest) protocols.

rdt 2.0 Operation

Sender:
  [Wait for data] --rdt_send(data)-->
    pkt = make_pkt(data, checksum)
    udt_send(pkt)
  -->[Wait for ACK/NAK]

  [Wait for ACK/NAK] --rdt_rcv(pkt) && isACK(pkt)-->
  -->[Wait for data]     (success, wait for next data)

  [Wait for ACK/NAK] --rdt_rcv(pkt) && isNAK(pkt)-->
    udt_send(pkt)     (retransmit)
  -->[Wait for ACK/NAK]

Receiver:
  [Wait] --rdt_rcv(pkt) && !corrupt(pkt)-->
    deliver_data(extract(pkt))
    udt_send(ACK)
  -->[Wait]

  [Wait] --rdt_rcv(pkt) && corrupt(pkt)-->
    udt_send(NAK)
  -->[Wait]

Fatal Flaw of rdt 2.0

What if the ACK/NAK itself has bit errors?

The sender cannot tell whether it received an ACK or NAK!

2.3 rdt 2.1: Introducing Sequence Numbers

Solution: Add a sequence number.

Resolution strategy:
  1. Retransmit the current packet when a corrupted ACK/NAK is received
  2. Receiver uses the sequence number to distinguish duplicates
  3. Since this is a stop-and-wait protocol,
     sequence numbers 0 and 1 are sufficient (1 bit)

rdt 2.1 Sender (simplified):

  [Wait seq=0] --rdt_send(data)-->
    pkt = make_pkt(0, data, checksum)
    udt_send(pkt)
  -->[Wait ACK for 0]

  [Wait ACK for 0]
    --ACK received, valid-->  [Wait seq=1]  (next data)
    --NAK received or corrupted--> retransmit pkt  [Wait ACK for 0]

  [Wait seq=1] ... (symmetric to seq=0)

rdt 2.1 Receiver (simplified):

  [Expect seq=0]
    --pkt valid, seq=0--> deliver, send ACK -> [Expect seq=1]
    --pkt valid, seq=1--> duplicate! send ACK -> [Expect seq=0] (ignore data)
    --pkt corrupted-->    send NAK             -> [Expect seq=0]

2.4 rdt 2.2: NAK-Free Protocol

Instead of NAK, send an ACK for the previous packet.

Key idea of rdt 2.2:
  Include sequence number in ACK: ACK(0), ACK(1)

  Receiver expects seq=1 but receives seq=0:
    -> Send ACK(0) (= "I received up to seq=0, but not seq=1 yet")
    -> From the sender's perspective, this has the same effect as a NAK

  Sender receives ACK(0) for seq=1 packet:
    -> "seq=1 did not arrive properly" -> retransmit

2.5 rdt 3.0: Bit Errors + Packet Loss

Assumption: Bit errors possible, packet loss also possible

Timer Mechanism

New problem: What if a packet completely disappears?
  - ACK will never arrive
  - Sender waits forever

Solution: Timer!
  - Start timer after sending a packet
  - If ACK does not arrive within a reasonable time, retransmit
  - What if the packet was just delayed, not lost?
    -> Duplicate packets occur -> handled by sequence numbers (already solved)

rdt 3.0 Scenarios

Scenario 1: No packet loss (normal)
  Sender        Receiver
   |--pkt(0)-->|
   |<--ACK(0)--|
   |--pkt(1)-->|
   |<--ACK(1)--|

Scenario 2: Packet loss
  Sender        Receiver
   |--pkt(0)-->  X (lost)
   |  Timer expires
   |--pkt(0)-->|  (retransmit)
   |<--ACK(0)--|

Scenario 3: ACK loss
  Sender        Receiver
   |--pkt(0)-->|
   |  ACK(0) X   (ACK lost)
   |  Timer expires
   |--pkt(0)-->|  (retransmit, duplicate)
   |<--ACK(0)--|  (receiver ignores duplicate)

Scenario 4: Premature timeout
  Sender        Receiver
   |--pkt(0)-->|
   |  Timer expires (ACK still in transit)
   |--pkt(0)-->|  (unnecessary retransmit)
   |<--ACK(0)--|  (original ACK arrives)
   |--pkt(1)-->|
   |<--ACK(0)--|  (ACK for duplicate pkt(0), ignored)
   |<--ACK(1)--|

3. Performance of Stop-and-Wait Protocol

rdt 3.0 works correctly but has very poor performance.

Example: 1 Gbps link, RTT = 30ms, packet size = 8000 bits

Transmission delay: L/R = 8000 / 10^9 = 0.008ms = 8us

Utilization:
  U = (L/R) / (RTT + L/R)
    = 0.008 / (30 + 0.008)
    = 0.00027
    = 0.027%

Actual throughput on 1 Gbps link:
  0.00027 * 1 Gbps = 267 kbps  <- Extremely inefficient!

Stop-and-wait timing diagram:

  Sender        Receiver
   |--pkt-->    |
   |            |
   |  (waiting) |
   |            |
   |     <--ACK-|
   |--pkt-->    |
   |            |
   ...

  Most time is wasted waiting for ACKs!

4. Pipelined Protocols

4.1 Pipelining Concept

Send multiple packets consecutively without waiting for ACKs.

Stop-and-wait:              Pipelining (window=3):

  |--pkt0-->|                |--pkt0-->|
  | wait    |                |--pkt1-->|
  |<--ACK---|                |--pkt2-->|
  |--pkt1-->|                |<--ACK0--|
  | wait    |                |--pkt3-->|
  |<--ACK---|                |<--ACK1--|
  |--pkt2-->|                |<--ACK2--|
                              ...

  Utilization improved 3x!

Consequences of Pipelining

Changes introduced by pipelining:
  1. Sequence number range increases (1 bit is not enough)
  2. Sender/receiver buffers needed (managing multiple packets)
  3. Error handling strategy must be decided:
     +-- Go-Back-N (GBN)
     +-- Selective Repeat (SR)

Utilization calculation (window size = W):

U = W * (L/R) / (RTT + L/R)

W=3 example:
  U = 3 * 0.008 / 30.008 = 0.0008 = 0.08%
  (3x improvement, but still low)

W=1000 example:
  U = 1000 * 0.008 / 30.008 = 0.267 = 26.7%
  (Much better!)

4.2 Go-Back-N (GBN)

Window Concept

Sender's sequence number space:

  [ACKed][Sent but unACKed][Usable][Not usable]
  --------|-----------------|---------|--------
         base           nextseqnum   base+N

  Window size = N
  base: Oldest unacknowledged packet
  nextseqnum: Next packet to send

GBN Sender Rules

GBN Sender:
  1. When upper layer requests data:
     - Send packet if window is not full
     - Refuse (or buffer) if window is full

  2. Timer management:
     - Single timer for the oldest unacknowledged packet
     - On timeout, retransmit ALL unacknowledged packets in the window

  3. On receiving ACK(n):
     - Confirms all packets up to n (cumulative ACK)
     - Update base = n + 1

GBN Receiver Rules

GBN Receiver (very simple):
  - Accept only packets with the expected sequence number
  - Discard all out-of-order packets
  - Send ACK for the last correctly received in-order packet

GBN Operation Example

Window size N=4, packet 2 is lost:

Sender                          Receiver
  |--pkt0-->|                    <- Received, send ACK(0)
  |--pkt1-->|                    <- Received, send ACK(1)
  |--pkt2-->  X (lost)
  |--pkt3-->|                    <- Out of order! Discard, resend ACK(1)
  |--pkt4-->|                    <- Out of order! Discard, resend ACK(1)
  |--pkt5-->|                    <- Out of order! Discard, resend ACK(1)
  |                              |
  | (Timer expires: retransmit from pkt2)
  |--pkt2-->|                    <- Received, send ACK(2)
  |--pkt3-->|                    <- Received, send ACK(3)
  |--pkt4-->|                    <- Received, send ACK(4)
  |--pkt5-->|                    <- Received, send ACK(5)

Disadvantage of GBN

A single packet error causes the entire window to be retransmitted (wasteful)
When error rates are high, the pipeline fills with unnecessary packets

4.3 Selective Repeat (SR)

Difference from GBN

GBN: Retransmit entire window on error
SR:  Selectively retransmit only the lost packet

SR Windows

Sender window:
  [ACK][ACK][unACKed][ACK][unACKed][Usable]
  ---------|----------------------|----------
          base                  base+N

  Individual timer maintained for each packet!

Receiver window:
  [Rcvd][Not rcvd][Rcvd][Not rcvd]
  ------|------------------------|
      base                   base+N

  Out-of-order packets are buffered!

SR Operation Example

Window size N=4, packet 2 is lost:

Sender                          Receiver
  |--pkt0-->|                    <- Received, send ACK(0), deliver
  |--pkt1-->|                    <- Received, send ACK(1), deliver
  |--pkt2-->  X (lost)
  |--pkt3-->|                    <- Received, send ACK(3), buffer
  |--pkt4-->|                    <- Received, send ACK(4), buffer
  |                              |
  | (pkt2 timer expires, retransmit pkt2 only)
  |--pkt2-->|                    <- Received, send ACK(2)
  |                              |  Deliver pkt2, pkt3, pkt4 in order to upper layer

SR Dilemma: Sequence Number Range

Relationship between window size and sequence number range:

  If the sequence number range is too small,
  new packets and retransmitted packets cannot be distinguished!

  Rule: Sequence number range >= 2 * window size
  (If window size is N, at least 2N sequence numbers are needed)

5. GBN vs Selective Repeat Comparison

Criterion	Go-Back-N	Selective Repeat
Retransmission scope	Entire window	Only the lost packet
Receiver buffer	Not needed	Needed (buffer out-of-order)
Timers	Single (oldest packet)	Per-packet individual timers
ACK method	Cumulative ACK	Individual ACK
Implementation	Simple	Complex
Efficiency (on error)	Low	High

6. Summary

Reliable data transfer mechanism evolution:

  rdt 1.0: Perfect channel -> Nothing needed
  rdt 2.0: + Bit errors -> Checksum + ACK/NAK
  rdt 2.1: + ACK/NAK errors -> Sequence numbers
  rdt 2.2: Remove NAK -> Use duplicate ACKs
  rdt 3.0: + Packet loss -> Timer

  Performance improvement:
  Stop-and-wait -> Pipelining (GBN or SR)

Key mechanisms summary:
  +-- Checksum: Detect bit errors
  +-- ACK: Confirm correct reception
  +-- Sequence numbers: Identify duplicate packets
  +-- Timer: Handle packet loss
  +-- Pipelining: Improve utilization

7. Review Questions

Q1. Why is a timer needed in rdt 3.0?

If a packet is completely lost, the receiver receives nothing and therefore sends no ACK. Without a timer, the sender would wait for an ACK forever. With a timer, the packet can be retransmitted when a reasonable amount of time passes without receiving an ACK. If the timer expires too early, unnecessary retransmissions occur, but the receiver can handle duplicates thanks to sequence numbers.

Q2. In Go-Back-N, why is the entire window retransmitted when a single packet is lost?

The GBN receiver only accepts packets with the expected sequence number and discards all out-of-order packets (no buffering). Therefore, when a middle packet is lost, all subsequent packets are also discarded. When the sender's timer expires, it must retransmit all packets from the oldest unacknowledged packet through the entire window.

Q3. Why must the sequence number range be at least twice the window size in Selective Repeat?

If the sequence number range is not large enough, the receiver cannot distinguish between new packets and retransmitted packets. For example, if the window size is 3 and sequence numbers are only 0, 1, 2, then when all ACKs are lost and the sender retransmits packet 0, the receiver might mistake it for a new packet 0. Having at least 2N sequence numbers prevents this confusion.