Midterm solution + Project 1 Stats

• Midterm solution is posted (under “assignments” section of the course’ webpage)
• Statistics for Project 1: (email one of the TAs for grade)
• CSE 489:min = 20, max = 100, average = 79.25, median = 85

• CSE 589: min = 20, max = 100, average = 70.79, median = 80

Some statistics for HW1

• CSE 489: min = 21, max = 50, average = 38.1, median = 39
• CSE 589: min = 29.6, max = 54, average = 45.6, median = 46
• The maximum possible score is 60. (10 points per problem.)

Solution to assignment 2 posted

There might be some errors in there. Please check and post questions ASAP before the midterm. Questions should be on the comment part of this post.

Sample midterm exam posted

You can find it here. I will not post the solution.

Programming Project 2 Posted

• The source code for my implementation of Project 1 is posted. Please at least take a glance. If you didn’t finish Project 1 properly, there are probably quite a few things you can learn from it.
• Project 2 is out. Due on Dec 11. You have to start early. All questions about the description should be posted as comments to this post.

A simple model for TCP congestion control

Network congestion is unavoidable under the “best-effort” paradigm. There are several ways to deal with congestion. TCP chooses to dynamically adjust the sending rate. When there’s congestion, reduce the rate; otherwise increase the rate. We want the total load on any link (total data rate sent by all users using that link) to be oscillating around a knee point. When the load increases pass the knee, congestion becomes exponentially worse. “Users” are the TCP connections whose paths go through the link.

As a simple model, we can view the problem this way: the “network” is either congested or not, the “users” can detect congestion either by automatic inference or by explicit feedback from the “network”. The key questions are: (1) how fast should the rate increase be when the network is not congested, (2) how fast should the rate decrease be when the network is congested, and (3) what exactly is (are) the main optimization objective(s)?

We can answer these questions roughly with a simple control model. Say there are users. At time user sends data with rate . The network gives a feedback (implicit or explicit) which is if there’s no congestion and if there’s congestion. The users are supposed to adjust their sending rate accordingly.

Thus, we want to find a function which helps the rate adjustment:

What properties should this rate adjustment function satisfy? There are four main criteria:

• Efficiency: let be the target total rate, and . Then network is congested at time if , in which case the feedback is ; otherwise, . We want to increase the total load toward the goal when and decrease the total load when . Thus, it should hold that
  , and
  .
• Distributedness: the adjustment for one user cannot be dependent on the rates of other users or the total number of users. There’s no way, in a realistic scenario, for a user to know precisely the sending rates of other users and the total number of users in the network.
• Fairness: there are many ways to define this tricky notion. We will take the most obvious one: the rates should be roughly equal. The fairness level at time is defined to be:
  .
  This function has several nice properties: (a) , (b) if one user takes all the channel capacity, (c) if the rate allocation is totally fair.
• Convergence: we want our adjustment protocol to “converge” nicely to good efficiency and fairness.

There are infinitely many functions to choose from. The first thing to try is always a linear function of some kind. Let’s consider the family of functions defined as follows:

(the subscript ‘I’ stands for ‘increase‘)

(the subscript ‘D’ stands for ‘decrease’)

As long as the coefficients do not depend on and the sending rates, the distributedness property is satisfied. Consider the efficiency property, which requires that

(1) , for any and , and

(2) , for any and . (The only way for the network to be congested is for .)

Condition (1) requires that and .

Condition (2) requires that and , and that (i.e. the equalities cannot hold at the same time).

What about the convergence to fairness requirement? To simplify notations, let be either or and be either or depending on whether or . Also, define . Then, we want and that eventually increases as increases.

For , we will need . Moreover, is an increasing function in . Thus, for good convergence to fairness we will need to be as large as possible. Thus, we must either have

and , or

and .

Since must be of the same sign, and , and they cannot be both negative (or else we’ll have negative rates). It must hold that and . Thus, during congestion (no improvement in fairness). When there’s no congestion, we should try to improve fairness as much as possible. In particular, for to be large in the no congestion case, we want to be as small as possible, which is .

We have nailed down our function to be:

(the additive increase phase)

(the multiplicative decrease phase)

If we only care about fairness, then obviously should be really large. However, setting to be large will overshoot , resulting in very large smoothness. Finding optimal values of requires complete knowledge of the system, which is impossible. TCP does that experimentally. It is also easy to see that an increase in responsiveness will result in a decrease in smoothness.

Project 1’s due date/time

is supposed to be 1am Oct 12, i.e. Sunday night.

How to send a TCP “packet”?

There have been a few (very late, I might add) questions about how to send a TCP packet. There are typically 2 ways to do this:

int32_t a=1;
int16_t b=2;

writen(sock, &a, 4);
writen(sock, &b, 2);

or

char s[6];

memcpy(s, &a, 4);
memcpy(s+4, &b, 2);
writen(sock, s, 6);

If you write a struct, you might run into memory alignment problems which make your program not inter-operable with mine.

If you start project 2 this late, you will not be able to complete it. So please, start early!

How to submit your programming project

Suppose you put all source files in a directory named project1

• tar -cvf project1.tar project1/*
• submit_cse489 project1.tar or submit_cse589 project1.tar, depending on which course you’re registered for.

If your have special compilation instructions, please put them in a README file in the directory project1. If it’s just a simple make, then you do not have to create the README file. It may still be helpful to put the names and IDs of you and your partner in the README though.

Finally, if you have any “special” explanation on how your program works (or, more bluntly, how and in which way it doesn’t work), please put them in the README file.

A few announcements

• There’s a small update to lecture 10 (one slide added on timer management).
• Lectures 11 & 12 uploaded.
• Solution to homework 1 uploaded.
• Homework 2 uploaded. Due on Monday, Oct 19. This homework probably takes more time than hw1. Please be warned.
• Grading criteria for programming project 1 uploaded.