4.7k 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?
edited | 4.7k views
0
can not ubderstand
0
Design a 5050-bit globally unique ID for this purpose.

pls someone explain this
+3

Please, can someone explain this question?

Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup.

Design a 5050-bit globally unique ID for this purpose

What do the above two sentences mean?

Worst case scenario can be that all $2^{32}$ host are present on the network each generating $1000$ packets simultaneously in $1$ second.

So, total packet produced in $1$ second $= 2^{32}\times 2^{10}$ $\text{(assuming 1024 = 1000)}= 2^{42}$

Now, we can distinguish $2^{50}$ packets, after that wrap around (so wrap around time will be when $2^{50}$ identifiers are used)

$2^{42}$ takes $1$ second,

$2^{50}$ will take $=\dfrac{2^{50}}{2^{42}}=2^8=256\text{ seconds.}$
edited
+23
How one is supposed to approximate 1000 to 1024 ? This was numerical answer question ! It was not like we could select one of answer.. Also One more thing, they said we are supposed to generate upto 100.. up to means, Maximum or As far as ! I think this question 's answer should be 262 !
0
What is the meaning of generating 50 bits?Design a 50-bit globally unique ID for this purpose?Can someone explain this?
+3
$262.144 sec$ is the precise answer for this qsn.
this is very strange that answer given is 256..ideally it should be 262 as 2^50/(2^32x1000)...for some reason they have considered 1000 as 2^10...don't why?
0
Those who calculated perfectly are fools and got -0.66??
+2
Can you answer this question ? @Arjun, I'm not satisfied with any of the answers :( Confused here ..
+3
@Arjun, How one is supposed to approximate 1000 to 1024 ? This was numerical answer question ! It was not like we could select one of answer.. Also One more thing, they said we are supposed to generate up to 100.. up to means, Maximum or As far as ! I think this question 's answer should be 262 ! Answer Debate Alert ! If they start approximating everything up / down for no reason GATE exam will become non deterministic !
0
why?? Its so unfair
+1
@Arjun Sir, I think question is NAT type so no negative marking..

Sorry for irrelevant comment
in question given that
Identification No. (unique ID) field is 50 bit long..
.
We can make 50 bit Unique ID No. in combination with 32-bit source IP Address and 18-bit no.
.
50-bit unique Id no. = Concat(32-Bit source IP, 18-bit no.)
.
Now we need to generate only 18-bit no. at each host.
.
1000 No. are generated per sec.
.
so 2^18 numbers are generated in (2^18/1000)sec
(after that ID no. will repeat   at that host)
=2^8 (1000 approximately equal to 2^10)
+5
@Pooja, How one is supposed to approximate 1000 to 1024 ? This was numerical answer question ! It was not like we could select one of answer.. Also One more thing, they said we are supposed to generate up to 1000.. up to means, Maximum or As far as ! I think this question 's answer should be 262 ! Answer Debate Alert ! If they start approximating everything up / down for no reason GATE exam will become non deterministic !
0
even i am not able to understand why is this approximation done and negative marks to those who calculatted accurately, Why?? Its so unfair. Any expert advice needed. Arjun sir plzz tell
+1
I guess it has something to do with resolution of clock but I don't understand it
0

hello @Pooja Palod your explanation is great.....i have just one doubt...that why are we generating only 18 bit no ....and not 50 bit.

is this because already it's given that 32 bits are unique and we have to generate 18 bits more to make id of

50 bits?

0
The 32 bits are that of the IPv4 address itself. Thus these 32 bits are already unique.

STEP 1:
IPv4 has size of 32 bits. so total hosts possible with 2^32
Each host can produce 1000 unique Ids(sequence numbers) per seconds
Therefore, total unique sequence number that can be produced in 1 second = (2^32)*1000
and 1 sequence number can be produced in = 1/((2^32)*1000) seconds.

STEP 2:
Design a 50-bit globally unique ID means that total possible unique sequence number can be produced using 50-bits.Therefore total unique sequence numbers that can generate using 50-bits  =  2^50

CONCLUSION:
From step 1 and step 2  we conclude that total 2^50 sequence numbers an be generated in (2^50)/((2^32)*1000) seconds = 262.14seconds = 262 seconds

Wrap around time = 262 seconds

edited
Wrap-around time is nothing but in how many seconds will all the hosts generate all IDs possible. (i.e. TOTAL_IDS / NO. OF IDS PER SEC). Total IDs possible with 50-bit is 2^50. One host generating 1000 identifiers per sec. So all hosts will generate 2^32 * 1000 ----> 2^32 * 2^10-----> 2^42 unique IDs. If we Divide them, we get answer (i.e. 2^50/2^42=2^8)
0
$1000 \neq 2^{10}$
0
1 second resolution real time clock means???
0
1 cycle time