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

To find the correct output interface, we convert the destination IP address and the routing table prefixes into binary to find the matching entries, and then apply the Longest Prefix Match (LPM) rule.

The destination IP address is 131.23.151.76. Let's convert the first two octets to binary:

• $131 = 10000011_2$
• $23 = 00010111_2$

Now, we check the prefixes in the routing table:

1. 131.16.0.0/12:
   • Prefix first 12 bits: $10000011.0001_2$
   • Destination IP first 12 bits: $10000011.0001_2$ (Matches)
2. 131.28.0.0/14:
   • Prefix first 14 bits: $10000011.000111_2$
   • Destination IP first 14 bits: $10000011.000101_2$ (Does not match)
3. 131.19.0.0/16:
   • Prefix first 16 bits: $10000011.00010011_2$
   • Destination IP first 16 bits: $10000011.00010111_2$ (Does not match)
4. 131.22.0.0/15:
   • Prefix first 15 bits: $10000011.0001011_2$ (since $22 = 00010110_2$)
   • Destination IP first 15 bits: $10000011.0001011_2$ (Matches)

Both 131.16.0.0/12 and 131.22.0.0/15 match the destination IP. By the Longest Prefix Match rule, the router selects the prefix with the longest mask ($/15 > /12$).

Thus, the packet is forwarded to interface 1.