这是我的第五篇博客，鉴于前⾯已经有很多⼈对前四个题⽬如三次握⼿等做了很透彻的分析，本博客将对拥塞控制算法做⼀个介绍。
⾸先我会简要介绍下TCP协议，其次给出拥塞控制介绍和源代码分析，最后结合源代码具体分析拥塞控制算法。
⼀、TCP协议
1.TCP协议产⽣背景：互联⽹络与单个⽹络有很⼤的不同，因为互联⽹络的不同部分可能有截然不同的拓扑结构、带宽、延迟、数据包⼤⼩和其他参数，且不同主机的应⽤层之间经常需要可靠的、像管道⼀样的连接，但是IP层不提供这样的流机制，⽽是提供不可靠的包交换。 2.TCP是能够动态地适应互联⽹络的这些特性，⽽且具备⾯对各种故障时的健壮性，且能够在不可靠的互联⽹络上提供可靠的端到端字节流⽽专门设计的⼀个传输协议。
3.TCP作⽤原理过程：
应⽤层向TCP层发送⽤于⽹间传输的、⽤8位字节表⽰的数据流，然后TCP把数据流分区成适当长度的报
⽂段（通常受该计算机连接的⽹络的数据链路层的最⼤传输单元（MTU）的限制）。之后TCP把结果包传给IP层，由它来通过⽹络将包传送给接收端实体的TCP层。TCP为了保证不发⽣丢包，就给每个包⼀个序号，同时序号也保证了传送到接收端实体的包的按序接收。然后接收端实体对已成功收到的包发回⼀个相应的确认（ACK）；如果发送端实体在合理的往返时延（RTT）内未收到确认，那么对应的数据包就被假设为已丢失将会被进⾏重传。TCP⽤⼀个校验和函数来检验数据是否有错误；在发送和接收时都要计算校验和。
4.TCP协议作⽤过程的7个要点：数据分⽚、到达确认、超时重发、滑动窗⼝、失序处理、重复处理、数据校验(具体可参见百度百科对TCP的解释)
5.TCP⾸部格式图：
⼏个重要参数解释如下：
紧急 URG —— 当 URG =1 时，表明紧急指针字段有效。它告诉系统此报⽂段中有紧急数据，应尽快传送(相当于⾼优先级的数据)。
信令风暴确认 ACK —— 只有当 ACK = 1 时确认号字段才有效。当 ACK =0 时，确认号⽆效。
推送 PSH (PuSH) —— 接收 TCP 收到 PSH = 1 的报⽂段，就尽快地交付接收应⽤进程，⽽不再等到整个缓存都填满了后再向上交付。
复位 RST (ReSeT) —— 当 RST =1 时，表明 TCP 连接中出现严重差错（如由于主机崩溃或其他原因），必须释放连接，然后再重新建⽴运输连接。
同步 SYN —— 同步 SYN = 1 表⽰这是⼀个连接请求或连接接受报⽂。
终⽌ FIN (FINis) —— ⽤来释放⼀个连接。FIN =1 表明此报⽂段的发送端的数据已发送完毕，并要求释放运输连接。
6.TCP⼯作⽅式：采⽤三次握⼿来建⽴连接，四次挥⼿来释放连接，这部分的内容⽹上资料极其详细，感兴趣的⼩伙伴可以参见百度百科TCP的内容
如下是TCP连接与终⽌的过程图：
⼆、拥塞控制介绍和源代码分析
⾸先在控制拥塞之前，我们需要了解拥塞指代的为何物。
百度百科解释如下：拥塞现象是指到达通信⼦⽹中某⼀部分的分组数量过多，使得该部分⽹络来不及
处理，以致引起这部分乃⾄整个⽹络性能下降的现象，严重时甚⾄会导致⽹络通信业务陷⼊停顿，即出现死锁现象。这种现象跟公路⽹中经常所见的交通拥挤⼀样，当节假⽇公路⽹中车辆⼤量增加时，各种⾛向的车流相互⼲扰，使每辆车到达⽬的地的时间都相对增加（即延迟增加），甚⾄有时在某段公路上车辆因堵塞⽽⽆法开动(即发⽣局部死锁)。
造成拥塞的原因由如下两点：
1.多条流⼊线路有分组到达，并需要同⼀输出线路，此时，如果路由器没有⾜够的内存来存放所有这些分组，那么有的分组就会丢失。
2.路由器的慢带处理器的缘故，以⾄于难以完成必要的处理⼯作，如缓冲区排队、更新路由表等。
在不同的层处理拥塞有不同的⽅法，具体如下：
1.在传输层可采⽤：重传策略、乱序缓存策略、确认策略、流控制策略和确定超时策略。 2.在⽹络层可采⽤：⼦⽹内部的虚电路与数据报策略、分组排队和服务策略、分组丢弃策略、路由算法和分组⽣存管理。
3.在数据链路层可采⽤：重传策略、乱序缓存策略、确认策略和流控制策略。
行政审批制度
本博客重点介绍的是传输层下TCP协议的拥塞控制⼿段
TCP传统的拥塞控制AIMD算法的四个部分如下：
（1）慢启动
每当建⽴⼀个TCP连接时或⼀个TCP连接发⽣超时重传后，该连接便进⼊慢启动阶段。进⼊慢启动后，TCP实体将拥塞窗⼝的⼤⼩初始化为⼀个报⽂段，即：cwnd=1。此后，每收到⼀个报⽂段的确认（ACK），cwnd值加1，即拥塞窗⼝按指数增加。当cwnd值超过慢启动阐值（sshterhs）或发⽣报⽂段丢失重传时，慢启动阶段结束。前者进⼊拥塞避免阶段，后者重新进⼊慢启动阶段。
（2）拥塞避免
在慢启阶段，当cwnd值超过慢启动阐值（ssthresh）后，慢启动过程结束，TCP连接进⼊拥塞避免阶段。在拥塞避免阶段，每⼀次发送的cwnd个报⽂段被完全确认后，才将cwnd值加1。在此阶段，cwnd值线性增加。
（3）快速重传
快速重传是对超时重传的改进。当源端收到对同⼀个报⽂的三个重复确认时，就确定⼀个报⽂段已经
丢失，因此⽴刻重传丢失的报⽂段，⽽不必等到重传定时器（RTO）超时。以此减少不必要的等待时间。
（4）快速恢复
快速恢复是对丢失恢复机制的改进。在快速重传之后，不经过慢启动过程⽽直接进⼊拥塞避免阶段。每当快速重传后，置sshtesrh=cwnd/2、
ewnd=ssthresh+3。此后，每收到⼀个重复确认，将cwnd值加1，直⾄收到对丢失报⽂段和其后若⼲报⽂段的累积确认后，置cwnd=ssthesrh，进⼊拥塞避免阶段。
AIMD传统算法现在已经很少使⽤了，故不再贴出对它的源代码分析
下⾯分析⽬前应⽤最⼴泛且较为成熟的Reno算法，该算法所包含的慢启动、拥塞避免和快速重传、快速恢复机制，是现有的众多算法的基础。
源代码位于内核linux5.0.1/net/ipv4/tcp_cong.c中，贴出部分代码分析如下：
/*
* TCP Reno congestion control
* This is special case used for fallback as well.
*/
/* This is Jacobson's slow start and congestion avoidance.
* SIGCOMM '88, p. 328.
*/
void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 acked)
{
struct tcp_sock *tp = tcp_sk(sk);
if (!tcp_is_cwnd_limited(sk))
return;
/* In "safe" area, increase. */
if (tcp_in_slow_start(tp)) {
acked = tcp_slow_start(tp, acked);
if (!acked)
return;
}
/* In dangerous area, increase slowly. */
tcp_cong_avoid_ai(tp, tp->snd_cwnd, acked);
}
EXPORT_SYMBOL_GPL(tcp_reno_cong_avoid);
/* Slow start threshold is half the congestion window (min 2) */
u32 tcp_reno_ssthresh(struct sock *sk)
{
cctv5体育人间const struct tcp_sock *tp = tcp_sk(sk);
return max(tp->snd_cwnd >> 1U, 2U);
}
EXPORT_SYMBOL_GPL(tcp_reno_ssthresh);
u32 tcp_reno_undo_cwnd(struct sock *sk)
{
const struct tcp_sock *tp = tcp_sk(sk);
return max(tp->snd_cwnd, tp->prior_cwnd);
}
EXPORT_SYMBOL_GPL(tcp_reno_undo_cwnd);
struct tcp_congestion_ops tcp_reno = {
.flags = TCP_CONG_NON_RESTRICTED,
.name = "reno",
.owner = THIS_MODULE,
.ssthresh = tcp_reno_ssthresh,
.cong_avoid = tcp_reno_cong_avoid,
.undo_cwnd = tcp_reno_undo_cwnd,
};
从Reno运⾏机制中很容易看出，为了维持⼀个动态平衡，必须周期性地产⽣⼀定量的丢失，再加上AIMD机制--减少快，增长慢，尤其是在⼤窗⼝环境下，由于⼀个数据报的丢失所带来的窗⼝缩⼩要花费很长的时间来恢复，这样，带宽利⽤率不可能很⾼且随着⽹络的链路带宽不断提升，这种弊端将越来越明显。公平性⽅⾯，根据统计数据，Reno的公平性还是得到了相当的肯定，它能够在较⼤的⽹络范围内理想地维持公平性原则。
Reno算法以其简单、有效和鲁棒性成为主流，被⼴泛的采⽤。
但是它不能有效的处理多个分组从同⼀个数据窗⼝丢失的情况。这⼀问题在New Reno算法中得到解决。
近⼏年来，随着⾼带宽延时⽹络（High Bandwidth-Delay product network）的普及，针对提⾼TCP带宽利⽤率这⼀点上，⼜涌现出许多新的基于丢包反馈的TCP协议改进，这其中包括HSTCP、STCP、BIC-TCP、CUBIC和H-TCP。
总的来说，基于丢包反馈的协议是⼀种被动式的拥塞控制机制，其依据⽹络中的丢包事件来做⽹络拥塞判断。即便⽹络中的负载很⾼时，只要没有产⽣拥塞丢包，协议就不会主动降低⾃⼰的发送速度。这种协议可以最⼤程度的利⽤⽹络剩余带宽，提⾼吞吐量。然⽽，由于基于丢包反馈协议在⽹络近饱和状态下所表现出来的侵略性，⼀⽅⾯⼤⼤提⾼了⽹络的带宽利⽤率；但另⼀⽅⾯，对于基于丢包反馈的拥塞控制协议来说，⼤⼤提⾼⽹络利⽤率同时意味着下⼀次拥塞丢包事件为期不远了，所以这些协议在提⾼⽹络带宽利⽤率的同时也间接加⼤了⽹络的丢包率，造成整个⽹络的抖动性加剧。
下⾯给出BIC-TCP源代码分析如下：位于linux5.0.1/net/ipv4/tcp_bic.c中
/* BIC TCP Parameters */
struct bictcp {
u32 cnt; /* increase cwnd by 1 after ACKs */
u32 last_max_cwnd; /* last maximum snd_cwnd */
u32 last_cwnd; /* the last snd_cwnd */
u32 last_time; /* time when updated last_cwnd */
u32 epoch_start; /* beginning of an epoch */
#define ACK_RATIO_SHIFT 4
u32 delayed_ack; /* estimate the ratio of Packets/ACKs << 4 */
};
static inline void bictcp_reset(struct bictcp *ca)
{
ca->cnt = 0;
ca->last_max_cwnd = 0;
ca->last_cwnd = 0;
ca->last_time = 0;
ca->epoch_start = 0;
ca->delayed_ack = 2 << ACK_RATIO_SHIFT;
}
static void bictcp_init(struct sock *sk)
{
struct bictcp *ca = inet_csk_ca(sk);
bictcp_reset(ca);
if (initial_ssthresh)
恩丹西酮tcp_sk(sk)->snd_ssthresh = initial_ssthresh;
}
/*
* Compute congestion window to use.
*/
static inline void bictcp_update(struct bictcp *ca, u32 cwnd)
{
if (ca->last_cwnd == cwnd &&
(s32)(tcp_jiffies32 - ca->last_time) <= HZ / 32)
return;
气象局医院
ca->last_cwnd = cwnd;
ca->last_time = tcp_jiffies32;
if (ca->epoch_start == 0) /* record the beginning of an epoch */
ca->epoch_start = tcp_jiffies32;
/* start off normal */
橙书包公益项目if (cwnd <= low_window) {
ca->cnt = cwnd;
return;
}
/* binary increase */
if (cwnd < ca->last_max_cwnd) {
__u32 dist = (ca->last_max_cwnd - cwnd)
/ BICTCP_B;
if (dist > max_increment)
/* linear increase */
ca->cnt = cwnd / max_increment;
else if (dist <= 1U)
/* binary search increase */
ca->cnt = (cwnd * smooth_part) / BICTCP_B;
else
/* binary search increase */
ca->cnt = cwnd / dist;
} else {
/* slow start AMD linear increase */
if (cwnd < ca->last_max_cwnd + BICTCP_B)
/* slow start */
ca->cnt = (cwnd * smooth_part) / BICTCP_B;
else if (cwnd < ca->last_max_cwnd + max_increment*(BICTCP_B-1))
/* slow start */
ca->cnt = (cwnd * (BICTCP_B-1))
/ (cwnd - ca->last_max_cwnd);
else
/* linear increase */
ca->cnt = cwnd / max_increment;
}
/* if in slow start or link utilization is very low */
if (ca->last_max_cwnd == 0) {
if (ca->cnt > 20) /* increase cwnd 5% per RTT */
ca->cnt = 20;
}
ca->cnt = (ca->cnt << ACK_RATIO_SHIFT) / ca->delayed_ack;
if (ca->cnt == 0) /* cannot be zero */
ca->cnt = 1;
}
static void bictcp_cong_avoid(struct sock *sk, u32 ack, u32 acked)
{
struct tcp_sock *tp = tcp_sk(sk);
struct bictcp *ca = inet_csk_ca(sk);
if (!tcp_is_cwnd_limited(sk))
return;
if (tcp_in_slow_start(tp))
tcp_slow_start(tp, acked);
else {
bictcp_update(ca, tp->snd_cwnd);
tcp_cong_avoid_ai(tp, ca->cnt, 1);
}
}
可以看出其在⼤⼤提⾼了⾃⾝吞吐率的同时，也严重影响了Reno流的吞吐率。基于丢包反馈的协议产⽣如此低劣的TCP友好性的组要原因在于这些协议算法本⾝的侵略性拥塞窗⼝管理机制，这些协议通常认为⽹络只要没有产⽣丢包就⼀定存在多余的带宽，从⽽不断提⾼⾃⼰的发送速率。其发送速率从时间的宏观⾓度上来看呈现出⼀种凹形的发展趋势，越接近⽹络带宽的峰值发送速率增长得越快。这不仅带来了⼤量拥塞丢包，同时也恶意吞并了⽹络中其它共存流的带宽资源，造成整个⽹络的公平性下降。
三、拥塞控制实验演⽰
可利⽤Wireshark 记录若⼲TCP 短流（少于5 秒，如访问web 页⾯，收发邮件等）和TCP长流（长于1 分钟，如FTP 下载⼤⽂件，⽤HTTP 观看在线视频等）。对于每个TCP 流，可画出其congestion window 随时间的变化曲线，指出拥塞控制的慢启动、拥塞避免、快恢复等阶段。
总结：选题之前没有意识到拥塞控制在内核中的实现实在太难了，⽹上对源代码的分析很少很少，本博客介绍的特别肤浅，后续还需要加强对拥塞控制的理解。
