GATE CSE 2014 Set 3 | Question: 27

Question

Every host in an $\textsf{IPv4}$ network has a $1\text{-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 $\textsf{IPv4}$ address. Design a $50\text{-bit}$ globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?

Comments

One of the catch here is that word $\textbf{generate}$ , which means it is not saying $1000$ is the unique ID's given, but it's a requirement that has to be generated. Hence 10 bits are required for it  which will generate at max 1024 unique ID's.

Each host needs to generate up to 1000 unique identifiers per second

---

I guess some questions are just meant to be ignored. :}

---

Computer Networks: GATE Overflow Test Series | Computer Networks | Test 1 | Question: 26

Answer 1

After what period (in seconds) will the identifiers generated by a host wrap around?

IDs generated per second by a host = 1000

Total IDs possible = $2^{50}$

So, in $\frac{2^{50}}{1000}$ seconds, a host will exhaust all IDs, and will have to wrap-around. This number is too high, and not in the options.

 

So, assume that the question means: every host generates 1000 IDs per second, after what time a random host will accidentally produce a duplicate ID?

IDs generated per second by a host = 1000

Total IDs possible = $2^{50}$

Total hosts possible with IPv4 = $2^{32}$ since IPv4 is a 32 bit address.

So, when all the hosts generate 1000 IDs each second, in how much time would they exhaust the total IDs =

$\frac{2^{50}}{2^{32}*1000}$; which is roughly equal to

$\frac{2^{50}}{2^{32}*2^{10}}$

$= \frac{2^{50}}{2^{42}}$

$= 2^{8}$

Comments

Check ace acedmay explain

---

What is answer key suggested by gate official 256 or 262 sec?

---

Official Answer was 256.

http://jam.iitkgp.ac.in/webdir/gatepapers/2014/cs_2014.pdf

Answer 2

The question needs to state it better that the global ID is a combination of unique identifiers and IP addresses. In that case, we have 32 + 18 bits to combine. The identifiers are being used at the rate of 1000 per second. As a result, it will wrap around in $\frac{2^{18}}{1000}$ = 262.144 seconds

Answer 3

THERE ARE 50 bits to be used to design Globally Unique ID ,out of which 32 bits are for IP address 

Remaining Bits : 50-32=18 bits 

Each Host needs to generate 1000 identifiers per second for which it will require 10 bits

Wrap Around time will be computed as: (Total ID’s which can be generated) / (ID required to generate per second)

i.e  --→    (2^18 / 2^10 ) = 256 ans.