Efficiency Analysis

We've thoroughly examined Go-Back-N's operational mechanics—its sliding window, cumulative ACKs, window constraints, and retransmission behavior. But understanding how a protocol works is incomplete without understanding how well it works. Efficiency analysis answers the quantitative questions that guide protocol selection.

The Fundamental Questions:

• What fraction of the channel capacity does GBN actually utilize?
• How does efficiency depend on window size, error rate, and propagation delay?
• When is GBN more efficient than Stop-and-Wait? Than Selective Repeat?
• How do we size the window for optimal throughput?

This page develops rigorous mathematical models for Go-Back-N efficiency, derives closed-form expressions, and provides practical guidance for applying these results to real network design problems.

Before deriving efficiency formulas, we must precisely define our terms and parameters.

Key Parameters:

Primary Metrics:

1. Utilization (U):

The fraction of time the sender is actually transmitting useful data:

U = (time spent transmitting useful frames) / (total time)

2. Throughput (S):

The effective data rate achieved:

S = U × R

3. Efficiency (η):

Often used synonymously with utilization. The ratio of useful data transmitted to channel capacity:

η = (bits of new data successfully delivered) / (total bits transmitted)

The Parameter 'a':

The ratio a = d·R / L = propagation delay / transmission time is crucial. It tells us how many frames could "fit" in the channel:

• a << 1: Propagation delay << transmission time; channel is "short" relative to frame duration
• a ≈ 1: Propagation delay ≈ transmission time; balanced
• a >> 1: Propagation delay >> transmission time; channel is "long" (satellite links, high-speed LANs)

Example Calculations:

Note: High-speed, long-distance links have very large 'a', making single-frame protocols extremely inefficient.

Let's first derive Go-Back-N efficiency assuming no frame loss or corruption. This establishes the upper bound on achievable efficiency.

Scenario Setup:

• Window size: N frames
• The sender can transmit up to N frames before needing an ACK
• ACKs arrive after RTT = 2d seconds from each frame's transmission

Case 1: Small Window (N < 2a + 1)

If the window is too small to fill the pipeline:

1. Sender transmits N frames, taking N × T_frame = N × L/R seconds
2. Sender must wait for ACK of first frame
3. ACK arrives after RTT from first frame's transmission start = 2d + T_frame from cycle start
4. Sender was idle for (2d + T_frame) - (N × T_frame) = 2d - (N-1) × T_frame seconds

Utilization (N < 2a + 1):

U = (N × T_frame) / (2d + T_frame)
  = N × (L/R) / (2d + L/R)
  = N / (2a + 1)

Case 2: Large Window (N ≥ 2a + 1)

If the window is large enough to keep the channel full:

1. By the time sender finishes transmitting N frames, ACKs start arriving
2. Sender is never idle—always has room to send the next frame
3. Channel is fully utilized

Utilization (N ≥ 2a + 1):

U = 1 (100%)

Comparison with Stop-and-Wait:

Stop-and-Wait is GBN with N = 1:

U_SW = 1 / (2a + 1)

For a = 100: U_SW = 1/201 ≈ 0.5%

With GBN and N = 201: U_GBN = 201/201 = 100%

The efficiency gain is dramatic for large 'a'.

In real networks, frames can be lost or corrupted. Go-Back-N's efficiency degrades due to retransmissions. Let's derive the efficiency formula accounting for errors.

Assumptions:

• P = probability of frame loss/error (independent per frame)
• ACKs are not lost (simplification; can be extended)
• Errors trigger retransmission of all outstanding frames

Analysis Approach:

Consider a transmission cycle:

1. Sender transmits a frame (call it frame k)
2. With probability (1-P), it succeeds
3. With probability P, it fails; sender must retransmit frame k and potentially subsequent frames

Expected Transmissions per Successful Frame:

Let E[T] = expected number of transmissions per successfully delivered frame.

Case 1: Frame k succeeds (probability 1-P):

Frame k is delivered in 1 transmission.

Case 2: Frame k fails (probability P):

Sender retransmits from frame k. If on average K frames are outstanding when error occurs, we retransmit K frames (including frame k). Each of these might fail again...

This gets complex. A standard approximation assumes that on average, (N-1)/2 other frames must be retransmitted with each failure.

Derivation of GBN Efficiency with Errors:

Using a more rigorous approach, the efficiency (or throughput normalized by capacity) is:

For N < 2a + 1:

η = (1 - P) × N / (2a + 1)
      × 1 / (1 + P(N - 1))

    = N(1 - P) / [(2a + 1)(1 - P + PN)]

For N ≥ 2a + 1:

η = (1 - P) / (1 - P + PN)
  = (1 - P) / (1 + P(N - 1))

The Master Formula (General Case):

       min(N, 2a+1) × (1 - P)
η = ────────────────────────────
    (2a + 1) × [1 + P(N - 1)]

Simplified for N ≥ 2a + 1:

       (1 - P)
η = ─────────────────
    1 + P(N - 1)

To understand when Go-Back-N is the right choice, we must compare it quantitatively with the alternatives.

Stop-and-Wait Efficiency:

η_SW = (1 - P) / (2a + 1)

S&W is simple but wastes the pipeline—efficiency drops as 1/(2a+1) even without errors.

Selective Repeat Efficiency:

For N ≥ 2a + 1:

η_SR = (1 - P)

SR achieves maximum efficiency (1 - P) because it only retransmits lost frames, not correct frames. The only efficiency loss is the lost frames themselves.

Comparison Table:

When Each Protocol Wins:

Stop-and-Wait is acceptable when:

• a is small (low latency, slow links)
• Simplicity is paramount
• Example: Local RS-232 connections, low-speed IoT links

Go-Back-N is best when:

• a is large (need pipelining for efficiency)
• P is small (low error rate, so retransmission overhead is rare)
• Receiver resources are limited (no buffering needed)
• Example: Satellite links with good signal quality, wired WANs

Selective Repeat is best when:

• P is significant (lossy wireless, congested networks)
• N is large (maximizing throughput matters)
• Receiver can afford buffering
• Example: WiFi, mobile networks, high-speed data centers

Let's apply the formulas to concrete scenarios—the type of problems that appear in networking exams and real design decisions.

Example 1: Satellite Link Efficiency

Given:

• Link rate: R = 10 Mbps
• One-way propagation delay: d = 270 ms (geostationary satellite)
• Frame size: L = 1000 bytes = 8000 bits
• Window size: N = 127 (7-bit sequence numbers)
• Frame error rate: P = 0.001

Calculate:

1. Parameter a:

a = d × R / L = 0.27 × 10^7 / 8000 = 337.5

2. Minimum window for full utilization (error-free):

N_min = 2a + 1 = 2(337.5) + 1 = 676

3. Error-free efficiency with N = 127:

U = N / (2a + 1) = 127 / 676 = 18.8%

4. Efficiency with P = 0.001:

η = N(1-P) / [(2a+1)(1 + P(N-1))]
  = 127(0.999) / [676(1 + 0.001 × 126)]
  = 126.87 / [676 × 1.126]
  = 126.87 / 761.2
  = 16.7%

Conclusion: Even with a large window, efficiency is only ~17% due to the extremely long propagation delay. Need N ≥ 676 for full error-free utilization.

Example 2: LAN Comparison

Given:

• Link rate: R = 1 Gbps
• One-way propagation delay: d = 5 μs (short LAN segment)
• Frame size: L = 1500 bytes = 12000 bits
• Window size: N = 7
• Compare efficiency at P = 0 and P = 0.01

Calculate:

1. Parameter a:

a = 5×10^-6 × 10^9 / 12000 = 5000 / 12000 = 0.417

2. Minimum window for full utilization:

N_min = 2a + 1 = 1.83 → 2 frames

3. Error-free efficiency (P = 0):

N = 7 > N_min = 2, so U = 1 (100%)

4. Efficiency with P = 0.01:

Since N ≥ 2a + 1:
η = (1 - P) / (1 + P(N-1))
  = 0.99 / (1 + 0.01 × 6)
  = 0.99 / 1.06
  = 93.4%

Comparison with Selective Repeat at P = 0.01:

η_SR = 1 - P = 0.99 = 99%

GBN vs SR difference: 99% - 93.4% = 5.6% throughput loss due to GBN's retransmission overhead.

Based on the efficiency analysis, here are practical guidelines for optimizing Go-Back-N performance.

Guideline 1: Size N Based on Bandwidth-Delay Product

For error-free full utilization:

N ≥ 2a + 1 = (2 × RTT × R / L) + 1

Round up to the next allowed value based on sequence number space.

Guideline 2: Consider Error Rate Impact

The product P × N determines efficiency loss:

• If P × N < 0.1: GBN efficiency is within ~10% of SR
• If P × N > 0.5: GBN efficiency significantly degraded; consider SR
• If P × N > 1.0: GBN is likely unacceptable; use SR or add FEC

Guideline 3: Balance Window Size

Larger N improves error-free efficiency but hurts error efficiency:

• Sweet spot: N slightly above 2a + 1
• Avoid making N much larger than necessary
• Sequence number overhead is wasted if N >> 2a + 1

This page culminates our Go-Back-N exploration with quantitative performance analysis. Let's consolidate the essential insights:

Module Complete:

You have now completed a comprehensive study of Go-Back-N ARQ. From its fundamental sliding window concept through cumulative acknowledgments, window size constraints, retransmission behavior, and efficiency analysis, you possess the deep understanding of this protocol that enables informed protocol selection, implementation, and optimization.

Go-Back-N represents a crucial point in the design space between simple Stop-and-Wait and sophisticated Selective Repeat. Its continued relevance in protocols like HDLC, and its conceptual influence on TCP, make this knowledge directly applicable to both legacy systems and modern networking.