CSE 461
Homework 2 Solution

1a.
	Latency = Propogation Delay + Transmit Time
		= 2ms + 8*8192 bits / 10 Mbs
		= 8.55 ms

1b.
	Latency = Latency from A to B + Latency from B to C
		= 8.55 ms (from above)+ 10 ms + 8*8192 bits /1.5 Mbs
		= 62.2 ms

1c.
	Number of packets sent from A to B as a function
	of time (t) is:
		Num packets = (t - 2ms) * (10 Mbs / 8192*8 bits/packet)
			    = (t - .002) * 152.58 packets/second
	Number of packets leaving B to C as a function
	of time is:
		Num packets = (t - 8.55ms) * (1.5 Mbs / 8192*8 bits/packet)
			    = (t - .00855) * 22.89 packets/second

	Subtract packets departing from packets arriving and 
	solve for when the difference equals 10:

		((t - .002)*152.58) - ((t-.00855)*22.89) = 10
		t = (10 + (.002*152.58) - (.00855*22.89)) /
			(152.58 - 22.89)
		t = .07795
		  = 77.95 ms

	Correct analytical solutions will continue with the following
	analysis:

	Number of packets sent to B in 77.95 ms =
		10 Mb/s * 77.95 ms / 8*8192 bits/packet
		= 11.89 packets

	Since last 0.89 packets can't be received (i.e. must either
	receive the whole packet into a buffer or drop it completely),
	12th packet is dropped on arrival.

	Time at which 12th packet arrives:
		= 11 * 8 * 8192 / 10 Mb/s + 2ms propogation delay
		= 74.1 ms

	How often will B drop packets?
		The answer to this question is simply the difference in
		the transmission rates between A/B and B/C expressed as
		packets per second:

		= (10Mb/s - 1.5Mb/s) / 8*8192 bits/packet
		=  B will drop 129.70 packets / second

	If B's queue is increased to 20, B will still drop packets
	at the same rate after the queue is filled.

1d.
	Assuming that the acknowledgement takes no transmission time 
	(i.e., only propogation time), the acknowledgement will arrive
	back at A in:
		Time for first packet to get from A to C + 
		Time for acknowldgement to get from C back to A

		62.2 ms (calculated in 1b) +
		12 ms

		74.2 ms.

	Number of packets A transmitted in this time:
		(10 Mb/s / 8*8192 bits/packet) * 74.2 ms
		11.3 packets

	Does B's queue overflow?
		Yes

	NOTE: if you assumed that the queue size for 1d was 20 (the
	wording of the problem was unclear) the answer is no.

2a.
	Propagation delay for 20Km fiber link with speed of light
	being 2x10^8 m/s =
		20 Km / 2*10e8 = 0.0001 s = .1 ms = 100 us

	
2b.
	A suitable ARQ timeout value should be at least bigger than 
	round trip time, so at least 200 us. 

2c.
	Acknowledgement and/or packet may be corrupted or lost due
	to transmission errors, thus we still may have to retransmit.

3.
	Once RWS equals SWS, the receiver can buffer any frame that
	the sender sends, so no need for a larger RWS.

4.
	Under different assumptions there are two different answers
	for this question. If you state that you  assume that
	the receiver can not receive out of order and that packets
	are strictly FIFO, then the answer is enough bits to encode
	a sequence number 1 larger than the desired window size, which
	is:

	ceiling (log base 2 ((Round Trip Time * Transfer Rate / Packet Size)+1))

	ceiling (log base 2 ((1.25 sec. * 2 * 1 Mb/s / 1024*8 bits/packet) + 1))
	ceiling (log base 2 (306.17))
	ceiling (8.26)
	9 bits

	Without these assumptions, the answer should be twice the 
	window size which is:

	ceiling (log base 2 ((Round Trip Time * Transfer Rate / Packet Size)*2))
	ceiling (log base 2 ((1.25 sec * 2 * 1 Mb/s / 1024*8 bits/packet)*2))
	ceiling (log base 2 (610.35))
	ceiling (9.25)
	10 bits

5.
	The reciever would need an extra timer if the sender did not
	probe because once the advertised window falls to zero, the
	sender will cease sending packets and since the advertised window
	is set in an acknowledgement packet, the sender will never discover
	when the window is no longer zero. The extra timer on the receiver's
	end would be needed to discover when the window was no longer zero
	and to signal the sender of this fact.

     ANDY'S ANSWER:

        The receiver can recognize when there is space because it will
happen when the receiving application reads from the buffer.  This
should be a fairly easy check to add.  The problem is that the packet
telling the sender to restart might get lost, and that would have to
be resent.  The algorithm of the receiver continually waking up and
sending a message if there is space is sufficient, but in reality you
only need to do this between when space was made available and when
you start getting data again.

6. 
	For the sequence number, you need enough bits such that you
	don't reuse a sequence number within the maximum segment lifetime.
	We can find this by computing how many sequence numbers the 
	network could possibly use within the specified segment lifetime
	and make sure that the number of bits used in sequence number
	can encode at least this number. So the solution is:

	ceiling (log base 2 ( Transfer Rate * Max. Seg. Life.))
	ceiling (log base 2 ( 100 Mb/s * 60 sec / 8 bits/byte))
	ceiling (log base 2 (7.5e+08))
	ceiling (29.48)
	30 bits

	For the advertised window, we want to be able to encode a value
	large enough to allow the sender to completely fill the pipeline
	as long as the receiver has the buffer space. To calculate this
	number we find the number of bytes that can be sent within a 
	round trip time and make sure that the advertised window can encode
	at least this number. So the solution is:
	
	ceiling (log base 2 ( Transfer Rate * Round Trip Time));
	ceiling (log base 2 ( 100 Mb/s * 100 ms / 8 bits/byte))
	ceiling (log base 2 (1250000))
	ceiling (20.25)
	21 bits