在上篇笔记中我们综合了诸多技术搭建了一个可靠的数据传输协议——位交替协议。然而，作为停等协议，位交替协议的效率实在太低。
举个例子，假设主机 A 和主机 B 之间的往返时延为 30 ms，二者之间连接的信道的传输率 R 为 1 Gbps，一个 packet 的大小 L 为 1000 bytes，那么一个 packet 从主机传输到信道上所花的时间为
$$d_{trans}=\frac{L}{R}=\frac {1000 \times 8 \: bit}{1 \times 10^{9}\, bps}=8 \times 10^{-6}s$$
然而，当 A 给 B 发送了一个packet之后，要等上 30ms + 0.008ms = 30.008 ms 才收到 ACK，然后 A 才能发送下一个 packet。发送方的实际利用率为：
$$U_{sender}=\frac{\frac{L}{R}}{RTT +\frac{L}{R}}=\frac{0.008\, ms}{30\, ms + 0.008\, ms}\approx 0.00027=0.027\%$$
也就是说在 30.008ms 里实际上只传输了 1000 个字节，实际吞吐量为 276kbps，大大的浪费啊~
这个性能问题的解决思路很简单：允许在之前发送地 packet 没有收到确认的情况下继续发送新的 packet。就像是水流源源不断地流经管道，因此这种模式又被称为管道化 (Pipeling)。
管道化是个好方案，但是，我们还得先解决管道化带来的新的问题：
- 如果数据流中的某个 packet 出错（损坏或丢失），这时后续的 packets 已经发出甚至已经到达接收方，发送方和接收方分别应采取什么措施从错误中恢复呢？
有两种基本方法用于处理管道化传输中出现的错误，它们分别是：
- 回退 N (Go-Back-N) 协议
- 选择重传 (Selective Repeat) 协议
这两种协议都属于滑动窗口协议。滑动窗口协议的本质是在任何时刻发送方总是维持着一组序号对应了允许它发送的 packets，这组序号被称为发送窗口 (sending window)。类似地接收方也为维持着一个接收窗口 (receiving window)对应一组允许它接收的 packets。
回退 N 协议
在回退 N 协议（以下简称 GBN）中，发送方允许有尚未确认的 packets 情况下继续发送新的 packet，但尚未被确认的 packets 的数量不能超过 N，即发送窗口的大小为 N。
下图（取自《计算机网络：自顶向下方法》）显示了在发送窗口为 N 的大小下，GBN 协议发送方维护的序号集合：
在上图中，base 表示当前尚未被确认的 packet 中最早发送的一个，nextseqnum 表示最小的可用于下一个待发送 packet 的序号，发送窗口大小为 N，由此可得：
[0, base-1]- 已经发送且被确认的 packets 的序号[base, nextseqnum-1]- 已经发送尚未被确认的 packets 的序号[nextseqnum, base+N-1]- 可用于那些要被立即发送的分组[base+N, ...]- 不可用的序号
GBN 发送方行为
GBN 发送方维护着 base, nextseqnum 和 N 三个值，以便在三种事件发生时做出正确的响应：
- 上层调用 - 检查当前发送窗口是否已满 (
nextseqnum = base + N)，这时可以有三种处理方式：- 直接拒绝上层的调用
- 将数据放到缓冲区
- 从根源上杜绝这种情况，采用同步机制，使得上层的调用只能在有可用窗口时发生
- 收到 ACK - GBN 协议采用累计确认 (cumulative acknowledgement) 的方式，也就是指
ACK n意味着序号n以前（包括n）的所有 packet 都确认收到。 - 超时事件 - GBN 只使用一个计时器，这个计时器可看作是最早的已被发送但尚未被确认的 packet 的定时器（也就是序号为
base的 packet 的定时器啦）。当超时发生时，发送方将重传之前已经发送但尚未确认的所有 packets。如果收到一个 ACK，但仍然有已发送未确认的 packet，那么定时器会重新启动，否则定时器会被终止。
GBN 接收方行为
GBN 接收方的行为很简单，如果一个序号为 n 的 packet 是按照正确顺序（即上一个正确接收的 packet 序号为 n-1）到达且没有出错，那么就交付给上层。其他情况，则丢弃这个 packet，并且为最近一个按序接收的 packet 重传 ACK。
也就是说，对于乱序到达的 packet，接收方一律丢弃，虽然有点浪费，但是却是最简便的做法，不需要额外的缓存来存放这些提前到达的 packet，也不要额外的逻辑来处理它们之间的关系。
如果传输过程中错误很少发生，那么 GBN 可以工作得很好，但如果信道差错率较大，那么 GBN 的重传机制将浪费大量带宽。这种情况下，我们可以选择另一种协议——选择重传。
选择重传协议
选择重传 (Selective Repeat, 简称 SR) 协议，顾名思义，就是有选择地重传 —— 仅重传那些发送方怀疑在接收方出错（损坏或丢失）的 packet。
下图（取自《计算机网络：自顶向下方法》）显示了 SR 中发送方和接收方各自维护的滑动窗口：
在上图中，我们可以看到在发送窗口中包含了一部分被确认的 packet，说明这部分乱序到达接收方的 packet 已经被接收方正确接收了。那么双方具体是如何协调工作的呢？
SR 发送方行为
SR 的发送方同样也要对如下三种事件做出响应：
- 上层的调用 - 与 GBN 一样，检查发送窗口是否已满，若仍有可用序号，则发送数据，否则拒绝请求或先缓存起来。
- 收到 ACK - 当收到某个 packet 的 ACK 时，如果它位于发送窗口中，那么发送方会将其标记为已确认。如果这个 packet 的序号刚好等于
send_base，那么就移动发送窗口到当前未被确认的最小序号，如果移动窗口后有序号落在窗口内的尚未发送的 packet，则发送这些 packet。 - 超时事件 - 与 GBN 不同，SR 为每一个 packet 设定单独的定时器，当超时发生则重传这个定时器对应的 packet。
SR 接收方行为
相比于 GNB 接收方简单粗暴的处理，SR 的接收方要多做不少工作：
- 只要收到的 packet 是正确的，接收方就会返回 ACK，而不管是否按序；
- 非按序到达的 packet 会被缓存起来，直到所有缺失的 packet （即序号更小的那些）都被收到，这时接收方会将这一批连续的 packets 一起交付给上层；
- 对于收到的序号小于
rcv_base的 packet，接收方也会返回 ACK。举个例子，假设最初send_base和rcv_base都为 1，当接收方确认收到序号为 1 的 packet 后返回了 ACK，接收窗口向前移动，rcv_base变为 2；结果遇上了 ACK 丢包，触发了发送方的超时事件，这时发送方会重传序号为 1 的 packet，如果接收方不对应答该 packet，发送方就会陷入重传 packet 1 的死循环，发送窗口永远都不会向前移动。
从上图可以看到，发送窗口与接收窗口并不总是一致的。不一致的成因就与刚刚举的例子有关，对于哪些分组已被正确接收，哪些没有，发送方和接收方看到的结果不一定相同。
二者之间的不同步还会带来一个严重的问题：由于现实中用来表示序号的字段是有限长度的，所以序号不可无限增长，而是有限范围。当序号增长到最大值后便会从头开始计数。这可能会导致接收方无法分辨一个 packet 是重传的还是新的，什么时候会发生这种情况呢？（偷个懒就不描述了，在这里先卖个关子~）
总之，为了避免这个问题，SR 要求滑动窗口的大小要小于或等于 sequence 最大值的一半。
小结
到此为止，我们提到了多种用于实现可靠数据传输的机制，包括了校验和、确认机制（肯定/否定确认）、序号的应用、计时器，重传以及滑动窗口和管道化。
那么，作为可靠数据传输协议中最为重要的一员，TCP 可谓是将这些机制的集大成者，等我摸透了再来跟大家聊一聊TCP究竟是个怎么用实践检验真理的~
参考资料
- Computer Networking: A Top-Down Approach, 7th Edition
- 计算机网络，第五版