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 of 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

How did u get that it requires 4 subnet bits??

---

1. Formula NetworkID +SubnetID=Subnet Mask (Continuous run of 1's)

  - 1500 IP addresses = Express in powers of 2 then take log(value), we get 11 bits

  - No of prefix bits for subnet is 32-11=21 bits as in subnetting bits are taken from network portion,

  -Using 17 + SubnetID=21(Subnet mask)

  -We get 21-17=4 bits taken to form subnets in addition to network bits

---

 What they want to say by this line :- ?

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. 

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

why 15th bit in the 4th option should not be 1?

---

> 15th bit cannot be 1

 

Q1) Why ?

Q2) but in i) & ii) 15th bit is 1, since 61 = 32+16+8+4+1(2^0)

---

actually its not 15th  its 16th bit from back  as intial NID contains 17 bits it should stay as it is but in 202.61.1000 1000.0000 0000 due to change in NID part of original we cant use it

---

Since we will have to minimize the no. of entries in the routing table of the router of ISP, so we must avoid change in the actual NID otherwise there will be a new route for the desired result.

---

what is the meaning of "will minimize the number of routing entries in the ISP’s router using route aggregation." ?

---

I might be missing something but can anyone explain why all of the Host bits need to be 0, is it because this is the first address of the block ?

---

Can anyone Explain Why 16^th bit from back  can not be 1??

---

network ID has all host bits as 0s. That’s the format of Network IDs.

---

Why the HID part needs to be 0? A CIDR block can be represented by any IP address in the block. And nowhere in the question is it written that they are Network IDs.

---

What does “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. ” mean?

---

subnetting. @nvs16

---

From my knowledge, I could eliminate option IV. But here the thing which is being said for option I, that it does not contain ALL ZEROES in the host id part, did not strike me. Rather I know that in CIDR subset, even if any random middle IP address is given it would refer to that chuck and it has nothing to do with that middle address.

So, from 202.61.84.0/21=202.61.01010 100.0 we could have known that it refers to the chunk starting at 202.61.01010 000.0

Just as in this question here [GATE2015-3-38]

Please help me.

---

I have the same doubt. Got any resolution?

---

same doubt

---

The ISP is using route aggregation/supernetting. So,in option (I) 84 → 0 1010 100 (HID bit 1 is not possible) because 3^rd rule of supernetting is violating here.

3^rd RULE – First Network id is also divisible by 2^11.  

---

@Pratham rathore you are saying network id should be divisible by the size of the block but where in question it is mentioned that the given IP addresses are network id.

---

In Supernetting the first ip address is always the supernet id/network id.

---

For those who think how option 1 could be wrong.

I think since the question says “entries in the ISP’s router”

Entries in the router table can only be the valid NID’s only. Option 1 can’t be a valid NID due to 1 in HID part.

The question is also a bit ambiguous.

---

Given IP address space: 202.61.0.0/17,

17bits are in-network ID bits(NID) and the rest will be host ID bits(HID).

In order to assign 1500 hosts, we need a minimum of 11 bits

total bits (32)- host bits(11)  We have 4 subnet bits,

eligible networks are those which belong among the possible 16 subnets.

If we expand the given Network bits we can see:

 

1st → 202.61.0.0 to 202.61.7.255   

2nd → 202.61.8.0 to 202.61.15.255 

                       …..

15th → 202.61.120.0 to 202.61.127.255

 

The Subnet Id for every range is a multiple of 8

0,8,16,24,32,40,48,56,64,72,80,88,96,104,112,120

 

 

---

in the last option 17^th bit (from the left side) should be unchanged means it should be 0 but here it is 1 so that's why we discard this

---

yes @Prateek pallaw 

---

If second last octet of IV were from { 112 , 96} then answer would be (D) III AND IV.

---

I did not understand why the $(iv)$ options were wrong here. please explain in a simple way.

---

@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

Answer 2

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