The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+36 votes

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 (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.

- I=2
- I=3
- I=4
- I=5

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

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.

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 ?

what is the answer in both the cases

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

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

+63 votes

Best answer

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\ ms$.

Bandwidth $=10^6\ 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\ 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}.$

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$

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.

"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 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

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 ?

+14 votes

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(10^{6} 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 + 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 acknowledgements, 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 acknowledgement coming back, that time also packets can be kept on transmitting in the channel,

So, Min. no. of packets required = 1 + 2a = 1 + 2*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 acknowledgements will be piggybacked in such a practical case.

+13 votes

+7 votes

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_{2} (25) = 5 bits.

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

+3 votes

Duplex simply means both sender and receiver can send and receive the signals which is bydefault as we know.

Tx = 1ms (1 frame data put on cable)

Tp = 25ms (25 frame data can be put on cable in this time if we fully utilize the link).

Total time : 1 + 25 = 26 ms (from frist bit of of first frame put on cable to last bit of frame reached to receiver)

So to fully utilize the link we must use the link for 26 ms (26 frames need to transmit)

frames numbered as 0,1,2,3,...25 thus we need 26 different sequence numbers

therefore bits rewuired for sequence number = ceil(log 26) =** 5**

+2 votes

_{p}

So we get capacity = $10^6$ b/s * 25 * 10 ^ -3 s

= 25 * $10^3 bits$

so a channel can contain 25 * $10^3 bits$ but we are sending only frames of 1000 bits

Therefore, the total no. of frames we are sending with its full channel capacity = 25 * 1000/1000 = 25 frames.

For this much frames the seq.numbers nedded are 25.

And Seq.no.bits required are $Ceil(\log_{2}25)$ = 5 bits

+1 vote

Propagation time is given as 25 ms.

Bandwidth = 106 bps.

So, to fully utilize the channel, we must send 106 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 ms, to fully pack the link we need to send at least 1000 * 25 * 10-3 = 25 frames. Since, to represent 25 frames we need 25 distinct index numbers. Thus, minimum no. of bits required to do this will be 5 (2^5=32) as 4 will not be enough (2^4=16, not enough to represent 25 distinct no.)

Bandwidth = 106 bps.

So, to fully utilize the channel, we must send 106 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 ms, to fully pack the link we need to send at least 1000 * 25 * 10-3 = 25 frames. Since, to represent 25 frames we need 25 distinct index numbers. Thus, minimum no. of bits required to do this will be 5 (2^5=32) as 4 will not be enough (2^4=16, not enough to represent 25 distinct no.)

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,230 answers

114,269 comments

38,798 users