The Gateway to Computer Science Excellence

+30 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 ______.

+36 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^{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^{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^{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^{st}$ and $4^{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^{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^{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^{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^{st}$ and $4^{th}$ entries are matched so among them we have to

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

+1

why link 3 is invalid and for (option 4)131.22.0.0/15 binary is 00010110...so network ip is coming out as 131.6.0.0...please correct me if i am wrong

0

@Arjun sir

Coming to the $3^{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}$

How the routing table have error$?$

$23:0 0 0 1$ $0 1 1 1$

$19:0 0 0 1$ $0 0 1 1$ Perform bitwise AND

-------------------------------------

$19:0 0 0 1$ $0 0 1 1$

--------------------------------------

Why this is `not`

valid$?$

This is also mathed.

Why this is not taken in the answer$?$

0

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 .

+34 votes

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

i)

ii)

ii)

ii)

Now there are two matches so we will choose the

+5 votes

+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.**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,253 answers

198,069 comments

104,707 users