How many bits for sequence number using Go-Back-N protocol

Question

I'm a regular over at Stack Overflow (Software developer) that is trying to get through a networking course. I got a homework problem I'd like to have a sanity check on. Here is what I got.

Q:

A 3000-km-long T1 trunk is used to transmit 64-byte frames using Go-Back-N protocol. If the propagation speed is 6 microseconds/km, how many bits should the sequence numbers be?

My Answer:

For this questions what we need to do is lay the base knowledge. What we are trying to find is the size of the largest sequence number we should us using Go-Back-N. To figure this out we need to figure out how many packets can fit into our link at a time and then subtract one from that number. This will ensure that we never have two packets with the same sequence number at the same time in the link.

Length of link: 3,000km Speed: 6 microseconds / km Frame size: 64 bytes T1 transmission speed: 1544kb/s (http://ckp.made-it.com/t1234.html)

Propagation time = 6 microseconds / km * 3000 km = 18,000 microseconds (18ms). Convert 1544kb to bytes = 1544 * 1024 = 1581056 bytes Transmission time = 64 bytes / 1581056bytes / second = 0.000040479 seconds (0.4ms)

So then if we take the 18ms propagation time and divide it by the 0.4ms transmission time we will see that we are going to be able to stuff ( 18 / 0.4) 45 packets into the link at a time. That means that our sequence number should be 2 ^ 45 bits long!

Am I going in the right direction with this?

Thanks, Mike

Answer 1

To figure this out we need to figure out how many packets can fit into our link at a time and then subtract one from that number. This will ensure that we never have two packets with the same sequence number at the same time in the link.

I do not agree with this reasoning. The point of not having two packets with the same sequence number will be achieved by the protocol entities not sending frames outside the window. You should distinguish between the window size, N, and the sequence number range. There is no problem in using 32 bit sequence numbers for a window of just say 5 frames, although this would of course not be optimal.

If transmission time in one direction is 18ms then you will have a RTT, round trip time, of 18ms + receiving end processing time + 18ms. I have no idea of what values of processing time that are sensible in this case, so let's just assume zero for simplicity. That gives a RTT of 36ms. That means that from the point you send a frame it will (in best case) take 38ms before you get an acknowledgement on that frame. That determines the upper limit on how much outstanding data that makes sense to have when deciding on a window size. If you have a bigger window size it will only fill the transmit buffer on the sending side and not affecting the throughput. There might very well be other factors (e.g. buffer size on the receiving end) that limits the window further, but since no information is given for this, let's assume the receiving end have unlimited buffers etc.

For optimal (throughput) performance the window should be large enough so that the sender can send 38ms continuously. The T1 speed is 193000 bytes per second. With 64 bytes per frame that corresponds to 3015.625 frames per second. 0.038 times 3015.625 gives 114.59375. That is, in 38ms you can send 114 frames. Therefore a window size of slightly larger than theoretical maximum (e.g. 115-120) can be chosen (so that the limiting factor is the physical link and not the window size). The sequence number range have to be larger than the window size, and in this case 128 is a close maximum value.

So the answer to you question is, you need minimum 7 bit for sequence numbers in this case. See also here for an interactive go-back-n java applet.