Go-Back-N Protocol Explained: Sliding Windows, Worked Numericals and Exam Traps

Go-Back-N looks simple until sequence numbers wrap, ACKs become cumulative, and one lost frame causes correct frames to be sent again. Knowing only that its sender window is greater than 1 will not solve a trace or throughput numerical. A six-frame loss trace shows why correct frames are discarded, the sequence-space derivation explains the legal window limit, and the utilisation calculation exposes idle link time. Here, ACK k means “the next frame expected is k”. Some questions mean “frame k was received”, so translate their convention before calculating.

1. Go-Back-N ARQ: what the sender and receiver are allowed to do

Go-Back-N is a pipelined automatic repeat request protocol. Its sender can transmit several numbered frames before ACKs return. The textbook receiver window is 1: it accepts only the next expected frame and discards out-of-order frames.

Stop-and-Wait allows one outstanding frame. Selective Repeat buffers acceptable out-of-order frames and retransmits individual missing frames. The earlier Selective Repeat ARQ worked example owns per-frame timers, half-space window limits, and buffering after one loss. The Go-Back-N example deliberately keeps the same 3-bit, four-frame window so the changed behaviour is visible: one timer, cumulative ACKs, discarded out-of-order frames, and suffix retransmission. The GATE category is the preparation hub.

Use a 3-bit field, values 0,1,2,3,4,5,6,7, sender window W = 4, receiver window 1, base = 0, and nextseqnum = 0. ACK transmission and processing are negligible unless stated.

2. Sender window, cumulative ACKs and the one-timer model

base is the oldest unacknowledged sequence number. nextseqnum labels the next new frame. The sender can add data while fewer than W frames are outstanding. Moving base opens right-edge slots.

A cumulative ACK covers every earlier frame in sequence. In a loss-free run, the sender transmits 0,1,2,3. ACK1 moves base from 0 to 1 and permits frame 4. ACK2 moves it to 2 and permits frame 5. ACK4 covers frames 0 through 3 even if ACK3 never arrived.

3. Worked Go-Back-N trace: frame 2 is lost in a four-frame window

The sender transmits 0,1,2,3. The receiver accepts 0 and returns ACK1, then accepts 1 and returns ACK2. Frame 2 is lost. Frame 3 arrives while the receiver expects 2, so it is discarded and another ACK2 is sent.

When ACK1 and ACK2 open two slots, the sender sends frames 4 and 5. The receiver still expects 2, discards both, and repeats ACK2 after each. Duplicate ACKs do not move base beyond 2 in basic Go-Back-N.

The timer for oldest unacknowledged frame 2 expires. The outstanding set is 2,3,4,5, so all four are retransmitted. The receiver accepts them in order and returns ACK3, ACK4, ACK5, and ACK6. Cumulative ACK6 leaves nothing outstanding.

Six original transmissions plus four retransmissions equal 10 data-frame transmissions for six distinct delivered frames. Frames 3, 4, and 5 were not lost, but their first copies were discarded while frame 2 was missing.

4. Sequence-number bits, maximum window size and wrap-around safety

An m-bit sequence field has 2^m values. Textbook Go-Back-N requires:

W_s <= 2^m - 1

For m = 3, there are 8 values and the maximum sender window is 7. Our window of 4 is legal, but not maximum.

Why not use all values? Let m = 2, giving 0,1,2,3, and incorrectly set W = 4. If the receiver accepts all four, wraps to expecting 0, and every ACK is lost, the sender later retransmits old frame 0. The receiver cannot distinguish it from frame 0 of the new cycle and may deliver duplicate data. Limiting W to 3 preserves one separating value.

Take m = 3, W = 4, base = 6, and nextseqnum = 2. The outstanding frames are 6,7,0,1. ACK1 acknowledges 6,7,0, moves base to 1, and leaves frame 1. Draw the sequence-number ring, mark base, walk W positions clockwise, and translate the ACK convention. Integer comparison fails across a wrap.

5. Go-Back-N utilisation worked numerical: window 4 versus window 7

Assume data rate R = 2 Mbps, frame length L = 1000 bytes = 8000 bits, one-way propagation delay T_p = 20 ms, negligible ACK transmission and processing, no errors, and a continuously backlogged sender.

First calculate transmission time:

T_t = L/R = 8000/2,000,000 = 0.004 s = 4 ms

Therefore, a = T_p/T_t = 20/4 = 5. Ideal no-error utilisation is:

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

For W = 4, U = 4/(1 + 10) = 4/11 = 0.3636, or 36.36%. Throughput is 0.3636 x 2 = 0.7272 Mbps. Directly, 4 x 8000 = 32,000 bits per 4 + 40 = 44 ms cycle, and 32,000/0.044 = 727,272.7 bit/s, about 0.7273 Mbps. The displayed difference is rounding.

For legal maximum W = 7, U = 7/11 = 63.64%, giving about 1.2727 Mbps. Full utilisation needs W >= 1 + 2a = 11. Three bits allow at most 7, but four bits allow 2^4 - 1 = 15, so W = 11 can fill this idealised link.

Do not treat 1000 bytes as 1000 bits, use round-trip propagation as T_p and double it again, or reuse a no-error result after adding loss. Mbps is decimal here.

6. ACK loss, data corruption and exactly what a timeout retransmits

Losing one ACK does not always cause retransmission. If ACK3 is lost but ACK5 later arrives, ACK5 cumulatively acknowledges every frame through 4 and advances base directly to 5.

A damaged frame is treated as missing, so later out-of-order frames are discarded. A duplicate ACK repeats the same expectation and does not acknowledge the missing frame. When the base timer expires, the sender retransmits base and every later sent but unacknowledged frame, not the sequence space or only the missing frame.

In our trace, base = 2, so 2,3,4,5 are resent. Had valid ACK4 arrived first, base would become 4, leaving only 4 and 5 for a later timeout. Fast retransmit, selective ACKs, and receiver buffering apply only if a question explicitly adds them.

7. Common Go-Back-N exam patterns and traps

Common questions ask for the maximum window, frames in a wrapped window, cumulative ACK interpretation, retransmission counts, and ideal utilisation or throughput.

For m = 5, the sequence space is 32 and maximum GBN sender window is 31. With W = 10, base = 29, and nextseqnum = 3, outstanding frames are 29,30,31,0,1,2. Six slots are occupied and four are free. ACK1 covers 29,30,31,0, moves base to 1, and leaves 1,2.

Keep these corrections ready:

• Maximum GBN sender window is 2^m - 1, not 2^m.

• Textbook GBN does not give its receiver a Selective Repeat buffer.

• ACK k has no universal meaning. Read the stated convention.

• Never resend cumulatively acknowledged frames.

• Cap utilisation with min(1, ...).

• A count of practice questions does not prove exam weightage.

Drill these forms until the window arithmetic and the retransmission count are automatic. Continue with the Computer Networks MCQs collection.

8. Go-Back-N in one minute: the short version and next step

Retrieve these five facts:

• Sender window is greater than 1.

• Textbook receiver window is 1.

• A cumulative ACK moves base.

• A timeout resends the oldest unacknowledged frame and every later outstanding frame.

• With m bits, sender window is at most 2^m - 1.

Self-check by moving the main trace's loss from frame 2 to frame 4. With frames 0 through 5 and W = 4, frame 5 arrives while 4 is missing and is discarded. Timeout retransmits 4 and 5. The result is 6 original sends + 2 retransmissions = 8 data-frame transmissions, ending at ACK6.

For an exam-syllabus route, use GATE Guidance by Sanchit Sir. For a core-CS route, use ZERO TO HERO. Then solve the trace again without the answer.