阅读须知：笔记为阅读《TCP IP 详解卷1：协议》后摘抄的一些知识点，其间也有加入一些根据英文原版的自己翻译和结合网上知识后的理解，所以有些段落之间并不能够串联上或者知识点与书上略有差别(基本差别不大，参考的资料属RFC官方文档)。
第十四章：超时与重传
TCP协议为了提供可靠的数据传输服务，会启动数据重传来解决下层网络层(IP)可能出现的数据包丢失。
超时重传介绍
TCP重传由两套独立机制来完成重传，基于时间的超时重传(RTO，TCP发送数据时会设置一个计时器，若至计时器超时仍未收到数据确认信息，则会引发相应的超时和计时器重传操作)，基于确认信息的构成(通常在没发生延时的情况下，若TCP累积确认无法返回新的ACK，或者当ACK包含的选择确认信息(SACK)表明出现失序报文段时，快速重传会推断出现丢包，这时候发送端认为接收端可能出现数据丢失时，需要决定发送新数据还是重传)。
对于超时和重传，之前有了一定的认识，如：
在ICMP目的不可达的时，采用UDP的TFTP客户端使用简单且低效的超时和重传策略：设置足够大的超时间隔，每5秒进行一次重传；
第13章提到TCP所使用指数回退行为：在目的主机不存在的场景中，TCP在尝试建立连接过程中，每次重传时采用比上次更大的延时间隔。
TCP能不断"学习"发送端与接收端之间的链路特征，以记录一些状态变量。早些的TCP中，当连接关闭，这些学习而得的状态便会丢失；在较新的TCP中实现了维护这些度量值，即使连接断开后，也能保存之前存在的路由或转发表项或其他一些系统数据结构。当创立一个新的连接时，首先查看数据结构中是否存在与该目的端的先前通信信息，如果存在则使用信息来初始化连接的一些变量值。如在linux中，变量值更新为现存值中的最大值和最近测量的数据，可通过iproute2[IPR2]的相关工具来查看变量值。这也称为TCP连接的目的度量。
当TCP超时重传时，它并不需要完全重传相同的报文段，TCP允许执行重新组包，发送一个更大的报文段来提高性能(但不能大于接收端通告的MSS和路径MTU)。因为TCP是通过字节号来识别发送和接收的数据的。
RTO值的计算
由于TCP需要适应不同环境进行操作，若TCP先于RTT开始重传，可能会在网络中引入不必要的重复数据；若延迟远大于RTT的间隔发送重传数据，整体网络利用率(以及单个连接吞吐量)会随之下降。因此，RTO需要TCP动态设置，且RTO的设置是TCP性能的关键。
TCP在收到数据后会返回确认信息，因此可在该信息中携带一个字节的数据来测量传输该确认信息所需的时间，每个此类的测量结果被称为RTT样本，TCP则根据这些样本来给出RTO估值。每个TCP连接的RTT均独立估算，并且重传计时器会对任何占用序列号的在传数据计时。
RTO计算的经典方法：
# 采用如下公式得到平滑的RTT估计值(称为SRTT)：
SRTT ← α(SRTT)+(1-α)RTTs (s为下标)
# SRTT是基于现存值和新的样本值RTTs得到的更新结果，常量α是平滑因子，推荐值为0.8~0.9，这个方法被称为指数加权移动平均或者低通过滤器。
# 采用以下公式设置RTO：
RTO = min(ubound,max(1bound,(SRTT)β))
# β为时延离散因子，推荐值为1.3~2.0，ubound为RTO的上边界(可设定建议值，如1分钟)，lbound为RTO的下边界(可设定建议值，如1秒)。它使得RTO的值设置为1秒或约2倍的SRTT。
# 相对于文档的RTT来说，这种方法能取得不错的性能，然而若TCP运行于RTT变化较大的网络中，则无法获得期望的效果。RTO计算的标准方法(结合平均值和平均偏差来进行估算)：
srtt ← (1 - g)(srtt) + (g)M
rttvar ← (1 - h)(rttvar) + (h)(|M - srtt|)
RTO = srtt + 4(rttvar)
# srtt代替了之前的SRTT，且rttvar为平均偏差的EWMA，M代替了之前的RTTs。这组等式也可以写成另一种形式：
Err = M - srtt
srtt ← srtt + g(Err)
rttvar ← rttvar + h(|Err| - rttvar)
RTO = srtt + 4(rttvar)
# srtt为均值的EWMA，rttcar为绝对误差|Err|的EWMA，Err为测量值M与当前RTT估计值srtt之间的偏差。增量g为新RTT样本M占srtt估计值的权重，取1/8，增量h为新平均偏差样本(新样本M与当前平均值srtt之间的绝对误差)占偏差估计值rttvar的权重，取1/4。这种方法是迄今为止许多TCP实现计算RTO的方法。
在测量RTT的过程中，TCP始终始终处于运转状态，对初始序列号来说，TCP时钟通常为某个变量，随着系统时钟而做出更新。TCP时钟一个"滴答"的时间长度称为粒度，通常该值相对较大(约500ms)，但近期实现的时钟使用更细的粒度(如linux的1ms)。
粒度会影响RTT的测量及RTO的设置，在[RFC6298]中，粒度用于优化RTO的更新情况，并给RTO设置了一个下界：
RTO = max(srtt + max(G,4(rttvar)),1000)
# G为计时器粒度，1000ms为整个RTO的下界值([RFC6298]的规则建议值)。因此，RTO至少为1s，同时也提供可选上界值，假设为60s。对于RTO的初始值，根据[RFC6298]描述，为1s，而初始SYN报文段采用的超时间隔为3s，当接收到收个RTT测量结果M，TCP按如下方式进行初始化：
srtt ← M
rttvar ← M/2在测量RTT样本过程中，可能会出现重传的二义性，如假设一个包的传输出现超时，该数据包被重传，接着收到一个确认信息，那么这个信息是对第一次还是第二次传输的确认就存在二义性。当出现超时重传时，接收到重传数据的确认信息时不能更新RTT估计值，这是Karn算法的第一部分，通过排除二义性数据来解决RTT估算中出现的二义性问题。
Karn算法的第二部分则在计算RTO过程中采用一个退避系数，每当重传计时器出现超时，退避系数加倍，该过程一直持续至接收到非重传数据，此时退避系数重新设置为1(二进制指数退避取消)，重传计时器返回正常值。
TCP时间戳选项(TSOPT)可用作RTT测量[RFC1323]。时间戳值(TSV)携带于初始化SYN的TSOPT中，并在SYN+ACK的TSOPT的TSER部分返回，以此设定srtt、rttvar与RTO的初始值。初始SYN也可看作数据，应测量其RTT值。
因为TCP并非对其接收到的每个报文段都返回ACK，如传输大批量数据时，TCP通常采取每两个报文段返回一个ACK的方法，或者当数据出现丢失、失序或重传成功时，TCP累积确认机制表明报文段与其ACK之间并非严格的一一对应，为解决这些问题，使用时间戳选项的TCP采用如下算法来测量RTT样本值：、
1. TCP发送端在其发送的每个报文段的TSOPT的TSV部分携带一个32比特的时间戳值。该值包含数据发送时刻的TCP时钟值。
2. 接收端记录接收到的TSV值(名为TsRecent的变量)并在对应的ACK中返回，并且记录其上一个发送的ACK号(名为LastACK的变量)。
3. 当一个新的报文段到达(接收端)时，如果其序列号与LastACK的值吻合(即为下一个期望接收的报文段)，则将其TSV值存入TsRecent。
4. 接收端发送的任何一个ACK都包含TSOPT，TsRecent变量包含的时间戳值被写入其TSER部分。
5. 发送端接收到ACK后，将当前TCP时钟减去TSER值，得到的差即为新的RTT样本估计值。
若在连接初始化过程中，TCP的通信一方启用时间戳，则另一端将启用时间戳。
linux的RTT测量过程与标准方法有所区别，使用更细的时钟粒度和更频繁的RTT测量。linux记录两个新的变量，mdev和mdev_mas，mdev为采用标准方法的瞬时平均偏差估计值，即之前的rttvar；mdev_max则记录在测量RTT样本过程中的最大mdev，其最小值不小于50ms。rttvar需定期更新以保证其不小于mdev_max，因此，RTO不会小于200ms。
TCP时间戳选项携带了发送端TCP时钟的副本。接着ACK将该值返回至接收端，通过计算两者之差(当前时钟减去返回的时间戳)来更新其srtt与rttvar估计值。如下图：
初始化RTO估算计算过程：
srtt = 16ms
mdev = (16/2)ms = 8ms
rttvar = mdev_max = max(mdev, TCP_RTO_MIN) = max(8,50) = 50ms
RTO = srtt + 4(rttvar) = 16 + 4(50) = 216ms第二次RTO估算计算过程：
m = 223 - 127 = 96
mdev = mdev(3/4) + |m - srtt|(1/4) = 8(3/4) + |80|(1/4) = 26ms
mdev_max = max(mdev_max,mdev) = max(50,26) = 50ms
srtt = srtt(7/8) + m(1/8) = 16(7/8) + 96(1/8) = 14+12 = 26ms
rttvar = mdev_max = 50ms
RTO = srtt + 4(rttvar) = 26 + 4(50) = 226ms针对RTT减小的情况，若新样本值小于RTT估计范围的下界(srtt - mdev)，则减小新样本的权重：
if(m < (srtt - mdev))
mdev = (31/32) * mdev + (1/32) * |srtt - m|
else
mdev = (3/4) * mdev + (1/4) * |srtt - m|该结果可以避免RTT减小导致的RTO增大问题。
重传的实现
基于计时器的重传
一旦TCP发送端得到基于时间变化的RTT测量值，就能据此设置RTO，发送报文段时应确保重传计时器设置合理。在设定计时器前，需记录被计时的报文段序列号，若及时收到了该报文段的ACK，则计时器被取消。之后发送端发送一个新的数据包时，需设定一个新的计时器并记录新的序列号。因此，每一个TCP连接的发送端不断地设定和取消一个重传计时器；如果没有数据丢失，则不会出现计时器超时。
对TCP而言，计时器需要有效的实现被设置、重新设置、取消的功能，若TCP正常工作，则计时器不会出现超时的情况。
若在连接设定的RTO内，TCP没有收到计时报文段的ACK，将会触发超时重传。TCP将超时重传视为相当重要的事件，当发生这种情况时，它通过降低当前数据发送率来对此进行快速响应。实现有两种方法：基于拥塞控制机制减小发送窗口大小；每当一个重传报文段被再次重传时，则增大RTO的退避因子。
RTO值乘上值γ来形成新的超时退避值：
RTO = γRTO通常情况下γ为1，随着多次重传，γ呈加倍增长：2，4，8...。通常γ不能超过最大退避因子(linux确保其RTO设置不超过TCP_RTO_MAX，其默认值为120s)。一旦受到相应ACK，γ会重置为1。
快速重传
快速重传机制[RFC5681]基于接收端的反馈信息来引发重传，而非重传计时器的超时，快速重传能更加及时有效的修复丢包情况。
快速重传概况如下：TCP发送端在观测到至少dupthresh(重复ACK阈值，一定数目的重复ACK，默认通常为3)，即重传可能丢失的数据分组，而不必等到重传计时器超时。
流程如图：
带选择确认的重传
随着选择确认选项的标准化[RFC2018]，TCP接收端可提供SACK功能，通过TCP头部的累积ACK号字段来描述其接收到的数据。采用SACK选项时，一个ACK可包含三四个告知失序数据的SACK信息。每个SACK信息包含32位的序列号，代表接收端存储的失序数据的起始至最后一个序列号(加1)。
SACK选项指定n个块的长度为8n+2字节，因此40字节可包含最多4个块。通常SACK会与TSOPT一同使用，因此需要额外的10个字节(外加2字节的填充数据)，所以每个ACK只能包含3个块。
SACK接收端行为：接收端在TCP连接建立期间受到SACK许可选项即可生成SACK。通常来说，每当缓存中存在失序数据时，接收端就可生成SACK。第一个SACK块内包含的是最近接收到的报文段序列号范围，其余的SACK块包含的内容按照接收的先后依次排列。也就是说，最新一个块中包含的内容除了包含最近接收的序列号信息，还需重复之前的SACK块。
SACK发送端行为：在发送端也应提供SACK功能，并且合理地利用接收到的SACK块来进行丢失重传，该过程也称选择性重传或选择性重发。SACK发送端记录接收到的累积ACK信息，还需记录接收到的SACK信息，并利用该信息来避免重传正确接收的数据。一种方法是当接收到相应序列号范围的ACK时，则在其重传缓存中标记该报文段的选择重传成功。
伪超时和重传
在一些情况下，即使没有出现数据丢失也可能引发重传，这种不必要的重传称为伪重传，其主要造成原因是伪超时，即过早判定超时，其他因素如包失序、包重复，或者ACK丢失也可能导致该现象。为处理伪超时问题提出许多方法，这些方法通常包含检测算法和响应算法。检测算法用于判断某个超时或基于计时器的重传是否真实，一旦认定出现伪超时则执行响应算法，用于撤销或减轻该超时带来的影响。
下面介绍一些处理方法：
重复SACK(DSACK)扩展：基本的SACK机制对接收端收到重复数据段时怎样运作没有规定，这些重复数据可能是伪重传、网络中的重复或其他原因造成的。在接收端采用DSACK(重复SACK)，并结合通常的SACK发送端，可在第一个SACK块中告知接收端收到的重复报文段序列号。DSACK的主要目的是判断何时的重传是不必要的，并了解网络中的其他事项，因此发送端至少可以推断是否发生了包失序、ACK丢失、包重复或伪重传。
Eifel检测算法：实验性的Eifel检测算法[RFC3522]利用了TCP的TSOPT来检测伪重传。在发生超时重传后，Eifel算法等待接收下一个ACK，若为针对第一次传输的确认，则判定该重传是伪重传。利用Eifel检测算法能比仅用采用DSACK更早检测到伪重传行为，因为它判断伪重传的ACK是在启动丢失恢复之前生成的。
前移RTO恢复：前移RTO恢复[RFC5682]是检测伪重传的标准算法，但只检测由重传计时器超时引发的伪重传。F-RTO会修改TCP的行为，在超时重传后收到第一个ACK时，TCP会发送新的数据，之后再响应后一个到达的ACK。如果其中有一个为重复ACK，则认为此次重传没问题，如果两个都不是重复ACK，则表示该重传是伪重传。如果新数据的传输得到了相应的ACK，就使得接收端窗口前移。如果新数据的发送导致了重复ACK，那么接收端至少有一个或更多的空缺。
Eifel响应算法：一旦判断出现伪重传，则会引发一套标准操作，即Eifel响应算法[RFC4015]。由于响应算法逻辑上与Eifel检测算法分离，所以它可与前面的任一种检测方法结合使用。原则上超时重传和快速重传都可使用Eifel响应算法，但目前只针对超时重传做了相关规定。Eifel响应算法根据是否能尽早或较迟检测出伪超时的不同而有所区别。前缀称为伪超时，通过检查ACK或原始传输来实现；后者称为迟伪超时，基于有超时而引发的重传所返回的ACK来判定，响应算法只针对第一种重传事件。
在重传计时器超时后，它会查看srtt和rttvar的值，并按如下方式记录新的变量srtt_prev和rttvar_prev：
srtt_prev = srtt + 2(G)
rttvar_prev = rttvar在任何一次计时器超时后，都会指定这两个变量，但只要在判定出现伪超时才会使用它们，用于设定新的RTO。在上式中，G代表TCP时钟粒度。srtt_prev设为rtt加上两倍的时钟粒度是由于srtt的值过小，可能会出现伪超时。
完成srtt_prev和rttvar_prev的存储后，就要触发某些检测算法。运行检测算法后可得到一个特殊的值，称为伪恢复。如果检测到一次伪超时，则将伪恢复置为SPUR_TO。如果检测到迟伪超时，则将其置为LATE_SPUR_TO。
若伪恢复为SPUR_TO，TCP可在恢复阶段完成之前进行操作，通过将下一个要发送报文段(称为SND.NXT)的序列号修改为最新的未发送过的报文段(称为SND.MAX)。这样就可在首次重传后避免不必要的"回退N"行为。如果检测到一次迟伪超时，此时已生成对首次重传的ACK，则SND.NXT不变。在以上两种情况下，都要重新设置拥塞控制状态(第16章介绍)。一旦接收到重传计时器超时后发送的报文段的ACK，就按如下方式风险srtt、rttvar、RTO：
srtt ← max(srtt_prev,m)
rttvar ← max(rttvar_prev,m/2)
RTO ← srtt + max(G,4(rttvar))m是一个RTT样本值，它是基于超时后收个发送数据收到的ACK计算得到的。
包失序和包重复
包失序
在IP网络中出现包失序的原因有：在于IP层不能保证包传输是有序进行的；硬件方面一些高性能设备(路由器)采用多个并行数据链路；不同的处理延时；等其他情况...
如果失序发生在反向(ACK)链路，就会使得TCP发送端窗口快速前移，接着又可能收到一些显然重复而应被丢弃的ACK。由于TCP的拥塞控制行为，这种情况可能导致发送端出现不必要的流量突发行为，影响可用网络带宽。
如果失序发生在正向链路，TCP可能无法识别失序和丢包。数据的丢失和失序都会导致接收端收到无序的包，造成数据之间的空缺。当失序比较严重时(数据包的字节值差距大)，TCP会误认为数据已经丢失，从而触发快速重传，导致伪重传。
互联网中严重的失序并不常见，且通过将dupthresh设为相对较小值(如3)就能处理大部分情况，或者一些方法得以动态调整dupthresh值。
参考图如下：
包重复
包重复的情况比较少，当IP协议也可能出现将单个包传输多次的情况。如当链路层网络协议执行一次重传并生成同一个包的两个副本(这种估计属于误操作了...)。这时候，TCP可能出现混淆。针对包重复现象，利用SACK(特别是DSACK)就可以简单的忽略这个问题。
相关攻击
有一类DoS攻击称为低速率DoS攻击[KK03]，在这类攻击中，攻击者向网关或主机发送大量数据，使得受害系统持续处于重传超时的状态。由于攻击者可预知受害TCP何时启动重传，并在每次重传时生成并发送大量数据。因此，受害TCP总能感知到拥塞的存在，根据Karn算法不断减小发送速率并退避发送，导致无法正常使用网络带宽。针对此类攻击的预防方法是随机选择RTO，使得攻击者无法预知确切的重传时间。
与DoS相关但不同的一种攻击为减慢受害TCP的发送，使得RTT估计值过大，使得受害者在丢包后不会立即重传。相反的攻击也是有可能的：攻击者在数据发送完成但还未到达接收端时伪造ACK。这样攻击者就能使受害TCP认为连接的RTT远小于实际值，导致过分发送而造成大量的无效传输。
