GATE CSE 2009 | Question: 47

Question

While opening a $TCP$ connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low order $32$ bits of the counter of the ToD clock is to be used for the initial sequence numbers. The clock counter increments once per milliseconds. The maximum packet lifetime is given to be $64$s.

Which one of the choices given below is closest to the minimum permissible rate at which sequence numbers used for packets of a connection can increase?

• A. $0.015$/s
• B. $0.064$/s
• C. $0.135$/s
• D. $0.327$/s

Comments

@Parikhit_Kurmi @Patel_And_Patel The question is poorly framed but from the sentence they have given "minimum permissible rate at which sequence numbers used" they are asking the minimum bandwidth possible?

we know , 

wrap around time = sequence number / bandwidth

1) wrap around time is inversly proportionaly to bandwidth (ie wrap around time ∝ 1/ bandwidth)

2) sequence number is directly propotional to bandwidth (ie bandwidth ∝ sequence number)

 

so to decrease bandwidth we can decrease the number of sequence number, 

Minimum bandwidth = 2^0 / 64 sec = 0.015625 sec, Option A is correct :)

---

S_Sandeep

i think you have taken wrong unit here...unit should be 1/sec

Minimum bandwidth = 2^0 / 64 sec = 0.015625 sec

you have written " to decrease bandwidth we can decrease the number of sequence number, Minimum bandwidth = $2^0 / 64$ sec". 

This technically not wrong correct.. because in TCP, the sequence number field is fixed at 32 bits, giving a static total space of $2^{32}$ sequence numbers (bytes). You cannot arbitrarily change the TCP header sequence space to $2^0 = 1$.Ur explnation might need some correction be like : --> If a packet stays alive in the network for $\text{MSL} = 64\text{ seconds}$, sequence numbers must not repeat faster than once every $64\text{ seconds}$.The minimum rate at which sequence numbers change per second to ensure at least 1 sequence step occurs over 1 packet lifetime is:

 

---

Because the problem gives no packet size, no data rate, and no bandwidth, we cannot use the usual wrap-around calculation
(2^{32}sequence numbers / 64 s).

Instead, the only hard safety constraint left is:

A sequence number that has already been used must not be reused while any old packet carrying that number could still be alive in the network.

That lifetime is 64 seconds.
Therefore the slowest rate at which we are allowed to introduce new sequence numbers (while still guaranteeing that duplicates cannot collide) is simply

164≈0.015 per second.\frac{1}{64} \approx 0.015 \text{ per second}.641​≈0.015 per second.

That is why the question asks for the minimum permissible rate, and why the answer is driven purely by the maximum packet lifetime.

Answer 1

One of the very rare ambiguous question in GATE. It is ambiguous what the question asks for 

minimum permissible rate at which sequence numbers used for packets of a connection can increase

It is not meaningful to use "minimum" with "can increase" - should be either "maximum" with "can" or "minimum" with "should/must"

Now the second problem, 

rate at which sequence numbers used for packets of a connection

In TCP, once the Initial Sequence Number(ISN) is set, the increase in sequence number is determined by the data sent rate - for every 8 bits, it increases by $1.$ If the question is asking for this rate, then it is independent of the ISN and depends on the packet lifetime and number of possible sequence numbers. With $32$ bits we have $2^{32}$ sequence numbers possible and to avoid using the same sequence number while a packet with one is still alive, we should ensure no more than $2^{32}$ sequence numbers in a packet lifetime which is given as $64s$. So, maximum increase possible for sequence number will be $2^{32}$ in $64s$ which will be $2^{26} /s= 64M/s $ corresponding to a data rate of $64 \times 8 = 512 Mbps.$ This is not in the option.

Now the other possible meaning of the question is the rate at which the ISN of a packet can increase. This problem comes when a connection gets aborted and re-established (i.e., same IP and Port addresses at sender and receiver) very soon. In this case, receiver might get confused if it gets any sequence number which might have been used by the old connection. To, avoid this the new sequence number must be used only after all previous ones are dead. i.e., only after Maximum Life time of a packet which is $64s$. (Page 29, TCP Specification) This ensure that ISN can change only once in $64s$ giving the rate change as $1/64 = 0.015/s$ which is option A. (Even though, the ISN is changing only once, as per the question the new ISN is not old ISN +1 but old ISN + time passed in milliseconds)

Option A.

Comments

@Arjun, I know this question is any way super weird but I want to ask: if the ISN can only increase once every 64 seconds does this mean we cannot initiate a new TCP connection during this time?

---

I understood that to make new connection it should wait for 1 MSL(maximum segment length). But why it is limiting the change of initial sequence number which is happening in the local clock of the host.

---

So packet numbered  x is sent but at the the same instant connection is restablished. Now the seq no x should not coinicide with The ISN of the new connection(new connection but same client-server).

So , max time gap between generation of x and isn is asked .

Answer 2

Answer is option (A) .

$3$ information present in the question.

1. The low order $32$ $bits$ of the counter of the ToD clock is to be used for the initial sequence numbers - That means only $32$ $bits$ are used to represent a sequence number. So, we have$ 2^{32}$ different sequence number.
2. The maximum packet lifetime is $64s$. So, by $1$ & $2$ we can calculate maximum data rate possible(bandwidth) to avoid the wraparound= $2^{32}/64= 2^{26}$ Bytes/sec.
3. The clock counter increments once per milliseconds -That means when then counter increments next possible sequence number is generated.

Suppose we make a TCP connection by picking initial sequence number that is derived by clock.If the connection terminate after sending few bytes of data then to avoid the ambiguity of sequence number we don't reestablish the connection immediately because of counter increment happen after $1$ msec.

Suppose the sender sends $2^{24}$ Byte data.

Time required to send $2^{24}$ Bytes data is $2^{24}/2^{26} =250 $ ms. So, $2^{24}$ Bytes takes $2^{24}$ sequence number . ($2^{24} \times 1)$ ms required to increment the counter .

So, the permissible rate of sequence number used for packets is in 64 sec we use only sequence number .

So, $1/64= 0.015$ (approx) which is option A here.

Comments

Can someone please help me, please? As far as I can understand, Max possible Bandwidth is 2^26 Bytes/sec. Since, TCP gives a sequence number to every byte, 2^26 sequence numbers are needed in a second. But the counter only generates 1000 sequence numbers in a second.

How is the counter generates only 1 sequence number in the packet lifetime of 64seconds. I mean if 1000 sequence numbers are generated in a second, wouldnt it be like 64000 sequence numbers in a packet lifetime?

Is ToD counter controlled by TCP? How is it that 2^24ms is needed to increment the counter when it is clearly stated that the counter gets incremented every 1 ms?

---

@gargi

I am understading that counter increments at every 1 ms. And as it increments it will produce a new sequence number. So in 64 seconds which is equal to 64000 ms there would 64000 sequence number.  I am getting confused. Can anyone clear this doubt?

---

they never said sequence number will increase along with the clock .......
so for the minimum bandwidth the sequence number will be consider an increment of one
one upon 64 and that is .....

Answer 3

A. Because sequence number is incremented once every 64 sec.

Rate = 1/64=0.015

Comments

@Arjun sir.. please help !

---

Why is sequence number incremented once every 64seconds?

---

It is incremented once 64 sec the only it will satisfy wrap around time condition if a seqence number is generated before 64 sec they map to same value since TCP used random intial sequence genarator

Answer 4

• To answer this question. we should know a bit about TCP Sequence numbers.
• Also, note that the question is worded extremely poorly. Packet is used, in place of Segment. And the last line of the question is criminally faulty.

How TCP ensures in-order delivery?

All the segments are given unique sequence numbers, through which the receiver can know the sequence of segments. The first TCP segment is given a random sequence number, sometimes called the Initial Sequence Number, or ISN.

---

Now, the sequence numbers of the next segments (after the first segment) depend on the ISN.

Suppose, ISN = 500. And each packet has 20 Bytes.

»Sequence number of second packet = 520

»Sequence number of third packet = 540

»Sequence number of fourth packet = 560... and so on.

Sequence number actually tells you the number of the first byte of the segment.

---

 

Now, coming to the question, it asks when can the ISN be changed? (Read the question thrice, first)

Given that, ISN depends on a ToD clock's last 32 bits. This clock increments every millisecond. So, we can change ISN every millisecond, ie,  $1/10^{-3}$ or 1000/second. 

---

This would be wrong because then, the sequence numbers would change abruptly.

Suppose, ISN = 500. And each packet has 20 Bytes.

»Sequence number of second packet = 784

»Sequence number of third packet = 116

»Sequence number of fourth packet = 9744... and so on.

How would the receiver know the sequence here? It can't.

---

 

We're given that a segment lasts 64 seconds maximum. So, for 64 seconds, whatever sequence numbers we're adding to our segments, need to depend on ISN.

After 64 seconds, the first packet expires, hence, the ISN expires and the sequence numbers of the following packet stop making sense. So, we need a new ISN now.

Hence, we can do it once every 64 seconds = 1/64 = Option A.

---

Using this, Sequence numbers would look like:

Suppose, ISN = 500. And each packet has 20 Bytes.

»Sequence number of second packet = 520

»Sequence number of third packet = 540

»Sequence number of fourth packet = 560.

New ISN = 800.

»Sequence number of fifth packet = 800

»Sequence number of sixth packet = 820

»Sequence number of seventh packet = 840... and so on. Which is fine.

---

 

Option A.

Comments

This would be wrong because then, the sequence numbers would change abruptly.

Suppose, ISN = 500. And each packet has 20 Bytes.

»Sequence number of second packet = 784

»Sequence number of third packet = 116

»Sequence number of fourth packet = 9744... and so on.

@ JashanArora kindly explain this part

---

@once_2019,

I think he wanted to say that, As clock is changing in every millisecond so the sequence number could be changed every Second. Is there any point in changing changing sequence number every millisecond?

Every packet will present in TCP should have a ISN, after 64 second packet will be no more and ISN will be no more.

the next packets will copy the sequence number as ISN + length of data in previous packets. When ISN is changing in 1 millisecond or very fast then the sequence numbers of next packets will also follow the the ISN, and also very fast, suppose we sent a packet with x Sequence of number, after fraction of time ISN changes, then next sequence number of next packet will also changed, this Leeds to show some abnormal sequence number, and to the receiver this will make no sense.

I think this will help, Correct me if I'm wrong.

---

Got it . Thanks 🙏

---

Thanks.

But as SYN will consume one byte for TCP connection, first packet will start from 501 and then +20 after that right ?

Answer 5

To find the minimum permissible rate of sequence no, we need to consider the packet life time. We need at least the rate such that it generate only one sequence no in packet life time i.e in 64 sec.

So , the minimum rate is =1/64 = 0.015/sec.

Comments

What is the meaning of Permissible rate?

Answer 6

Here not any problem like ambiguity.

since if we increment 1 per 1ms and life time of packet is given 64s. But i think question is not asking in this scenario.TCP uses Sliding Window Protocol.

Here Minimum Permissible rate may be confusing but think like that if life time of packet is given 64s so this is max . Means if we increment seq.no per 64 sec is allowed but more than 64s should not be allowed. If we keep more than 64s for 1 sequence number we need to wait for next sequence without any reason.

so ans should be=1/64s = 0.015/s

Comments

@papesh,

 "sequence number used for a packets of a connection" does it mean that we are not talking about a single byte or single packet but packets of a connection in SWP. But for each byte of a packet withing 65 sec we have to increment seq number then why we are not considering this fact.OR we are just considering the seq number of packet.

for eg A connection of TCP sending two packets with 100 bytes in each packet and intial seq number of packet is 100.then

Packet 1(seq number from 100 to 199)

and packet 2(seq number from 200 to 299)

withing 64 sec these seq number will be live so after that for a new connection we have to assign new seq number for packets.If we increment before 64 sec then there is no problem still the new connection will get a seq number.BUT if we wait suppose for 70 sec then for establishing a new connection we have to wait for 6 more sec to get a seq number for our connection.

Is my understanding correct or I am missing something?