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

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

---

I guess some questions are just meant to be ignored. :}

---

Computer Networks: GATE Overflow Test Series | Computer Networks | Test 1 | Question: 26

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

32- bits for IP

10-bits to generate 1000 identifier [ counter may use]

8- bits are meant to be A single second.. [ for every second we use different eight bits]

For every second we have to generate 1000 Id' , ... 1 particular 8 bits from the clock generate 1000 ID's ,,,

8 bits wrap around will be after 256 times so,, 256 seconds

---

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.

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

Don’t assume anything unnecessarily 1024 to 1000 is assumed only when bandwidth is given

---

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 😭

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

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?