How the TCP works ?

In the course probabilistic algorithm, we talk about how the TCP works. In fact, what we do on the course is a reverse engineering, that is, we know the policy taken in our reality and then try to find the philosophy behind.

What the TCP does?

What TCP does is very simple. When we send the pocket on Internet, there are always limits for the bandwidth. The PC will increase the number sent if it receives a success signal in order to accelerate the speed, but divide by 2 to avoid the traffic problem if it receives a signal of failure.  Intuitively, this is a good strategy, but what it achieves?

A general model

Inspired by the model in economics, we apply the model of optimization. In this model, we aim at a function of utility and some limits. In our problem, the limit is clearly the physical limit: the sum of flux cannot be greater than the admissible one. But the goal function, in fact, can be very different. There are max-min, proportional function, alpha weight function. The TCP is just one specific case of alpha weighted function.

Technique part 1: primal algorithm

The next problem is that what can we do when facing a general optimization problem. We ca ignore the condition and just treat the relaxed question and apply the primal algorithm. The Lyapunov function and ODE theory assures that this method converges.

Technique part 2: Lagrange  multiplier and dual method

A second method which treat the problem directly is the theory of optimization. Maybe we know always the method of Lagrange multiplier method, it is correct and always correct given a good function. However, the most profound theory is Kuhn-Tucker theory and a dual problem. If we would like to minimiser the function, we can minimiser given the parameter, and then maximiser the parameter. This procedure always works if we find the Kuhn-Tucker vector, this is true when it has control from the lower bound. So this idea propose the dual algorithm for our question.