GATE CSE 2004 | Question: 55

Question

The routing table of a router  is shown below:
$$\begin{array}{|l|l|l|} \hline \textbf {Destination} & \textbf {Subnet Mask} & \textbf{Interface}  \\\hline \text {128.75.43.0} &  \text{255.255.255.0} & \text{Eth$0$} \\\hline\text {128.75.43.0} &  \text{255.255.255.128} & \text{Eth$1$} \\\hline\text {192.12.17.5} &  \text{255.255.255.255} & \text{Eth$3$}\\\hline \text {Default} &  \text{} & \text{Eth$2$}\\\hline\end{array}$$
On which interface will the router forward packets addressed to destinations $128.75.43.16$ and $192.12.17.10$ respectively?

• A. Eth$1$ and Eth$2$
• B. Eth$0$ and Eth$2$
• C. Eth$0$ and Eth$3$
• D. Eth$1$ and Eth$3$

Comments

Note : Longest Prefix Match

source : https://en.wikipedia.org/wiki/Longest_prefix_match

---

Source of Longest Prefix Match : https://www.sciencedirect.com/topics/computer-science/longest-matching-prefix

Default Route Explanation : https://en.wikipedia.org/wiki/Default_route#:~:text=The%20default%20route%20is%20generally,calculation%20for%20the%20transmission%20path.

Why does the router uses longest prefix matching technique when there is a multiple match ?

 

The main reason for this rule is that a longer prefix represents a smaller, more specific network. A shorter prefix, like a default route 0.0.0.0/0 , matches all possible destination addresses and is very general.  A longer prefix, such as /27 matches a much smaller set of addresses and is, therefore, more specific. By choosing the longest match, the router ensures the packet follows the path that is most relevant to its exact destination.

 

 

---

Simple approach :

192.12.17.10 with 255.255.255.255 = 192.12.17.10 (same)  Not matches with anyone, hence default.

This eliminates C & D

Now, 128 AND 16 = 0     as well as 0 AND with 16 = 0     .....both A & B matches
Higher power or longer subnet is choosen.

Hence, ANS (B)

Answer 1

The answer must be A.

(Using $\wedge$ to denote bitwise AND)

For 1$^{st}$packet,

$(128.75.43.16) \wedge (255.255.255.0) = (128.75.43.0)$ since $\{16 \wedge 0 = 0\}$, as well as 

$(128.75.43.16) \wedge (255.255.255.128) = (128.75.43.0)$ since $\{16 \wedge 128 = 0\}$.

Now, since both these subnet masks are producing the same Network ID, hence The one with greater number of ones will be selected, and the packet will be forwarded there. Hence packet $1$ will be forwarded to Eth$1$.

For $2^{nd}$ packet,

$(192.12.17.10)$ when ANDed with each of the subnet masks does not match with any of the network ID, since:

$(192.12.17.10) \wedge (255.255.255.0) = (192.12.17.0)$ {Does not match with any of the network addresses}

$(192.12.17.10) \wedge (255.255.255.128) = (192.12.17.0)$ {Does not match with any of the network addresses}

$(192.12.17.10) \wedge (255.255.255.255) = (192.12.17.10)$ {Does not match with any of the network addresses}

Hence, default interface must be selected for packet $2$, i.e., Interface Eth$2.$

Comments

A network is divided in the many subnets,

But now the entries of the original network and new subnets both are present in routing tables
and the subnet mask of the new subnet will be longer. so it is more meaningful to send the data to subnet
Longest Prefix Matching in Routers - GeeksforGeeks here you can understand it better.

---

@Nisha Bharti Longest prefix match subnet mask is preferred because in Routing table Network ID are stored in decreasing order of subnet mask , also can understand the network mask having less number of host is more specific than the network have more number of host.

---

so only we use maximum prefix ip:

Answer 2

How router makes decisions ?

Router check the destination address by decapsulating packet and perform bitwise AND with subnet mask of all interfaces and if the resulting n/w address matches with corresponding interface n/w address then router send packet to this interface , in case of tie , router uses Longest prefix match

interface eth0 :- 128.75.43.0/24 (128.75.43.0 to 128.75.43.255)

interface eth1 :- 128.75.43.0/25 (128.75.43.0 to 128.75.43.127)

for 128.75.43.16 we can see there is a tie as it falls within the n/w addresses for eth0 and eth1...which route would the router choose? It depends on the prefix length, or the number of bits set in the subnet mask. Longer prefixes are always preferred over shorter ones when forwarding a packet.

https://en.wikipedia.org/wiki/Longest_prefix_match

https://stackoverflow.com/questions/9335504/network-longest-prefix-matching

Comments

"Longer prefixes are always preferred over shorter ones when forwarding a packet." why so ?

---

read about RIPv2

and packet forwarding

Answer 3

Start with the maximum mask:

128.75.43.16 while doing masking(bit wise AND operation) with

255.255.255.128 will give 128.75.43.0 .

we always takes the maximum mask so ans would be eth1

Answer 4

It'll be through eth1. If bit wise OR of packet address and subnet mask matches with more than one destination address then we go with the one with longer run of 1s.

Answer 5

Gabbar is right. But why do we take maximum mask?

Because the mask 255:255:255:128 is included in mask 255:255:255:0

i.e. 2nd destination is part of the 1st destination. So, if we forward directly to 2nd destiantion, the packet may reach the main destination faster.

Answer 6

1) Destination : 128.75.43.0

Subnet Mask : 255.255.255.0  i.e  111...1 . 111...1 . 111...1 . 000..0

So range will be from 125.75.43.0 to 125.75.43.255 as first three bytes (24 bits) are fixed and last byte (8 bits) can vary from 000..0 to 111..1 i.e 0 to 255 in decimal.

2) Destination : 128.75.43.0

Subnet Mask : 255.255.255.128  i.e  111...1 . 111...1 . 111...1 . 10000000

So range will be from 125.75.43.0 to 125.75.43.127 as first two bytes and first bit (25 bits) are fixed and last byte (7 bits) can vary from 0000000 to 1111111 i.e 0 to 127 in decimal.

3) Destination : 192.12.17.5

Subnet Mask : 255.255.255.255  i.e  111...1 . 111...1 . 111...1 . 111..1

So range will be 192.12.17.5 as all four bytes (32 bits) are fixed.

 

Now, for the given destinations : 

(i)  128.75.43.16 : It falls in the range of 1 and 2 (explained above), but the no. of fixed bits are larger in 2 (25 bits) than in 1 (24 bits), so it will be forwarded through Eth1. Here, we use the concept of longest prefix matching.

NOTE : When a given destination address falls in the range of more than one network, we choose the longest prefix address which matches the destination address i.e in which the no. of fixed bits (i.e 1) is greater than others. This concept is longest prefix matching.

(ii) 192.12.17.10 : Since it does not falls in the range of anyone, it wil be forwarded through default i.e Eth2.

 

Hence , Answer is option (A).