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

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

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]

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

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]

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]

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

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)

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)--|

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!

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

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

  Utilization improved 3x!

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)

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!)

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:
  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 (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

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)

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

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!

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

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)

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