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 tt.t for ack 1 ms? dnt make sense...

t.t. for ack is very lees than t.t. for data..so we have to ignored it...so ans will be..25+25+1=51-32=19

---

Given in question ACK is piggy backed. So, even if ACK is very small, we need to count the transmission time of the frame on which ACK is piggy backed.

---

Why have we calculated only for one direction . Because when the very first frame reaches destination source would have already transmitted 25 more frames.Now when destination sends ACK for that very first frame,it would also take 25ms to reach the source and During this span it again would have transmitted 25 more frames. So total frames that source can transmit UNTIL the ACK for first frame comes back is 51 which needs 6 bits. But not in options.

Where m I missing ??

Please explain.

What does full duplex has to do with it ?? Since RTT wouls still remain 50ms for a packet ??

Thank You

---

I have the same doubt as Sandeep .To fully pack link we should send 1+2*(Tp/tt) frames ,which will be 51
and which will give 6 sequence bits

---

Question says "Frames are to be transmitted into this link to maximally pack them in transit".

So, while transmitting only we need to ensure full packing. After "n" frames are sent (n = 25 here), there will be a waiting time and that is asked in Qn. 58.

In the optimal case, we need n = 52 and hence 6 bits and that can ensure no waiting time. (time for ACK to reach back is 52 and not 51 as ACK is piggybacked and hence we need to add propagation time for a frame in place of propagation time for ACK)

---

Thanx @Arjun: That is the terms "Maximally pack in transit= fill the pipeline as long as our first frame takes to reach destination"  that I could not understand. Did I translate it correctly now ??

But you dint answer my second question.What does FULL duplex has to do here ?? Nothing !! I dont understand how does full duplex affects the answer, if not in this question then some other problems where it is given many a times.

Please explain to me how does it affect Transmission time, RTT, utilization and other things IF POSSIBLY IT DOES  SO ..

---

Yes. That translation is correct as per me. I mean my logic tells me to interpret the question that way.

Here ACKs are piggybacked meaning they will be appended on back of a frame. So, while this piggybacked frame is being sent to the original sender can the sender also send a frame? Yes, because the medium is full duplex. This is the use of full duplex.

---

some where given  as following

time  taken  to send 10^6 bits  = 1 second

so, time  taken  to  send 2^5 frames = 32 m second

(1 frame  = 1000 bits  )

time taken  for the first frame to be acknowledged = 25*2=50 ms.

then  waiting time =50 - 32 18 ms.

i don't  knew , this is right or wrong , can you tell me ,what  is  the  flaw of this approach  ???

---

Transmission time not considered..

---

This is awesome Question ! So many concepts in 1 question !

---

http://cs.stackexchange.com/questions/21324/sliding-window-protocol-calculation-of-sequence-number-bits

---

Please explain why we are taking 1000*25ms?...I got your point of sending 1000 frames

---

@ arjun sir, had it been mentioned in the question that acks are not piggybacked but link is half duplex only, we will consider transit time as Tt+Tp ot Tt+2Tp. Can we send data when ack is coming in reverse direction in half duplex link??

---

Tt + 2Tp

---

I suppose an easy argument for this question would be

Transmission Time= 1ms

Propagation Delay= 25ms

So to fully utilize the channel frames must be transmitted in Propagation Delay. So no of frames that can be transmitted = 25/1= 25 so bits required will be 5.

---

sorry sir for asking again but i am a bit confused.

"Frames are to be transmitted into this link to maximally pack them in transit"---- is this statement the only reason for taking tp time for transmission? otherwise we would have considered the full capacity right 1+2a???

---

@sushmita I do not know what is 1+2a, I intentionally never studied that formula, because there is no use in GATE- you must know to derive it. Try deriving it here.

---

Efficiency= (T_t × Window size) / ( T_t + 2P_t)

Dividing by T_t we get W/(1+2(P_t/T_t)) = W/(1+2a). @Arjun sur what is wrong in this formula??? 

---

@Rahul The formula is correct but under what conditions? I need not know because I did not study it.

In the formula, in the denominator the term corresponds to the time ACK reaches back. And this neglects the transmission time for ACK as it is quite often zero. But in this question (actually second part, given here it says ACKs are piggybacked. Piggybacked means they are attached behing data packets which means transmission time of the packet gets added as the effective transmission time of the ACK. Even otherwise for somereason ACKs are big and their transmission time is not negligible we should add it. The professor who made this question intentionally wanted 0 or negative mark for all those who studied the formula without understanding the concept. That is how most GATE questions are made.

---

@Arjun sir, I think defination of piggybacking is different. But anyway log₂ 25 or 26 gives same answer.

https://en.m.wikipedia.org/wiki/Piggybacking_(data_transmission)

---

Definition of piggybacking is the one given on wikipedia and I did not contradict it. But when that happens, we have to add the transmission time of packet as effective ACK transmission time. This was required for the part 2 of this question.

---

Thanks for clearifying☺

---

in Tt time we can transmit 1 frame

thus, in Tt+2Tp time, we can transmit=(Tt+2Tp)/Tt frames.

Tt/Tp =a

Therefore Number of frames we can trasnmit=1+2a.

Here we have  considered transmission time of ack as negligible.

But sir, when piggybacking will be used we will consider the transmission time of ACK too and if the link if full duplex we can fully utilize the channel right?? I mean sender can keep on transmitting packets in total of

Tt(Data Frame)+Tp+Tt(ACK)+Tp time.

This is what i understand about full duplex and piggybcking. Plz tell me sir where i am wrong. :(

---

Arjun sir, please check my comment and guide me where i am going wrong. And one more thing sir even though i understand fully that we should consider the transmission time of ACK when they are piggybacked why here we have considered onky Tt+Tp time just beacause of this line="TO MAXIMALLY PACK THEM IN TRANSIT" or any other reason too??

---

when piggybacking will be used we will consider the transmission time of ACK

No, in any case we always include transmission time of ACK- though it usually becomes 0 (if its size is not given take as 0).

What happens in piggybacking is ACK is attached behind the data frame. So, transmission time of ACK becomes transmission time of data frame. This is the catch here.

All the above assumes full duplex- for half duplex, to calculate anything, we would need to know how the senders and receivers synchronize for communication. This is never going to be asked in GATE, as currently full duplex is the standard and making such a question also will be extremely hard.

---

And for the given question

"maximally pack in transit"

This I took as when the first frame reaches destination, someother frame is being transmitted by sender (the medium is fully loaded). Not exactly same as 100% efficiency as in that case, the sender should be sending when the ACK arrives. So, for the given question ACK is irrelevant.

---

Thanku sir, just one question is this line was not there maximally pack in transit, we should have gone with 100% efficiency case then right??

---

If that was not there, something else would have been there :) GATE won't be having ambiguity like mock tests except if some mistakes happen. In the exam hall seeing "maximally transit" for the first time, it is really difficult to get the answer. Fortunately at least for this question (not the second part) even if we assume efficiency answer comes same.

---

yes sir, for the first time really difficult. Thanx sir for clarifying everything :).

Thats the advantage of having options but with numerical type- things have become harder. :(

---

Not really.  Actually choices make the question harder in exams like GATE :)

---

Thanks :)

---

Once the packet is sent, it will take 25 ms for the last bit of that packet to reach destination. ACK will take 25 ms to reach back. Assuming ack is of negligible length, between the last bit of packet and the ack packet we have a total of 50 ms time. Why can't we fill all that 50 ms with packets (each taking 1ms for transmission), making a total of 50 packets stuffed during that time period (instead of 25)?

---

@Arjun Sir what would be the window size in this case? because window size is number of frames in 1 RTT, so would it be 25 or 50 ?

---

Is this approach correct?:

Transmission time = $1000/10^6 = 1 msec$
Since we have to maximally pack the transit, we modify the formula for utilization a bit as:

$1 = (N \times 1)/(1 + 25)$ (25 because we need not care for the ACK's propagation time)
Here $N$ is the window size.
$\rightarrow N = 26$
$\rightarrow 2^n - 1 = 26 \rightarrow n = \left \lceil log_2{27} \right \rceil = 5$

---

@just_bhavana

"Window size is the number of frames in 1 RTT" is wrong. When we need 100% efficiency then window size is the number of frames in 1 RTT and here it is not the case where we need 100% efficiency.

---

@Arjun.. Nowhere in the question it is given that acknowledgment is piggybacked

---

@Arjun Sir, RTT as calculated by you is 52 in this case and we want to maximally pack the channel. So why dont we consider sending frames for 52 unit of time, why only 25? Please explain

---

@ Hemant Parihar Doesn't "maximally pack the packets" and 100% efficiency mean the same???  RTT in this example is 52. Why we are considering during propagation time of data from sender only.. Sender can send frames even after receiver starts sending acknowlegement. Why are not considering that time, when we have to maximally pack the frames.. Kindly explain 

---

Can we send data when ack is coming in reverse direction in half duplex link?

 @sushmita Do not you think if this will happen then it will become full duplex link ?

---

Can anyone guide me where am I heading wrong?

---

Becoz transmission is possible from a to b and b to a also so  sir capacity of full duplex =2*propogation delay * bandwidth =2*25*(10^-3)*10^6 i.e = 50*10^3= 50 frames for identifying log(50)base 2 = 6 bits are required.

Please correct me if i am wrong

---

@sushmita the derivation of that formula is like

in Tt sec -> 1 pkt is transmitted, then in 1 sec -> 1/Tt packet is transmitted

Now as Arjun sir said Ack will be piggybacked, here the general formula is

Optimal win size = (Tt + RTT) * 1/ Tt (Packets per second * seconds gives total packets)

Now as sir said Tp will not be considered as they are piggybacked but now the Tt will be considered from receiver. so it becomes

optimal win size= (Tt(during sending) + Tp(traveling from S to D ) + Tt of Ack) * 1/Tt

you will get the answer.

Don't blindly follow 1+2a it is straightforward case. Many manipulation can be done in RTT.

But after reading the question it is very difficult to think given full duplex ack is not considered.

---

I feel the question just uses the concept of bandwidth delay product. We don't need to bring in all the concepts of stop and wait or sliding window here.

bandwidth is 10⁶bps which means per second 10⁶ bits are put onto the channel.

So in 1ms 10³ bits are transmitted on the channel.

At t=0ms a bunch of 10³ bits starts to get transmitted which is finally on the channel at t=1ms.

At t=1ms 2nd bunch of 10³ bits is transmitted and is finally on the channel at t=2ms and the previous 10³ bits has traveled by some distance.

At t=2ms 3rd bunch of 10³ bits is transmitted and is finally on the channel at t=3ms and the 2nd 10³ bits has traveled by some distance and the first has traveled a further more.

This continues till t=25ms when the first bunch  just reaches the destination ( as 25ms is the propagation delay) and 25th bunch just got transmitted on the channel.

At this instant the channel is filled with 25*10³bits = 25 frames.

So to represent 25 frames we need 5 bits.

 

---

MiNiPanda

Channel utilization = 2*Tp *bandwidth

                                = 50 x 10³ bits

total data send =  50 x 10³ bits

Frame size = 1000 bits

 No of frames we sent   =   50 x 10³ bits /  1000 bits 

                                         = 50 frames

we you tell me where I'm wrong ??

---

My question is I understood your logic clearly but If in xam in the question paper they didn't mention anything about full-duplex and half-duplex....

and "6 bits" is also there in the options

then I have serious doubt in it  :3

---

@Magma

yes right but I read in one of the previous comments that duplex by default means full duplex, also Sir took it as full duplex.

But now there might be this confusion that why aren't we considering the frames being piggybacked from the other end. They are also present in the channel. In that way a total of around 50 packets will be there at the same time in the channel. But the sequence no. wrt to End A and End B are different. A can send at most 25 frames to fill up the channel which requires 5 bits and same for the receiver. They individually require 5 bits.

 

---

Oh yes  MiNiPanda :p

great

---

Sir how to decide when to use which formula

1/+2a or some other one

---

@Khushal...Read above all comment , you will get answer.

---

Sequence number is based on bytes of all combined frames the why we calculated log of number of frames?

---

Excellent elaboration ..

---

Why is the transmission time not consider?

---

Because this is the concept of Bandwidth delay product.

---

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