全部博文（413）
分类： LINUX
2012-01-03 21:11:08
确认、重传和超时
1. 累计确认（cumulative acknowledgement）
由于 TCP 使用可变长度的报文段来发送数据，而且重传的报文段中可能比原报文段包含更多的数据，所以不能简单地对数据报和报文段进行确认。实际上，TCP使用流序号对流中的一个位置进行确认(序号---确认号)。接收方使用序号将报文段重新排序，接收方总是对已正确收到流的最长连续前缀进行确认。每个确认给出一个序号值，其值比收到的连续前缀中最高八位组的位置大 1。这样，发送方就能在继续发送流的同时，从接收方得到连续的反馈信息。因此：
一个TCP确认指出了接收方期望收到的下一个字节的序号。
TCP的确认方法称为累积确认（cumulative acknowledgement） ，因为它报告了接收方已累积收到流中的多少个字节。累计确认，允许ACK丢失，没有必要进行重传。
2. 自适应重传算法（adaptive retransmission algorithm）
TCP监视每条连接的性能，由此推算出适当的超时时限值。当网络负载发生变化时，TCP随即修改触发重传的定时器的长短。
“样板往返时间”(sample round trip time)或者“往返时间样板”（round trip sample）:
TCP软件计算往返时间的加权平均值，作为往返时间的估计值（RTT,即round trip time），并不断的使用新的往返时间样板来逐步修改这个平均值:
RTT = (α * OLD_RTT) + ((1 - α) * New_Round_Trip_Time)
超时时限值为：Timeout = β * RTT (β一般等于2)
3. 往返时间样本的精确测量
1）确认二义性（acknowledgement ambiguity）
TCP使用累积确认方式，把测量一个往返时间样本的问题复杂化了。因为确认针对的是收到的数据，而不是针对携带这些数据的某个数据报实例。当发生重传时，接收方可能会收到的那个ACK确认，我们不知道它是针对原来的数据包还是重传的数据包。
2）Karm算法与计时器补偿
为了避免二义性的确认，Karm算法规定：TCP不为重传的报文更新往返时间估计值，而只对没有重传，不会发生二义性确认来调整往返时间的估计值。
同时为了避免网络时延突然增大后，超时时限太小从而造成报文段反复重传的情况发生。Karn 算法要求发送方在对重传的超时时限进行设置时结合使用计时器退避（timer backoff）策略：
当发生重传时：new_timeout = γ * timeout (γ一般等于2)
4. 对高方差时延的对策
1989 年的 TCP 协议规范要求，协议在实现时既要估计往返时间的平均值，也要估计往返时间的方差，并使用方差的估计值替代常数β。这样，TCP的新实现就能适应更大范围变化时延的情况，还能实现较高的吞吐率。
5. 拥塞控制
1）拥塞（congestion）:
是指一个或多个交换点（如路由器）的数据包超载而导致时延剧烈增加的现象。当发生拥塞时，数据报的时延增加，路由器开始把数据报放在队列中排队，直到能够对它们进行转发。在最坏的情况下，到达拥塞路由器的数据报总数不断增加，直至路由器容量达到饱和，并开始丢弃报文。从而导致重传，重传只会加剧拥塞，而不会减轻拥塞。如此恶性循环，直至网络变得无法使用。这种现象称为拥塞崩溃（congestion collapse）。
为了避免出现拥塞崩溃，TCP必须在拥塞发生时减小传输速率。路由器观察队列的长度，使用类似于ICMP源站抑制（source quench）的技术通知主机已发生拥塞。类似 TCP的运输协议，在时延较大时可以自动降低传输速率，这样有助于避免拥塞的发生。
为了避免拥塞，TCP 标准推荐使用两种技术：慢开始（slow-start）和乘法减小（multiplicative dcrease）.为了控制拥塞，TCP 使用第二个窗口限制，即拥塞窗口限制（congestion window limit）或称拥塞窗口（congestion window）。当发生拥塞时，可使用此限制让数据流量小于接收方的缓冲区大小。也就是说，在任何时候，TCP通信把窗口的大小当成：
Allowed_window = min(receiver_adversement, congestion_window)
为了估算拥塞窗口的大小，TCP 假设报文的丢失大多数是由于拥塞造成的，并使用下面的策略来改变窗口大小，乘法减小的拥塞避免策略：
一旦发现报文段丢失，就把拥塞窗口的大小减半（直到减至最小的窗口，窗口中应包括至少一个报文段） 。对于留在许可窗口内的那些报文段，采用指数退避算法计算重传计时器的时限值。
拥塞结束后，TCP 如何恢复正常通信呢？
实际上，TCP使用慢开始（slow-start）的技术来逐步恢复传输:
慢开始（加法）恢复：在一条新连接上开始传输通信量时，或在一段时间的拥塞后增加通信量时，拥塞窗口的大小刚开始只有一个报文段，以后随着一个确认的到达，拥塞窗口的大小每次增加一个报文段。当拥塞窗口到达拥塞发生前窗口大小的一半时，TCP进入一个拥塞避免（congestion avoidance）的阶段，减慢窗口增长的速度。在拥塞避免期间，只有当窗口中的所有报文段都被确认之后，窗口大小才能增加 1。
把慢开始、乘法减小、加法增加、方差估计、计时器指数退避等技术结合在一起，就能显著地提高TCP的性能，同时不需要为协议软件增加大量的计算开销。使用了这些技术的TCP版本，比过去一些版本的性能提高了2～10倍。（使用这些机制的是早期的TCP版本——也称为Tahoe版本）
6. Reno版本——快重传改进
1990 年出现了 Reno 版本的 TCP，它对旧版本做了几处改进，包括一个名为快恢复（fast
recovery）或快重传（fast retransmit）的启发式方法，在偶尔发生丢失的环境中具有更高的吞吐率。
在快恢复中使用的技巧产生于 TCP 的累积确认机制：如果一个报文段丢失，当后续的报文段到达接收方时，要求接收方产生一个 ACK，该确认指明了丢失的报文段在流中的位置点。从发送方的角度来看，它会收到一连串的确认，每个确认中携带的是同一个序号。快重传启发式方法使用一连串的三个重复确认（即最初的确认加上三个完全相同的副本）来激活一次重传，而不必等到计时器超时后再重传。
为了维持更高的吞吐率，快重传启发式方法在等待重传报文段的确认时，还继续发送窗口中的数据。此外，拥塞窗口被人为地膨胀开：拥塞窗口因重传而被缩小一半，但伴随每个重复 ACK 在重传前后的到达，都会使拥塞窗口扩大一个最大长度的报文段。由此可见，在快重传期间，TCP让很多报文段处于发送方和接收方之间的传输途中。7. TCP友好速率控制（TCP Friendly Rate Control,简称TFRC）
我们发现，虽然在发生拥塞时 TCP 减少了传输通信量，但UDP并没有减少，这意味着随着 TCP 流量继续回退， UDP流量将占据更多的宽带。由于 UDP 不使用滑动窗口，TFRC 让接收方向发送方报告分组丢失的情况，并让发送方使用被告知丢失的数据来计算UDP应该使用的发送速率，通过这些措施来尝试模仿 TCP的行为。
8. 拥塞、尾部丢弃、随机早期丢弃（RED）
1）尾部丢弃
路由器的尾部丢弃策略：如果数据报到达时输入队列已满，则丢弃该数据报。
尾部丢弃策略很可能使路由器丢弃来自N个连接的N 个报文段（每个连接丢失一个报文段） ，而不是来自一个连接的 N个报文段。这种同时发生的丢失造成TCP的 N 个实例同时进入慢开始。导致了全局的同步。
2）随机早期丢弃（RED）
路由器如何避免全局的同步呢？答案是一种尽可能避免尾部丢弃的方法。 这种方法称为随机早期检测（Random Early Detection）或者随机早期丢弃（Random Early Discard/Drop,简称RED）
