Problem D It has been stated that the largest possible windo

Problem D. It has been stated that the largest possible window for go-back-N ARQ with N-bit sequence number field is W = 2N-1. Show by example that for N=3, W=8 does not work. Hint: Consider a case when all info-frames are lost, and then a case when all ACKs are lost.

Solution

If k=3 and window size=8, the

sequence number of frames can range from 0 to 7. Suppose there are frames

0 through 7 in the sliding window of the receiver:

01234567012345670123...

The sender sent out frames 0 through 7 and is waiting for the ACK for

frame 0. The receiver received these 8 frames successfully and sent back

an ACK 0. Then the sliding window of the receiver became:

0123456701234567012345670123...

The ACK is lost due to some reasons. The sender didn’t receive the

expected ACK before the time-out timer expires. The sender re-sends the

frames starting from 0. The receiver receives the re-sent frames. It

cannot distinguish whether these are expected frames or repeated frames,

so frame duplication happens.

If we limit the sliding window size to 7 the problem will not happen (see

below). The receiver is expecting frame 7. If it receives frame 0, it

knows for sure that the frame 0 is a repeated frame which needs to be

ignored.

01234567012345670123...

0123456701234567012345670123...