GATE CSE 2020 | Question: 38

Question

An organization requires a range of IP address to assign one to each of its $1500$ computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serves the requests from the available IP address space $202.61.0.0/17$. The ISP wants to assign an address space to the organization which will minimize the number of routing entries in the ISP’s router using route aggregation. Which of the following address spaces are potential candidates from which the ISP can allot any one to the organization?

1. $202.61.84.0/21$
2. $202.61.104.0/21$
3. $202.61.64.0/21$
4. $202.61.144.0/21$

• A. $\text{I}$ and $\text{II}$ only
• B. $\text{II}$ and $\text{III}$  only
• C. $\text{III}$ and $\text{IV}$ only
• D. $\text{I}$ and $\text{IV}$ only

Comments

Route aggregation is the practice of combining multiple smaller, contiguous network addresses into a single, larger network address in a routing table.

 Aim : To keep global routing tables (the memory inside core internet routers) as small as possible. Smaller tables mean faster lookups, less CPU usage, and a more stable internet.

The ISP wants to assign an address space to the organization which will minimize the number of routing entries in the ISP’s router using route aggregation. 

The question is testing whether you know that the new /21 subnet must be mathematically derived fromand contained entirely within the parent /17 block.

---

Shortest possible approach, 

→ /21  =>  255.255.248.0      here, 256 - 248 = 8 ......every 3rd octet should be divisible by 8

A - 84  → not multiple of 8  .......hence eliminated
B - 104 → multiple of 8 
C - 64  → multiple of 8 
D - 144 → multiple of 8 

Now /17 means third octet 0–127 only

B - 104 .....works
C - 64   .....works
D - 144 .....already inside 128 hence eliminated. 

Those, who are not cleared and want more discussion about 144, read this
https://gateoverflow.in/333193/gate-cse-2020-question-38?show=541939#c541939

Answer = II and III only

---

it is not supernating ,,in supernating  we borrow bit from network id and aggregate them

yes question has mantion but meaning less line it is

it a subnating question

Answer 1

(B) II and III only 

---

Given IP address space: $202.61.0.0/17$, $17$ bits are in network ID bits(NID) and rest will be host ID bits(HID).

$\underbrace{202.61.0}_{17 \text{ NID } bits}0000000.00000000$

In order to assign $1500$ hosts we need minimum $11$ bits

$\underbrace{202.61.0}_{17 \text{ NID }  bits}\ \underbrace{0000}_{4 \text{ SID } bits}\underbrace{000.00000000}_{11 \ \text{ HID } \ bits}$

We have $4$ subnet bits, eligible networks are those which belongs among possible 16 subnets.

If we expand the given Network bits we can see:

• $202.61.\textbf{84}.0/21 = 202.61.0\textbf{1010}100.0$
  Not possible as all Host Bits should be zero
• $202.61.\textbf{104}.0/21 = 202.61.0\textbf{1101}000.0$
  Possible
• $202.61.\textbf{64}.0/21 = 202.61.0\textbf{1000}000.0$
  Possible
• $202.61.\textbf{144}.0/21 =202.61.1\textbf{0010}000.0 $
  Not possible as $16^{th}$ bit from right (part of $\text{NID}$ is $0$ and not $1)$

Comments

@Hira Thakur option(iv) is not even part of the network

given the ISP has 202.61.0.0/17=202.61.00000000.0 

option (iv) is 202.61.144.0/21 = 202.61.10010000.0 

---

@Sachin Mittal 1 sir i thnk
(I) is not a valid address space

Reason:-
Let’s first see, from routing table,how to decide which interface an incoming packet will be routed to?
- we basically do AND ops between the subnet mask of the interfaces and the incoming packet's IP,
the result of this AND is the network id of the interface when the packet should be routed.
Below is a an example of this

now, let's go back to our qstn
(I)'s address space =$202.61.84.0/21$
                                 =$202.61.01010 |$ $100.0$ (with /21 subnet mask)

Now, as per the qstn any IP inside the address space $202.61.0.0/17$ can be a valid IP(cuz the organisation request for IP to the ISP,which  serves the requests from the available IP address space 202.61.0.0/17 ),so any incoming packet having IP addresses inside this address space should be routed to the organisation .

But see in the below photo, a packet came with ip $202.61.01010$ $111.0/21$ [this is inside the 202.61.0.0/17 address space], but it cannot be routed to (I)'s address space!!, cuz after the AND ops, the network id won't match(i think this happens due to this 1 [ 202.61.01010 |100.0 ]  inside (I)'s address space)

Thereby we can say no valid packet can ever be routed to (I) address space

NB:- I also set that 6th 1 in 3rd octet to 0, i.e 202.61.01010 | 000.0 (with /21 subnet mask),which i denoted as interface B, now and any valid packet can route to (I) address space

---

For those who not understand why A not correct follow this statement:-

For a block to be a valid network address and allow for efficient route aggregation, the host bits must be all zeros.

Answer 2

Given :
Network ID = 202.61.0.0/17
No.of hosts = 1500
Bits of Network ID = 17
Solution :
No. of bits required for Host ID = ⌈log2(1500)⌉ ≈ 11 (Rounding off)
No. of bits in Subnet Part = 32 - (17+11) = 4
i.e Required IP Address Assigned can be
202.61.0 _ _ _ _ 000.00000000/21
i.e... Possible Values of 3rd Octet are 0 , 8 , 16 , 24 , 32 , 40 , 48 , 56 , 64 , 72 , 80 , 88 , 96 , 104 , 112 , 120.
i.e Possible IP Addresses are - 
202.61.0.0/21, 202.61.0.8/21 , 202.61.16.0/21, 202.61.24.0/21 , 202.61.32.0/21 , 202.61.40.0/21 , 202.61.48.0/21 , 202.61.56.0/21 , 202.61.64.0/21 , 202.61.72.0/21 , 202.61.80.0/21 , 202.61.88.0/21 , 202.61.96.0/21 , 202.61.104.0/21 , 202.61.112.0/21,
202.61.120.0/21 

i.e IP addresses II and III are potential candidates to be alloted by the ISP.
Correct Option is b) II and III only 

Comments

this is teh best way to do this kind of problem just find the possible values in the thirsd octet . we have 3 host bits in third ocetet 2^ =8

so the third octet should be divisible by 8 only option 2 and 3  have the third octet which is divisible by 8

---

This method is really helpful, but I want to highlight why even 144 is divisible by 8 but not considered here,

Because

In a /17 network, 17 bits are fixed.
Since the first bit of the third octet is fixed, the third octet is split into two ranges:
0–127 (first bit = 0) and 128–255 (first bit = 1).

Therefore, 202.61.0.0/17 includes only addresses with the third octet from 0 to 127.

Since 144 lies in the range 128–255, 202.61.144.0/21 belongs to 202.61.128.0/17, not 202.61.0.0/17,
so it cannot be allocated.

---

thanks man @Siddharth_Perkar

Answer 3

It can be done in just few seconds if you know the property that to form a supernet the first address of the block must be divisible by the number of demanded ip addresses.

Here the demand is 1500 but we need to give 2048 which is 2^11.

Now test each of the option given.

To be eligible the IP addresses must be divisible by 2^11 that is it must contain 11 zeros from last.

When you check the number of zeros from last only option B and C will be valid.

Comments

dutta18 According to your logic in option (D) last $11$ bits are $0$. it is also matched.

$202.61.144.0\implies 202.61.10010000.00000000$

---

at 17^th bit should be 0 it is given /17 that’s why see after 17^th bit

---

😄

---

Really nice question, clears a lot of misconceptions.

Answer 4

Could save time?

Answer 5

COMMENT BELOW IF YOU HAVE ANY DOUBT

Comments

Better to write : minimum number of host bits ($h$) where $2^h - 2 \ge 1500$ (exclude Network id and broadcast id )

Instead of :

$$2^h  \ge 1500$$.

Answer 6

COMMENT BELOW IF YOU HAVE ANY DOUBT