The Gateway to Computer Science Excellence

+45 votes

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?

+6

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

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

After what period (in seconds) will the identifiers generated by

host wrap around?a

This "a" is confusing.

0

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

+63 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.}$

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.}$

+58

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?

+29 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)

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)

+10

@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

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

@Akash Kanase Sir, @Arjun Sir,

why263 second is not the answer? Answer would be given in range like (262 to 263). See this question-

0

@Arjun sir, how would I know that when to use value 2^10= 1024 as 1000 while solving these kind of questions?

+25 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**

+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?

+2

Can you answer this question ? @Arjun, I'm not satisfied with any of the answers :( Confused here ..

+4

@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 !

+5 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)

+3 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).*

+3 votes

Answer: 256 seconds.

Let's get the gist of the question first, breaking it down bit by bit.

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

It tells that hosts have a cycle of 1 sec each and the "battery backup" part is given that so that it is assumed that there is no concept of the clock going off before the sequences wrap. (Quite irrelevant actually!)

Eachhost needs to generate up to 1000 unique identifiers per second.

This pertains to the unique ID field of the IPv4 packet which is used to identify a packet over the whole global internet.

So, this means that a host on the internet has the capability of creating 1000 such nos. and due to that each host over the internet has the capability of sending a max of 1000 packets per second.

Design a 50−bit

globallyunique ID for this purpose.

Now, these nos. need be designed in such a way that they are unique throughout the world, i.e. there may be chances that all the hosts over the internet are sending out packets simultaneously and it may create confusion if all are not working in tandem with each other.

And it's assumed that this ID being generated ( by **all **the hosts simultaneously, in the worst case) is 50 bit long.

So, they are asking that is such a scenario where all hosts work together, how long will it take for them to consume all the nos. and wrap around back to 0.

Now, the calculation part.

Total hosts present globally in IPv4 = $2^{32}$

In 1 sec, each host generates = 1000 IDs

In 1 sec, $2^{32}$ host genetate = $2^{32} \times 1000$

= $2^{32} \times 2^{10}$ (approximating 1000 as 1024 to make calculations easy)

= $2^{42}$

Nos. of possible IDs with 50 bits= $2^{50}$

Time to generate 1 ID = $\frac{1}{2^{42}}$ sec

Time to generate $2^{50}$ IDs = $\frac{2^{50}}{2^{42}}$

= 256 Seconds.

+2 votes

After what period (in seconds) will the identifiers generated by

host wrap around?a

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}$

52,217 questions

59,907 answers

201,103 comments

118,146 users