Advanced Computer Network Review(4)——Congestion Control of MPTCP

This article is about MPTCP To understand and sort out congestion control , References are from ：
《Design, implementation and evaluation of congestion control for multipath TCP》(NSDI’11) In class with the teacher PPT.

The question to understand in the review outline is ：

1.MPTCP The goal of congestion control
2. understand EWTCP and Coupled
3. Can be judged EWTCP and Coupled Respective bandwidth

One 、MPTCP The goal of congestion control
This part is my understanding and summary , From the paper ,MPTCP Congestion control has two goals ：
1. Make sure MPTCP The introduction of will not cause serious interference to the original network traffic ( Fairness, etc )
2. Ensure high throughput as much as possible

As the original paper said ：
The basic question we set out to answer is how precisely to adapt the subflow windows of a multipath TCP so as to get the maximum performance possible, subject to the constraint of co-existing gracefully with existing TCP traffic.

“ A basic question we intend to answer is ： How to accurately adjust MPTCP Subflow window of , In order to compare with existing TCP Get the maximum possible performance under the constraint of harmonious coexistence of traffic .( laugh )”

Two 、 understand EWTCP and Coupled
MPTCP The essence of the protocol is as a middleware of the transport layer , Its main purpose is Divide a data stream into multiple paths for transmission . One TCP Connect Manage multiple subflow, Every subflow It can be carried out in the network Free choice of route , And each of these subflow They all maintain Own a private sending window $W_r$, and MPTCP The sender of is in any subflow When there is margin in the sending window, the data will be distributed to them for transmission , The above is right MPTCP A brief summary of .

First of all, let's start with the first story , original TCP(Regular TCP) The congestion control algorithm in is as follows .

This and classic TCP Congestion control is consistent , It's like the last one BBR As mentioned in , It has some characteristics ： such as AIMD( Additive increase , Multiplicative subtraction ), Throughput fluctuates greatly , The algorithm is aggressive .

If Direct the original TCP Congestion control is used in MPTCP Scene , that MPTCP Every one of subflow All will be Independent competitor identity And the original single path TCP Stream to compete , This is obviously for a single path TCP It's very bad . As you can imagine , Suppose that RTT In the same case , A possession n individual subflow Of MPTCP, The final bandwidth obtained will be a single path TCP Of n times , It has greatly damaged the fairness of the network , Cannot be achieved with existing TCP The harmonious coexistence of traffic .

Then the first problem to be solved is Fairness , A very simple idea is to give each stream the bandwidth it can get Weighted limit , And that leads to EWTCP(Equally-Weighted TCP) Congestion control algorithm ：

There is an important conclusion about this algorithm ： every last subflow The transmission window value obtained is proportional to $a^2$, The proof of this conclusion needs to refer to another paper , Here is a brief introduction .

Then you can imagine , If you take $a=\frac{1}{\sqrt{n}}$, also hypothesis RTT Values are equal , Will eventually contain n individual subflow Of MPTCP As a whole, you can On the bottleneck chain Get and a single path TCP The same network bandwidth , Thus forcibly obtained the fairness of distribution .( One MPTCP Entity in EWTCP Under the agreement , No matter how much it governs subflow, The total bandwidth it can obtain will never exceed a single path TCP Entity )

When n = 1 when ,EWTCP It will degenerate to Regular TCP Congestion control algorithm . Besides ,EWTCP Algorithm involved MPTCP every last subflow They are independent of each other ( Because it's based on $W_r$ For congestion control ), therefore Even if there is one subflow Is blocked , Other subflow It will not become more aggressive , This ensures that MPTCP It is impossible for an entity to occupy more bandwidth than a single path TCP.

EWTCP Achieve fairness in bandwidth competition , But the paper also points out EWTCP Cannot use links efficiently ( Lack of dynamic adaptability , As it says , One subflow If it's blocked , It will not affect others subflow, however MPTCP The total bandwidth obtained is actually reduced ). A typical example cited in the paper is as follows ：

Three n=2 Of MPTCP Use EWTCP Compete for three bandwidths 12Mb/s The link to , Use EWTCP The result is The three are divided on two channels respectively 4Mb/s The bandwidth of the . every last MPTCP The total bandwidth obtained by the entity is 8Mb/s, But in fact, the optimal solution can be Every MPTCP get 12Mb/s The bandwidth of the , That is, a MPTCP Only one link , In this way, you can win hemp directly without going through the procedure ( I'm tired of writing , laugh ), however EWTCP You can't find such an optimal solution by yourself , Instead, it is executed stupidly “ It seems fair ” Suboptimal solution of .

It is pointed out in the article that , There is theoretical evidence that ： For multipath transmission , The optimal solution always migrates all its traffic to the path with the lowest congestion . And an algorithm has been proved theoretically , The optimal solution can be found adaptively without congestion detection , This is it. COUPLED Algorithm ：

among $W_{total}$ It's a MPTCP Under the jurisdiction of the entity all subflow The sum of the sending window sizes of . There are two situations to understand this agreement ：

2.1 The congestion degree of each link is equal
In this case, there is no adaptive problem of routing , That is to say, each subflow Can roughly operate according to a certain sending window size , But there is a basic law to be respected ( laugh ), That's it ： every last subflow The sending window increases and the sending window decreases , In the long run, they must offset each other , Is to solve the following equation (p Is the packet loss rate ,1-p Is the probability of successful transmission )：

Solve it and find $W_{total}=\sqrt{2(1-p)(p)}\approx \sqrt{\frac{2}{p}}$, This directly points to another important conclusion ： stay COUPLED In the algorithm, , One MPTCP Each of them subflow The sum of the total available bandwidth is only related to the link packet loss rate , This proves COUPLED Have Natural bandwidth competition fairness , This is the case when the packet loss rate of each link is the same .

2.2 The congestion degree of each link is different
First of all COUPLED In the algorithm, for each subflow for , Every time Increase or decrease the window value for all subflow It is unified. , Only with that moment $W_{total}$ of . Then the link with high congestion It is bound to encounter more packet losses in a specified period of time , In the long run, the final algorithm will slowly converge its traffic to low congestion links , So that EWTCP The adaptive function is not realized .

---

What's more interesting is , A conclusion is mentioned in the article ： The migration of traffic from high congestion links to low congestion links will bring the packet loss rate of the whole network gradually converge to equilibrium . This means that if you execute COUPLED Algorithm ,2.2 The state will eventually move to 2.1 State transition ( Pleasantly surprised ), Final When convergence is reached, each MPTCP Entities will obtain equal global link bandwidth , This leads directly to the next part ： How to calculate ？

3、 ... and 、 Judge EWTCP and Coupled Respective bandwidth
In fact, the article is written here , This problem is quite obvious , Take an example from the paper ：
3.1EWTCP The calculation of
about EWTCP, It tends to be friendly with Each competitor maintains equal distribution . So in the left figure above ,12Mb/s Links and 10Mb/s All links will be equally divided . therefore ：

• A Bandwidth will be obtained ：5+6 = 11
• B Bandwidth will be obtained ：6+5 = 11
• C Bandwidth will be obtained ：5+3 = 8

3.2COUPLED The calculation of
First of all, according to our above explanation , each MPTCP The entity will obtain equal global link bandwidth , So they The final bandwidth will be the same , Set to unified x. Let the following unknowns ：

Write a system of equations and solve it …

Actually COUPLED The algorithm also has its own problems ( Adapt to load changes and RTT mismatch The problem of ), These are mentioned later in the paper , And the corresponding compensation scheme is given , And finally put forward a complete MPTCP Congestion control algorithm , Be interested in your health , If you really pass the exam, send it directly orz…