Sliding window protocols, pipelining & k-bit sequence numbers

1. In Stop-and-Wait ARQ with a = 4, what fraction of each cycle is the sender actually transmitting data?
   Stuck? Peek at 4.2.1 Stop-and-Wait ARQ, 1-bit sequence numbers & link utilisation

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

   Read lesson 4.2.1

2. What is the Bandwidth-Delay Product (BDP) of a link?
   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 many distinct values can a k-bit binary field represent?
   Stuck? Peek at 0.2.4 Exponents, logarithms and basic probability

   • 2ᵃ·2ᵇ = 2ᵃ⁺ᵇ; 2¹⁰ ≈ 10³ (estimates only).
   • log₂ x = power of 2 giving x; bits for N values = ⌈log₂ N⌉.
   • P(none) = (1−p)ⁿ · P(≥ 1) = 1 − (1−p)ⁿ · P(exactly 1) = n·p·(1−p)ⁿ⁻¹.
   • (1 − 1/n)ⁿ → 1/e ≈ 0.368; 1/(2e) ≈ 0.184.
   • 1 + 2 + … + 2ᵏ⁻¹ = 2ᵏ − 1; expected tries = 1/p.

   Read lesson 0.2.4

In Lesson 4.2.1, when Tt = 2 ms and 2·Tp = 18 ms (cycle = 20 ms), our sender transmitted for 2 ms and sat idle for 18 ms. Notice that 20 ms / 2 ms = 10 packets could have fit back-to-back inside that 20 ms cycle!

Pipelining lets the sender transmit up to N packets back-to-back without waiting for an ACK. A sliding window of size N tracks which packets are currently in flight and slides forward every time an ACK arrives.

In our example where 1 cycle is Tt + 2·Tp = 2 + 18 = 20 ms (so 1 + 2a = 10), what is the link utilisation if the sender window size is N = 5 packets? What if N = 10 packets? What if N = 15 packets?

• For N = 5: sender transmits for 5 × 2 = 10 ms out of every 20 ms cycle → η = 5/10 = 50%.
• For N = 10: the first ACK returns at t = 20 ms, right as the 10th packet finishes transmitting → η = 10/10 = 100%!
• For N = 15: the link is already 100% busy (utilisation can never exceed 100%) → η = min(1, 15/10) = 100%!

Pipelining & the Sliding Window Utilisation Formula

A sliding-window protocol allows the sender to have up to N (also written W_s) unacknowledged packets in flight simultaneously. In one cycle of duration Tt + 2·Tp, the sender can transmit N packets (taking N · Tt time):

Sender Window (Ws) and Receiver Window (Wr)

Both endpoints maintain a window over the sequence number space:

• Sender Window (W_s = N): The range of sequence numbers the sender has transmitted (or is allowed to transmit) that are not yet acknowledged. When the oldest packet in the window is ACKed, the window's left and right edges slide forward.
• Receiver Window (W_r): The range of sequence numbers the receiver is willing to accept and buffer:
  — If W_r = 1, the receiver accepts packets strictly in order (Go-Back-N, 4.2.3).
  — If W_r > 1, the receiver can buffer out-of-order packets until the missing gap arrives (Selective Repeat, 4.2.4).

k-bit Sequence Numbers & Wrap-Around Ambiguity

In a header, the sequence number field has a fixed width of k bits, so sequence numbers cycle modulo 2ᵏ: 0, 1, 2, …, 2ᵏ − 1, 0, 1, ….

Critical insight: Can a sender use a window of size Ws = 2ᵏ with k-bit sequence numbers? NO! As we prove in 4.2.3 and 4.2.4, to prevent wrap-around ambiguity between old retransmitted packets and new packets when ACKs are lost, every sliding-window protocol must obey the Fundamental Window Bound:

Putting it together

• Pipelining keeps up to N packets in flight at once, boosting link utilisation to η = min(1, N / (1 + 2a)).
• Full (100%) link utilisation is reached when the window size covers the entire round-trip pipe: N ≥ 1 + 2a.
• With k-bit sequence numbers (2ᵏ values), sender and receiver windows must satisfy W_s + W_r ≤ 2ᵏ.

• Utilisation cannot exceed 1 (100%)! If 1 + 2a = 5 and N = 8, utilisation is 1 (100%), NOT 8/5 = 160%! Always apply min(1, N/(1+2a)).
• k bits ≠ window size k! A k-bit sequence number field gives 2ᵏ sequence numbers (not k).

Fill the pipe of length (1 + 2a) with N packets: η = min(1, N / (1 + 2a)), and Ws + Wr ≤ 2ᵏ!

Now we have the general sliding-window framework. What happens when Packet #3 in the middle of a window of 8 packets gets lost? Next question (4.2.3): How does Go-Back-N (GBN) handle losses when the receiver refuses to buffer out-of-order packets (Wr = 1)?

1. NAT

   A link has ratio a = T_p / T_t = 7.5. What is the minimum sender window size N required to achieve 100% link utilisation?

   Write your answer before opening the key.

2. NAT

   On a link where 1 + 2a = 20, what is the link utilisation (in percent) when a sliding-window protocol uses a sender window of size N = 7?

   Write your answer before opening the key.

3. MCQ

   What is the universal relationship between sender window size W_s, receiver window size W_r, and a k-bit sequence number field to guarantee no sequence-number ambiguity?

   1. W_s + W_r ≤ k
   2. W_s + W_r ≤ 2ᵏ
   3. W_s × W_r ≤ 2ᵏ
   4. W_s + W_r ≤ 2ᵏ − 1
4. NAT

   A 4 Mbps link has one-way propagation delay T_p = 10 ms and sends 4000-bit frames. What is the link utilisation (in percent) if the sender window size is N = 25?

   Write your answer before opening the key.

• Sliding-window utilisation: η = min(1, N / (1 + 2a)); full utilisation at N = ⌈1 + 2a⌉.
• k-bit sequence space: 0 .. 2ᵏ − 1 (2ᵏ numbers); universal bound: Ws + Wr ≤ 2ᵏ.

• sliding window
• sender window Ws
• receiver window Wr
• k-bit sequence space 0..2ᵏ−1
• pipelining
• η = min(1, N/(1+2a))

1. Formula for sliding-window link utilisation with window size N?
   Reveal answer

   η = min(1, N / (1 + 2a)), where a = T_p / T_t.
2. Minimum window size N for 100% link utilisation?
   Reveal answer

   N = ⌈1 + 2a⌉ = ⌈(T_t + 2·T_p) / T_t⌉.
3. State the universal window bound connecting W_s, W_r, and k.
   Reveal answer

   W_s + W_r ≤ 2ᵏ.

• Universal Window Bound Ws + Wr ≤ 2ᵏ: Memorise this ONE inequality and plug in Wr = 1 for GBN (Ws ≤ 2ᵏ − 1) or Wr = Ws for SR (Ws ≤ 2ᵏ⁻¹)! — never mixing up the GBN and SR window size formulas.
• Target Utilisation Window Formula: To reach target efficiency η_target, minimum integer window is N = ⌈η_target × (1 + 2a)⌉. — GATE NAT questions asking for window size or bits for 50%, 80%, or 100% efficiency.