GATE CSE 2009 | Question: 57, ISRO2016-75

Question

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

What is the minimum number of bits $(I)$ 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. $I=2$
• B. $I=3$
• C. $I=4$
• D. $I=5$

Comments

Imagine the network as a pipe, the length of the pipe is the propagation delay, and diameter of pipe as the bandwidth.

At any time it can contain $\frac{10^{6} \text{ bits}}{\text{ sec}} \times \frac{25}{1000}\text{ sec} = 25,000 \text{ bits} \implies 25 \text{ frames}.$

Each of these $25$ frames must have different sequence number, so, we need $\lceil\log_{2} 25\rceil=5\;\text{bits}.$

---

Cool

---

GO to the Root of Concept: Video Explanation with timestamp: Efficiency,Throughput| Relation Between WindowSize & Sequence No. Sliding Window | With NOTES

Answer 1

Bandwidth won't be halved in full duplex.
http://superuser.com/questions/335979/does-1-gbit-s-port-in-full-duplex-mean-1-gbit-s-send-and-1-gbit-s-receive

Propagation time is given as $25\;\text{ms}$. 

Bandwidth $=10^6\;\text{bps}$. 

So, to fully utilize the channel, we must send $10^6$ bits into the channel in a second, which will be $1000$ frames per second as each frame is $1000$ bits.

Now, since the propagation time is $25\;\text{ms},$ to fully pack the link we need to send at least $1000\times 25\times 10^{-3}=25$ frames.

So, we need $\lceil\log_{2} 25\rceil=5\;\text{bits}.$

Correct Answer: $D$

Comments

@Arjun sir, why number of Frames to be transmitted into this link to maximally pack them in transit is not 26.

Time taken to transmit 1 frame =1ms. Then last bit of this first frame will propagate in 25ms. In these 25ms 25 more frames will be transmitted. So total frames transmitted into link when first packet was in transit = 26.

Why this is wrong?

---

@Ayushak let $t_0$ be start of transmission.

$t_0$  + 1 → 1st frame, $t_0$ + 2 → 2nd frame ... $t_0$ + 25 → 25th frame. Since, Propagation Time = 25 msec. Hence at 25 msec one-way link is fully packed!.

---

@Arjun Sir, Can we say that as they are asking “maximally pack them in transit”  is equivalent to channel capacity/ link capacity.

Channel Capacity = Bandwidth*Propagation Delay 
                 = 10^6 bps*25 msec dd
                 = 25*10^3 bits = 25*10^3/1000 frames = 25 frames

Hence maximum bits required for sequencing of 25 frames is 5 bits.

 

Answer 2

BW both the sides will be $10^6$​ ​bps for a full-duplex channel/wire/link.

We are actually only considering transit to one side while transmission of the packets to fully pack them in the link(106 bps). So, instead of the general approach of taking $1+2a$ packets, here we are taking $1+a$ packets since we are only considering the time of $1$ Tp, we need to keep the link full for $1$ Tp.

So, Min. no. of packets required $= 1 + a = 1 + \frac{25}{1} = 26$ packets.

Min. no. of bits required $= log_2​(26) = 5$ bits.

So, $5$ bits are enough to pack one side of the link while the frames are in transit.

---

Actually, both the hosts will send data packets and acknowledgments, but for both the sides, $5$ bits are enough individually to fully pack $10^6$​ bits from both the sides(full-duplex). Here, to keep things simple, I have only discussed considering one sender and one receiver only.  

For optimal case, when we also consider the time of the acknowledgment coming back, that time also packets can be kept on transmitting in the channel,

So, Min. no. of packets required $= 1 + 2a = 1 + 2*\frac{25}{1} = 51$ (doesn't matter if the ack. is piggybacked or not).

and Min. no. of bits req $= log_2​(51) = 6$ if we want this kind of link utilization.

Again, here also for simplicity, only considered one sender and one receiver.

But in reality both the hosts will act as source and destination simultaneously. Obviously, the acknowledgments will be piggybacked in such a practical case.

Answer 3

When the link is duplex do we have to take Bandwidth  = B/2 ?

My solution:

Comments

I have a doubt in your approach.Why did you half the given bandwidth?
As mentioned in solution why should we half the given bandwidth when it is duplex?

Thank you in advance.

---

No , in case of duplex link bandwidth won't be divided by 2

---

I have also taken the same approach But not sure about "When the link is duplex do we have to take Bandwidth  = B/2 ?"

Can anyone tell?

---

@Vikrant @Rishav Kumar Singhthis is correct as link is full duplex with rate 1mbps. Band width get divided between sender and receiver and each can transmit at rate 0.5mbps.

So here by 1+2a formula we get 5 bit sequence number use by sender only as we have takekn half Bandwidth Therefore max window size is 32 for sender  .  Similerly receiver also has max window size as 32.

Answer 4

Answer (D).

Given, propagation time =25 ms.

Time required to transmit 1 frame = 1000 bits (frame size)/ 10^6 bps(bandwidth) = 1 ms

To fully utilize the channel, we need to transmit frames for propagation time(25 ms), 25 frames.

therefore, minimum no. of bits required for numbering 25 frames is = log₂ (25) = 5 bits.

Comments

I just have 1 question if it would have not been given that the channel is duplex. Then

"To fully utilize the channel, we need to transmit frames for propagation time(25 ms)"

wil change to

"To fully utilize the channel, we need to transmit frames for round trip time which is 2*propagation time=(50ms) ??