赵占旭的博客

Linux内核报文收发-TCP

版本说明


Linux版本: 3.10.103
网卡驱动: ixgbe

协议头


avatar

注意上图中的五个非常重要的东西:

  • Sequence Number是包的序号,用来解决网络包乱序(reordering)问题。
  • Acknowledgement Number就是ACK——用于确认收到,用来解决不丢包的问题。
  • Window又叫Advertised-Window,也就是著名的滑动窗口(Sliding Window),用于解决流控的。
  • TCP Flag ,也就是包的类型,主要是用于操控TCP的状态机的。
  • TCP Options,主要是用于协商信息用的。

flags

avatar
avatar

options

avatar

数据是tlv形式,主要有kind-len-content,一些kind类型如下:

KindMeaning
0End of Option List
1No-Operation
2Maximum Segment Size
3WSOPT - Window Scale
4SACK Permitted
5SACK
6Echo (obsoleted by option 8)
7Echo Reply (obsoleted by option 8)
8TSOPT - Time Stamp Option
9Partial Order Connection Permitted
10Partial Order Service Profile
11CC
12CC.NEW
13CC.ECHO
14TCP Alternate Checksum Request
15TCP Alternate Checksum Data
16Skeeter
17Bubba
18Trailer Checksum Option
19MD5 Signature Option
20SCPS Capabilities
21Selective Negative Acknowledgements
22Record Boundaries
23Corruption experienced
24SNAP
25Unassigned (released 12/18/00)
26TCP Compression Filter

状态转换图


avatar

连接建立和销毁


avatar

对于建链接的3次握手,主要是要初始化Sequence Number的初始值。通信的双方要互相通知对方自己的初始化的Sequence Number(缩写为ISN:Inital Sequence Number)——所以叫SYN,全称Synchronize Sequence Numbers。也就上图中的 x 和 y。这个号要作为以后的数据通信的序号,以保证应用层接收到的数据不会因为网络上的传输的问题而乱序(TCP会用这个序号来拼接数据)。

对于4次挥手,其实你仔细看是2次,因为TCP是全双工的,所以,发送方和接收方都需要Fin和Ack。只不过,有一方是被动的,所以看上去就成了所谓的4次挥手。如果两边同时断连接,那就会就进入到CLOSING状态,然后到达TIME_WAIT状态。

数据传输


avatar

该图是我从Wireshark中截了个我在访问百度时的有数据传输的图,看下SeqNum是怎么变的。

SeqNum的增加是和传输的字节数相关的。该图中,三次握手后,来了个Len:351的包,而第二个包的SeqNum就成了352。然后第一个ACK回的是352,表示第一个352收到了。

重传机制


TCP要保证所有的数据包都可以到达,所以,必需要有重传机制。
重传机制:

  • 超时重传机制。
  • 快速重传机制。
  • SACK(Selective Acknowledgment)。
  • Duplicate SACK – 重复收到数据的问题。

超时重传

avatar

接收端给发送端的Ack确认只会确认最后一个连续的包。比如,发送端发了1,2,3,4,5一共五份数据,接收端收到了1,2,于是回ack 3,因为数据包3丢失了,所以收不到ACK,等到一定的时间超时之后就会重新发送。

需要关注的问题就是我们设置超时时间多长?

  • 设长了,重发就慢,没有效率,性能差。
  • 设短了,重发的就快,会增加网络拥塞,导致更多的超时,更多的超时导致更多的重发。

这时TCP也比较纠结到底设置多长时间(后续也会讲具体的超时依据,但也不是完美设置超时时间),所以我们还需要找到一种方式来缓解超时带来的误差。

快速重传

avatar

TCP引入了一种叫Fast Retransmit 的算法,不以时间驱动,而以数据驱动重传。
如果包没有连续到达,就ack最后那个可能被丢了的包,如果发送方连续收到3次相同的ack,就重传。Fast Retransmit的好处是不用等timeout了再重传。
比如:发送方发出了1,2,3,4,5份数据,第一份先到送了,于是就ack回2,结果2因为某些原因没收到,3到达了,于是还是ack回2,后面的4和5都到了,但是还是ack回2,因为2还是没有收到,于是发送端收到了三个ack=2的确认,知道了2还没有到,于是就马上重转2。然后,接收端收到了2,此时因为3,4,5都收到了,于是ack回6。
Fast Retransmit缓解了超时误差的问题,但是我是要重传2还是重传2、3、4、5?因为发送端并不清楚这连续的3个ack(2)是谁传回来的?也许发送端发了20份数据,是#6,#10,#20传来的呢。
对此有两种选择:

  • 仅重传2。这样会节省带宽,但是慢,要继续等ACK。
  • 重传2之后所有的数据。这样不用等,比较快,但是会浪费带宽,也可能会有无用功。

所以TCP急需知道对方丢掉的具体包是哪个。

SACK

avatar

Selective Acknowledgment(SACK),这种方式需要在TCP头里加一个SACK的东西,ACK还是Fast Retransmit的ACK,SACK则是汇报收到的数据碎片。这样,在发送端就可以根据回传的SACK来知道哪些数据到了,哪些没有到。于是就优化了Fast Retransmit的算法。当然,这个协议需要两边都支持。在 Linux下,可以通过tcp_sack参数打开这个功能(Linux 2.4后默认打开)。
这里还需要注意一个问题——接收方Reneging ,所谓Reneging的意思就是接收方有权把已经报给发送端SACK里的数据给丢了。这样干是不被鼓励的,因为这个事会把问题复杂化了,但是,接收方这么做可能会有些极端情况,比如要把内存给别的更重要的东西。所以,发送方也不能完全依赖SACK,还是要依赖ACK,并维护Time-Out,如果后续的ACK没有增长,那么还是要把SACK的东西重传,另外,接收端这边永远不能把SACK的包标记为Ack。
注意:SACK会消耗发送方的资源,试想,如果一个攻击者给数据发送方发一堆SACK的选项,这会导致发送方开始要重传甚至遍历已经发出的数据,这会消耗很多发送端的资源。

传输控制


TCP需要保证尽量合理使用带宽资源,不能抢太多资源,也不能空闲太多资源。抢太多资源,就容易造成负荷太重而丢包,太空闲何必买这么大的带宽,败家。
传输控制机制:

  • TCP的RTT算法。
  • TCP滑动窗口协议。
  • TCP的拥塞处理。
  • 其它拥塞控制算法简介

RTT

从前面的TCP的重传机制我们知道Timeout的设置对于重传非常重要。
这个超时时间在不同的网络的情况下,有不同的时间,根本没有办法设置一个固定值。只能动态地设置。 为了动态地设置,TCP引入了RTT——Round Trip Time,也就是一个数据包从发出去到回来的时间。这样发送端就大约知道需要多少的时间,从而可以方便地设置Timeout——RTO(Retransmission TimeOut),以让我们的重传机制更高效。 听起来似乎很简单,好像就是在发送端发包时记下t0,然后接收端再把这个ack回来时再记一个t1,于是RTT = t1 – t0。没那么简单,这只是一个采样,不能代表普遍情况。

RTT算法:

  • 经典算法。
  • Karn / Partridge 算法。
  • Jacobson / Karels 算法(Linux当前使用)

经典算法

RFC793 中定义的经典算法是这样的:

  • 首先,先采样RTT,记下最近好几次的RTT值。
  • 然后做平滑计算Smoothed RTT。公式为: SRTT = (αSRTT) + ((1-α)RTT)(其中的 α 取值在0.8 到 0.9之间,这个算法叫加权移动平均(Exponential weighted moving average))
  • 开始计算RTO。公式如下: RTO = min[UBOUND, max[LBOUND, (β*SRTT)]]

其中:
UBOUND是最大的timeout时间,上限值。
LBOUND是最小的timeout时间,下限值。
β 值一般在1.3到2.0之间。

avatar

经典算法在重传的时候会出有一个终极问题——你是用第一次的时间和ack回来的时候做RTT样本,还是用重传的时间和ACK的时间做RTT样本?
如图所示:

  • 是ack没回来,所发重传。如果你计算第一次发送和ACK的时间,那么,明显算大了。
  • 是ack回来慢了,重传不一会,之前ACK就回来了。如果你是算重传的时间和ACK回来的时间,就会短了。

Karn / Partridge 算法

1987年的时候,搞了一个叫Karn/Partridge的算法,这个算法的最大特点是——忽略重传,不把重传的RTT做采样(眼不见心不烦)。

但是,这样一来,又会引发一个大BUG:
如果在某一时间,网络闪动,突然变慢了,产生了比较大的延时,这个延时导致要重转所有的包(因为之前的RTO很小),于是,因为重转的不算,所以,RTO就不会被更新,这是一个灾难。

于是Karn算法用了一个取巧的方式——只要一发生重传,就对现有的RTO值翻倍(这就是所谓的指数退避(Exponential backoff))。

Jacobson / Karels 算法

前面两种算法用的都是“加权移动平均”,这种方法最大的毛病就是如果RTT有一个大的波动的话,很难被发现,因为被平滑掉了。
1988年,又有人推出来了一个新的算法,这个算法叫Jacobson / Karels Algorithm(参看RFC6289)。
这个算法引入了最新的RTT的采样和平滑过的SRTT的差距做因子来计算。
公式如下:

1
2
3
SRTT = SRTT + α (RTT – SRTT)
DevRTT = (1-β)*DevRTT + β*(|RTT-SRTT|) //(其中的DevRTT是Deviation RTT的意思)
RTO= µ * SRTT + ∂ *DevRTT //(其中:在Linux下,α = 0.125,β = 0.25, μ = 1,∂ = 4 ——这就是算法中的“调得一手好参数”,nobody knows why, it just works…)

最后的这个算法在被用在今天的TCP协议中(Linux的源代码在:tcp_rtt_estimator)。

滑动窗口

TCP使用一种窗口(window)机制来控制数据流,TCP头里有一个字段叫Window,这个字段是接收端告诉发送端自己还有多少缓冲区可以接收数据。于是发送端就可以根据这个接收端的处理能力来发送数据,而不会导致接收端处理不过来。

avatar

图中的1,2,3号数据已经发送成功。
4,5,6号数据帧已经被发送出去,但是未收到关联的ACK。
7,8,9帧则是等待发送。
可以看出发送端的窗口大小为6,这是由接受端告知的。
此时如果发送端收到4号ACK,则窗口的左边缘向右收缩,窗口的右边缘则向右扩展,此时窗口就向前“滑动了”,即数据帧10也可以被发送。

avatar

Zero Window
从上一张图,我们可以看到一个处理缓慢的Server是怎么把TCP Sliding Window给降成0的。
如果Window变成0了,TCP会使用Zero Window Probe技术(缩写为ZWP),发送端会发ZWP的包给接收方,让接收方来ack他的Window尺寸,一般这个值会设置成3次,第3次大约30-60秒(依实现而定)。如果3次过后还是0的话,有的TCP实现就会发RST把链接断了。

注意:
只要有等待的地方都可能出现DDoS攻击,Zero Window也不例外,一些攻击者会在和HTTP建好链发完GET请求后,就把Window设置为0,然后服务端就只能等待进行ZWP,于是攻击者会并发大量的这样的请求,把服务器端的资源耗尽。

现在接收窗口的大小是根据对端接收能力来确定的,那么网络中间状态或者说我们的带宽是否需要考虑?

拥塞处理

TCP通过一个timer采样了RTT并计算RTO,如果网络上的延时突然增加,那么,TCP对这个事做出的应对只有重传数据,而重传会导致网络的负担更重,于是会导致更大的延迟以及更多的丢包,于是,这个情况就会进入恶性循环被不断地放大。

试想一下,如果一个网络内有成千上万的TCP连接都这么行事,那么马上就会形成“网络风暴”,TCP这个协议就会拖垮整个网络。这是一个灾难。 所以,TCP不能忽略网络上发生的事情,而无脑地一个劲地重发数据,对网络造成更大的伤害。

对此TCP的设计理念是:TCP不是一个自私的协议,当拥塞发生的时候,要做自我牺牲。就像交通阻塞一样,每个车都应该把路让出来,而不要再去抢路了。

拥塞控制主要是四个算法:

  • 慢启动。
  • 拥塞避免。
  • 拥塞发生。
  • 快速恢复。

这四个算法不是一天都搞出来的,这个四算法的发展经历了很多时间,到今天都还在优化中。

慢启动

慢启动的意思是,刚刚加入网络的连接,一点一点地提速,不要一上来就像那些特权车一样霸道地把路占满。

慢启动的算法如下(cwnd全称Congestion Window):

  • 连接建好的开始先初始化cwnd = 1,表明可以传一个MSS大小的数据。
  • 每当收到一个ACK,cwnd++或者每当过了一个RTTcwnd = cwnd*2呈指数上升。
  • 还有一个ssthresh(slow start threshold),是一个上限,当cwnd >= ssthresh时,就会进入“拥塞避免算法”。

avatar

如果网速很快的话,ACK也会返回得快,RTT也会短,那么,这个慢启动就一点也不慢。
Linux 3.0后把cwnd 初始化成了 10个MSS。 而Linux 3.0以前,比如2.6,Linux采用了RFC3390,cwnd是跟MSS的值来变的,如果MSS < 1095,则cwnd = 4;如果MSS > 2190,则cwnd=2;其它情况下,则是3。
ssthreshold初始值为0x7fffffff。

拥塞避免

前面说过,还有一个ssthresh(slow start threshold),是一个上限,当cwnd >= ssthresh时,就会进入“拥塞避免算法”。一般来说ssthresh的值是65535,单位是字节,当cwnd达到这个值时后,算法如下
收到一个ACK时,cwnd = cwnd + 1/cwnd OR 当每过一个RTT时,cwnd = cwnd + 1;线性增长。
这样就可以避免增长过快导致网络拥塞,慢慢的增加调整到网络的最佳值。

拥塞发生

前面我们说过,当丢包的时候,会有两种情况:

  • 等到RTO超时,重传数据包。TCP认为这种情况太糟糕,反应也很强烈。
    1
    2
    sshthresh = cwnd /2
    cwnd = 1

进入慢启动过程。

  • Fast Retransmit算法,也就是在收到3个duplicate ACK时就开启重传,而不用等到RTO超时。
    TCP Tahoe的实现和RTO超时一样。
    TCP Reno的实现是:
    1
    2
    cwnd = cwnd /2
    sshthresh = cwnd

进入快速恢复算法——Fast Recove
上面我们可以看到RTO超时后,sshthresh会变成cwnd的一半,这意味着,如果cwnd<=sshthresh时出现的丢包,那么TCP的sshthresh就会减了一半,然后等cwnd又很快地以指数级增涨爬到这个地方时,就会成慢慢的线性增涨。我们可以看到,TCP是怎么通过这种强烈地震荡快速而小心得找到网站流量的平衡点的。

快速恢复

快速恢复算法是认为,你还有3个Duplicated Acks说明网络也不那么糟糕,所以没有必要像RTO超时那么强烈。 注意,正如前面所说,进入Fast Recovery之前,cwnd 和 sshthresh已被更新。

1
2
cwnd = cwnd /2
sshthresh = cwnd

然后,真正的Fast Recovery算法如下:

1
cwnd = sshthresh  + 3 * MSS //3的意思是确认有3个数据包被收到了

重传Duplicated ACKs指定的数据包
如果再收到 duplicated Acks,那么cwnd = cwnd +1
如果收到了新的Ack,那么,cwnd = sshthresh ,然后就进入了拥塞避免的算法了。
如果你仔细思考一下上面的这个算法,你就会知道,上面这个算法也有问题,那就是——它依赖于3个重复的Acks。注意,3个重复的Acks并不代表只丢了一个数据包,很有可能是丢了好多包。但这个算法只会重传一个,而剩下的那些包只能等到RTO超时,于是,进入了恶梦模式——超时一个就减半一下,多个超时会超成TCP的传输速度呈级数下降,而且也不会触发Fast Recovery算法了。 通常来说,正如我们前面所说的,SACK或D-SACK的方法可以让Fast Recovery或Sender在做决定时更聪明一些,但是并不是所有的TCP的实现都支持SACK(SACK需要两端都支持),所以,需要一个没有SACK的解决方案。

avatar

TCP New Reno算法提出来,主要就是在没有SACK的支持下改进Fast Recovery算法。
当sender这边收到了3个Duplicated Acks,进入Fast Retransimit模式,开发重传重复Acks指示的那个包。如果只有这一个包丢了,那么,重传这个包后回来的Ack会把整个已经被sender传输出去的数据ack回来。如果没有的话,说明有多个包丢了。我们叫这个ACK为Partial ACK。

一旦Sender这边发现了Partial ACK出现,那么,sender就可以推理出来有多个包被丢了,于是乎继续重传sliding window里未被ack的第一个包。直到再也收不到了Partial Ack,才真正结束Fast Recovery这个过程。
我们可以看到,这个“Fast Recovery的变更”是一个非常激进的玩法,他同时延长了Fast Retransmit和Fast Recovery的过程。

avatar

FACK

FACK全称Forward Acknowledgment,算法是其于SACK的。
snd.una就是还没有收到ack的序列号,unack。
snd.fack SACK中最大的序列号,更新由ack触发,如果网络一切安好则和snd.una一样。

然后触发Fast Recovery 的条件:
((snd.fack – snd.una) > (3*MSS)) || (dupacks == 3))
这样一来,就不需要等到3个duplicated acks才重传,而是只要sack中的最大的一个数据和ack的数据比较长了(3个MSS),那就触发重传。

avatar

snd.nxt 表示下一个要发送的包

重传流程:

  • cwnd不变。
  • 当第一次丢包的snd.nxt<=snd.una(也就是重传的数据都被确认了),进入拥塞避免机制——cwnd线性上涨。

优点:
我们可以看到如果没有FACK在,那么在丢包比较多的情况下,原来保守的算法会低估了需要使用的window的大小,而需要几个RTT的时间才会完成恢复,而FACK会比较激进地来干这事。

缺点:
FACK如果在一个网络包会被 reordering的网络里会有很大的问题。

拥塞算法


类型算法
丢包BIC/CUBIC, HSTCP, STCP, MulTCP, TFRC
时延Vegas, FastTcp
综合Veno, WestWood, Compound TCP, UDT, TFRC Veno

BIC :曾经的linux默认tcp拥塞算法,拥塞避免阶段,每RTT加1,丢包时降一半。
CUBIC :现在的linux默认tcp拥塞算法,慢启动阶段,每RTT乘2,然后进入拥塞避免阶段,每RTT加1。
HSTCP :相对于CUBIC添加了参数,增得快,降得慢。拥塞避免时的窗口增长方式: cwnd = cwnd + α(cwnd) / cwnd,丢包后窗口下降方式:cwnd = (1- β(cwnd))*cwnd,当α(cwnd)=1,β(cwnd)=0.5时就和cubic一致了。
Vegas :RTT增大代表拥堵,减小拥塞窗口。
FastTcp :相对于Vegas主要引入了一个动态参数alpha。
Veno :基于Vegas和Reno提出的,Veno提升了TCP在单跳无线网络中的性能,大量研究已经表明,Veno在蜂窝通信众性能得到较好的提升。
DCTCP :DataCenter TCP使用ECN。
HTCP :根据时延抖动。
Hybla :主要解决不同RTT的公平性问题,基于时延补偿的方法,大时延网络下,这种算法可以提高传输效率。
illinois:基于RTT估计,调整AI、MD因子。
STCP :快速回复,与当前窗口无关,是常数。
WestWood:适用于无线网络,丢包后重新调整阈值。

vegas

avatar

这个算法通过对RTT的非常重的监控来计算一个基准RTT。然后通过这个基准RTT来估计当前的网络实际带宽,如果实际带宽比我们的期望的带宽要小或是要多的活,那么就开始线性地减少或增加cwnd的大小。如果这个计算出来的RTT大于了Timeout后,那么,不等ack超时就直接重传。(Vegas 的核心思想是用RTT的值来影响拥塞窗口,而不是通过丢包)关于这个算法实现,你可以参看Linux源码:/net/ipv4/tcp_vegas.h, /net/ipv4/tcp_vegas.c

HSTCP(High Speed TCP)

使得Congestion Window涨得快,减得慢。其中:
拥塞避免时的窗口增长方式:cwnd = cwnd + α(cwnd) / cwnd
丢包后窗口下降方式:cwnd = (1- β(cwnd))*cwnd
注:α(cwnd)和β(cwnd)都是函数,如果你要让他们和标准的TCP一样,那么让α(cwnd)=1,β(cwnd)=0.5就可以了。 对于α(cwnd)和β(cwnd)的值是个动态的变换的东西。 关于这个算法的实现,你可以参看Linux源码:/net/ipv4/tcp_highspeed.c

BIC

在Linux 2.6.8中是默认拥塞控制算法。BIC的发明者发这么多的拥塞控制算法都在努力找一个合适的cwnd – Congestion Window,而且BIC-TCP的提出者们看穿了事情的本质,其实这就是一个搜索的过程,所以BIC这个算法主要用的是Binary Search——二分查找来干这个事。 关于这个算法实现,你可以参看Linux源码:/net/ipv4/tcp_bic.c

Westwood

westwood采用和Reno相同的慢启动算法、拥塞避免算法。westwood的主要改进方面:在发送端做带宽估计,当探测到丢包时,根据带宽值来设置拥塞窗口、慢启动阈值。 那么,这个算法是怎么测量带宽的?每个RTT时间,会测量一次带宽,测量带宽的公式很简单,就是这段RTT内成功被ack了多少字节。因为,这个带宽和用RTT计算RTO一样,也是需要从每个样本来平滑到一个值的——也是用一个加权移平均的公式。 另外,我们知道,如果一个网络的带宽是每秒可以发送X个字节,而RTT是一个数据发出去后确认需要的时候,所以,X RTT应该是我们缓冲区大小。所以,在这个算法中,ssthresh的值就是est_BD min-RTT(最小的RTT值),如果丢包是Duplicated ACKs引起的,那么如果cwnd > ssthresh,则 cwin = ssthresh。如果是RTO引起的,cwnd = 1,进入慢启动。 关于这个算法实现,你可以参看Linux源码: /net/ipv4/tcp_westwood.c

传输层数据调用


UDP报文接收

  • __udp4_lib_rcv找到匹配的sock,根据skb的net、四元组和入端口信息,sock会记录连接的状态。
  • __udp4_lib_rcv->udp_queue_rcv_skb->__udp_queue_rcv_skb->sock_queue_rcv_skb添加到sk_receive_queue队列中。

TCP报文接收

  • tcp_v4_rcv找到匹配的sock,根据skb的net、四元组和入端口信息,sock会记录连接的状态。
  • `tcp_v4_do_rcv–>tcp_rcv_established–>tcp_queue_rcv`添加到`sk_receive_queue`队列中

应用层接收

  • 用户态调用recvfrom会调用kernel代码的系统用SYSCALL_DEFINE6(recvfrom,…)net/socket.c
  • 这里面调用sock_recvmsg-> __sock_recvmsg-> __sock_recvmsg_nosec
  • __sock_recvmsg_nosec调用不同协议的对应recvmsg接口,比如TCP的tcp_recvmsg和UDP的udp_recvmsg
  • 里面分别从sk_receive_queue拿到skb,然后将skb的数据部分拷贝到buffer上传。
  • 应用层收到数据。

应用层发送

  • 用户态调用sendto会调用kernel代码的系统用SYSCALL_DEFINE6(sendto,…)
  • 首先通过参数fd查找对应的sock,找到之后调用sock_sendmsg
  • 这里面调用sock_sendmsg > __sock_sendmsg > __sock_sendmsg_nosec
  • __sock_sendmsg_nosec调用不同协议的对应sendmsg接口,比如TCP的tcp_sendmsg和UDP的udp_sendmsg

TCP报文发送

  • tcp_sendmsg将buffer转换成skb,如果超过mss,则生成多个skb,存入sock的sk_write_queuesk_send_head
  • 调用tcp_push_one-> tcp_write_xmitsk_send_head拿到skb之后调用tcp_transmit_skb-> ip_queue_xmit-> ip_local_out发送报文。
  • ip_output-->ip_finish_output2-->dst_neigh_output-->neigh_hh_output-->dev_queue_xmit-->__dev_xmit_skb-->sch_direct_xmit-->dev_hard_start_xmit-->ndo_start_xmit

注意:所有文章非特别说明皆为原创。为保证信息与源同步,转载时请务必注明文章出处!谢谢合作 :-)

原始链接:http://zhaozhanxu.com/2016/07/17/Linux/2016-07-17-Linux-Kernel-Pkts_Processing6/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。