QUESTION: Consider the problem of flow control on the link from Alice
to Bob. The transmitting application at Alice wants to download a huge
file to Bob, but the receiving application at Bob is sometimes busy
with other work. When Bob is busy, he must be able to make Alice slow
down or else his receive buffer may overflow and cause packets to be
lost. Assume that:
- The link can carry 1000 fixed-size packets/sec;
- The one-way propagation delay from Alice's data link controller
to Bob's data link controller (or Bob to Alice) is 5 milliseconds;
- Alice is always capable of transmitting 1000 packets/sec (PPS);
and
- Bob's application layer can process either 1000 PPS or 10 PPS
according to the following pattern: between time 0 and 4 seconds he can
receive 1000 PPS, between 4 and 5 seconds he can receive 10 PPS,
between 6 and 9 seconds he can receive 1000 PPS, and so on.
PART (a): If the two data link controllers use Stop-and-Wait, what is
the maximum throughput that can be achieved in PPS, assuming the length
of the ACKs is very short? [HINT: draw a space-time diagram of the
system]
PART (b): Suppose Bob's data link controller returns an ACK as soon as
it receives a frame and checks that the CRC is valid. Can his receive
buffer overflow under Stop-and-Wait? If not, explain why not. If so,
then when should he return the ACK?
PART (c): Ignoring errors, is a sliding window algorithm with a
transmit window size of 20 packets large enough to allow Alice to
transmit at
full speed when Bob is not busy? Explain.
PART (d): During each 5 second period, Bob is capable of receiving a
maximum of 1000 PPS for 4 seconds and 10 PPS for 1 second, for a total
of 4010 packets over 5 seconds, or an average of 802 PPS. Thus, Alice
could transmit at a constant rate of 800 PPS without Bob
exceeding the average
rate at which Bob can receive packets. How large would Bob's receive
buffer need to be to avoid dropping packets in this case?
PART (e): Suppose Alice and Bob are using a sliding window algorithm
with a transmit window size of 20 packets. Bob wants to delay the ACKs
in order to force Alice to slow down when he is busy with other work.
What is the minimum size for Bob's receive buffer if he never wants to
make sure he never has to drop any packets because of buffer overflow?
Briefly describe the algorithm he would use to decide when to return an
ACK. Your algorithm should allow them to transfer data at the maximum
rate of 802 PPS.