Stop-and-Wait ARQ, 1-bit sequence numbers & link utilisation

1. What is the difference between best-effort delivery and reliable delivery?
   Stuck? Peek at 4.1 Transport basics: process-to-process delivery, ports, sockets & multiplexing

   • Delivery: Network Layer = host-to-host; Transport Layer = process-to-process.
   • Port number = 16 bits (0–65,535): Well-known 0–1023, Registered 1024–49151, Ephemeral 49152–65535.
   • Demultiplexing: UDP uses 2-tuple (DstIP, DstPort); TCP uses 4-tuple (SrcIP, SrcPort, DstIP, DstPort).
   • UDP (Foundation) = 8-byte header, connectionless, best-effort; TCP = connection-oriented, reliable, flow + congestion controlled.

   Read lesson 4.1

2. From Lesson 1.3.3, what is the ratio a = T_p / T_t, and what is the utilisation of a send-and-wait cycle?
   Stuck? Peek at 1.3.3 RTT, bandwidth-delay product, utilisation and a = Tp/Tt

   • RTT = 2·T_p for tiny signals (add T_t / queuing if stated).
   • BDP = B × T_p bits in flight; B × RTT before any reply.
   • a = T_p / T_t.
   • Send-and-wait: U = T_t/(T_t + 2T_p) = 1/(1 + 2a); throughput = U·B.
   • To keep the link busy: about 1 + 2a units in flight.

   Read lesson 1.3.3

3. How does a receiver detect whether an arriving frame/packet suffered bit flips on the link?
   Stuck? Peek at 2.2.4 CRC: generator polynomial, modulo-2 division, what CRC catches

   • G of degree r (r + 1 bits); append r zeros, divide modulo 2, send data + r-bit remainder.
   • Receiver divides the whole frame: remainder 0 → accept.
   • Undetected ⇔ error pattern E is a multiple of G.
   • Catches: all single-bit errors (≥ 2 terms), all odd counts (x + 1 | G), all bursts ≤ r; (r+1)-bursts missed w.p. 2⁻⁽ʳ⁻¹⁾, longer 2⁻ʳ.

   Read lesson 2.2.4

In Lesson 1.3.3 we saw that sending one packet and waiting one round-trip time (RTT = 2·Tp) before sending the next has utilisation η = 1 / (1 + 2a). Now let's make that protocol reliable over a lossy network where packets and confirmations can vanish!

This protocol family is called ARQ (Automatic Repeat Request), and its simplest member — Stop-and-Wait ARQ — hides a famous subtle trap: why do we still need a 1-bit sequence number (0 and 1) when only one packet is in flight at a time?

Suppose Sender A sends Data Packet, Receiver B receives it cleanly and sends back an ACK (acknowledgement), but the ACK is lost on the way back! Sender A's timer expires, so A retransmits the exact same Data Packet. If packets have NO sequence numbers, what mistake will Receiver B make?

Receiver B cannot tell whether this arriving packet is a retransmission of the old packet (whose ACK was lost) or a brand-new second packet! B will hand a duplicate copy of the data to the application! Stamping alternating 1-bit sequence numbers (0, 1, 0, 1, …) solves this completely.

The Four Ingredients of Stop-and-Wait ARQ

Stop-and-Wait ARQ achieves reliable delivery over an unreliable channel using four mechanisms:

1. Error Detection (Checksum/CRC): Receiver silently discards (or sends a negative acknowledgement for) corrupted packets.
2. Positive Acknowledgement (ACK): When an uncorrupted packet arrives, the receiver sends an ACK back to the sender.
3. Timeout Timer & Retransmission: The sender starts a timer when transmitting a packet; if no ACK arrives before the timer expires, the sender retransmits the buffered packet.
4. 1-bit Sequence Numbers (0 and 1): Packets alternate Seq = 0 and Seq = 1 so the receiver can detect and discard duplicate packets caused by lost or delayed ACKs!

Utilisation (Efficiency) & Throughput of Stop-and-Wait

Let packet length be L bits, link bandwidth be B bit/s, one-way propagation delay be T_p, and transmission time be Tt = L / B. In every cycle, the sender spends T_t putting bits on the link and then waits RTT = 2·Tp for the ACK:

Delayed Duplicate ACKs & Why Alternating 0/1 Works

What if an ACK is not lost, just delayed past the timeout? If the receiver replies with ACK 0 (acknowledging Seq 0, or equivalently ACK 1 meaning "I next expect Seq 1"), the sender knows which packet the ACK belongs to and ignores a late duplicate ACK for an already-acknowledged packet.

Putting it together

• Stop-and-Wait ARQ adds ACKs, timeouts, retransmissions, and 1-bit sequence numbers (0, 1) to make send-and-wait reliable.
• The 1-bit sequence number is essential to prevent duplicate delivery when an ACK is lost.
• Because only 1 packet is sent per cycle T_t + 2·T_p, link utilisation is 1 / (1 + 2a), which is very poor when a = T_p / T_t is large.

• Forgetting the factor of 2 on T_p: The packet must travel forward (T_p) AND the ACK must travel back (T_p), so the wait is RTT = 2·Tp!
• Check if the question gives RTT or one-way T_p! If the question says "RTT = 20 ms", then 2·Tp = 20 ms already — do NOT multiply 20 ms by 2 again!
• Packet loss increases total transmissions: If frame loss probability is p, expected transmissions per packet is 1 / (1 − p), so effective utilisation becomes (1 − p) / (1 + 2a).

1 bit (0/1) catches twin packets when an ACK dies; Efficiency = Tₜ / (Tₜ + RTT) = 1 / (1 + 2a)!

Stop-and-Wait wasted 90% of our 10 Mbps link because the sender sat idle for 2·Tp waiting for one ACK. Next question (4.2.2): What if we allow the sender to keep up to N packets in flight at the same time before waiting for the first ACK?

1. NAT

   In a Stop-and-Wait ARQ system, the transmission time of a data frame is 2 ms and the round-trip propagation time (2·T_p) is 18 ms (ignore ACK size and processing delay). What is the link utilisation in percent?

   Write your answer before opening the key.

2. MCQ

   Why does Stop-and-Wait ARQ require a 1-bit sequence number (0 and 1) in each data frame?

   1. To allow the sender to transmit two frames before receiving an ACK.
   2. To allow the receiver to reorder frames that arrive out of order.
   3. To allow the receiver to distinguish a retransmitted duplicate frame (when an ACK was lost) from a new next frame.
   4. To calculate the round-trip propagation delay.
3. NAT

   A 1 Mbps link has a one-way propagation delay of 12 ms. Data frames are 1000 bits long, and ACK frames are negligible in size. What is the maximum throughput (in kbps) achievable using Stop-and-Wait ARQ?

   Write your answer before opening the key.

4. MSQ

   Which of the following changes will INCREASE the link utilisation η = 1 / (1 + 2·T_p / T_t) of a Stop-and-Wait protocol?

   1. Increasing the data frame length L (while keeping link rate B and distance d constant)
   2. Decreasing the physical link distance d
   3. Increasing the link data rate B (while keeping L and d constant)
   4. Increasing the signal propagation speed v on the medium

• Stop-and-Wait ARQ: 1 packet in flight; uses 1-bit sequence numbers (0, 1) to discard duplicates when ACKs are lost.
• Utilisation: η = Tt / (Tt + 2·Tp) = 1 / (1 + 2a), where a = Tp / Tt (with losses of prob p: (1 − p)/(1 + 2a)).
• Throughput: η × B = L / (Tt + 2·Tp).

• ARQ (Automatic Repeat Request)
• ACK (acknowledgement)
• timeout
• retransmission
• stop-and-wait ARQ
• η = 1/(1+2a)
• throughput = η·B
• 1-bit sequence numbers
• duplicate detection

1. Formula for Stop-and-Wait link utilisation η in terms of a = T_p / T_t?
   Reveal answer

   η = 1 / (1 + 2a) = T_t / (T_t + 2·T_p).
2. Why are 1-bit sequence numbers (0 and 1) needed in Stop-and-Wait?
   Reveal answer

   So the receiver can tell a retransmitted duplicate (after a lost ACK) apart from the next new packet.
3. What happens to Stop-and-Wait efficiency if link bandwidth B doubles while frame size L and distance d stay fixed?
   Reveal answer

   T_t halves, so a = T_p / T_t doubles and efficiency η = 1/(1+2a) DECREASES!
4. If each packet is lost independently with probability p, what is the expected number of transmissions per packet?
   Reveal answer

   1 / (1 − p).

• Direct Throughput Formula (skipping η): Throughput = Packet Bits L / Total Cycle Time (Tt + 2·Tp). — when a GATE NAT question asks directly for throughput in kbps or Mbps.
• Minimum sequence numbers for Stop-and-Wait: Always 2 sequence numbers (0 and 1 → 1 bit). — conceptual MCQs asking why 1 bit is needed.