6.2k 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 | 6.2k 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?

0

Why 1000 is taken as 1024 ? nobody has explained this. Answer should be 262.144 Sec

Explanation is provided here but i am not getting it

https://stackoverflow.com/questions/33691136/design-a-50-bit-globally-unique-id

https://stackoverflow.com/questions/25201274/in-ipv4-network-finding-the-period-of-identifiers-generated-by-a-host-wrap-aroun

0

Various other websites like Geeksforgeeks and Techtud has also mentioned the options along with this question as -

(A) 128
(B) 64
(C) 256
(D) 512

So in order to pick up a right option, one has to take (1000 as 2^10) otherwise no option won't match, but if it would have been a numerical answer then surely answer is 262.14 seconds.

0
The only way to explain the approximation would be that if a computer has to generate 1000 IDs, it can't do so exactly. It'll have to use 10 bits somewhere, which will generate 1024 IDs. This generation is done regardless of the fact that we only need 1000 IDs in the worst case and hence, the wrap around time will be 256 seconds.
0
Couldn't imagine all 2^32 hosts will be involved!

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
+35
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?
+6
$262.144 sec$ is the precise answer for this qsn.
0

identification field in IP Header is of 16 bit, then why here 232 hosts are considered , why not 216??

0
32 bits of IP are teken .. And also they mentioned that each host has a globally unique I'd for this pourpose
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)
+8
@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.
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

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

In this question, they are saying that 50 bits are globally allocated for unique identity field,

with 50 bits in the unique identity field, we can distinguish  2^ 50 B data uniquely

now total Byte spend in 1 sec is-

let assume at worst case all host are there so the total number of host =( 2^32) and each consuming 1000 B (for simplicity takes 1024) so

total byte consumed = (2^ 32) * (2^10) = 2^ 42 B

now

2^ 42 B is consumed in 1 sec, then 2^ 50 B is consumed in 256 sec  (you please do the maths).

0
Why we are taking total number of hosts as 32?

Is there any general assumption for all protocols like this?