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

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

Explain with AI
Consider the entries shown below in the forwarding table of an IP\text{IP} router. Each entry consists of an IP\text{IP} prefix and the corresponding next hop router for packets whose destination IP\text{IP} address matches the prefix. The notation " /N\mathrm{N} " in a prefix indicates a subnet mask with the most significant N\mathrm{N} bits set to 11.PrefixNext hop router10.1.1.0 / 24R110.1.1.128 / 25R210.1.1.64 / 26R310.1.1.192 / 26R4\begin{array}{|ll|ll|} \hline \textbf{Prefix} && \textbf{Next hop router} \\ \hline \text{10.1.1.0 / 24} && \text{R1} \\ \hline \text{10.1.1.128 / 25}&& \text{R2} \\ \hline \text{10.1.1.64 / 26}&& \text{R3} \\ \hline \text{10.1.1.192 / 26}&& \text{R4} \\ \hline \end{array}
This router forwards 2020 packets each to 55 hosts. The IP\text{IP} addresses of the hosts are 10.1.1.16,10.1.1.72,10.1.1.132,10.1.1.191,10.1.1.16, 10.1.1.72, 10.1.1.132, 10.1.1.191, and 10.1.1.20510.1.1.205. The number of packets forwarded via the next hop router R2\mathrm{R} 2 is __________.
View worked solution

Answer: 40

To find the number of packets forwarded via the next hop router R2, we determine the routing path for each host using the Longest Prefix Match (LPM) rule.

Let's analyze the IP ranges for each prefix:

  • 10.1.1.0 / 24: Range 10.1.1.0 to 10.1.1.255 (Next hop: R1)
  • 10.1.1.128 / 25: Range 10.1.1.128 to 10.1.1.255 (Next hop: R2)
  • 10.1.1.64 / 26: Range 10.1.1.64 to 10.1.1.127 (Next hop: R3)
  • 10.1.1.192 / 26: Range 10.1.1.192 to 10.1.1.255 (Next hop: R4)

Now, we match each host IP address to its longest matching prefix:

  1. 10.1.1.16: Matches only 10.1.1.0 / 24. Next hop is R1.
  2. 10.1.1.72: Matches 10.1.1.0 / 24 and 10.1.1.64 / 26. Best match is /26. Next hop is R3.
  3. 10.1.1.132: Matches 10.1.1.0 / 24 and 10.1.1.128 / 25. Best match is /25. Next hop is R2.
  4. 10.1.1.191: Matches 10.1.1.0 / 24 and 10.1.1.128 / 25. Best match is /25. Next hop is R2.
  5. 10.1.1.205: Matches 10.1.1.0 / 24, 10.1.1.128 / 25, and 10.1.1.192 / 26. Best match is /26. Next hop is R4.

The packets destined for hosts 10.1.1.132 and 10.1.1.191 are forwarded via R2. Since 2020 packets are sent to each host, the total number of packets forwarded via R2 is:

20 packets×2 hosts=40 packets20 \text{ packets} \times 2 \text{ hosts} = 40 \text{ packets}

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