Dark Mode

12,735 views

42 votes

An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address $131.23.151.76$. The router's routing table has the following entries:

$$\begin{array}{|c|c|c|} \hline \textbf {Prefix} & \textbf {Outer Interface Identifier} \\\hline \text {131.16.0.0/12} & \text{3 } \\\hline \text{131.28.0.0/14} & \text{5} \\\hline \text{131.19.0.0/16} & \text{2} \\\hline \text{131.22.0.0/15} & \text{1} \\\hline \end{array}$$

The identifier of the output interface on which this packet will be forwarded is ______.

$$\begin{array}{|c|c|c|} \hline \textbf {Prefix} & \textbf {Outer Interface Identifier} \\\hline \text {131.16.0.0/12} & \text{3 } \\\hline \text{131.28.0.0/14} & \text{5} \\\hline \text{131.19.0.0/16} & \text{2} \\\hline \text{131.22.0.0/15} & \text{1} \\\hline \end{array}$$

The identifier of the output interface on which this packet will be forwarded is ______.

0

50 votes

Best answer

Answer is Interface $1.$

Given address $133.23.151.76$ coming to the first field of given routing table

$\Rightarrow 131.16.0.0/12$

$\quad\; 131.\mathbf{0001\ 0111}.151.76$

$\quad\; 131.\mathbf{0001\ 0000}.0.0 (\because \text{given mask bits} = 12 )$

$\Rightarrow 131.16.0.0 \qquad \text{Matched}$

Coming to the $2^{\text{nd}}$ field of the given Routing table

$\Rightarrow 131.28.0.0/14$

$\quad\; 131.\mathbf{0001\ 0111} .151.76$

$\quad\; 131. \mathbf{0001\ 0100}.0.0 (\because \text{given mask bits} = 14 )$

$\Rightarrow 131.20.0.0 \qquad \text{Not matched.}$

Coming to the $3^{\text{rd}}$ field of the given Routing table

Error$!$ Not a valid link. $131.19.0.0/16$

$131.\mathbf{0001\ 0111}.151.76$

$131.\mathbf{0001\ 0111}.0.0 (\because \text{given mask bits} = 16 )$

$\Rightarrow 131.23.0.0 \qquad \text{Not matched}$

Coming to the $4^{\text{th}}$ field of given Routing table

$\Rightarrow 131.22.0.0/15$

$\quad\; 131.\mathbf{0001\ 0111} .151.76$

$\quad\; 131. \mathbf{0001\ 0110}.0.0 (\because \text{given mask bits} = 15 )$

$\Rightarrow 131.22.0.0 \qquad \text{Matched.}$

We are getting $1^{\text{st}}$ and $4^{\text{th}}$ entries are matched so among them we have to

picked up longest mask bit, so output interface identifier is $1.$

Given address $133.23.151.76$ coming to the first field of given routing table

$\Rightarrow 131.16.0.0/12$

$\quad\; 131.\mathbf{0001\ 0111}.151.76$

$\quad\; 131.\mathbf{0001\ 0000}.0.0 (\because \text{given mask bits} = 12 )$

$\Rightarrow 131.16.0.0 \qquad \text{Matched}$

Coming to the $2^{\text{nd}}$ field of the given Routing table

$\Rightarrow 131.28.0.0/14$

$\quad\; 131.\mathbf{0001\ 0111} .151.76$

$\quad\; 131. \mathbf{0001\ 0100}.0.0 (\because \text{given mask bits} = 14 )$

$\Rightarrow 131.20.0.0 \qquad \text{Not matched.}$

Coming to the $3^{\text{rd}}$ field of the given Routing table

Error$!$ Not a valid link. $131.19.0.0/16$

$131.\mathbf{0001\ 0111}.151.76$

$131.\mathbf{0001\ 0111}.0.0 (\because \text{given mask bits} = 16 )$

$\Rightarrow 131.23.0.0 \qquad \text{Not matched}$

Coming to the $4^{\text{th}}$ field of given Routing table

$\Rightarrow 131.22.0.0/15$

$\quad\; 131.\mathbf{0001\ 0111} .151.76$

$\quad\; 131. \mathbf{0001\ 0110}.0.0 (\because \text{given mask bits} = 15 )$

$\Rightarrow 131.22.0.0 \qquad \text{Matched.}$

We are getting $1^{\text{st}}$ and $4^{\text{th}}$ entries are matched so among them we have to

picked up longest mask bit, so output interface identifier is $1.$

Amazing explanation @saurabhrk

I am just adding few things :

as we know 1st and 4th have matched . then why we select only interface 1 ??

the reason behind this is we know that at interface 1 , subnet mask contain 15 bits 1's ,so we have 2^17 -2 host available to send our packet . but in interface 3 subnet mask contain 12 bits 1's , it have 2^20 -2 bits , which is large than hosts in interface 1 . so,always choose the interface which have less hosts. so interface 1 is better choice than interface 3 .

1

Lakshman Patel RJIT we do bitwise AND between given IP address and subnet mask not with given network id ...hence

**(ip-address bitwise AND subnet mask)** gives network id to address belongs

in third option subnet mask is 255.255.0.0 (since /16 given) so

**(131.23.151.76 ^255.255.0.0)= 131.23.0.0** which is not matching with given network id (131.19.0.0)

hence C no matched

1

50 votes

From the table it is clear that we need to focus on 2nd part of ip address only.

131.**23**.151.76 -> 131.* 00010111*.151.76

i)

ii)

ii)

ii)

Now there are two matches so we will choose the

5 votes

In this question, we need to find out Netmask for each entry and BITWISE AND with given packet address, whichever equals the Netid, is the ans. Ex. 1st entry in table: 131.16.0.0/12. its MASK is first 12 bits of network(they are all 1) and remaining 20 bits of host(they are all 0). so MASK is 255.240.0.0 AND 131.23.151.76 = 131.16.0.0. Last entry is 131.22.0.0/15 MASK--->255.254.0.0 AND 131.23.151.76 = 131.22.0.0. Two ans coming interfaces 1,3. Longest Prefix Matching is used to decide among two. When one destination address matches more than one forwarding table entry. The most specific of the matching table entries is used as the interface. The interface 1 has the longest matching prefix with the input IP address. Therefore 1 is chosen.

5 votes

When there are multiple matches, the router uses the longest prefix matching rule; that

is, it finds the longest matching entry in the table and forwards the packet to the link interface associated with the longest prefix match.

Given dest.address

131.23.151.76: 1 0 0 0 0 0 1 1 . 0 0 0 1 0 1 1 1 . 1 0 0 1 0 1 1 1 . 0 1 0 0 1 1 0 0

3 -- 131.16.0.0/ 12: 1 0 0 0 0 0 1 1 . 0 0 0 1 x x x x . x x x x x x x x . x x x x x x x x No.of prefix bits matched = 12

5 -- 131.28.0.0/ 14: 1 0 0 0 0 0 1 1 . 0 0 0 1 1 1 x x . x x x x x x x x . x x x x x x x x Bit mismatch(discarded) as highlighted

2 -- 131.19.0.0/ 16: 1 0 0 0 0 0 1 1 . 0 0 0 1 0 0 1 1 . x x x x x x x x . x x x x x x x x Bit mismatch(discarded) as highlighted

1 -- 131.22.0.0/ 15: 1 0 0 0 0 0 1 1 . 0 0 0 1 0 1 1 x . x x x x x x x x . x x x x x x x x **No.of prefix bits matched = 15**

Ans : **Thus the identifier of the output interface on which this packet will be forwarded is 1.**