The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
5k 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?
asked in Computer Networks by Veteran (111k points)
edited by | 5k 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.

 

6 Answers

+40 votes
Best answer
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.}$
answered by (431 points)
edited by
+27
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?
+4
$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??

+19 votes
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)
answered by Boss (31.9k points)
+6
@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.
+17 votes
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?
answered by Loyal (6.9k points)
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
+11 votes

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

ANSWER :
Wrap around time = 262 seconds

answered by (137 points)
edited by
+4 votes
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)
answered by Loyal (8.7k points)
0
$1000 \neq 2^{10}$
0
1 second resolution real time clock means???
0
1 cycle time
0 votes

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).

 

answered by (213 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

43,942 questions
49,497 answers
162,339 comments
65,748 users