本文分析所采用的Linux版本为4.18
Linux系统中的TCP拥塞控制采用面向对象的设计思想，提供拥塞控制接口用于实现不同的拥塞控制策略，主要实现文件在tcp_cong.c中。
基本数据结构
tcp_cong_list为拥塞支持的拥塞控制策略（算法实现）的列表，列表中的每一表项对应一种拥塞控制策略的具体实现。
tcp_cong_list_lock为控制并发访问tcp_cong_list的自旋锁。
tcp_congestion_ops结构为拥塞控制的接口，暴露出可以修改实现的接口函数。
struct tcp_congestion_ops {
struct list_head list;
u32 key;
u32 flags;
/* 初始化私有数据（可选） */
void (*init)(struct sock *sk);
/* 清除私有数据（可选） */
void (*release)(struct sock *sk);
/* 返回慢启动阈值(必须的) */
u32 (*ssthresh)(struct sock *sk);
/* 计算新的cwnd值(必须的) */
void (*cong_avoid)(struct sock *sk, u32 ack, u32 acked);
/* 改变ca_state前调用(可选) */
void (*set_state)(struct sock *sk, u8 new_state);
/* 当cwnd事件发生时调用(可选) */
void (*cwnd_event)(struct sock *sk, enum tcp_ca_event ev);
/* ack到达时调用（可选） */
void (*in_ack_event)(struct sock *sk, u32 flags);
/* 丢包后新的cwnd值（必须的） */
void (*undo_cwnd)(struct sock *sk);
/* 数据包ack计数的钩子（可选的） */
void (*pkts_acked)(struct sock *sk, const struct ack_sample *sample);
/* 覆盖sysctl_tcp_min_tso_segs */
u32 (*min_tso_segs)(struct sock *sk);
/* 返回tcp_sndbuf_expand中使用的multiplier（可选的）*/
u32 (*sndbuf_expand)(struct sock *sk);
/* 在所有ca_state处理之后，当数据包交付以更新cwnd和
pacing rate时调用（可选的）*/
void (*cong_control)(struct sock *sk, const struct rate_sample *rs);
/* 获取inet_diag的信息（可选的）*/
size_t (*get_info)(struct sock *sk, u32 ext, int *attr,
union tcp_cc_info *info);
char name[TCP_CA_NAME_MAX];
struct module *owner;
}
当需要定义新的拥塞控制策略时，只需要修改相应的接口函数即可。
以下代码给出tcp_reno控制策略的接口实现。
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,
};
基本操作
tcp_ca_find用于在列表中查找指定名称的拥塞控制算法。该函数使用简单的线性查找，当表项较多时会导致性能下降。
static struct tcp_congestion_ops *tcp_ca_find(const char *name)
{
struct tcp_congestion_ops *e;
/* 遍历列表项 */
list_for_each_entry_rcu(e, &tcp_cong_list, list) {
if(strcmp(e->name, name) == 0)
return e;
}
return NULL;
}
tcp_ca_find_autoload函数用于查找具有指定名称的拥塞控制算法并自动载入，调用时要保持rcu锁定状态。
首先在列表中查找指定的拥塞控制算法，之后存在两种情况：
- 查找到指定的拥塞控制算法，直接返回。
- 为查找到指定的拥塞控制算法，且内核支持模块动态加载，且具有相应的权限，则尝试加载指定的拥塞控制算法。
static struct tcp_congestion_ops *tcp_ca_find_autoload(struct net *net, const char *name)
{
struct tcp_congestion_ops *ca = tcp_ca_find(name);
/* 支持内核模块时，加载该模块 */
#ifdef CONFIG_MODULES
// 该算法尚未载入并且具有加载权限
if(!ca && capable(CAP_NET_ADMIN） {
rcu_read_unlock();
request_module("tcp_%s", name);
rcu_read_lock();
ca = tcp_ca_find(name);
}
#endif
return ca;
}
tcp_ca_find_key用于在列表中查找指定键值(key)的拥塞控制算法。该函数使用简单的线性查找，当表项较多时会导致性能下降。
static struct tcp_congestion_ops *tcp_ca_find_key(u32 key)
{
struct tcp_congestion_ops *e;
/* 遍历列表项 */
list_for_each_entry_rcu(e, &tcp_cong_list, list) {
if(e->key == key)
return e;
}
return NULL;
}
tcp_register_congestion_control用于注册新的拥塞控制算法，即将新的拥塞控制算法添加到列表中。
int tcp_register_congestion_control(struct tcp_congestion_ops *ca)
{
int ret = 0;
/* 所有的拥塞控制算法都必须实现这些操作 */
if(!ca->ssthresh || !ca->undo_cwnd ||
!(ca->cong_avoid || ca->cong_control)) {
pr_err("%s does not implement required ops\n"， ca->name);
return -EINVAL;
}
ca->key = jhash(ca->name, sizeof(ca->name), strlen(ca->name));
spin_lock(&tcp_cong_list_lock);
if(ca->key == TCP_CA_UNSPEC || tcp_ca_find_key(ca->key)) {
pr_notice("%s already registered or non-unique key\n", ca->name);
return -EEXIST;
} else {
list_add_tail_rcu(&ca->list, &tcp_cong_list);
pr_debug("%s registered\n", ca->name);
}
spin_unlock(&tcp_cong_list_lock);
return ret;
}
EXPORT_SYMBOL_GPL(tcp_register_congestion_control);
与tcp_register_congestion_control函数相反，tcp_unregister_congestion_control函数在列表中删除指定的拥塞控制算法。该函数由模块的remove函数调用。模块的引用计数器保证只有在没有套接字使用该算法是才被删除。
void tcp_unregister_congestion_control(struct tcp_congestion_ops *ca)
{
spin_lock(&tcp_cong_list_lock);
list_del_rcu(&ca->list);
spin_unlock(&tcp_cong_list_lock);
/* 在模块完全删除前等待所有的读操作完成。*/
/* 此时，try_module_get将失败，这是因为模块处于"going"状态
(没有引用), 并且module_exit()正在被调用。*/
synchronize_rcu();
}
EXPORT_SYMBOL_GPL(tcp_unregister_congestion_control);
tcp_ca_get_key_by_name用于通过名称获取指定拥塞控制算法的键值(key）。ecn_ca为返回值。
u32 tcp_ca_get_key_by_name(struct net *net, const char *name, bool *ecn_ca)
{
const struct tcp_congestion_ops *ca;
u32 key = TCP_CA_UNSPEC;
might_sleep();
rcu_read_lock();
ca = tcp_ca_find_autoload(net, name);
if (ca) {
key = ca->key;
*ecn_ca = ca->flags & TCP_CONG_NEEDS_ECN;
}
rcu_read_unlock();
return key;
}
EXPORT_SYMBOL_GPL(tcp_ca_get_key_by_name);
tcp_ca_get_name_by_key用于通过键值获取指定拥塞控制算法的名称。
char *tcp_ca_get_key_by_name(u32 key, char *buffer)
{
const struct tcp_congestion_ops *ca;
char *ret = NULL;
rcu_read_lock();
ca = tcp_ca_find_key(key);
if(ca)
ret = strncpy(buffer, ca->name, TCP_CA_NAME_MAX);
rcu_read_unlock();
return ret;
}
EXPORT_SYMBOL_GPL(tcp_ca_get_name_by_key);
tcp_assign_congestion_control函数用于设置指定sock的拥塞控制算法。
首先，获取系统中设置的拥塞控制算法。如果该算法尚未加载，则将拥塞控制算法设置为tcp_reno；否则，使用系统中设置的拥塞控制算法。
void tcp_assign_congestion_control(struct sock *sk)
{
struct net *net = sock_net(sk);
struct inet_connection_sock *icsk = inet_csk(sk);
const struct tcp_congestion_ops *ca;
rcu_read_lock();
ca = rcu_dereference(net->ipv4.tcp_congestion_control);
if(unlikely(!try_module_get(ca->owner()))
ca = &tcp_reno;
icsk->icsk_ca_ops = ca;
rcu_read_unlock();
memset(icsk->icsk_ca_priv, 0, sizeof(icsk->icsk_ca_priv));
if(ca->flags & TCP_CONG_NEEDS_ECN)
INET_ECN_xmit(sk);
else
INET_ECN_dontxmit(sk);
}
tcp_init_congestion_control函数用于初始化指定sock的拥塞控制算法。
void tcp_init_congestion_control(struct sock *sk)
{
const struct inet_connection_sock *icsk = inet_csk(sk);
tcp_sk(sk)->prior_ssthresh = 0;
if(icsk->icsk_ca_ops->init)
icsk->icsk_ca_ops->init(sk);
if(tcp_ca_needs_ecn(sk))
INET_ECN_xmit(sk);
else
INET_ECN_dontxmit(sk);
}
tcp_reinit_congestion_control函数用于重新初始化指定sock的拥塞控制算法。
static void tcp_reinit_congestion_control(struct sock *sk, const struct tcp_congestion_ops *ca)
{
const struct inet_connection_sock *icsk = inet_csk(sk);
tcp_cleanup_congestion_control(sk);
icsk->icsk_ca_ops = ca;
icsk->icsk_ca_setsockopt = 1;
memset(icsk->icsk_ca_priv, 0, sizeof(icsk->icsk->icsk_ca_priv));
if(sk->sk_state != TCP_CLOSE)
tcp_init_congestion_control(sk);
}
tcp_cleanup_congestion_control用于清除指定sock的拥塞控制算法。
void tcp_cleanup_congestion_control(struct sock *sk)
{
struct inet_connection_sock *icsk = inet_csk(sk);
if(icsk->icsk_ca_ops->release)
icsk->icsk_ca_ops->release(sk);
module_put(icsk->icsk_ca_ops->owner);
}
tcp_set_default_congestion_control用于设置默认的拥塞控制算法。sysctl调用该函数。
int tcp_set_default_congestion_control(struct net *net, const char *name)
{
struct tcp_congestion_ops *ca;
const struct tcp_congestion_ops *prev;
int ret;
rcu_read_lock();
ca = tcp_ca_find_autoload(net, name);
if(!ca) {
ret = -ENOENT;
} else if(!try_module_get(ca->owner)) {
ret = -EBUSY;
} else {
prev = xchg(&net->ipv4.tcp_congestion_control, ca);
if(prev)
module_put(prev->module);
ca->flags |= TCP_CONG_NON_RESTRICTED;
ret = 0;
}
rcu_read_unlock();
return ret;
}
tcp_congestion_default函数用于系统启动时通过kernel配置信息设置默认值。
static int __init tcp_congestion_default(void)
{
return tcp_set_default_congestion_control(&init_net, CONFIG_DEFAULT_TCP_CONG);
}
late_initcall(tcp_congestion_default);
tcp_get_available_congestion_control用于获取可用的拥塞控制算法
void tcp_get_available_congestion_control(char *buf, size_t maxlen)
{
struct tcp_congestion_ops *ca;
size_t offs = 0;
rcu_read_lock();
list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
offs += snprintf(buf+offs, maxlen - offs, "%s%s",
offs == 0 ? "" : " ", ca->name);
}
rcu_read_unlock();
}
tcp_get_default_congestion_control用于获取当前的默认拥塞控制算法。
void tcp_get_default_congestion_control(struct net *net, char *name)
{
const struct tcp_congestion_ops *ca;
rcu_read_lock();
ca = rcu_dereference(net->ipv4.tcp_congestion_control);
strncpy(name, ca->name, TCP_CA_NAME, MAX)；
rcu_read_unlock();
}
tcp_get_allowed_congestion_control用于获取non-restricted的拥塞控制算法。
void tcp_get_allowed_congestion_control(char *buf, size_t maxlen)
{
struct tcp_congestion_ops *ca;
size_t offs = 0;
*buf = '\0';
rcu_read_lock();
list_for_each_entry_rcu(ca, &tcp_cong_list, list) {
if(!(ca->flags & TCP_CONG_NON_RESTRICTED))
continue;
offs += snprintf(buf + offs, maxlen - offs, "%s%s",
offs == 0 ? "" : " ", ca->name);
}
rcu_read_unlock();
}
tcp_set_allowed_congestion_control用于改变non-restricted拥塞控制算法列表。val为以空格分隔的拥塞控制算法名称列表。
int tcp_set_allowed_congestion_control(char *val)
{
struct tcp_congestion_ops *ca;
char *saved_clone, *clone, *name;
int ret = 0;
saved_clone = clone = kstrdup(val, CFP_USER);
if(!clone)
return -ENOMEM;
spin_lock(&tcp_cong_list_lock);
/* pass 1: 检查bad表项 */
while ((name = strsep(&clone, " ")) && *name) {
ca = tcp_ca_find(name);
if(!ca) {
ret = -ENOENT;
goto out;
}
}
/* pass 2: 清除旧值 */
list_for_each_entry_rcu(ca, &tcp_cong_list, list)
ca->flags &= ~TCP_CONG_NON_RESTRICTED;
/* pass 3: 标记 */
while ((name = strsep(&clone, " ")) && *name) {
ca = tcp_ca_find(name);
WARN_ON(!ca);
if(ca)
ca->flags |= TCP_CONG_NON_RESTRICTED;
}
out:
spin_unlock(&tcp_cong_list_lock);
kfree(saved_clone);
return ret;
}
tcp_set_congestion_control用于设置指定sock的拥塞控制算法。如果load的值为false，调用者负责调用tcp_init_congestion_control或者tcp_reinit_congestion_control(如果当前的拥塞控制算法已经初始化)。
int tcp_set_congestion_control(struct sock *sk, const char *name, bool laod, bool reinit)
{
struct inet_connection_sock *icsk = inet_csk(sk);
const struct tcp_congestion_ops *ca;
int err = 0;
if(icsk->icsk_ca_dst_locked)
return -EPERM;
rcu_read_lock();
if(!load)
ca = tcp_ca_find(name);
else
ca = tcp_ca_find_autoload(sock_net(sk), name);
/* 如果当前值和设置值相同，不需要修改 */
if (ca == icsk->icsk_ca_ops) {
icsk->icsk_ca_setsockopt = 1;
goto out;
}
if(!ca) {
err = -ENOENT;
} else if(!load) {
const struct tcp_congestion_ops *old_ca = icsk->icsk_ca_ops；
if（try_module_get(ca->owner)) {
if(reinit) {
tcp_reinit_congestion_control(sk, ca);
} else {
icsk->icsk_ca_ops = ca;
module_put(old_ca->owner);
}
} else {
err = -EBUSY;
}
} else if(!((ca->flags & TCP_CONG_NON_RESTRICTED) ||
ns_capable(sock_net(sk)->user_ns, CAP_NET_ADMIN))) {
err = -EPERM;
} else if(!try_module_get(ca->owner)) {
err = -EBUSY;
} else {
tcp_reinit_congestion_control(sk, ca);
}
out:
rcu_read_unlock();
return err;
}
当拥塞窗口的大小不大于慢启动阈值时，使用慢启动过程。tcp_slow_start函数基于RFC2581，且适当地处理stretch ACKs。本函数没有实现RFC3456的Appropriate Byte Counting (ABC)。
u32 tcp_slow_start(struct tcp_sock *tp, u32 acked)
{
u32 cwnd = min(tp->snd_cwnd + acked, tp->snd->ssthresh);
acked -= cwnd - tp->snd_cwnd;
tp->snd_cwnd = min(cwnd, tp->snd_cwnd_clamp);
return acked;
}
EXPORT_SYMBOL_GPL(tcp_slow_start);
tcp_cong_avoid_ai函数实现拥塞避免阶段的加法增加。理论上，对每个acked的数据包，更新tp->snd_cwnd += 1/tp->snd_cwnd（或w）。
void tcp_cong_avoid_ai(struct tcp_sock *tp, u32 w, u32 acked)
{
/* 如果在较高的w值累计信用，则温和地应用 */
if(tcp->snd_cwnd_cnt >= w) {
tp->snd_cwnd_cnt = 0;
tp->snd_cwnd++;
}
tp->snd_cwnd_cnt += acked;
if(tp->snd_cwnd_cnt >= w) {
u32 delta = tp->snd_cwnd_cnt / w;
tp->snd_cwnd_cnt -= delta * w;
tp->snd_cwnd += delta;
}
tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_cwnd_clamp);
}
EXPORT_SYMBOL_GPL(tcp_cong_avoid_ai);
导出的函数列表
- tcp_register_congestion_control
- tcp_unregister_congestion_control
- tcp_ca_get_key_by_name
- tcp_ca_get_name_by_key
- tcp_slow_start
- tcp_cong_avoid_ai
RFC2581
RFC2581描述了4中拥塞控制算法：慢启动、拥塞避免、快速重传和快速恢复。
慢启动和拥塞避免
发送端控制向网络中发送的数据量。为了实现这些算法，每个TCP连接状态增加两个变量：拥塞窗口(cwnd)为发送端在接收到ACK前可以发送到网络中的数据量；发送端通告窗口(rwnd)主机端数据量限制。cwnd和rwnd的较小值决定了数据传输量。
另外，还需要状态变量慢启动阈值(ssthresh)，用于确定使用慢启动算法还是拥塞避免算法。
在向未知状态的网络中发送数据时，需要TCP缓慢地探测网络以确定可用的容量。慢启动算法用于这一目的。
ssthresh的初始值可以任意大（例如，一些实现使用通告窗口大小）,但在响应拥塞时减少。当cwnd < ssthresh时，使用慢启动算法，当cwnd > ssthresh时使用拥塞避免算法。当cwnd和ssthresh的值相等时，发送端可以使用慢启动或者拥塞避免。
慢启动期间，对每个收到的新数据的ACK，TCP最多将cwnd的值增加SMSS字节。当cwnd值超过ssthresh或观察到拥塞时，慢启动过程终止。
拥塞避免期间，每RTT时间cwnd的值增加1个全尺寸数据段大小。拥塞避免阶段持续到检测到拥塞。,该式是对上述更新1个全尺寸数据段大小的一种可接受逼近，且在每个非重复ACK时更新。另一种可接受的增加cwnd值的方法是计算新数据ACK确认地字节数（缺点是需要维护附加的状态变量）。当确认地字节数量达到cwnd时，cwnd的值增加SMSS字节。
快速重传/快速恢复
当乱序数据包到达时，TCP接收端需要立即发送重复ACK，用于通告发送端接收到乱序数据包和期望的序列号。
发送端使用快速重传算法检测和恢复丢包，基于重复ACK。快速重传算法使用3个重复ACK(4个相同的ACK,且期间没有其他ACK）作为数据包丢失的指示。发送端接收到3个重复ACK后，执行丢失数据包的重传，而不是等到重传计数器超时。
快速重传算法发送丢失的数据包后，进入快速恢复阶段，直到非重复ACK到达。
