edited by
21,540 views
79 votes
79 votes
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?
edited by

11 Answers

18 votes
18 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?
8 votes
8 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!)

Each host 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 globally unique 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.

 

 

edited by
5 votes
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
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).

 

Answer:

Related questions

50 votes
50 votes
6 answers
1
go_editor asked Sep 28, 2014
17,089 views
An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address $131.23.151.76$. The router's routing table has the following entries:$$\be...