TCP拥塞控制算法的Linux内核实现
TCP拥塞控制算法及Linux内核实现
朱前1
（1.华中科技大学电子与信息工程学院09种子班 U200913678,湖北武汉 430074）
摘要：Internet在过去的几十年当中经历了飞速的发展，而作为互联网协议中的一个重要部分的TCP
拥塞控制算法无疑也是受到了很大的挑战；现在互联网上运行着的TCP拥塞控制算法已经不下十种，而且还有新的算法在不断地提出中，但是很少有真正能够用到实际中的。本文将以互联网上流量最的操作系统Linux的内核源码着手，主要研究一下现在在互联网上运行着的TCP拥塞控制算法都是哪些算法以及源码分析。
关键词：传输控制协议；拥塞协议；拥塞算法；Linux内核
中图分类号：TN915 文献标识码：A 文章编号：1000-100X(2011)12-0101-07
TCP Congestion Avoidance Algorithm Identification
ZHU Qian
(1.Electric&Information College U200913678, Huazhong University of Science&Technology, Wuhan 430074
China)
Abstract: Internet has experienced an amazing speed’s development in the passed dozens of years. As an important part of Internet protocol. TCP congestion avoidance algorithm faced so many challenges. There are more than ten kinds of algorithms running in the Internet. And more algorithms is approved. Even though much of these algorithm can’t be running in the Internet. In this paper, we will star t with the source code of Linux, which is the most popular operating system running on nowadays Internet. We will try to understand the source code and see which algorithm is used in Linux.
Key words: TCP; Congestion Avoidance; Congestion Algorithm; Linux Kernel
1.引言
由于Internet是一种基于Best-Effort服务的网络，传输控制协议TCP却能够在不可靠的互联网上提供可靠的服务，所以说TCP已经得到了大量的部署和使用并且统治着几乎全部的Internet数据流量。然而TCP协议的性能又在很大程度上由TCP拥塞控制算法决定，当今互联网上的算法又实在太多，如果想要专心研究几个算法还真不知道应该研究那些，不过有过研究称现在传统的AIMD算法已经不再是
用得最多的算法了[1]。不过在研究中只是对前5000的服务器进行了一个并不一定准确的测定，笔者
认为现在很多的很多服务器还是基于Linux操作系统，很多人并不会对原本的算法进行修改也没有多
大的必要，我们通过查看/proc/sys/net/ipv4/tcp_congestion_control可以发现现在的Linux内核默认是cubic算法，所以我笔者猜测之前的研究[1]虽然是基于真正的事实，但是毕竟是最大的服务器集群，那是属于一个很专业的系统，也就是说管理员很有可能在每个地方都尽量给出最好的方案，但是大多数
普通的服务器并没有这个必要，也就是说那5000个流量最大的服务器集群并不能够真实地反应我们当今Internet上的算法部署情况。毫无疑问的是现在的服务器大多都是Linux内核，相信cubic以及一些
别的Linux内核内置的算法在整个Internet上占有的比率肯定大于之前的研究。本文并不会在具体的占有率上进行研究，只是谈及一下Linux内核2.6.36版本的TCP拥塞控制算法实现，同时会介绍一下Linux的TCP拥塞控制。
2.TCP拥塞控制简介
我们知道现在的整个互联网体系结构是以IP协议为基础的，是一种基于无连接的端到端的报文传输服务，端到端传输的有点很多，但是有一个基本的问题就是需要自己来保证数据的可靠性。
所以说TCP的拥塞控制对于整个Internet来说都是非常重要的，本文就将对Linux操作系统的拥塞控制算法进行一定的源码分析，更为深层次的分析笔者可能会在以后做一定的阐述。
先来看一下TCP是如何保证数据的可靠传输的[2]，TCP的设计其实非常容易理解的，TCP对所传输的数据都做了序号标记，序号按着字节数来增长，TCP的接收方在接到数据后发出一个确认（ACK）给对端，ACK里面包含一个序列号，这个序列号n表示序号在n之前的数据已经全部收到了，现在期待序号为n的数据到来。我们必须要知道的一个事实就是，主机发去网络上的任何一个数据包都有可能在网络上被丢弃，由于网络中路由器处理能力限制、链路错误等原因都会导致数据包的丢弃。如果ACK被丢弃了的话，，那么就要靠重传机制了。TCP对发出去的数据包都保留有计时器，如果定时器到而确认还没有收到的情况下，TCP会对刚才发送的数据包进行重传。TCP使用确认和超时重传机制保障了数据的可靠性传输。
当网络中存在过多的报文时，网络的性能就会相应下降，这种现象就被称为拥塞。TCP的拥塞控制有很多的机制（慢启动、拥塞避免、快速重传、快速恢复等），具体的一些工作方式在很多书籍论文中都已经有所阐述，本文将不再赘述。
3.Linux源码概述
作为黑客们技术和梦想的结晶，Linux无疑是这个世纪黑客们以及那些开源爱好者们最大的创举，有时候不禁感慨如果这个世界没有Linux或是Unix将是怎样，应该来说肯定会有别的系统来替代Linux的位置，但是现在，Linux在这么多年的发展，在世界的各个地方都布满了Linux的身影，尤其是这几十年随着Internet的迅速发展，Linux这样一个开源的操作系统更是大发神威，因为其在Internet上的出色表现（稳定、可定制、免费等），现在的Linux操作系统已经成为Internet 上最重要的操作系统，为世界的交流和互通提供了最基本的服务。
既然Linux在现代社会和Internet占有这么重要的地位，那么毫无疑问的是这个系统上的任何一个设计，尤其是关于网络的设计对整个互联网而言都是非常重要的，笔者也是考虑到这个问题所以说选择Linux的源码来分析我们所探讨的主题。但是因为笔者时间并不宽裕，很多地方也没有深入去研究，所以说肯定还有很多需要提升的地方，待日后再返工。
4.Linux源码分析一：基本数据结构和函数
Linux内核支持相当多种的TCP拥塞控制算法，不过在内核2.6.19版本之后默认的算法调成了CUBIC算法。首先说说Linux内核拥塞控制算法实现的框架，Linux
下面介绍一下Linux内核实现拥塞控制的几个共同的数据结构或函数：
1)inet_connection_sock是Linux内核拥塞控制实现相当重要的一个数据结构。由于这个数据
结构实在太大，具体的定义可以参考include/inet/inet_connection_sock.h里面的定义，这里
笔者就大概拿出几个比较重要的来说一下吧。
首先是conststructtcp_congestion_ops *icsk_ca_ops，这个结构体指向的是一个包含大量的处
理拥塞控制算法的指针，结构体中还有一个是u32 icsk_ca_priv[16]，这里的作用是放置拥
塞控制模块需要的变量控制，也就是算法运行过程中需要的那些常量都是保存在这里的，
具体的赋值运行过程由于在代码里面也没有太多的注释所以很难理解深刻，需要注意的一
点是Linux内核设定了一套算法注册和删除的体系。其实就是一个链表，把新注册的数据
结构插在链表的第一位，连接建立的时候会把最新注册的算法数据结构赋给连接；当然我
们也是可以调整算法顺序的，/proc/sys/net/ipv4/tcp_congestion_contril就是干这个事的。
2)Tcp_sock这个结构体是一个很重要的结构体，里面定义了相当多的和TCP拥塞控制有关的，
这个结构体非常大，具体的定义在include/linux/Tcp.h里面，下面大概介绍一下比较重要的
几个参数：
structtcp_sock
{ ...
u32 window_clamp ; /* 最大窗口值 */
u32 rcv_ssthresh ; /* 当前窗口阈值 */
u32 rcv_wnd ; /* 当前接收窗口大小 */
...
/* snd_wll记录发送窗口更新时，造成窗口更新的那个数据报的第一个序号。
* 它主要用于在下一次判断是否需要更新发送窗口。
*/
u32 snd_wll ; /* 用于窗口更新的seq值 */
u32 snd_wnd ; /* 发送窗口的大小，直接取值于来自对方的数据报的TCP首部 */
u32 max_window ; u32 snd_una ;
...
u32 snd_ssthresh ; /* 慢启动的阈值 */
u32 snd_cwnd ; /* 发送方拥塞窗口 */
/*表示在当前的拥塞控制窗口中已经发送的数据段的个数*/
u32 snd_cwnd_cnt ; /* 增长因子 */
u32 snd_cwnd_clamp ; /* 增长因子的最大值 */
...
u32 mss_cache ; /* 有效mss值 */
u32 bytes_acked ; /* ACK的计数 */
...
}
3)Tcp_slow_start这个方法是定义在net/ipv4/tcp_cong.c文件中的一种方法。当拥塞窗口小于
慢启动阈值的时候就会启动。主要在RFC2581中定义。
voidtcp_slow_start(structtcp_sock *tp)
{
intcnt; /* 报文数目 */
if (sysctl_tcp_abc&&tp->bytes_acked
return; /* ACK接收完毕 */
if (sysctl_tcp_max_ssthresh> 0 &&tp->snd_cwnd>sysctl_tcp_max_ssthresh)
cnt = sysctl_tcp_max_ssthresh>> 1; /* 受限慢启动 */
else
cnt = tp->snd_cwnd; /* 指数递增 */
if (sysctl_tcp_abc> 1 &&tp->bytes_acked>= 2*tp->mss_cache)
cnt<<= 1;
tp->bytes_acked = 0;
tp->snd_cwnd_cnt += cnt;
while (tp->snd_cwnd_cnt>= tp->snd_cwnd) {
tp->snd_cwnd_cnt -= tp->snd_cwnd;
if (tp->snd_cwnd
tp->snd_cwnd++;
}
}
4)拥塞避免算法tcp_cong_avoid_ai定义于net\ipv4\Tcp_cong.c，这个算法其实就是判断一下
当前发送拥塞窗口和一个传入参数w进行比较，如果发送计数器大于w且发送窗口没有到
达阈值就自增，如果到达阈值了就置为0；如果发送计数器压根没有大于w的话计数器自
增。
5.Linux源码分析二：cubic算法
前面的介绍可能不是很清楚，如果想要更全面更清楚弄清楚这个流程可能需要更多的资料和代码研究，本文限于篇幅和笔者的水平只能尽力描述一下这一块的实现及主要的结构流程，那么我们接下来看一
看默认算法cubic的代码实现。
首先和很多别的算法都一样，cubic算法会调用tcp_slow_start这个方法来处理slow start，内核中的
slow start的实现机制是接收一个ack，snd_cwnd就会加1，然后当cwnd大于设置的拥塞窗口阈值的时
候就会进入拥塞避免状态。而在发送数据包的时候回判断这个值，在in_flight字段大于它的时候就会
停止发包。因为cubic算法的设定是一直都通过慢启动来调整窗口大小的，当然，具体的这个算法特
性本文不会讲得太多。
我们通过分析源码可以知道，在slow start的状态时发送拥塞窗口就是简单地每次加一，进入拥塞避免后，拥塞窗口的增大速度就会变慢很多[3]。
算法的核心状态控制代码定义在net/ipv4/Tcp_bic.c如下：
static void bictcp_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
{
structtcp_sock *tp = tcp_sk(sk);
structbictcp *ca = inet_csk_ca(sk);
if (!tcp_is_cwnd_limited(sk, in_flight))//判断拥塞窗口是否达到限制
return;
if (tp->snd_cwnd<= tp->snd_ssthresh)//决定下一步进入的状态
tcp_slow_start(tp);
else {
bictcp_update(ca, tp->snd_cwnd);
tcp_cong_avoid_ai(tp, ca->cnt);
}
}
这段代码主要是控制状态之间的转换，接下来会有一个tcp_is_cwnd_limited的函数来实现对拥塞窗口的检测，通过这个函数我们可以知道是否还能继续添加包。
inttcp_is_cwnd_limited(conststruct sock *sk, u32 in_flight)
{
conststructtcp_sock *tp = tcp_sk(sk);
u32 left;
if (in_flight>= tp->snd_cwnd)
//in_flight的计算很纠结，应该是和未确认数据包相关的一个参数
return 1;
//未发送的报文
left = tp->snd_cwnd - in_flight;
if (sk_can_gso(sk) &&
left * sysctl_tcp_tso_win_divisor
left * tp->mss_cache
return 1;
return left <= tcp_max_burst(tp);//所以返回的是1就是被限制，需要增加窗口}
这个算法的主要代码都在Tcp_cong.c、Tcp_cubic.c两个文件里面，有很多的相关的设置没有弄得很清楚，反正最后的拥塞避免处理就是tcp_cong_avoid_ai，这里决定是否增加拥塞窗口的值，否则增加snd_cwnd_cnt。大体的流程和主要函数就如上所述。
6.总结
内核代码的研究是一件非常富有挑战而艰难的工作，其实笔者最后并没有把这些为数不少的代码完全串起来，应该说就算是现在网上有一些代码分析，但是很多都是有问题的，内核代码的注释也并不足以让一个菜鸟一下子能够理解整个流程，这是一个真正的大工程，可能在一些专门的互联网公司中会有一定的总结和经验，但是并没有真正比较权威的分析报告在网上来让那些对开源感兴趣的大学生或别的入门级的感兴趣的人来做一个参考，本文的分析自然是纰漏无数，逻辑也并不缜密，
只是希望更多的人能够感受到开源的魅力，让更多的人加入到开源社区中去真正实现自己技术上的价值。
参考文献：
[1] Peng Yang, Wen Luo, LisongXu, JitenderDeogun, and Ying Lu TCP Congestion Avoidance Algorithm Identification 2011 31st International Conference on Distributed Computing Systems
[2]Larry L.Peterson Bruce S.Davie计算机网络-系统方法 2005
[3]刘炜 Linux kernel tcp拥塞处理之cubic算法https://www.wendangku.net/doc/7012391943.html,/