一般而言，拥塞的时候会出现很多问题，其中尤为频发的是报文段丢失和乱序。丢失的可能原因有不少，例如路由器转发队列满时丢弃，甚至可能是随机早期丢弃（RED）；乱序就是到达先后顺序颠倒，乱序的报文可能走过了不同的转发路径，其转发排队时间、链路传播时间等都可能不一样，进而抹平乃至逆转了发送的先后时差。
接下来我们会先介绍CC的一些理论，然后分析现代的Linux网络栈是怎样实现拥塞控制的。
1. 拥塞控制方法
1.1. TCP Tahoe
Tahoe包括慢启动和拥塞避免。最开始慢启动，cwnd设为1 MSS，每一次收到ACK，cwnd都会被增大一个MSS。直到cwnd到达ssthresh（它有一个初始值，例如64 KB），此时进入拥塞避免每一个RTT才会使cwnd增大一个MSS。
全程如果出现丢包事件（超时或者3个DACK），cwnd都会回到1 MSS，开始慢启动，同时ssthresh变为原先cwnd的一半。
ssthresh其实指示了上一次发生拥塞时的窗口大小的一半，换言之，cwnd到达ssthresh的时候，已经到了拥塞的一半，所以cwnd的增长不能够太激进。
1.2. TCP Reno
Reno在Tahoe之上提出了快速恢复算法。DACK指示的丢包可以说明，既然一个RTO内还能收到3个DACK，说明拥塞应该并不严重，所以也不必将cwnd暴力地置为1。
此时的做法是，将ssthresh置为cwnd的一半，所以前面提到的ssthresh的意义没有变，还是拥塞点的一半；而cwnd在ssthresh的基础上加3 MSS，它的意思是既然收到3个DACK，说明DACK对应的报文段还是正常发出去了，应该计到cwnd的变化中。接下来重设计时器，进入快速恢复。
快速恢复中，每收到一个DACK，都为cwnd加1 MSS。收到new ACK，就回到拥塞避免；如果计时器超时了，就进入慢启动。
1.3. TCP NewReno
Reno考虑了一个数据包丢失导致DACK的情况。那如果是多个数据包丢失呢？Reno只能看到第一个丢失的数据包，所以将窗口减半，重传一次，收到new ACK，退出快速恢复；然后又看到一个，再减半、重传；如此反复几次，窗口就减得差不多了。
为了解决这一问题，NewReno确保一个窗口内的所有丢失报文都收到ACK后，才退出快速恢复。可以想想看，Reno的问题出在哪里？如果丢失的报文不止一个，接收方发回的new ACK可能还是没有赶上发送方发送的最新的报文段的序号。
例如，假设6号报文段已经发送完，而4、5、6均在网络中丢失。发送方重传4，假设成功了，那么new ACK就是5，换言之还有报文段没送达，这种情况下就不应该退出快速恢复，而是继续重发。直到某次new ACK（例如ACK 11）恰好应答了所有已发送报文段（例如发送方发送完第10个报文段），才退出快速恢复。
上面例子的两种情况分别对应收到PACK（Partial ACK）和RACK（Recovery ACK)。在TCP Reno的基础上作补充，快速恢复状态下，收到PACK，则重发PACK对应的数据报；收到RACK，则进入拥塞避免。
1.4. TCP SACK
现代的TCP一个RTT能发好多报文段，一个窗口内丢包的期望值也增加了。TCP NewReno虽然减少了窗口缩减的次数，但没有改变一个RTT只重传一个报文段的本质。假如丢失的速率比重传的速率更高，接收方的缓存有可能会越来越少，使rwnd处于低位，这可就拉胯了。
为了提高重传效率，接收方可以多提供点信息，即把窗口内报文段的接受情况写在TCP报头里，这样发送方一分析就知道该批量重传哪些报文了。
TCP报头的20字节虽然基本写死了，但是选项字段有40字节，还可以放一些东西。选项编号占1字节，长度占1字节，后面紧邻着各个区间段，包括4字节的开始编号和4字节的结束编号，所以理论上这样的区间段最多能放4个。但其实SACK还要和另外一个时间戳选项并存，时间戳占10字节，所以也就放得下3个区间段了。
选项的具体内容是接收方提供的，但其实在缓冲区不足的时候，接收方可能会把已经接收的段删除掉而不再另行通知，即有违约（renege）的可能；更糟糕的是，这一字段还可以被精心设计用于攻击发送方，导致发送方panic，不过该bug已被修复。
在连接建立时，通信双方可协商是否支持SACK。不支持SACK，就使用(New)Reno。Tahoe被Reno向后兼容，但是已经没什么OS会用这个算法了。
2. 拥塞状态
这是各状态的定义。
/*
* Sender's congestion state indicating normal or abnormal situations
* in the last round of packets sent. The state is driven by the ACK
* information and timer events.
*/
enum tcp_ca_state {
/*
* Nothing bad has been observed recently.
* No apparent reordering, packet loss, or ECN marks.
*/
TCP_CA_Open = 0,
#define TCPF_CA_Open (1<<TCP_CA_Open)
/*
* The sender enters disordered state when it has received DUPACKs or
* SACKs in the last round of packets sent. This could be due to packet
* loss or reordering but needs further information to confirm packets
* have been lost.
*/
TCP_CA_Disorder = 1,
#define TCPF_CA_Disorder (1<<TCP_CA_Disorder)
/*
* The sender enters Congestion Window Reduction (CWR) state when it
* has received ACKs with ECN-ECE marks, or has experienced congestion
* or packet discard on the sender host (e.g. qdisc).
*/
TCP_CA_CWR = 2,
#define TCPF_CA_CWR (1<<TCP_CA_CWR)
/*
* The sender is in fast recovery and retransmitting lost packets,
* typically triggered by ACK events.
*/
TCP_CA_Recovery = 3,
#define TCPF_CA_Recovery (1<<TCP_CA_Recovery)
/*
* The sender is in loss recovery triggered by retransmission timeout.
*/
TCP_CA_Loss = 4
#define TCPF_CA_Loss (1<<TCP_CA_Loss)
};
3. 显式拥塞通知ECN
ECN需要TCP和IP层的共同支持。简单说，路由器是拥塞的报告方，会在IP层的一对比特位中记录是否发生了拥塞。接收方收到报文段时，就知道它在传输的过程中是否发生了拥塞。然而，发送方才真正地需要了解拥塞状况并调节发送速率，所以接收方会把拥塞信息设置在ACK数据报并发回到发送方。
3.1. IP层支持
enum {
INET_ECN_NOT_ECT = 0,
INET_ECN_ECT_1 = 1,
INET_ECN_ECT_0 = 2,
INET_ECN_CE = 3,
INET_ECN_MASK = 3,
};
它们用于表示ECN的状态。00表示不支持ECN，01或10表示支持ECN（但没有发生拥塞），11表示发生拥塞。设置拥塞比特在这里实现：
static inline int IP_ECN_set_ce(struct iphdr *iph)
{
u32 check = (__force u32)iph->check;
u32 ecn = (iph->tos + 1) & INET_ECN_MASK;
/*
* After the last operation we have (in binary):
* INET_ECN_NOT_ECT => 01
* INET_ECN_ECT_1 => 10
* INET_ECN_ECT_0 => 11
* INET_ECN_CE => 00
*/
if (!(ecn & 2))
return !ecn;
/*
* The following gives us:
* INET_ECN_ECT_1 => check += htons(0xFFFD)
* INET_ECN_ECT_0 => check += htons(0xFFFE)
*/
check += (__force u16)htons(0xFFFB) + (__force u16)htons(ecn);
iph->check = (__force __sum16)(check + (check>=0xFFFF));
iph->tos |= INET_ECN_CE;
return 1;
}
进行了一些位运算骚操作，并重新计算了校验和。
3.2. TCP层支持
TCP有什么字段是支持ECN的？或许我们可以用选项字段？实际上没必要，TCP用了6位保留位的后2位CWR、ECE来支持ECN，它的后面紧接着就是传统的6个flag。
- ECE用于ACK，表明收到了来自路由器的拥塞通知。
- CWR是发送端拥塞窗口减小标志，用于通知接收端已经收到了设置ECE标志的ACK。
三次握手时，通过将ECE和CWR都设为1，可构造一个SYN报文段，表示自己支持ECN。宏定义如下，包含了其他一些flag，可自行体会。
#define TCPHDR_FIN 0x01
#define TCPHDR_SYN 0x02
#define TCPHDR_RST 0x04
#define TCPHDR_PSH 0x08
#define TCPHDR_ACK 0x10
#define TCPHDR_URG 0x20
#define TCPHDR_ECE 0x40
#define TCPHDR_CWR 0x80
#define TCPHDR_SYN_ECN (TCPHDR_SYN | TCPHDR_ECE | TCPHDR_CWR)4. 快速重传
快速重传的状态处理函数在tcp_fastretrans_alert，接下来我们梳理快速重传的发生时机和具体动作。
4.1. tcp_ack中
这是处理到来ACK的函数，定义于tcp_input.c。函数具体做了什么我们就不展开分析了，源码其实写得很清楚，或许我会在另一篇文章出给出讲解。我们只考虑快速重传的可能触发时机：
- 当前CC状态不是Open。
- 收到的ACK是SACK、dup ACK，或者ACK中带ECE位。
#define FLAG_CA_ALERT (FLAG_DATA_SACKED|FLAG_ECE|FLAG_DSACKING_ACK)
static inline bool tcp_ack_is_dubious(const struct sock *sk, const int flag)
{
return !(flag & FLAG_NOT_DUP) || (flag & FLAG_CA_ALERT) ||
inet_csk(sk)->icsk_ca_state != TCP_CA_Open;
} if (tcp_ack_is_dubious(sk, flag)) {
if (!(flag & (FLAG_SND_UNA_ADVANCED | FLAG_NOT_DUP))) {
num_dupack = 1;
/* Consider if pure acks were aggregated in tcp_add_backlog() */
if (!(flag & FLAG_DATA))
num_dupack = max_t(u16, 1, skb_shinfo(skb)->gso_segs);
}
tcp_fastretrans_alert(sk, prior_snd_una, num_dupack, &flag,
&rexmit);
}此时有快速重传的可能性，故需要进一步确认，并在有必要的时候修改CC状态。
ACK处理结束的时候，会统一调用以下函数，以完成速率采样、拥塞控制和可能的重传：
tcp_rate_gen(sk, delivered, lost, is_sack_reneg, sack_state.rate);
tcp_cong_control(sk, ack, delivered, flag, sack_state.rate);
tcp_xmit_recovery(sk, rexmit);4.2. tcp_fastretrans_alert
该函数只是进行alert，计算已离开主机的报文数（包括已被对方接收但并未ACK的报文，和已经被不可靠网络弄丢的报文），修改标志位，并进行CC状态转换；换言之，不会进行拥塞控制操作（如窗口调节），也不参与重发。
第一步，如果收到的ACK置了ECE位，说明收到显示拥塞通知，此时要开始减小拥塞窗口。
* A. ECE, hence prohibit cwnd undoing, the reduction is required. */
if (ece_ack)
tp->prior_ssthresh = 0;第二步，如果在ACK报文处理中发现有SACK违约，即ACK指向了SACK中已经接收到的段。说明接收方处于重度拥塞，或者接收方处理出现BUG。我们先将其记下，设个计时器，等max(RTT/2, 10ms)的时间，好让接收方能够发送更多的ACK，并期望接收方重新履行SACK。如果接收方仍然违约，则必须执行重传。
/* If ACK arrived pointing to a remembered SACK, it means that our
* remembered SACKs do not reflect real state of receiver i.e.
* receiver _host_ is heavily congested (or buggy).
*
* To avoid big spurious retransmission bursts due to transient SACK
* scoreboard oddities that look like reneging, we give the receiver a
* little time (max(RTT/2, 10ms)) to send us some more ACKs that will
* restore sanity to the SACK scoreboard. If the apparent reneging
* persists until this RTO then we'll clear the SACK scoreboard.
*/
static bool tcp_check_sack_reneging(struct sock *sk, int flag)
{
if (flag & FLAG_SACK_RENEGING) {
struct tcp_sock *tp = tcp_sk(sk);
unsigned long delay = max(usecs_to_jiffies(tp->srtt_us >> 4),
msecs_to_jiffies(10));
inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS,
delay, TCP_RTO_MAX);
return true;
}
return false;
}
static void tcp_fastretrans_alert(struct sock *sk, const u32 prior_snd_una,
int num_dupack, int *ack_flag, int *rexmit)
{
/* ... */
/* B. In all the states check for reneging SACKs. */
if (tcp_check_sack_reneging(sk, flag))
return;
}第三步，检查状态一致性。
/* C. Check consistency of the current state. */
tcp_verify_left_out(tp);检查的是left_out，我们要确保这个数量不能多于packet_out。那应该是显然的，前者是离开主机的未被确认的报文数，后者是离开发送队列的未被确认的报文数；如果出现了反常，就需要进行WARN。
第四步，检测从拥塞状态返回的条件。
/* D. Check state exit conditions. State can be terminated
* when high_seq is ACKed. */
if (icsk->icsk_ca_state == TCP_CA_Open) {
WARN_ON(tp->retrans_out != 0);
tp->retrans_stamp = 0;
} else if (!before(tp->snd_una, tp->high_seq)) {
switch (icsk->icsk_ca_state) {
case TCP_CA_CWR:
/* CWR is to be held something *above* high_seq
* is ACKed for CWR bit to reach receiver. */
if (tp->snd_una != tp->high_seq) {
tcp_end_cwnd_reduction(sk);
tcp_set_ca_state(sk, TCP_CA_Open);
}
break;
case TCP_CA_Recovery:
if (tcp_is_reno(tp))
tcp_reset_reno_sack(tp);
if (tcp_try_undo_recovery(sk))
return;
tcp_end_cwnd_reduction(sk);
break;
}
}
首先，Open状态是最常见的。需要断言下，肯定不应该有正在重传的报文吧？
其次对非正常的状态进行处理。对于tp->snd_una >= tp->high_seq，前者是期望收到ACK的第一个字节序号，而后者是拥塞开始时将要发送的第一个字节序号，该式成立时说明拥塞前发送的所有报文都已确认收到，可以考虑退出拥塞状态。如果此时是CWR状态，还要确保拥塞期间发送的报文也可以被ACK，这起码说明拥塞比之前好多了，可以结束该状态，并进入Open。如果是Recovery状态，那么根据协议，此时也可以退出快速恢复。
第五步，进行状态转移。这里内容比较多就不一一列举了，我们看Disorder、Loss和Open状态下的状态转移：
default:
/* ... */
tcp_identify_packet_loss(sk, ack_flag);
if (!tcp_time_to_recover(sk, flag)) {
tcp_try_to_open(sk, flag);
return;
}
/* ... */
/* Otherwise enter Recovery state */
tcp_enter_recovery(sk, ece_ack);
fast_rexmit = 1;进入Recovery状态，并作一个fast_rexmit的标记；或者尝试进入Open状态。
做完这些之后，为需要重传的报文打标记，并将rexmit标记REXMIT_LOST。
if (!tcp_is_rack(sk) && do_lost)
tcp_update_scoreboard(sk, fast_rexmit);
*rexmit = REXMIT_LOST;4.3. tcp_cong_control
tcp_cong_control是拥塞控制引擎的调用函数，方便兼容各种各样的拥塞控制算法。看看这注释，“终极”拥塞控制函数。
它会尝试调用icsk->icsk_ca_ops中注册的拥塞控制函数，如果没有注册则采用默认策略：使用传统的窗口减小tcp_cwnd_reduction和增大tcp_cwnd_reduction函数。
/* The "ultimate" congestion control function that aims to replace the rigid
* cwnd increase and decrease control (tcp_cong_avoid,tcp_*cwnd_reduction).
* It's called toward the end of processing an ACK with precise rate
* information. All transmission or retransmission are delayed afterwards.
*/
static void tcp_cong_control(struct sock *sk, u32 ack, u32 acked_sacked,
int flag, const struct rate_sample *rs)
{
const struct inet_connection_sock *icsk = inet_csk(sk);
if (icsk->icsk_ca_ops->cong_control) {
icsk->icsk_ca_ops->cong_control(sk, rs);
return;
}
if (tcp_in_cwnd_reduction(sk)) {
/* Reduce cwnd if state mandates */
tcp_cwnd_reduction(sk, acked_sacked, flag);
} else if (tcp_may_raise_cwnd(sk, flag)) {
/* Advance cwnd if state allows */
tcp_cong_avoid(sk, ack, acked_sacked);
}
tcp_update_pacing_rate(sk);
}
4.4. tcp_xmit_recovery
在拥塞控制算法更新窗口大小之后，tcp_xmit_recovery将处理可能产生的重传。
/* Congestion control has updated the cwnd already. So if we're in
* loss recovery then now we do any new sends (for FRTO) or
* retransmits (for CA_Loss or CA_recovery) that make sense.
*/
static void tcp_xmit_recovery(struct sock *sk, int rexmit)
{
struct tcp_sock *tp = tcp_sk(sk);
if (rexmit == REXMIT_NONE || sk->sk_state == TCP_SYN_SENT)
return;
if (unlikely(rexmit == REXMIT_NEW)) {
__tcp_push_pending_frames(sk, tcp_current_mss(sk),
TCP_NAGLE_OFF);
if (after(tp->snd_nxt, tp->high_seq))
return;
tp->frto = 0;
}
tcp_xmit_retransmit_queue(sk);
}
rexmit标志为REXMIT_NONE的时候自然不用重传；但是以下两种情况时，rexmit会被设为需要重传：
REXMIT_LOST：在tcp_fastretrans_alert中确认有丢包，或在tcp_process_loss（Loss状态）收到PACK，确认需要继续重传。REXMIT_NEW：需要发送一些新的数据，和F-RTO机制相关，这里不再做更深的探究。
REXMIT_LOST的情况下，我们会进入输出引擎的tcp_xmit_retransmit_queue，后者经过一系列调用链，到达TCP协议的重传入口__tcp_retransmit_skb。
5. 超时重传
5.1. 初始化重传定时器
icsk作为面向连接套接字，理应有重传管理。该结构体中有一个域叫icsk_retransmit_timer，它就是重传定时器。我们看一下它的初始化：
void tcp_init_sock(struct sock *sk)
{
struct inet_connection_sock *icsk = inet_csk(sk);
struct tcp_sock *tp = tcp_sk(sk);
/* ... */
tcp_init_xmit_timers(sk);
/* ... */
}tcp_init_xmit_timers初始化了很多定时器，例如经典的重传、delayed ACK、keep-alive计时器等。在内核学习笔记（七）——定时器和时间管理中我们讲过了定时器的基础知识和使用方法。
TIME_WAIT计时器在哪里？
TIME_WAIT计时器放在了一个迷你套接字inet_timewait_sock中，它派生出的tcp_timewait_sock只有232字节，相比于tcp_sock的2192字节，它在不违反TCP协议的条件下大幅节约了TIME_WAIT状态使用的内存。
void tcp_init_xmit_timers(struct sock *sk)
{
inet_csk_init_xmit_timers(sk, &tcp_write_timer, &tcp_delack_timer,
&tcp_keepalive_timer);
hrtimer_init(&tcp_sk(sk)->pacing_timer, CLOCK_MONOTONIC,
HRTIMER_MODE_ABS_PINNED_SOFT);
tcp_sk(sk)->pacing_timer.function = tcp_pace_kick;
hrtimer_init(&tcp_sk(sk)->compressed_ack_timer, CLOCK_MONOTONIC,
HRTIMER_MODE_REL_PINNED_SOFT);
tcp_sk(sk)->compressed_ack_timer.function = tcp_compressed_ack_kick;
}
5.2. 启动重传定时器
在L4/L3数据通路中我们提到过，TCP协议在向IP层交付新的报文段后，就启动一次tcp_event_new_data_sent，在其中完成计数、定时器等工作。我们看看它的实现：
/* Account for new data that has been sent to the network. */
static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb)
{
struct inet_connection_sock *icsk = inet_csk(sk);
struct tcp_sock *tp = tcp_sk(sk);
unsigned int prior_packets = tp->packets_out;
WRITE_ONCE(tp->snd_nxt, TCP_SKB_CB(skb)->end_seq);
__skb_unlink(skb, &sk->sk_write_queue);
tcp_rbtree_insert(&sk->tcp_rtx_queue, skb);
if (tp->highest_sack == NULL)
tp->highest_sack = skb;
tp->packets_out += tcp_skb_pcount(skb);
if (!prior_packets || icsk->icsk_pending == ICSK_TIME_LOSS_PROBE)
tcp_rearm_rto(sk);
NET_ADD_STATS(sock_net(sk), LINUX_MIB_TCPORIGDATASENT,
tcp_skb_pcount(skb));
}做了下面一些事情：
- 将刚发送出去的skb从
sk_write_queue中移除，然后再插入到tcp_rtx_queue中，这一步语义非常自然。 - 设置SACK相关的参数。
- 更新
packets_out，它代表已离开TCP发送队列的报文数量。 - 调用
tcp_rearm_rto重启超时计时器。 - 更新SNMP的一些统计数据。
tcp_rearm_rto调用tcp_reset_xmit_timer以重启计时器，主要看下面else分支的部分：
/* Restart timer after forward progress on connection.
* RFC2988 recommends to restart timer to now+rto.
*/
void tcp_rearm_rto(struct sock *sk)
{
// Omit some boring initialization here
if (!tp->packets_out) {
inet_csk_clear_xmit_timer(sk, ICSK_TIME_RETRANS);
} else {
u32 rto = inet_csk(sk)->icsk_rto;
// Omit some edge case handling for RTO here
tcp_reset_xmit_timer(sk, ICSK_TIME_RETRANS, rto,
TCP_RTO_MAX);
}
}
tcp_reset_xmit_timer中，启动重传超时器前，不应直接将其设为“当前时间+RTO”，因为从L4到离开主机还有一段时间，我们需要预估一个合理值并将其加上去，该工作由tcp_pacing_delay完成。最后通过icsk的通用接口inet_csk_reset_xmit_timer完成超时器的重设。
static inline void tcp_reset_xmit_timer(struct sock *sk,
const int what,
unsigned long when,
const unsigned long max_when)
{
inet_csk_reset_xmit_timer(sk, what, when + tcp_pacing_delay(sk),
max_when);
}
5.3. 超时重传回调操作
我们来关注超时重传的回调操作，通过一些锁操作后，tcp_write_timer会调用tcp_write_timer_handler。后者可能走向很多分支，但对于超时重传的情况，最终调用的是tcp_retransmit_timer。我们把关注的最核心的部分抽出来看看，其中我将个人理解以行内注释写在了代码中。
void tcp_retransmit_timer(struct sock *sk)
{
// ...
// Retreive a skb that caused timeout, then rtx it.
skb = tcp_rtx_queue_head(sk);
if (WARN_ON_ONCE(!skb))
return;
// ...
if (!tp->snd_wnd && !sock_flag(sk, SOCK_DEAD) &&
!((1 << sk->sk_state) & (TCPF_SYN_SENT | TCPF_SYN_RECV))) {
// ...
if (tcp_jiffies32 - tp->rcv_tstamp > TCP_RTO_MAX) {
// TCP_RTO_MAX is 120 seconds. If we couldn't recv
// any ACK for more than 2 mins, some bad things
// may have happened on the peer or network. We can't
// wait no more but have to close the connection.
tcp_write_err(sk);
goto out;
}
// Loss of packet is confirmed, we'll enter Loss state.
tcp_enter_loss(sk);
// Only rtx the skb that caused timeout.
tcp_retransmit_skb(sk, skb, 1);
// ...
goto out_reset_timer;
}
// ...
out_reset_timer:
// Omit some adjustment of RTO here. Next step is to reset the rtx timer.
inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS,
tcp_clamp_rto_to_user_timeout(sk), TCP_RTO_MAX);
// ...
out:;
}调用tcp_retransmit_skb时已经与快速重传合流，之后进入所有重传的入口__tcp_retransmit_skb。
