Lab: Congestion Control Part 1
In this lab, you will add congestion control to your reliable transport protocol. You will use the simulator to examine the correctness of your implementation.
Implement congestion control using TCP Tahoe as your model. This should include the following features:
Slow start. At the start of the connection, or after any kind of loss event, set cwnd (congestion window) to 1 MSS. Every time the sender receives an ACK for new data, increment cwnd by the number of new bytes of data acknowledged.
Threshold: Stop slow start when cwnd exceeds or equals the threshold. Start with a threshold of 100000 bytes.
Additive Increase: Once cwnd is larger than the threshold, use additive increase. Every time the sender receives an ACK for new data, increment cwnd by MSS*b/cwnd, where MSS is the maximum segment size (1000 bytes) and b is the number of new bytes acknowledged.
Fast Retransmit: A loss event is detected when there are three duplicate ACKs (meaning the fourth ACK in a row for the same sequence number), and TCP immediately retransmits instead of waiting for the retransmission timer.
When a loss event is detected (a timeout or 3 duplicate ACKs), then set the threshold to max(cwnd/2,MSS) and set cwnd to 1 MSS.
Create a script that can produce the following type of graph:
- Sequence plot. On the X axis, plot time. On the Y axis, plot the sequence number divided by 1000 and mod 50. Each time a packet is transmitted by TCP (it is placed into the queue on the link), plot a square box at the appropriate X and Y values. If the packet is dropped, plot an X instead. In addition, each time TCP receives an ACK, plot a dot at the appropriate X and Y values.
You can use the TCP Plotting using Python GitHub repository for sample plotting code.
Use a series of tests to demonstrate that your congestion control algorithm works properly. Use a sequence plot graph to verify the correct behavior in each case.
Slow start: Transfer a small file such that the entire transmission occurs during slow start, with no loss. The window size should grow to cover at least 32 packets.
Additive increase: Repeat the above experiment, but with a slow start threshold of 16000 bytes (16 packets). Show that the rest of the transfer transitions to additive increase, with no loss.
AIMD: Repeat the slow start test, but with a large threshold and a single packet dropped when the window has grown to 32000 bytes (32 packets). You can do this with a small queue size on the link. Show that when the loss occurs TCP restarts slow start up to a smaller threshold and then continues. Be sure the file is large enough to reach additive increase again after the loss.
Burst loss: Repeat the AIMD test with multiple packets being lost at once. Show that Tahoe resets to slow start and recovers normally.
As a guide, use the graphs shown in the SACK paper we covered in class.
Write a formal, scientific report that includes the following:
Congestion Control: Describe in detail how you implemented congestion control. Use figures where appropriate. Do not include all your code, but you may include small sections to illustrate your algorithm.
Tests: Describe each test, include your graphs, and discuss whether you got the expected results.
Write using a formal, scientific report style. Your report should be written as if you are explaining your work to another CS student, and they need all of the details of what you did so that they can replicate your experiments.
Your report can be any length, as long as you thoroughly describe your project and results. The paper must use 11 point type, single spacing, and one column per page.
Your code should be located in a directory called lab3 in the top level:
bene/ src/ examples/ lab3/
Turn in a tarball that includes all of your code (for the simulator, experiments, graphing, etc), and a PDF of your report:
tar -czvf bene.tgz bene
using Learning Suite.
This lab is worth 150 points, and will be graded using the following rubric:
50% for partial work that indicates substantial effort was made
70% - 80% for C quality work (Congestion control tests partly work, the report is well written.)
80% - 90% for B quality work (Congestion control tests mostly work, the report is fair.)
90% - 100% for A quality work (Congestion control tests all work, and the report is well written.)
Extra 15 points for implementing Fast Recovery (Reno), which sets the congestion window to 1/2 the previous value instead of 1 MSS when loss is detected via duplicate ACKs. You must be able to show Tahoe style congestion control in the rest of your report, and this section must use a sequence number plot to validate accuracy. Full points if you can show Reno reacting poorly to burst loss, like in the SACK paper.
To get full points, all experiments must work well and the report must be complete and written with a scientific style.