search
Log In
31 votes
6.4k views
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 ______.
in Computer Networks
edited by
6.4k views
0
131.19.0.0/ 16  Why is it not used?Can any one explain.
0
Isn't the first match in the table should be considered instead of the longest matching?
0
no, the longest match is considered

6 Answers

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.$

edited by
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
We need to just check the longest matching of 0's and 1's with the given packet
0
among all the matching mask we will take the longest one
0

@ 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
Why we are choosing longest mask ? Is there any specific reason ?
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 . 

0

The longest match is selected due to the router's longest prefix matching property.

37 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 

(No need to find binary of any subnet id, we just want subnet mask which is all 1's in net id part & all 0's in host id part.)
 
i)    /12     11111111.11110000.00000000  bitwise &  131.00010111.151.76 =    131.16.0.0  (Matched with interface 3)
ii)   /14     11111111.11111100.00000000   bitwise &  131.00010111.151.76 =    131.20.0.0  (not matched with any interface)
ii)   /16     11111111.11111111.00000000   bitwise &  131.00010111.151.76 =    131.23.0.0  (not matched with any interface)
ii)   /15     11111111.11111110.00000000   bitwise &  131.00010111.151.76 =    131.22.0.0  (Matched with interface 1)

Now there are two matches so we will choose the longer one which is interface 1. i.e 131.22.0.0 


edited by
0
Correct the binary expansion of 2nd part of ip
0
@Mostafize Is it fine now? & I have not rechecked bitwise &. Please check and say.
0
thanks
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.

0 votes

The more number of 1st in Subnet Mask will be selected so keep this point in mind.

But before, look carefully at Second octet.

It is 00010111

In option A  it is 00010000

In option D it is 00010110

Clearly option D matches more number of bits than option A, also its Subnet mask has more number of 1's 

So option D is correct i.e. interface 1

 

–2 votes
131.19.0.0/ 16  Why is it not used?Can any one explain.
0
we need to consider "longest matching" here 131.16.0.0/ 12 and 131.22.0.0/ 15 both matched but /15 is longest matching it has more prefix so interface will be "1"
Answer:

Related questions

47 votes
8 answers
1
9k views
Every host in an IPv4 network has a $1-second$ resolution real-time clock with battery backup. Each host needs to generate up to $1000$ unique identifiers per second. Assume that each host has a globally unique IPv4 address. Design a $50-bit$ globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?
asked Sep 28, 2014 in Computer Networks jothee 9k views
49 votes
4 answers
2
6.1k views
There are two elements $x,\:y$ in a group $(G,*)$ such that every element in the group can be written as a product of some number of $x$'s and $y$'s in some order. It is known that $x*x=y*y=x*y*x*y=y*x*y*x=e$ where $e$ is the identity element. The maximum number of elements in such a group is ____.
asked Sep 28, 2014 in Set Theory & Algebra jothee 6.1k views
20 votes
4 answers
3
3.1k views
Let $S$ be a sample space and two mutually exclusive events $A$ and $B$ be such that $A \cup B = S$. If $P(.)$ denotes the probability of the event, the maximum value of $P(A)P(B)$ is_____.
asked Sep 28, 2014 in Probability jothee 3.1k views
45 votes
4 answers
4
10k views
The memory access time is $1$ $nanosecond$ for a read operation with a hit in cache, $5$ $nanoseconds$ for a read operation with a miss in cache, $2$ $nanoseconds$ for a write operation with a hit in cache and $10$ $nanoseconds$ for a write operation ... operations. The cache hit-ratio is $0.9$. The average memory access time (in nanoseconds) in executing the sequence of instructions is ______.
asked Sep 28, 2014 in CO and Architecture jothee 10k views
...