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

这篇文章对有关MPTCP的拥塞控制进行理解和梳理，参考资料来自：
《Design, implementation and evaluation of congestion control for multipath TCP》(NSDI’11)和老师上课时的PPT。

复习提纲中要理解的问题是：

1.MPTCP拥塞控制的目标
2.理解EWTCP和Coupled
3.可以判断EWTCP和Coupled各自获取的带宽

一、MPTCP拥塞控制的目标
这部分是自己的理解和总结，从论文中来看，MPTCP拥塞控制的目标有两个：
1.确保MPTCP的引入不会对原有网络流量造成严重干扰(公平性等)
2.尽可能地保证高吞吐率

正如论文原文说的那样：
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.

“我们打算作出回答的一个基本问题是：如何精确地调整MPTCP的子流窗口，以便在与现有TCP流量和谐共存的约束下获得最大可能的性能。(笑)”

二、理解EWTCP和Coupled
MPTCP协议本质是作为一个传输层的中间件出现的，它的主要目的是将一个数据流划分到多个路径上传输。一个TCP连接管理多个subflow，每个subflow可以在网络中进行自由选路，并且每一个subflow都维护着属于自己的一个私有的发送窗口$W_r$，而MPTCP的发送者则在任何一个subflow发送窗口有余量时将数据分发给它们去传输，以上是对MPTCP的一个简要概括。

首先从最开始的故事说起，原始TCP(Regular TCP)中的拥塞控制算法如下。

这个和经典的TCP拥塞控制是一致的，就像上一篇BBR中提到的一样，它有一些特性：比如AIMD(加性增，乘性减)，吞吐率波动大，算法侵略性强等。

如果直接将原始的TCP拥塞控制用在MPTCP场景中，那么MPTCP的每一个subflow都将以独立的竞争者身份和原始的单路径TCP流进行竞争，这样显然对单路径TCP是非常不利的。可以想象，假设在RTT相同的情况下，一个拥有n个subflow的MPTCP，其最终获取的带宽将会是单路径TCP的n倍，极大地损害了网络的公平性，不能实现与现有TCP流量的和谐共存。

那么首先要解决的问题就是公平性，一个非常朴素的思想就是给每个流可以获得的带宽进行一个加权限制，进而引出了EWTCP(Equally-Weighted TCP)拥塞控制算法：

关于这个算法有一个重要的结论：每一个subflow会获得的发送窗口值正比于$a^2$，此结论的证明需参考另一篇论文，此处从略。

那么可以想见的是，如果取$a=\frac{1}{\sqrt{n}}$，并且假设RTT值都相等，就会使得最终含有n个subflow的MPTCP作为一个整体可以在瓶颈链路上获得和一个单路径TCP同样的网络带宽，从而强行地获得了分配上的公平性。(一个MPTCP实体在EWTCP协议下，无论它下辖多少subflow，它所能获得的总带宽总不会超过一个单路径TCP实体)

当n = 1时，EWTCP会退化到Regular TCP拥塞控制算法。此外，EWTCP算法中涉及到的MPTCP每一个subflow彼此之间相互独立(因为是按照$W_r$来进行拥塞控制的)，所以即使有一条subflow被阻塞了，其他的subflow也不会因此变得更加有侵略性，这保证了MPTCP实体不可能在总占用带宽上超过单路径TCP。

EWTCP实现了带宽竞争中的公平性，但是论文中同样指出EWTCP不能高效地使用链路(缺乏动态适应性，就像上面说的，一个subflow如果阻塞了，也不会影响到其他subflow，但是MPTCP获得的总带宽却实打实减少了)。论文中举出的一个典型的例子如下：

三个n=2的MPTCP使用EWTCP去竞争三条带宽为12Mb/s的链路，使用EWTCP的结果是三者各自在两条信道上分4Mb/s的带宽。每一个MPTCP实体获得的带宽总额是8Mb/s，但其实最优解可以是每个MPTCP获得12Mb/s的带宽，即一个MPTCP只走一条链路，这样就可以不走程序直接赢麻(写累了，笑)，但是EWTCP不能自己找到这样的最优解，而是呆呆地执行“看似公平”的次优解。

文中指出，已有理论上的证据表明：对于多路径传输的情形，最优解总是将其所有流量迁移至拥塞程度最低的路径。而且有一种算法在理论上被证实，不需要进行拥塞程度侦测也可以自适应地找到最优解，这就是COUPLED算法：

其中$W_{total}$是一个MPTCP实体下管辖的所有subflow的发送窗口大小之和。要理解这个协议需要分两种情况：

2.1 各个链路拥塞程度相等的情况
这种情况下不存在选路的自适应问题，也就是说每个subflow都可以大致地按照一个确定的发送窗口大小去运作，但是有一个要尊重的基本法(笑)，那就是：每一个subflow的发送窗口增长和发送窗口减少，从长远来看一定要相互抵消，就是解下面这个方程(p是丢包率，1-p是成功发送概率)：

解出来发现$W_{total}=\sqrt{2(1-p)(p)}\approx \sqrt{\frac{2}{p}}$，这直接指向了另外一个重要结论：在COUPLED算法中，一个MPTCP的各个subflow可以获得的总带宽之和只与链路丢包率有关，这证明了COUPLED拥有天然的带宽竞争公平性，这是各个链路丢包率相同时的情况。

2.2 各个链路拥塞程度不同的情况
首先注意COUPLED算法中对每一条subflow而言，每次增加或减少的窗口值对所有subflow是统一的，只与那个时刻的$W_{total}$有关。那么拥塞程度高的链路势必在指定的一段时间内会遇到更多的丢包，长远来看最终算法会慢慢地将其流量逐渐向低拥塞链路汇集，从而实现了EWTCP没有实现自适应功能。

---

更加有趣的是，文中提到一个结论：将流量从高拥塞链路向低拥塞链路迁移的动作会带来全网络的丢包率逐渐收敛到均衡。这意味着如果执行COUPLED算法，2.2状态会最终向2.1状态过渡(惊喜)，最终达到收敛时各个MPTCP实体都会获得相等的全局链路带宽，这直接引出了下一部分的问题：如何计算？

三、判断EWTCP和Coupled各自获取的带宽
其实文章写到这里，这个问题已经比较显而易见了，举个论文中的例子：
3.1EWTCP的计算
对于EWTCP，它会倾向于友好地和每一个竞争者保持均等分配。所以在上面左图中，12Mb/s的链路和10Mb/s的链路都会被均分。所以：

• A会获得的带宽：5+6 = 11
• B会获得的带宽：6+5 = 11
• C会获得的带宽：5+3 = 8

3.2COUPLED的计算
首先根据我们上面的解释，各个MPTCP实体会获得相等的全局链路带宽，所以它们最终会获得的带宽是一致的，设为统一的x。设以下未知量：

写个方程组解它就是了…

其实COUPLED算法也还是有自己的问题(适应负载变化和RTT mismatch的问题)，这些在论文的后面提到了，并且给出了相应的补偿方案，并最终提出了完整的MPTCP拥塞控制算法，有兴趣自己康康吧，真考了就直接寄orz…