# Sliding window protocol, calculation of sequence number bits

I am preparing for my exams and was solving problems regarding Sliding Window Protocol and I came across these questions..

A 1000km long cable operates a 1MBPS. Propagation delay is 10 microsec/km. If frame size is 1kB, then how many bits are required for sequence number?

A) 3 B) 4 C) 5 D) 6

I got the ans as C option as follows,

propagation time is 10 microsec/km
so, for 1000 km it is 10*1000 microsec, ie 10 milisec
then RTT will be 20 milisec

in 10^3 milisec 8*10^6 bits
so, in 20 milisec X bits;

X = 20*(8*10^6)/10^3 = 160*10^3 bits

now, 1 frame is of size 1kB ie 8000 bits
so total number of frames will be 20. this will be a window size.

hence, to represent 20 frames uniquely we need 5 bits.


the ans was correct as per the answer key.. and then I came across this one..

Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts. The propagation time is 25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

What is the minimum number of bits (l) that will be required to represent the sequence numbers distinctly? Assume that no time gap needs to be given between transmission of two frames.

(A) l=2 (B) l=3 (C) l=4 (D) l=5

as per the earlier one I solved this one like follows,

propagation time is 25 ms
then RTT will be 50 ms

in 10^3 ms 10^6 bits
so, in 50 ms X bits;

X = 50*(10^6)/10^3 = 50*10^3 bits

now, 1 frame is of size 1kb ie 1000 bits
so total number of frames will be 50. this will be a window size.

hence, to represent 50 frames uniquely we need 6 bits.


and 6 is not even in the option. Answer key is using same solution but taking propagation time not RTT. and their answer is 5 bits. I am totally confused, which one is correct?

Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts.

When the data is transmitted using a duplex link, Round Trip Time (RTT) do not include the time taken by ACK frame to reach sender from the receiver. This is because the ACK frames are piggybacked with the data frames that are coming from the receiver for the sender (maybe a bit later).

Aforementioned, we must now calculate the number of frames transmitted during propagation time (rather than round trip time)

$No.\ of\ frames = \left(25*10^{-3}*10^{6}\right)/10^3 = 25$

Thus, we will need minimum of $5\ bits$ to represent sequence number distinctly.

HTH

• What is the piggybacking used here ? Receiver is not sending any data – Akhil Nadh PC Jan 19 '17 at 11:39
• See the Rtt Calculated Here [link]gateoverflow.in/43470/gate2009-58 – Akhil Nadh PC Jan 19 '17 at 11:40
• @AkhilNadhPC Alright. By any chance did you notice that the link you shared makes a similar argument about piggybacking right where RTT is calculated. To your first question, I want to point out that what the sender is sending is not of our interest. ACKs are piggybacked, thus we cannot be very certain about the time it will reach back to the sender. – Prateek Jan 19 '17 at 19:16
• Yeah, But see the Rtt calculated it is 52ms. – Akhil Nadh PC Jan 20 '17 at 3:14
• That's right. Because the question asks us to chose the closest time the sender has to wait. Under ideal circumstances, we got to assume that there is absolutely no delay in sending ACK from the other end. Keeping this in mind, we need to compute the time it will take for the packet (that contains the ACK) from the other end to reach back to the sender. – Prateek Jan 20 '17 at 10:05

Thing is, the link is full duplex so only half of the capacity can be used by the sender. Bandwidth in calculation will be (10^6)/2 bps. So answer will be 5 bits.

Ignore the key... Your answer is absolutely correct.

However, you have missed a small point in the procedure.

While calculating the window size, you must also consider the Transmission time.

Trans. time = 1000bits / 10^6 bps = 1ms.

Cycle time = 1ms +RTT = 51ms

01sec -> 10^6 bits

51msec -> 51*10^(-3) *10^6 bits = 51000bits = (51000/1000) frames = 51 frames

Sender window size is 51 frames. lets assume the receiver window size is 1 frame.

then, minimum number of bits required for sequence number =log(51+1)/(log2) {base 2} = 6 bits.

• Sequence numbers that wrap are neither signed or unsigned, but need a 'circular' compare. You will need an extra bit for that. If (A < B) then (B-A) will not have its high bit set. – Rob Apr 24 '15 at 22:46