ARQ Protocol Comparison: Stop-and-Wait, Go-Back-N, and Selective Repeat

Understanding concepts is necessary but not sufficient. True mastery requires the ability to apply formulas, perform calculations, and solve novel problems under exam conditions. This page provides structured practice with increasingly complex numerical problems.

Each problem section includes worked solutions with detailed step-by-step reasoning. Study not just the answer but the methodology—how parameters are extracted, which formulas apply, and how to verify reasonableness of results.

Before tackling problems, consolidate the key formulas you'll need:

These problems test fundamental formula application with minimal complexity.

Solution:

(a) Frame transmission time: $$t_f = \frac{L}{C} = \frac{1000 \times 8 \text{ bits}}{4 \times 10^6 \text{ bps}} = \frac{8000}{4,000,000} = 0.002 \text{ s} = 2 \text{ ms}$$

(b) Bandwidth-delay ratio: $$a = \frac{t_p}{t_f} = \frac{20 \text{ ms}}{2 \text{ ms}} = 10$$

(c) Stop-and-Wait efficiency: $$\eta_{SW} = \frac{1}{1 + 2a} = \frac{1}{1 + 20} = \frac{1}{21} \approx 0.0476 = 4.76%$$

(d) Throughput: $$S = \eta \times C = 0.0476 \times 4 \times 10^6 = 190,400 \text{ bps} = 190.4 \text{ Kbps}$$

Verification: Despite a 4 Mbps channel, we achieve only 190 Kbps—a 95% loss due to waiting for acknowledgments. This is characteristic of high-'a' scenarios with Stop-and-Wait.

Solution:

(a) Maximum window size for GBN: $$N_{max,GBN} = 2^k - 1 = 2^4 - 1 = 16 - 1 = 15$$

(b) Maximum window size for SR: $$N_{max,SR} = 2^{k-1} = 2^{4-1} = 2^3 = 8$$

(c) With window size N = 12:

• GBN: N = 12 ≤ 15 = N_{max,GBN} ✓ Yes, valid for GBN
• SR: N = 12 > 8 = N_{max,SR} ✗ No, violates SR constraint

With 4-bit sequence numbers and window size 12, only Go-Back-N can be used safely. Selective Repeat would risk frame ambiguity after wraparound.

Solution:

Step 1: Calculate frame transmission time $$t_f = \frac{L}{C} = \frac{2500 \times 8}{10 \times 10^6} = \frac{20,000}{10,000,000} = 0.002 \text{ s} = 2 \text{ ms}$$

Step 2: Calculate propagation delay from RTT $$t_p = \frac{RTT}{2} = \frac{500 \text{ ms}}{2} = 250 \text{ ms}$$

Step 3: Calculate 'a' $$a = \frac{t_p}{t_f} = \frac{250 \text{ ms}}{2 \text{ ms}} = 125$$

Step 4: Minimum window for 100% efficiency $$N_{min} = \lceil 1 + 2a \rceil = \lceil 1 + 250 \rceil = 251$$

Answer: Minimum window size is N = 251 frames.

Practical note: This requires at least 9-bit sequence numbers for GBN (2^9 - 1 = 511 ≥ 251) or 10-bit for SR (2^9 = 512 ≥ 502 = 2×251).

These problems require combining multiple concepts and formulas.

Solution:

Step 1: Calculate basic parameters

Frame transmission time: $$t_f = \frac{500 \times 8}{2 \times 10^6} = \frac{4000}{2,000,000} = 0.002 \text{ s} = 2 \text{ ms}$$

Propagation delay: $$t_p = \frac{d}{v} = \frac{600,000 \text{ m}}{2 \times 10^8 \text{ m/s}} = 0.003 \text{ s} = 3 \text{ ms}$$

Bandwidth-delay ratio: $$a = \frac{t_p}{t_f} = \frac{3}{2} = 1.5$$

Check window adequacy: $$1 + 2a = 1 + 3 = 4$$ $$N = 7 > 4 \quad \checkmark \text{ Window is sufficient}$$

Step 2: Calculate efficiencies (with p = 0.02)

(a) Stop-and-Wait: $$\eta_{SW} = \frac{1 - p}{1 + 2a} = \frac{1 - 0.02}{1 + 3} = \frac{0.98}{4} = 0.245 = 24.5%$$ $$S_{SW} = 0.245 \times 2 \times 10^6 = 490,000 \text{ bps} = 490 \text{ Kbps}$$

(b) Go-Back-N: $$\eta_{GBN} = \frac{1 - p}{1 + Np} = \frac{0.98}{1 + 7 \times 0.02} = \frac{0.98}{1.14} = 0.860 = 86.0%$$ $$S_{GBN} = 0.86 \times 2 \times 10^6 = 1,720,000 \text{ bps} = 1.72 \text{ Mbps}$$

(c) Selective Repeat: $$\eta_{SR} = 1 - p = 1 - 0.02 = 0.98 = 98%$$ $$S_{SR} = 0.98 \times 2 \times 10^6 = 1,960,000 \text{ bps} = 1.96 \text{ Mbps}$$

(d) Performance comparison:

Selective Repeat provides the best performance, achieving 4× the throughput of Stop-and-Wait and 14% better than Go-Back-N.

Solution:

Step 1: Calculate parameters

$$t_f = \frac{1250 \times 8}{100 \times 10^6} = \frac{10,000}{100,000,000} = 0.0001 \text{ s} = 0.1 \text{ ms}$$

$$t_p = \frac{1,000,000}{2 \times 10^8} = 0.005 \text{ s} = 5 \text{ ms}$$

$$a = \frac{5 \text{ ms}}{0.1 \text{ ms}} = 50$$

(a) Stop-and-Wait efficiency: $$\eta_{SW} = \frac{1}{1 + 2(50)} = \frac{1}{101} = 0.99%$$

No, Stop-and-Wait achieves less than 1% efficiency. It cannot meet the 90% target.

(b) Required window size for 90% efficiency:

For GBN/SR with N ≥ 1+2a, efficiency is 100% (error-free). We need N such that: $$\frac{N}{1 + 2a} \geq 0.90$$ $$\frac{N}{101} \geq 0.90$$ $$N \geq 90.9$$

Minimum window: N = 91 frames

To achieve full 100% efficiency: N ≥ 1 + 2(50) = 101 frames

(c) Sequence number bits for GBN:

With N = 91 (for 90% efficiency): $$2^k - 1 \geq 91$$ $$2^k \geq 92$$ $$k \geq \lceil \log_2(92) \rceil = \lceil 6.52 \rceil = 7$$

With N = 101 (for 100% efficiency): $$2^k - 1 \geq 101$$ $$2^k \geq 102$$ $$k \geq 7$$ (since 2^7 = 128 ≥ 102)

Answer: 7-bit sequence numbers (values 0-127, max window 127)

Solution:

(a) Original efficiency (p = 0.005): $$\eta_{GBN,good} = \frac{1 - 0.005}{1 + 15 \times 0.005} = \frac{0.995}{1.075} = 0.926 = 92.6%$$

This is close to 95% but not exact. The problem statement may have assumed the window is sufficient for 100% error-free efficiency, giving: η ≈ (1-p) = 99.5%. Using the exact GBN formula with errors: $$\eta = \frac{0.995}{1.075} ≈ 92.6%$$

(b) New efficiency during rain (p = 0.05): $$\eta_{GBN,rain} = \frac{1 - 0.05}{1 + 15 \times 0.05} = \frac{0.95}{1.75} = 0.543 = 54.3%$$

(c) Percentage reduction in throughput: $$\text{Reduction} = \frac{\eta_{good} - \eta_{rain}}{\eta_{good}} \times 100%$$ $$= \frac{92.6% - 54.3%}{92.6%} \times 100% = \frac{38.3}{92.6} \times 100% = 41.4%$$

Throughput drops by 41.4% due to rain.

(d) Selective Repeat efficiency during rain: $$\eta_{SR,rain} = 1 - p = 1 - 0.05 = 95%$$

Comparison:

Selective Repeat maintains near-full efficiency during adverse conditions, while Go-Back-N degrades significantly.

These problems integrate multiple concepts and require careful end-to-end analysis.

Solution:

Step 1: Basic parameters

$$t_f = \frac{1500 \times 8}{10^9} = \frac{12,000}{1,000,000,000} = 12 \text{ μs}$$

$$t_p = \frac{50,000}{2 \times 10^8} = 250 \text{ μs} = 0.25 \text{ ms}$$

$$a = \frac{250 \text{ μs}}{12 \text{ μs}} = 20.83$$

(a) Frame error rate from BER:

Bits per frame: 1500 × 8 = 12,000 bits

$$P(\text{frame error}) = 1 - P(\text{all bits correct})$$ $$= 1 - (1 - BER)^{12000} = 1 - (1 - 10^{-9})^{12000}$$

Using approximation (1-x)^n ≈ 1 - nx for small x: $$\approx 1 - (1 - 12000 \times 10^{-9}) = 12000 \times 10^{-9} = 1.2 \times 10^{-5}$$

Frame error rate p = 0.0012% ≈ 0

(b) Maximum window sizes (k = 3 bits):

$$N_{max,GBN} = 2^3 - 1 = 7$$ $$N_{max,SR} = 2^{3-1} = 4$$

(c) Check window adequacy: $$1 + 2a = 1 + 41.66 ≈ 42.66$$

Both N=7 (GBN) and N=4 (SR) are less than 42.66, so windows are insufficient!

Efficiencies (window-limited):

Stop-and-Wait: $$\eta_{SW} = \frac{1}{1 + 2(20.83)} = \frac{1}{42.66} = 2.34%$$

Go-Back-N (N=7): Given near-zero errors: $$\eta_{GBN} = \frac{7}{42.66} = 16.4%$$

Selective Repeat (N=4): Given near-zero errors: $$\eta_{SR} = \frac{4}{42.66} = 9.4%$$

Note: With these sequence number constraints, GBN outperforms SR because GBN allows larger window!

(d) Optimal protocol choice:

Given the 3-bit sequence number constraint:

• Go-Back-N is optimal with N=7, achieving 16.4% efficiency
• SR is limited to N=4, achieving only 9.4%
• The real problem is insufficient sequence number space

Better solution: Use more sequence number bits. With 6 bits:

• GBN: N=63 > 42.66 → 100% efficiency
• SR: N=32 < 42.66 → 75% efficiency

With 7 bits:

• GBN: N=127 → 100% efficiency
• SR: N=64 > 42.66 → 100% efficiency

(e) Throughput improvement:

With 3-bit sequence numbers: $$\frac{\eta_{GBN}}{\eta_{SW}} = \frac{16.4%}{2.34%} = 7× \text{ improvement}$$

With 7-bit sequence numbers (GBN or SR): $$\frac{100%}{2.34%} = 42.7× \text{ improvement}$$

Absolute throughput:

• SW: 0.0234 × 1 Gbps = 23.4 Mbps
• GBN (3-bit): 0.164 × 1 Gbps = 164 Mbps
• GBN/SR (7-bit): 1.0 × 1 Gbps = 1 Gbps

Solution:

(a) Maximum window from buffer constraint:

$$N_{max} = \frac{\text{Buffer size}}{\text{Frame size}} = \frac{1 \times 10^6 \text{ bytes}}{1000 \text{ bytes}} = 1000 \text{ frames}$$

(b) Check window sufficiency:

$$t_f = \frac{1000 \times 8}{20 \times 10^6} = \frac{8000}{20,000,000} = 0.4 \text{ ms}$$

$$t_p = \frac{RTT}{2} = \frac{600}{2} = 300 \text{ ms}$$

$$a = \frac{300}{0.4} = 750$$

$$1 + 2a = 1 + 1500 = 1501$$

N_{max} = 1000 < 1501, so window is NOT sufficient for 100% efficiency.

Window-limited efficiency (error-free): $$\eta = \frac{1000}{1501} = 66.6%$$

(c) Efficiency with errors (p = 0.01):

Go-Back-N: $$\eta_{GBN} = \frac{N(1-p)}{(1+2a)(1+Np)}$$ $$= \frac{1000 \times 0.99}{1501 \times (1 + 1000 \times 0.01)}$$ $$= \frac{990}{1501 \times 11} = \frac{990}{16,511} = 6.0%$$

Selective Repeat: $$\eta_{SR} = \frac{N(1-p)}{1+2a} = \frac{1000 \times 0.99}{1501} = \frac{990}{1501} = 66.0%$$

(d) Protocol recommendation:

Selective Repeat is mandatory. GBN's efficiency is devastated by the N×p factor (1000 × 0.01 = 10!). The 1% error rate combined with large window makes GBN lose 94% of channel capacity.

(e) Sequence number bits:

For SR with N = 1000: $$2N = 2000$$ $$2^k \geq 2000$$ $$k \geq \lceil \log_2(2000) \rceil = \lceil 10.97 \rceil = 11 \text{ bits}$$

11-bit sequence numbers required (0-2047, max SR window = 1024)

These problems simulate exam conditions with multiple parts and require efficient problem-solving.

Solution:

(a) Calculate 'a': [2 marks]

$$t_f = \frac{512 \times 8}{512 \times 1000} = \frac{4096}{512,000} = 8 \text{ ms}$$

$$a = \frac{t_p}{t_f} = \frac{40 \text{ ms}}{8 \text{ ms}} = 5$$

(b) Maximum window sizes: [2 marks]

$$N_{max,GBN} = 2^3 - 1 = 7$$ $$N_{max,SR} = 2^2 = 4$$

(c) GBN efficiency with N=7: [4 marks]

$$1 + 2a = 1 + 10 = 11$$ $$N = 7 < 11$$ (window insufficient)

Window-limited efficiency with errors: $$\eta_{GBN} = \frac{N(1-p)}{(1+2a)(1+Np)}$$ $$= \frac{7 \times 0.995}{11 \times (1 + 7 \times 0.005)}$$ $$= \frac{6.965}{11 \times 1.035} = \frac{6.965}{11.385} = 61.2%$$

(d) Effect of doubling bandwidth: [4 marks]

With C = 1024 Kbps: $$t_f = \frac{4096}{1,024,000} = 4 \text{ ms}$$ $$a = \frac{40}{4} = 10$$ $$1 + 2a = 21$$

GBN efficiency (still window-limited with N=7): $$\eta_{GBN} = \frac{7 \times 0.995}{21 \times 1.035} = \frac{6.965}{21.735} = 32.0%$$

Counter-intuitive result: Efficiency DECREASES from 61.2% to 32.0%!

Explanation: Higher bandwidth means shorter transmission time, larger 'a', and worse window limitation. The fixed window becomes even more inadequate.

(e) Sequence numbers for 95% SR efficiency: [3 marks]

For original link (a = 5):

Need N such that: $$\frac{N(1-p)}{1+2a} \geq 0.95$$ $$\frac{N \times 0.995}{11} \geq 0.95$$ $$N \geq \frac{0.95 \times 11}{0.995} = 10.5$$

So N ≥ 11 frames.

For SR: 2N ≤ 2^k, so: $$2 \times 11 = 22 \leq 2^k$$ $$k \geq 5$$ bits (2^5 = 32 ≥ 22)

5-bit sequence numbers required for 95% SR efficiency

Solution:

Common parameters: $$t_p = \frac{200,000}{2 \times 10^8} = 1 \text{ ms}$$ $$L = 1000 \times 8 = 8000 \text{ bits}$$

(a) Throughput calculations:

Option A (2 Mbps, p ≈ 0): $$t_f = \frac{8000}{2 \times 10^6} = 4 \text{ ms}$$ $$a = \frac{1}{4} = 0.25$$ $$1 + 2a = 1.5$$

With N ≥ 2 (easily achievable), efficiency = 100% $$S_A = 1.0 \times 2 \text{ Mbps} = 2 \text{ Mbps}$$

Option B (10 Mbps, p = 0.03): $$t_f = \frac{8000}{10 \times 10^6} = 0.8 \text{ ms}$$ $$a = \frac{1}{0.8} = 1.25$$ $$1 + 2a = 3.5$$

Using Selective Repeat with N ≥ 4: $$\eta_{SR} = 1 - p = 1 - 0.03 = 97%$$ $$S_B = 0.97 \times 10 \text{ Mbps} = 9.7 \text{ Mbps}$$

(b) Comparison:

Option B provides 4.85× better throughput despite 3% frame errors.

(c) At 10% error rate:

$$\eta_{SR,10%} = 1 - 0.10 = 90%$$ $$S_B = 0.90 \times 10 = 9 \text{ Mbps}$$

Option B still wins with 9 Mbps vs 2 Mbps (4.5× advantage).

The bandwidth advantage (5×) outweighs the efficiency loss. Option A would only become competitive if Option B's error rate exceeded 80%.

Learn from frequent errors to avoid them in your own solutions.

These problems are provided without solutions for self-assessment. Work through them independently, then verify your approach matches the methods demonstrated earlier.

This page has provided extensive practice with ARQ protocol calculations, from basic formula application to complex design scenarios:

Module Complete:

You have now completed the comprehensive study of ARQ Protocol Comparison. You understand:

• The operational differences between Stop-and-Wait, Go-Back-N, and Selective Repeat
• Quantitative efficiency analysis under various conditions
• Complexity tradeoffs that balance against efficiency gains
• Practical selection criteria for real-world scenarios
• Numerical problem-solving techniques for exam and professional contexts

This knowledge forms the foundation for understanding modern transport protocols (TCP, QUIC) and designing reliable communication systems across diverse network environments.