Skip to content
GATETECH
Official PYQ · 2024Set 1 · Q26Routing Protocols: Shortest Path, Flooding, Distance Vector, Link StateMCQ2 marks

GATE CS 2024 Set 1 Q26 — Routing Protocols: Shortest Path, Flooding, Distance Vector, Link State

Explain with AI

Consider a network path P−Q−R\mathrm{P}-\mathrm{Q}-\mathrm{R} between nodes P\mathrm{P} and R\mathrm{R} via router Q\mathrm{Q}. Node P\mathrm{P} sends a file of size 10610^6 bytes to R\text{R} via this path by splitting the file into chunks of 10310^3 bytes each. Node P\text{P} sends these chunks one after the other without any wait time between the successive chunk transmissions. Assume that the size of extra headers added to these chunks is negligible, and that the chunk size is less than the MTU\text{MTU}.

Each of the links P−Q\mathrm{P}-\mathrm{Q} and Q−R\mathrm{Q}-\mathrm{R} has a bandwidth of 106bits/sec10^6 \mathrm{bits} / \mathrm{sec}, and negligible propagation latency. Router Q\text{Q} immediately transmits every packet it receives from P\text{P} to R\text{R}, with negligible processing and queueing delays. Router Q\text{Q} can simultaneously receive on link⁡P−Q\operatorname{link} \mathrm{P}-\mathrm{Q} and transmit on link⁡Q−R\operatorname{link} \mathrm{Q}-\mathrm{R}.

Assume P\text{P} starts transmitting the chunks at time t=0t=0.

Which one of the following options gives the time (in seconds, rounded off to 33 decimal places) at which R\mathrm{R} receives all the chunks of the file?

Choose one option
View worked solution

Answer: B

To find the total time taken for node R\mathrm{R} to receive the entire file, we can model the transmission as a pipelined process over two links: P−Q\mathrm{P}-\mathrm{Q} and Q−R\mathrm{Q}-\mathrm{R}.

1. Parameter Calculations

  • Total file size: 106 bytes10^6 \text{ bytes}
  • Chunk size: 103 bytes=103×8 bits=8000 bits10^3 \text{ bytes} = 10^3 \times 8 \text{ bits} = 8000 \text{ bits}
  • Number of chunks (NN): 106 bytes103 bytes=1000 chunks\frac{10^6 \text{ bytes}}{10^3 \text{ bytes}} = 1000 \text{ chunks}
  • Bandwidth (BB): 106 bits/sec10^6 \text{ bits/sec}

2. Transmission Delay (TtT_t)

The transmission delay for a single chunk on any of the links is:

Tt=Chunk sizeBandwidth=8000 bits106 bits/sec=0.008 secondsT_t = \frac{\text{Chunk size}}{\text{Bandwidth}} = \frac{8000 \text{ bits}}{10^6 \text{ bits/sec}} = 0.008 \text{ seconds}

3. Total Time with Pipelining

Since propagation, processing, and queueing delays are negligible, the transmission happens in a pipelined fashion over k=2k = 2 links (P−Q\mathrm{P}-\mathrm{Q} and Q−R\mathrm{Q}-\mathrm{R}):

  • The first chunk takes 2×Tt2 \times T_t seconds to reach R\mathrm{R} (one transmission delay to reach router Q\mathrm{Q}, and another to reach node R\mathrm{R}).
  • Each of the remaining (N−1)(N - 1) chunks will arrive at R\mathrm{R} sequentially, each taking an additional TtT_t seconds.

Thus, the total time (TtotalT_{\text{total}}) is given by the standard pipeline formula:

Ttotal=(N+k−1)×TtT_{\text{total}} = (N + k - 1) \times T_t

Substituting the values (N=1000N = 1000 and k=2k = 2):

Ttotal=(1000+2−1)×0.008 sT_{\text{total}} = (1000 + 2 - 1) \times 0.008 \text{ s} Ttotal=1001×0.008 s=8.008 secondsT_{\text{total}} = 1001 \times 0.008 \text{ s} = 8.008 \text{ seconds}

Therefore, the correct option is B.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Routing Protocols: Shortest Path, Flooding, Distance Vector, Link State questions