GATE CSE 2014 | Set 3 | Question: 27

Question

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?

Comments

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

 

---

Lets take an Example: You are given 6 bits.  
You are told to generate 3 numbers per second.  
You are also told that the two MSB bits are fixed for your name (your unique IP address), meaning there are four hosts and these two bits identify who is generating; these two bits never change for a host.

So effectively only 4 bits are left for the changing part.

With 4 bits you can represent values from $0$ to $15$.  
The only rule is: in one second, you can generate at most 3 numbers.  
Nothing is said about restarting every second or that $1,2,3$ must always have the same bit-pattern.

So you keep a single running counter.

First second: $0,1,2$  
Second second: $3,4,5$  
Third second: $6,7,8$  
Fourth second: $9,10,11$  
Fifth second: $12,13,14$

After this, the next value is $15$ and then wrap to $0$.  
Hence, for a given host, identifiers repeat after about 5 seconds.  
This is the wrap-around when all 4 bits are treated as a flat sequence space.

Now consider an alternative interpretation.  
Assume that in every second the values $1,2,3$ must always be encoded in the same way, i.e., you must explicitly represent the position within the current second.  
Then 2 bits are required for the per-second counter.  
Out of the 4 bits, 2 are consumed for this purpose, leaving only 2 bits to distinguish different seconds.

Those remaining 2 bits can represent only 4 seconds.  
Therefore, wrap-around occurs after 4 seconds.

Apply the same reasoning to the actual problem.

Out of 50 bits, 32 bits are fixed for the IP address.  
So 18 bits remain.

If all 18 bits are used as a flat sequence space, total values are $2^{18} = 262144$.  
With a rate of 1000 per second, wrap occurs after
\[
\frac{2^{18}}{1000} \sim 262 \text{ seconds.}
\]

If instead you assume that each second must encode positions $1$ to $1000$ in a fixed way, then 10 bits are required for the per-second counter.  
Out of 18 bits, 10 are consumed, leaving 8 bits for time.  
These 8 bits can represent $2^8$ different seconds, so wrap occurs after
\[
2^8 = 256 \text{ seconds.}
\]

so not sure, if 10 bits for timer clock should be reserved, the result depends on whether the 18 bits are treated as a single running sequence or are partitioned into a per-second counter and a time field, if you have a resource, kindly ping.

---

My take on why 262 won't be the answer. 

The people who are claiming 262 -> they are ignoring the structured fields approach (IP + Time + Counter) and are instead using a Pure Mathematical Capacity Approach (Global ID Consumption).

Post 32 bits, people who claim 262 to be the answer use the whole 18 bits for wrap around time. However, we are supposed to find wrap around time for EACH sequence number. Hence, since each IP and sequnce number pair will be unique, we only need to find wrap around time for each sequence number. 

So 10 bits for(1000) each sequence number. 

Now we have 8 remaning bits. 8 remaining bits here will be used for keeping the status. 1 second for each status. So we have 2^8 = 256 seconds to keep track of each sequnce number. 

Now THIS IS IMPORTANT. 

Purpose of wrap around time -> It stops a completely different, newly created data object (or transaction) from stealing the exact same identity string as an older, completely separate object while that older object is still active or stored in the system.

So in at 10 am , we have a data packet with ipaddress1-sequence number 500-counter=0

and 256 seconds, we can again have a packet with ipaddress1-sequence number 500-counter=0.

Hence, the 8 bits will only be used for wrap around time. 

Answer 1

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.

Comments

RamaSivaSubrahmanyam this is not correct cause we r generating 1000 identifier per second and NOT 1024 identifiers. for the answer to be 256 seconds we must generate 1024 ie 2^10 identifiers per second. For 1000 identifiers per sec we will wrap around a little later than 256 second because we still have 24 identifiers left that can be generated using the same 8-bits that u have mentioned

---

But what will be the use of 16 bit identification no. field present in ipv4 header it has the capability to uniquely identify upto 2^16 packets.

---

Hosts in IPv4 Network:

• Each host has a globally unique IPv4 address, which can be represented as a 32-bit number.
• Example: 192.168.0.1 → 11000000 10101000 00000000 00000001 (32 bits).

Answer 2

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

Comments

But what will be the use of 16 bit identification no. field present in ipv4 header it has the capability to uniquely identify upto 2^16 packets.

---

Don't 😭

---

very much confusion

Answer 3

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

Answer 4

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)

Comments

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

---

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

---

I guess it has something to do with resolution of clock but I don't understand it

---

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?

---

The 32 bits are that of the IPv4 address itself. Thus these 32 bits are already unique.

---

@Akash Kanase Sir, @Arjun  Sir,

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

https://gateoverflow.in/204099/gate2018-25

---

Well official answer was 256 only.
https://gatecse.in/w/images/9/9e/Key_CS_03.pdf

---

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

---

I agree here.

Why are they not replying?

Answer 5

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?

Comments

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

---

why?? Its so unfair

---

@Arjun Sir, I think question is NAT type so no negative marking..

Sorry for irrelevant comment

Answer 6

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.

 

 

Comments

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

Please Correct it. 

---

Done!

Thnaks @ayushsomani!