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

Downvoting won't ace you rather explain question.

---

can someone plz explain the second part of the question..mainly in this part" no time gap needs to be given between transmission of two frames" .how it has been used in the question

---

Please explain me
Here they are not given the gbn or sr
then which one to consider..
And they ask for half duplex
How to approach for that

---

I think its similar to gbn protocol where they have mentioned window size which requires sequence no. ,but direct formula wont work here for gate questions.Here the catch is ACKs are always piggybacked which is given in the second part of the question.Now is Acks are piggybacked ,

Sender transmits one packet in 1 ms and receiver in 1 ms.Useful time = 2 ms

Total time from sending one packet from source to destination and back with piggybacked acks will take = 2 ms (total transmission time)+25 ms (sender to receiver propagation time)+25 ms (receiver to sender propagation time for Piggybacked Ack,which contains data as well as ack) = 52 ms

So,2 packets are sent in 52 ms timeframe from two sides,sender first packet reaches receiver in 26 ms after which receiver starts sending its data with ack of the sender added to it.By normal given book formula it is 52 packets we can pack,here its also same but both sender and receiver are packing 52 together 26 from sender,26 from receiver. Efficiency is also better here than normal case.

---

what is dulex mean here ?

what is the answer in both the cases

i used ceil of 1+2a .what is wrong with this approach ?

---

sushmita

why we are not considering 1+2a here directly ?pls explain 

---

Link for $2^{nd}$ part  -> https://gateoverflow.in/43470/gate2009-58

---

@set2018 duplex can be full duplex half duplex any of them but assume full duplex by default 

---

This question is purely wordplay! The most important words are transit and maximal. 

There's a night and day difference in the meaning of words - TRANSMIT and TRANSIT.

Informally Transit is - When you order a package from say China and destination is say Delhi the tracking shows - 

China - Shenzhen - Kolkata  . . . . . . . .  Delhi.

Currently your package is stuck at customs in Kolkata and not reached the destination Delhi (your home). So you can say your package is in transit or according to question your frame is in transit and not delivered to your home or receiver, but in this question we are sending many frames per second and to be precise, here 1000 frames are in transit per second or Sender should send 1000 frames per second to utilize the link fully and in question they are asking - 

Maximal (not maximum) frames should be in transit i.e the maximum frames should be on the way from Sender to Receiver or simply put before the first frame reaches the destination, how many frames sender can put on the link, that we need to find. 

That's why it's only one way (Tp i.e the time which is in the hands of the acting Sender to bombard the channel/link with as many packets he can send, but B/W is 10^6 bps and Sender can only send data in bundles of 1000 bits because frame size is 1000 bits. So, 10^6 divided by 1000 gives you 1000 frames per second, but sender has allocated a fixed time for this Transmission which is the Tp time of 25 millisecond.) and there's no concept of RTT because of word transit.

So, Sender can send 1000 frames per second. So in 25 seconds sender can send 25000 frames, but sender doesn't have 25 seconds, sender has 25 milliseconds. So Sender can only send for 25 milliseconds thus - 25000*10^-3 will give you 25 frames per millisecond and that makes sense because when you calculate Tt it's 1ms i.e Sender takes 1 ms to put one frame on the link and thus in 25ms it can put 25 frames, thus verified, things are fine! So SWS in transit maximally can hold 25 frames and thus log(25) ceil = 5 bits.

More information ---- When you take the word TRANSMIT AND TRANSIT AS SAME, which indeed is wrong!

The below SWS = 51 packets when the word mentioned is TRANSMIT or Transmitted.

The reason we are getting N (SWS) = 51 packets and then 6 bits for sequence # field is wrong because we are calculating MAXIMUM packets (TRANSMITTED TO R (not sure of being successfully transmitted because no ACK, but trasmit nonetheless from S to R AND NOT IN TRANSIT to R) that S can send which includes the RTT of 2*25ms = 50ms and then you say it's 1 + 50 = 51 packets, but those are MAXIMUM packets and not maximal and on top of that those packets are not in transit because at least one packet has reached the destination, processed and ACKED. Considering 1ms for piggybacking, that's something different.

My main intention was to tell "the words TRANSIT and MAXIMAL" even the link is full duplex restricts us to find max # of transmissions in only one side like a half duplex kind of!

---

 those packets are not in transit because at least one packet has reached the destination, processed and ACKED

brilliant answer by you.  really transit word  was playing a key role.

if nothing is mentioned about piggybacking in this question then we should not talk about it.

---

@iarnav sir it was really a brilliant explaination..

can you please also explain..that when we have to divide/ multiply the Bandwidth by 2, in cases of full or half duplex links

---

Thank you very much for this clarity.

---

I got the difference between transit and transmit but what is the difference between maximal and maximum in here....what would be the effect in answer if we have maximum in place of macimum?

---

Amazing answer, thank you. One question though, why do we need sequence numbers anyway? What purpose do they serve in this specific question.

---

@iarnav

not 51 frame only 50 

total frame = RTT/TT

50 ms /1 ms= 50 frame 

anyway thank you for sharing good information  

---

@mohan123

No, the SWS is equal to the no. of frames transmitted in Transmission Time + Round Trip Time.

---

It's 50 not 51

---

it will be 51 only , "1 packet is put into link even before(or at the same moment) the start of propagation time (because that packet only going to start propagation time countdown)"

---

@dr_Jackal 51 is max frame  send 

but in question mention pt=25ms ,  then rtt =50ms  

50*ms*10^6=50000bit 

frame size 1000 then 50000/1000=50  

 

refer this 

https://gateoverflow.in/1820/gate2006-44  

---

Because every millisecond one packet gets transmitted onto to link and propagation delay to B is 25ms so at any instant of time there can be 25 packets on the link between source and destination. 25 packets can be in transit at any instant of time. So we can maximally pack 25 packets and for that we need $log \left \lceil 25 \right \rceil$  bits  = 5 bits for sequence nuber.

---

@iarnav very nice explanation...

---

This is tagged normal😶😶

---

maximally pack them in transit is the key here.

---

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) ??