CSE 222

Graduate Communication Networks

Winter 2001

Midterm Project Assignment


PART A: Rate-based congestion control

For this question, you will simulate and evaluate different algorithms for adjusting the rate of a simple-minded rate-based congestion control scheme. The code you will be working with is in $NS/midterm/rc.tcl on the APE lab machines or can also be downloaded here. For your information, this is just a slightly modified version of rc.tcl that is part of the standard ns source tree in $NS/ns-2/tcl/ex. You will experiment with the rate increase/decrease algorithm by modifying the "increase" and "decrease" methods of class Agent/Message/Sender.

The scheme implemented by this module is as follows. A sender transmits data packets at some fixed initial rate. At randomized intervals (uniform over 50ms to 150ms), the sender transmits a probe packet to the receiver. Upon receipt of a probe, the receiver sends an ACK back to the source if it deems the network "uncongested". Otherwise, it ignores the probe. When the sender receives such an ACK, it increases its sending rate by calling its "increase" method. When the receiver detects packet loss, it immediately sends a "congested" notification to the source. When the source receives such a packet, it decreases it rate by calling the "decrease" method. After detecting congestion, the receiver waits an extra probe packet before sending back an ACK (to give the source a chance to adjust its rate etc.)

  1. Modify the rc.tcl script to log each rate change to a file and plot it (vs time) for each of the two flows (Hint: To obtain the indentity of the flow (1 or 2) you can use [[$self set udp_] set class_] inside increase/decrease methods). Similarly, plot packet loss at the receiver (vs time). Does the protocol react appropriately to losses? Is the protocol stable? Is it fair?

  2. Update the script to calculate the total number of dropped packets and the total amount of data that got through. Experiment with the increase/decrease methods. Try altering the step size and experiment with the four different combinations of multiplicative and additive changes. What is the best policy in terms of dropped packets, throughput? Can you tune the parameters for the particular network topology defined in rc.tcl?

  3. Change the link delay between nodes 2 and 3 from 10ms to 100ms. How is performance impacted?

  4. Modify the protocol to dynamically compute a round-trip time estimation and use this estimator to choose the interval between probe packets. (Hint: ACK packets already contain the timestamp from the corresponding probe packet, and it can be retrieved inside sender's handle routine using [lindex $msg 1]). Does your modified scheme solve the problems encountered in question 3? Describe the formula that you used.


PART B: Fair Queuing

In this problem, you will study the performance of Fair Queuing in comparsion with a simple FCFS scheduling policy. A good paper about Fair Queueing can be found on the midterm overview page. There is also a description of the algorithm in section 6.2.2 of the textbook. You will use the file $NS/midterm/fq.tcl on the APE lab machines that can also be downloaded here (this one is part of the ns source tree, too). Don't worry about the complexity of this script -- you won't have to modify it much (even the code for generating the graphs is there).

  1. Explain in your own words how the fair queueing algorithm works. Be sure to give some details. For example, be sure to answer one of the following:

    By the way, the heart of implementation of fair queueing in ns is located in file $NS/ns/fq.cc for those who are curious to see whether the formula in the paper/textbook matches the reality.

  2. Using fq.tcl, run a 40 second simulation of two TCP sources with the topology defined by the "build_topology" routine. As you can see, the routine places one TCP source at node 0 and one at node 1 both sending to a sink at node 3. Use a FIFO router with drop-tail drop policy for node 2. (You can specify FIFO or FQ as the second argument to build_topology envocation.) Generate two TCP sequence-space plots on the same graph (use the "finish" proc in fq.tcl). Do the connections receive equal shares of bandwidth? Why or why not? The finish proc will print out the highest sequence number of achieved by each connection, which you can use to compare throughputs. Are packet drops distributed equally between the two connections? Why or why not?

  3. Now repeat the experiment from question 2 but use a fair-queueing scheduler with drop-tail drop policy at node 2. Do the two connections receive equal shares of bandwidth? Are packet drops distributed equally between the two connections? Why or why not?


WHAT TO TURN IN

Submit the midterm project via email (to Geoff and Dmitrii). The body of the message should contain answers to the questions listed above. Please, be thorough in your analysis. List all parameters and formulas that you used. Use number of dropped packets and total number of transmitted data in your discussion.

Also you will need to submit the following plots in JPEG format as attachments to the message:

Please, keep the images reasonably small (620x440 as generated by gnuplot is perfect). You can generate JPEGs by capturing a portion of the screen with xv or a similar Windows image editor. The reason for using JPEG is that it is more or less the same on all platforms, what cannot be said about PostScript. This way you are free to use graphing software of your choice (e.g. gnuplot or Excel) and I can still view the results.
dzagorod@cs.ucsd.edu