Sliding Window Protocols for GATE

Sliding-window numericals often combine units, propagation delay, a window size, and sequence numbers in one paragraph. The core is smaller than it looks: compute a = Tp/Tt, use one utilization expression, and apply the correct window bound for the protocol.

Most wrong answers come from using round-trip delay where one-way delay belongs, or giving Go-Back-N and Selective Repeat the same sequence-number rule.

Stop-and-Wait efficiency

Stop-and-Wait sends one frame and waits for its acknowledgement before sending the next. If acknowledgement transmission time and processing time are negligible, one cycle takes:

Tt + 2Tp

The sender spends only Tt of that cycle transmitting useful frame bits. Therefore:

Efficiency = Tt / (Tt + 2Tp)
           = 1 / (1 + 2a), where a = Tp / Tt

Work a complete numerical. A 1 Mbps link spans 2000 km. Propagation speed is 2 x 10^8 m/s, and the frame size is 1000 bytes. Assume negligible ACK transmission and processing times.

First convert the frame to bits:

L = 1000 x 8 = 8000 bits

Transmission delay is:

Tt = L / B
   = 8000 / 10^6 seconds
   = 0.008 seconds
   = 8 ms

Distance is 2000 km = 2 x 10^6 m, so one-way propagation delay is:

Tp = d / v
   = (2 x 10^6) / (2 x 10^8) seconds
   = 0.01 seconds
   = 10 ms

Now:

a = Tp / Tt = 10 / 8 = 1.25

Efficiency = 1 / (1 + 2 x 1.25)
           = 1 / 3.5
           = 0.2857
           = 28.57%

A second check uses cycle time directly. The cycle is 8 + 2(10) = 28 ms, so useful fraction is 8/28 = 2/7 = 28.57%. Both methods agree.

Go-Back-N window and sequence-number bounds

Go-Back-N allows the sender to have up to N unacknowledged frames in flight. Under the same negligible-ACK assumptions, utilization is:

U = min(1, N / (1 + 2a))

For 100% utilization, the sender window must cover the complete send-and-return gap:

N >= 1 + 2a

Use the previous link, where a = 1.25:

N >= 1 + 2(1.25)
N >= 3.5

Window size counts whole frames, so the minimum is N = 4. Check it in the formula:

U = min(1, 4/3.5) = 1

Now find the minimum sequence field. With m sequence bits, Go-Back-N requires:

N <= 2^m - 1

For N = 4, two bits allow at most 2^2 - 1 = 3, which is insufficient. Three bits allow 2^3 - 1 = 7. Therefore the minimum is m = 3 bits.

The missing one sequence number separates outstanding old frames from the next cycle after numbering wraps. If the sender could use all 2^m values in its window, an old delayed acknowledgement could be mistaken for one belonging to a new frame with the same number.

Selective Repeat and the halved window

Selective Repeat accepts and buffers correct out-of-order frames. It retransmits only frames that are lost or damaged, but that receiver flexibility needs a stricter bound:

N <= 2^(m - 1)

Equivalently, the sequence-number space must be at least twice the window size. With m = 3, the safe Selective Repeat window is at most 2^(3 - 1) = 4.

Why half? After sequence numbers wrap, the receiver window must not overlap the set of numbers that might still represent delayed frames from the previous cycle. If the old and new receiver windows overlap, a delayed duplicate can look like a fresh frame. Splitting the sequence space into two non-overlapping windows removes that ambiguity.

Do not import the GBN bound here. GBN discards out-of-order frames and has receiver window size one, while Selective Repeat buffers a full receiver window.

What happens when one frame is lost?

Suppose a Go-Back-N sender has window N = 4 and sends frames F0, F1, F2, and F3. Let ACKk mean that the receiver next expects frame Fk.

• F0 arrives, so the receiver sends ACK1.

• F1 is lost.

• F2 and F3 arrive out of order. The GBN receiver discards them and repeats ACK1.

• The timer for F1 expires.

• The sender retransmits F1 and every later outstanding frame, so it sends F1, F2, and F3 again.

• After receiving the burst in order, the receiver can send cumulative ACK4.

With Stop-and-Wait, only the single outstanding frame can be retransmitted. With Selective Repeat, F2 and F3 may be buffered, so only lost F1 is retransmitted. This bandwidth saving is the practical difference behind the protocol names.

For the surrounding transport concepts and acknowledgement behaviour, revise TCP versus UDP. For mixed practice across layers, use the Computer Networks question set.

How GATE tests sliding windows

Questions ask for utilization, minimum window, minimum sequence bits, throughput, or retransmissions after a loss. Use a small data sheet before substituting:

• Convert bytes to bits before using link rate in bits per second.

• Compute Tp from one-way distance. The formula already contains 2Tp.

• Distinguish frame transmission time from propagation time.

• Include ACK transmission or processing time only when the question supplies it or says it is not negligible.

• Take a ceiling when the required window is fractional.

• Apply 2^m - 1 to GBN and 2^(m-1) to Selective Repeat.

Confirm current syllabus and paper instructions on the official GATE portal of the organising IIT. Use the GATE CS preparation category for the wider networking study path.

The short version

Compute Tt = L/B, Tp = d/v, and a = Tp/Tt. Stop-and-Wait gives 1/(1+2a). A window N gives up to N/(1+2a), capped at 1. For sequence numbers, GBN needs N <= 2^m - 1, while Selective Repeat needs N <= 2^(m-1).

Rework the numerical once without notes, then use the GATE Test Series for timed utilization and retransmission problems. Keep units and protocol bounds on separate lines.