GATE CSE 2022 | Question: 45

Question

Consider routing table of an organization’s router shown below:

$$\begin{array} {|l|l|l|} \hline \text{Subnet Number} & \text{Subnet Mask} & \text{Next Hop} \\\hline 12.20.164.0 & 255.255.252.0 & \text{R1} \\\hline  12.20.170.0 & 255.255.254.0 & \text{R2} \\\hline 12.20.168.0 & 255.255.254.0 & \text{Interface 0} \\\hline 12.20.166.0 & 255.255.254.0 & \text{Interface 1} \\\hline \text{default} & & \text{R3} \\\hline \end{array}$$

Which of the following prefixes in $\text{CIDR}$ notation can be collectively used to correctly aggregate all of the subnets in the routing table?

• A. $12.20.164.0/20$
• B. $12.20.164.0/22$
• C. $12.20.164.0/21$
• D. $12.20.168.0/22$

Comments

A and C can never be the options as they both have wrong CIDR range,
 

---

if its mcq then A would be ans

---

see this explaination

Answer 1

 GATE official initial key has given B,D as answers. 

I strongly feel this question should be challenged to give marks for all because this question requires certain assumptions.

In this answer, I have explained the reason why options B and D are correct and the required assumptions for their correctness.

I have prepared a draft to submit. Please find it here – here

 

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Please watch this short video if you want to understand suppernetting. 
Video explanation for route aggregation – Route aggregation or Supernetting | Easiest explanation

Four networks are given in question as follows –

$\textbf{Network1: } 12.20.164.0/22  $

$\textbf{Network2: } 12.20.170.0/23  $

$\textbf{Network3: } 12.20.168.0/23 $

$\textbf{Network4: } 12.20.166.0/23 $

 

 

Four options are also given, following is range of options along with range of networks –

Option A covers everything (all networks) but it also covers lot more extra IPs.
Option C and D  collectively aggregate everything (all networks) but  also covers few more extra IPs.

Option B and D  collectively aggregate everything (all networks) without covering extra IPs.

Hence B and D should be answer.

Still, there is a possibility of marks to all
Explaining in short (Please read the above draft for full detail)-

Two reasons – 

1. Whats wrong with option A or (C,D) ? – they are just covering extra IPs but it is given in kurose that we can cover extra IPs if these IPs are unallocated. (Please see above draft where kurose screenshots are attached.)
2. Even If we agree that B and D are more precise in terms of not covering extra IPs still option B and D requires an assumption about topology of network (given below)

Now we explain the assumption about topology of network to make  option B, D  correct. – 

 

Option D combines network 2 and 3. But you can combine only when Next Hop is same for both networks.

$$\begin{array} {|l|l|l|} \hline
\text{Subnet Number} & \text{Subnet Mask} & \text{Next Hop} \\\hline
12.20.164.0 & 255.255.252.0 & \text{R1} \\\hline 
12.20.170.0 & 255.255.254.0 & \color{green}{\text{R2}} \\\hline
12.20.168.0 & 255.255.254.0 & \color{green}{\text{Interface 0}} \\\hline
12.20.166.0 & 255.255.254.0 & \text{Interface 1} \\\hline
\text{default} & & \text{R3} \\\hline \end{array}$$

THE VERY FIRST CONDITION IN AGREGGRATION IS TO HAVE SAME NEXT HOP. OTHERWISE AGREGGRATION IS NOT POSSIBLE.

$\color{green}{\text{R2}}$ and $\color{green}{\text{Interface 0}} $ should be same. Which means following topology – 

If network 2 and 3 are on same side of router R then only we can combine them in routing table of R.

What if networks 2 and 3 are connected to different interfaces?

In this case we can not even combine network 2 and 3 hence none of the option should be correct.

First Figure : R2 = Interface 0

Second Figure : R2 ≠ Interface 0

Both Fiigures are very much possible.

Option B and D are correct subject to two assumptions - 

1. We should have topology given in first diagram
2. We are not allowed to cover extra IPs. 

 

Comments

C and D can not be that answer for this question since they are only considering the ip from this forwarding table(only)that should be covered.(I think)

and thats why they have given the answer B & D.

---

did they give marks to all in 2022 for this questions?, do we need to assume that in future questions covering all ips given in the routing table is the best option and eliminate options that cover extra ips in future gate questions?

---

Refer this 

 

After going through, u can get to know why We are avoiding Opt. {A} and {C,D} as they contains extra addresses also

 

Now, after spending some more time, the trick I got it check options directly,

Prefix              Third Octet multiples

/22         =>       4

/21         =>       8

/20         =>       16 

Opt. A  =>  164 / 16  =  10.25 (not whole no. so invalid)

Opt. B  =>  164 / 4   =   41      (Valid)

Opt. C  =>  164 / 8   =   20.5   (invalid)   

Opt. D  =>  168 / 4   =  42       (Valid)

Hence, Ans (B, D)

 

Here, I want to stress why A and C are invalid shortly, 

/20  ⇒  164 is not divisible by 16 ⇒ So Actual network becomes 160/20 ⇒ Covers extra IPs
 

/21  ⇒ 164 is not divisible by 8 ⇒ So the actual network becomes 160/21 ⇒ Covers only 160–167 (does not cover 168–171).

 

 

Answer 2

12.20.164.0/22  → 12.20.10100100.00000000

12.20.170.0/23  → 12.20.10101010.00000000

12.20.168.0/23  → 12.20.10101000.00000000

12.20.166.0/23  → 12.20.10100110.00000000

 

12.20.170.0 and 12.20.168.0 can be combined to 12.20.10101000.0 (12.20.168.0/22).

12.20.166.0/23 comes inside 12.20.164.0/22. So, 12.20.164.0/22 can be used for route aggregation of both.

12.20.168.0/22 and 12.20.164.0/22 can’t be combined further.

So, answer is option B and D.

---

Question is asking which prefixes can be collectively used to correctly aggregate all of the subnets in the routing table. Not which options independently does it.

Also, Option A contains IP address 12.20.175.1 which doesn’t belong to the specified organization.

Comments

Can you please explain, why C and D cannot be right. C contains 1st and last subnets, just like B. So answer can be C and D.

I know I am wrong. Please telll me where am I making a mistake.

---

best ans

---

12.20.164.0/21:

164 in binary = 10100 100

If /21 keeps first 5 bits fixed, those are: 10100

The last 3 bits can be: 000, 001, 010, 011, 100, 101, 110, 111

So the 3rd octet ranges from:

• 10100 000 = 160
• 10100 111 = 167

So 12.20.164.0/21 actually represents 160-167, which includes extra addresses (160-163) not in the original table.

Answer 3

• Routing Table Subnet Numbers and Masks:

  • 12.20.164.0 ------ 255.255.252.0
  • 12.20.170.0 ------ 255.255.254.0
  • 12.20.168.0 ------ 255.255.254.0
  • 12.20.166.0 ------ 255.255.254.0

 

• CIDR Notation Options:

  • A. 12.20.164.0/20
  • B. 12.20.164.0/22
  • C. 12.20.164.0/21
  • D. 12.20.168.0/22

 

• we convert into binary the third octet of the networks ( forwarding table) which are 
  • 164 --> 10100100 (network 1)
  • 170 --> 10101010 (network 2)
  • 168 --> 10101000 (network 3)
  • 166 --> 10100110 (network 4)
• we start with each options and try to match , which networks will be included --  

 

 

A.) 12.20.164.0/20

12.20.1010xxxx.xxxxxxxx

164 --> 10100100 (network 1)

170 --> 10101010 (network 2)

168 --> 10101000 (network 3)

166 --> 10100110 (network 4)

 

hence , it will aggregate every network ,therefore it can be a potential correct option . but it includes many IPs that may not be included in the networks . For example , 12.20.172.0/22 which is not a part of any of the entries in the forwarding table is also a part of 12.20.164.0/20. Hence this option stand suspicious. ( lagta hai Kauno firki le raha hai )

 

 

 

B.) B. 12.20.164.0/22

12.20.101001xx.xxxxxxxx

164 --> 10100100 (network 1)

170 --> 10101010 (network 2)

168 --> 10101000 (network 3)

166 --> 10100110 (network 4)

 

hence B does not entirely include the Networks as it includes hosts of the range from 12.20.164.0/22 to 12.20.167.255/22 only . 

 

 

C.) 12.20.164.0/21

12.20.10100xxx.xxxxxxxx

164 --> 10100100 (network 1)

170 --> 10101010 (network 2)

168 --> 10101000 (network 3)

166 --> 10100110 (network 4)

 

hence C does not entirely include the Networks as it includes hosts of the range from 12.20.160.0/21 to 12.20.167.255/21 only . 

 

 

D.) 12.20.168.0/22

12.20.101010xx.xxxxxxxx

164 --> 10100100 (network 1)

170 --> 10101010 (network 2)

168 --> 10101000 (network 3)

166 --> 10100110 (network 4)

 

hence D does not entirely include the Networks as it includes the range from 12.20.168.0/22 to 12.20.171.255/22 only . 

 

 

It's not over yet , wait there is a catch , if you pay close attention to the ranges of B and D (and not on reels )  .

B ranges from  12.20.164.0/22 ----> 12.20.167.255/22

D ranges from  12.20.168.0/22 ----> 12.20.171.255/22

on combining both the ranges we will include every IP ( not even extra IPs , just meal no fancy desserts )  the range becomes 

 

12.20..164.0/22 ----> 12.20.171.255/22 

 

• 12.20.164.0 ------ 255.255.252.0                |
• 12.20.170.0 ------ 255.255.254.0                |        forwarding table networks 
• 12.20.168.0 ------ 255.255.254.0                |
• 12.20.166.0 ------ 255.255.254.0                |

so , you can check - every network will belong to B and D COMBINED 

yes , i supported answer A for a while and changed the climax to B and D because B and D combined is the real thing .

 

 

(just opinion ) --->   If the question is an MSQ B and D (combined) is the best option and A is the best option if the question is MCQ. 

 

Answer 4

A is the answer by combining the last common bits by the principle of supernetting.

Comments

It is not, a can never be correct, How can you make .164 in 3 octet by just /20. It is one of the host id's it can never be a subnet id, Also the routing table stores the subnet or network id's.

You are blindly applying the rules, but it is not the case you have to think carefully in this question..

Answer 5

Write the changing bits in binary and select the overall range from the options accordingly.

Answer 6

Here, the question played very well. It is asked that which prefixes (Network IDs) are collectively used that means it is simple that there won't be any single network which will combine all four subnets. So here first of all, we will represent all the networks in CIDR notation:
N1: 12.20.164.0/22
N2: 12.20.170.0/23
N3: 12.20.168.0/23
N4: 12.20.166.0/23

---

Now we will find the range of which network because the real game lies in it only:

Range of N1: 12.20.10100100.00000000 (=12.20.164.0) to 12.20.10100111.11111111(=12.20.167.255)
Range of N2: 12.20.10101010.00000000 (=12.20.170.0) to 12.20.10101011.11111111(=12.20.171.255)
Range of N3: 12.20.10101000.00000000 (=12.20.168.0) to 12.20.10101001.11111111(=12.20.169.255)
Range of N4: 12.20.10100110.00000000 (=12.20.166.0) to 12.20.10100111.11111111(=12.20.167.255)

Notice that the range of N4 (166-167) is already covered in that of N1 (164-167). Thus, we can ignore N4 while aggregating the networks.

---

Remaining networks are: 
N1: 12.20.164.0/22
N2: 12.20.170.0/23
N3: 12.20.168.0/23

N3: 12.20.168.0/23
N2: 12.20.170.0/23

Now we will arrange N2 and N3 in sequence as they can form supernet because their network size is same (2^9 IP addresses), they are contiguous (We found the range so we can say) and the first Network ID (12.20.168.0) is divisible by the total size of the supernet which is (2^9 + 2^9 = 2^10) as follows:

12.20.10101000.00000000/2^10 . So here last 10 bits are representing the remainder or Host ID bits which is zero in decimal. 
So the supernet ID after combining N3 and N2 is 12.20.168.0/22 as there are 2 networks to be combined and we have borrowed 1 bit from Network ID part so it will be /22.
 

---

Now remaining networks to be aggregated are as follows:

12.20.164.0/22
12.20.168.0/22
For these above two networks, we will again check the three rules to decide whether these two networks can be aggregated or not.
1. Yes, the above two networks are contiguous
2. Yes, they are of same size (=2^10) and no. of networks are also in power of 2 (=2^1).
3. No the first network id which is 12.20.164.0/22 won't be divisible by total size of supernet which is 2^10 +2^10 = 2^11. Let's check:
12.20.10100100.00000000 / 2^11
We can observe here that last 11 bits are not zero so remainder is not zero which implies that it is not divisible by total size which is 2^11.
 

---

Thus, we can give a final conclusion that the two networks 12.20.164.0/22 and 12.20.168.0/22 are collectively used to aggregate all the subnets which are given in the question. So answer will be options B) & D).