edited by
21,477 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

Best answer
33 votes
33 votes
Each host needs to generate $1000$ unique identifiers per second which requires $\left \lceil \lg 1000 \right \rceil= 10$ bits.

Now, these $10$ bits along with $32$ bit globally unique IP address will give a globally unique $42$ bit IDs which stays constant.

Since we are allowed $50$ bits we can use the next $8$ bits using the clock which changes every second. Thus our IDs will wrap around once in $2^{8}=256$ seconds.
130 votes
130 votes
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 by
37 votes
37 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

edited by
36 votes
36 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)
Answer:

Related questions

50 votes
50 votes
6 answers
1
go_editor asked Sep 28, 2014
17,071 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...