文章目录
写在前面：
- 本文主要参考《计算机网络自顶向下方法》，主要为个人学习整理的记录，如果能够帮到同样正在学习计算机网络的你，那也再好不过了，一起进步！
- 读完本文，你将了解为实现可靠的数据传输都将面临哪些现实挑战，而校验和、序列号、ACK 应答、计时器、管道化传输、滑动窗口、选择重传这些机制又都是如何使得数据传输变得可靠和高效的！
1. 引言
稍微了解计算机网络的朋友都会知道的一点是，我们一般说 TCP/IP 协议栈中传输层的协议 TCP 是可靠的，而同样是传输层的协议，UDP 协议则是不可靠的。实际上，不仅对于传输层的部分协议，针对网络协议分层模型中的数据链路层和应用层，实际应用中也都对其中一些协议存在数据传输的可靠性要求。
由于数据传输可靠性的意义不言而喻，因此本文旨在讨论一般情况下，针对无论处于哪一层的协议，保证其实现可靠的数据传输需要哪些机制，以及这些机制是如何保证数据传输的可靠性，以此来加深读者对于 TCP 等协议是如何实现可靠数据传输这一点的理解。
为便于读者理解，下图首先给出接下来讨论所使用的框架，如图 a 所示，可靠的数据传输信道为上层的实体提供了服务的抽象，在可靠的信道内，传输的数据不会发生丢失或误码，而且所有数据在接收端被接收到的顺序和其在发送端被发送出去的顺序一致。实际上，这也是当互联网应用调用 TCP 协议发送数据时，后者向前者提供的服务模型。
上述提到的服务抽象实际上就是由可靠的数据传输协议负责实现的。事实上，要实现一个可靠的数据传输协议却并不简单，因为一个可靠的数据传输协议，其底层所依赖的传输链路可能并非是可靠的。例如：传输层协议 TCP 是一个可靠的数据传输协议，但其所赖以实现的网络层协议 IP 却并非是可靠的。
由于对于可靠的数据传输协议底层所依赖的传输链路来说，导致其不可靠本质的原因有很多；因此，接下来，本文将通过不断考虑更加复杂的情况，来尝试设计一个可靠的数据传输协议。例如：如果底层的链路或信道可能引起误码或丢包1，那么应该使用什么样的机制来解决。
上面的图 b 展示了后续即将设计的可靠数据传输所涉及的接口：
- 在发送端，数据传输协议将由其所服务的上层应用通过
rdt_send()2接口发起调用，然后数据会被传输至接收端的上层应用； - 在接收端，当数据包到达信道在接收方的一端时，
rdt_rcv()接口将会被调用； - 当可靠的数据传输协议希望将数据传递给上层时，其将调用
deliver_data()接口； - 可靠数据传输的发送端和接收端3都通过调用下层不可靠协议的
udt_send()接口发送数据，其中udt全称为 unreliable data transfer 即不可靠数据传输。
2. 设计一个可靠的数据传输协议
下面，本文将人为通过对底层信道或链路进行施加约束的方式，来一步步介绍怎么样在不断变得负责的情况下实现一个可靠的数据传输协议。
2.1 rdt1.0 假定底层信道也可靠
首先是最简单的情形，即假定底层信道也是可靠的。这是我们称该协议为 rdt1.0 ，下图给出了此时发送端和接收端的有限状态机，其中图 a 表示发送端的操作而图 b 表示接收端的操作。
在解释图中收发双方的状态机之前，有必要对图中的符号和文字含义解释如下：
- 虚线表示状态机的初始状态；
- 箭头表示从一个状态转移至另一个状态4 ；
- 导致状态转移的事件由横线上方接口调用表示；
- 横线下方表示状态转移事件触发后，相应需要执行的动作；
- 后续图中还将使用符号 Λ \text{Λ} Λ 表示无事件发生或无动作执行。
下面是对于下图中 rdt1.0 收发双方状态机的详细解释：
- rdt1.0 的发送端会通过
rdt_send(data)事件接收来自上一层的数据，然后使用make_pkt(data)创建一个数据包，接着使用udt_send(packet)将数据发送至信道或链路中； - rdt1.0 的接收端会通过
rdt_rcv(packet)事件从底层信道或链路接收数据包，然后使用extract(packet)获取其中的数据5 ，接着使用deliver_data(data)将数据传递给上一层。
在 rdt1.0 中，由于其构建在本身就是可靠的信道或链路之上，因此接收方不需要向发送方提供是否接受成功的应答。
2.2 rdt2.0 假定底层信道有误码
实际上，在实际中上述假设是不可能成立的，即底层的信道总是有可能出现误码6的，因此在 rdt2.0 中来讨论如何解决这个问题，同时这里依旧假设数据包在收发双方被发送或接受的顺序是一致的。
在尝试解决上述问题之前，我们来看一个现实中的例子。假设你正在和别人打电话，而且这时候你需要将对面说的一大段内容都记录下来。在正常情况下，当你每记录一句话之后你都会和对方说“好的”，但如果你没有听清楚对方说的某一句话，此时你会跟对方说“请再重复一下”。
上面这个实际的例子其实就通过使用“肯定应答”和“否定应答”的方式来实现准确的信息交互。实际上，在计算机网络中也是同样的道理，且基于这种方式实现的可靠数据传输协议称为自动重复请求协议（ARQ: Automatic Repeat reQuest）。
由上述讨论可知，要应对可靠传输协议底层信道可能产生误码的情况，ARQ 类协议至少应该具体的机制如下：
- 错误探测。首先，当误码发生时，需要有机制能让接收方探测到。在实际中，这是通过在报文中加入报文校验和字段来实现的，该字段可以让接收方探测甚至可能修正报文误码。
- 接收应答。其次，由于报文的收发双方通常在相隔很远的不同主机上，因此让发送方知道接收方是否成功是否报文的唯一方法就是后者为前者提供明确的应答。在 rdt2.0 中，类似于上述记录对话内容例子，这里使用 ACK 和 NAK 数据包作为接收方在收到报文后向发送方反馈的反馈应答。原则上来说这类应答报文只需一个比特位即可，例如：用 1 1 1 表示 ACK ，用 0 0 0 表示 NAK 。
- 报文重传。最后，显然如果接收方收到的报文在传输过程中发生误码，则发送方将对该报文进行重传。
下图是 rdt2.0 协议即采用了上述机制实现的可靠数据传输协议的收发双方有限状态机：
- 如下图 a 所示，发送端有两个状态：
- 左边的状态表示发送端正在等待上层发起调用并传递数据。具体地，当事件
rdt_send(data)发生时，发送方将会创建一个数据包sndpkt，其中除了包含待发送数据以外，还包括了数据包的校验和（checksum），接着使用udt_send(sndpkt)将数据包发出； - 右边的状态表示发送方正在等待接收方的反馈应答，有可能是 NAK 也可能是 ACK 数据包：
- 如果收到 ACK 应答，即
rdt_rcv(rcvpkt) && isACK (rcvpkt)判断为true，那么发送方就知道自己刚刚传输的数据包被对方成功接受且传输过程无误码产生，自然地发送方此时将会转移至等待上层应用发起调用的状态； - 如果收到 NAK 应答，即
rdt_rcv(rcvpkt) && isNAK (rcvpkt)判断为true，那么发送方就会将刚刚发送过的报文进行重传，同时继续等待对方的 ACK 或者 NAK 应答7。
- 如果收到 ACK 应答，即
- 左边的状态表示发送端正在等待上层发起调用并传递数据。具体地，当事件
如上图 b 所示，接收端仅有一个状态：
- 在数据包到达后，接收方会向发送方反馈 ACK 或 NAK 数据包，具体是哪一个取决于到达的数据包是否产生了误码，在上图中，
rdt_rcv(rcvpkt) && corrupt(rcvpkt)就表示收到了数据包且数据包有错误。
上述 rdt2.0 看起来好像是一个可靠的数据传输协议，但实际上其有一个致命的缺陷，即 rdt2.0 没有考虑到 ACK 或 NAK 数据包也可能发生误码的情况。
为了解决这个问题，你的第一反应可能是给 ACK 或 NAK 数据包也加上校验和字段，然而更关键的问题不止于此，而是该协议如何能在发送方收到发生误码的 ACK 或 NAK 之后还能正确判断接收方是否准确的收到了刚刚的数据包，因此更关键的问题是发送方如何直接从产生误码的 ACK 或 NAK 得到期望的信息。
下面考虑当 ACK 或 NAK 确实发生误码时，可能采取的 3 3 3 中处理方式：
- 对于第一种情况，这里还是用前面提到的记录通话内容的例子来说明。如果对面说话的人没有听清记录人反馈（可能是“好的”或“请再重复一下”），那么对面可能会问“你刚刚说的是什么？”，如果记录人听清了这句话还好，如果没有记录人又没有听清这句话，那么记录人也会问“你刚刚说的是什么？”在极端情况下，这可能陷入无穷尽的循环之中；
- 第二种方式是新增足够位数的校验和，以此让发送方不仅可以探测到误码，还可以从误码中推断出究竟收到的是 ACK 还是 NAK ；
- 第三种方式是当发送方收到产生误码的 ACK 或 NAK 包时，发送方直接重发当前的数据包。问题是，这种方式会为收发双方的信道引入重复的数据包。由此进一步引发的问题是，接收方其实并不知道发送方究竟是否正确地接收了其刚刚应答的 ACK 或 NAK 报文，从而接收方也就无从得知发送方直接重传的数据包是包含新数据还是仅为重传的报文。
2.2.1 rdt2.1
针对 ACK 和 NAK 可能发现误码这个问题，包括 TCP 在内的数据传输协议都采用了一种简单的方式来解决这个问题，即为发送方的数据包中新增一个字段，该字段填写的是发送方为数据包编号之后的数字即序列号，然后接收方只需要检查该序列号就能确定收到的数据包究竟是否为重传报文。
对于上述 rdt2.07 而言，使用 1 1 1 个比特位的序列号就能满足要求，因为这就已经能让接收方知道发送方究竟是在进行报文重传还是发送新的数据包，具体地：
- 当接收方收到的数据包有着和最近收到的数据包相同的序列号，这说明是重传报文；
- 当接收方收到的数据包有着和最近收到的数据包不同的序列号，这说明是新的报文。
需要说明的是，由于截至目前我们依然假设收发双方的信道不会产生丢包，因此 ACK 和 NAK 报文本身并不需要指定是针对哪个收到的数据包的应答反馈，即发送方天然地就知道其收到的 ACK 或 NAK （无所谓是否产生误码8）是针对其最近发出去的数据包的反馈。
上面增加了序列号的数据传输协议（以下称为 rdt2.1），相较于 rdt2.0 ，其收发双方的有限状态机都有更多的状态。原因在于，协议状态需要反映发送方当前发送的或者接收方期望接收的报文究竟序列号为 0 0 0 还是 1 1 1 。
下图分别是 rdt2.1 中发送方和接收方的有限状态机：
-
发送方有限状态机：
-
接收方有限状态机：
2.2.2 rdt2.2
上述 rdt2.1 使用 NAK 来表明其收到来自发送方的数据包有误码产生，实际上，也可以不用 NAK 而是仅使用 ACK 就实现同样的效果，即当接收方收到来自发送方的数据包有误码产生时，接收方向发送方应答针对上一个正确接收的数据包的 ACK ，如果提前约定好，那么此时发送方收到针对同一个数据包的两个 ACK 时，就知道接收方并未能正确接收紧随其后的数据包。
上面给出的不使用 NAK 而仅使用 ACK 作为接收方对所有收到报文（不管产生误码与否）进行应答的协议以下称为 rdt2.2 。rdt2.1 和 rdt2.2 之间的区别主要就在于，接收方在发送 ACK 应答时需要带上对应报文的序列号，而发送方在收到 ACK 时，也需要检查其中的序列号。
下图分别是 rdt2.2 中发送方和接收方的有限状态机：
-
发送方有限状态机：
-
接收方有限状态机：
2.3 rdt3.0 假定底层信道有误码和丢包
现在假定收发双方间的信道除了可能引起误码外，还可能产生丢包，实际上丢包在今天的计算机网络（包括因特网）中还是很常见的现象。信道丢包的可能又引出了对设计可靠数据传输协议的两大挑战：
- 如何探测丢包的产生；
- 丢包产生时如何处理。
实际上，rdt2.2 协议中已有的报文校验和、序列号、ACK 应答包和报文重传等机制已经可以解决上述第二个挑战了，而解决第一个挑战则需要新的协议机制。
这里，新的协议机制将会把负责探测丢包和丢包处理的任务都放到发送方来解决。
假设发送方发送了数据包之后，要么数据包本身，要么接收方针对该数据包的 ACK 应答包丢失了，此时都将导致发送方不可能收到接收方的应答。如果愿意等待足够长的时间，那么发送方是可以判断出数据包是否丢失的，但是问题是究竟多长时间算足够长？
首先，接收方的等待时间至少要大于收发双方间报文往返的时间（可能还要包括在二者中间的路由器中缓存的时间）加上接收方处理报文的时间等。实际上，在多数计算机网络中，这一所谓足够长的时间是很难精确计算的。
其次，为实现高效地数据传输，理想的情况下，丢包的问题应该尽快得到解决，否则将导致数据传输的效率急剧下降。
在实际中，发送方通过审慎地选择一个折中的时间长度，使得过了这么长时间后就判定数据包大概率已经丢失了，此时发送方将进行报文重传。
需要注意的是，如果一个数据包在传输过程中经历了特别长的时延，即使最终该数据包本身以及接收方的 ACK 应答都没有丢失，发送方也将进行报文重传，虽然这将会为收发双方的信道中引入重复的数据包，但幸运的是 rdt2.2 中的报文序列号机制已经可以处理这一情形了。
实际上，从发送者的角度可以说是“遇事不决，报文重传”了。当发送方并不知道究竟是数据包本身丢失或延时过长了，还是 ACK 应答丢失了抑或是延时过长了。在所有这些情况下，发送方的做法都一样：报文重传。
下图是 rdt3.0 中发送方的有限状态机：
由上图可知，相较于 rdt2.2 ，为了应对丢包的情况，这里引入了计时器，具体地：
- 当发送或重传数据包时，发送方需要复位计时器；
- 当计时器显示超时，发送方当前状态被中断，并且需要进行报文重传；
- 当发送方在超时时间内收到接收方应答时，发送方需要停止计时器。
为了更好地理解引入计时器机制的 rdt3.0 是如何在收发双方信道可能引起误码和丢包情况下进行可靠的数据传输，下面给出几个示例，分别表示 rdt3.0 在无丢包和有丢包的情况下是如何工作的：
截至目前，rdt3.0 已经是一个较为成形的可靠的数据传输协议了。
3. 设计一个可靠且高效的数据传输协议
3.1 管道化传输
上述 rdt3.0 在功能上已经基本可以实现可靠的数据传输了，但是其传输效率却差强人意，其本质原因是 rdt3.0 是一个停止-等待型协议。
为了更好的理解为什么停止-等待型协议的效率低下，可以用下面这样一个例子：假设有两台主机，分别位于黑河和腾冲（如下图所示），报文在二者之间的往返传播时延（记为RTT）大概为 30 30 30 毫秒，假设两台主机之间通过传输速率为 R R R 为 1 Gbps 1\text{ }\text{Gbps} 1 Gbps （即每秒传输 1 0 9 10^9 109 比特）的链路相连。
假设每个数据包大小
L
L
L 为
1000
1000
1000 字节（约
8000
8000
8000 个比特，包括报文头和数据），因此将每个数据包传入二者链路所需时间为：
d
t
r
a
n
s
=
L
R
=
8000
bits/packet
1
0
9
bits/sec
=
8
ms
d_{trans}=\frac{L}{R}=\frac{8000\text{ }\text{bits/packet}}{10^9\text{ }\text{bits/sec}}=8\text{ }\text{ms}
dtrans=RL=109 bits/sec8000 bits/packet=8 ms
通过下图 a 我们可以进一步量化停止-等待型协议效率低下的程度。如果发送方在 t = 0 t=0 t=0 的时候发送数据包，那么由上述计算：
- 首先，在 t = L / R = 8 ms t=L/R=8\text{ }\text{ms} t=L/R=8 ms 时，数据包的最后一个比特将进入传输链路；
- 接着，在 t = RTT / 2 + L / R = 15.008 ms t=\text{RTT}/2+L/R=15.008\text{ }\text{ms} t=RTT/2+L/R=15.008 ms 时，数据包的最后一个比特出现在接收端；
- 最后，为简单起见，这里假定 ACK 数据包大小可以忽略（因此其传输时间传输进链路的时间可忽略），另外还假定接收方收到数据包的最后一个比特后立马发送 ACK ，则发送方在 t = RTT + L / R = 30.008 ms t=\text{RTT}+L/R=30.008\text{ }\text{ms} t=RTT+L/R=30.008 ms 时接收到 ACK 。
因此，在整整
30.008
ms
30.008\text{ }\text{ms}
30.008 ms 的时间里，发送方只有
0.008
ms
0.008\text{ }\text{ms}
0.008 ms 的时间在发送数据。具体，可以计算发送方对信道的利用率为：
U
sender
=
L
/
R
R
T
T
+
L
/
R
=
0.008
30.008
=
0.00027
U_{\text{sender}}=\frac{L/R}{RTT+L/R}=\frac{0.008}{30.008}=0.00027
Usender=RTT+L/RL/R=30.0080.008=0.00027
解决上述传输效率低下问题的方法其实也比较简单，如上图 b 所示，即实际可以一次性发送多个数据包然后等待接收方对这些数据包的 ACK 应答，而不是以串行的方式一次只发送一个数据包然后等到收到 ACK 应答后才发送下一个。这种解决方式就是所谓的管道化数据传输。
然而，管道化传输给可靠的数据传输又带来了新的挑战：
- 报文序列号的大小范围需要扩大。因为同一时间可能有多个正在传输且未被确认的数据包，而每一个正在传输过程中的数据包（不包括重传报文）都需要有一个唯一的报文序列号；
- 收发双方需要缓存一个以上数据包。最起码地，发送方需要缓存那些已发送但是未收到确认的数据包，而如下所述，接收方也需要缓存数据包；
- 协议所需的序列号范围以及对报文缓存的要求取决于数据传输协议是如何应对丢包、误码和时延过长等情况。具体地将分别由下面介绍的滑动窗口协议和选择重传协议来解决。
3.2 滑动窗口协议
在滑动窗口协议（又被称为GBN协议，全称Go-Back-N）中，发送方可以一次性发送不超过某个最大值如 N N N 个数据包。下图是从发送者角度来看显示的滑动窗口协议中序列号的范围和工作原理：
其中：
-
base表示所有已发送且未收到 ACK 应答的数据包中，最早被发出去的那一个数据包所拥有的报文序列号； -
nextseqnum表示下一个被发出去的数据包所应该拥有的报文序列号。
由此，所有可能的报文序列号就被分成 4 4 4 个区间：
- [ 0 , base − 1 ] [0,\text{base}-1] [0,base−1] ：序列号在此区间的报文都是已发送且发送方已收到接收方 ACK 应答的；
- [ base , nextseqnum − 1 ] [\text{base},\text{nextseqnum}-1] [base,nextseqnum−1] ：序列号在此区间的报文都是发送方已发送但还未收到 ACK 应答的；
- [ nextseqnum , base + N − 1 ] [\text{nextseqnum},\text{base}+\text{N}-1] [nextseqnum,base+N−1] ：序号序列号在此区间表示如果有报文需要发送，则可以使用此区间的序列号；
-
≥
base
+
N
\ge \text{base}+\text{N}
≥base+N ：序列号在此区间表示此时这些序号暂不可用，只有当发送方收到了针对序列号为
base的报文的 ACK 应答才可能被使用。
由上图可知，长度为 N N N 的区间是所有可用于已发送但未收到 ACK 应答报文的序列号，该区间可视为一个窗口，在协议进行数据包收发期间，相当于该窗口在序列号所有可能取值的区间进行滑动，因此该协议被称为滑动窗口协议，而 N N N 被称为窗口大小。
需要注意的是，在实际中，滑动窗口协议中的报文序列号并非是只增不减，由于序列号这一数据域在数据包的数据头中是固定长度的，假设该长度是 k k k 个比特，那么序列号取值区间就是 [ 0 , 2 k − 1 ] [0,2^k-1] [0,2k−1] 。有人可能会问那如何确保数据包的数量不超过序列号的最大可能取值？
实际上，并没有必要有这样的要求，因为序列号是可以重用的，具体实现方式是对于序列号的所有数学运算都使用按 2 k 2^k 2k 取模的方式进行，这就意味着序列号区间可以视为一个环形区间，即序列号 2 k − 1 2^k-1 2k−1 后跟着的序列号9将会是 0 0 0 。
下面是基于滑动窗口协议实现可靠数据传输所对应的发送方有限状态机：
滑动窗口协议中的发送方必须响应以下三种事件：
-
来自上一层的调用。当上一层调用
rdt_send()接口时，发送方会先检查窗口是否已满，即目前收发双方的信道中是否有 N N N 个发送方已发送但未收到接收方 ACK 应答的数据包：- 如果窗口未满，传递过来的数据将会被打包进数据包中然后发出去，相关变量也会被相应更新；
- 如果窗口已满，发送方可能直接会将数据返回给上一层，即间接向上一层表明当前窗口已满，上一层可能会稍后进行重试10。
- 来自接收方的 ACK 。在上述滑动窗口算法中，接收方针对序列号为 n n n 的数据包发出的 ACK 在发送方被视为累积确认，即该 ACK 表示先前所有序列号小于等于 n n n 的数据包都被接收方成功接收了。
-
未收到 ACK 但超时。如之前所述，这里的滑动窗口协议也被称为 Go-Back-N 算法，这个名字的由来取自发送方在应对丢包或超时情况下的机制。具体地，和上述 rdt3.0 一样，滑动窗口协议也使用计时器来应对丢包和超时情况：
- 如果发生超时，那么发送方会重传所有之前已发送但未收到 ACK 应答的数据包；
- 上面发送方的有限状态机仅使用了一个计时器，该计时器是针对最早发送但未收到 ACK 的数据包，启动计时器的时间是该数据包被发送方发出的同时；
- 如果收到了代表累积确认的 ACK ，则此时除了需要先更新
base变量的值，即向后滑动窗口，还需要根据更新后的base值做不同的处理：- 如果
base等于nextseqnum，这表示收发双方的信道中已经无任何数据包在传输或未被确认，此时直接停止计时器即可； - 如果
base小于nextseqnum，此时需要重新启动计时器。
- 如果
下面是基于滑动窗口协议实现可靠数据传输所对应的接收方有限状态机：
- 如果序列号为 n n n 的数据包被正确接收并且序列号为 n − 1 n-1 n−1 的数据包也已经被正确接收，接收方就会针对序列号为 n n n 的数据包发送 ACK 应答，而后将数据包中的数据部分剥离出来后传递给上一层；
- 在所有其他可能出现的情况下，接收方会丢弃接收到的数据包，然后针对最近一个被正确接收的数据包发送一个 ACK 11。
对于上述滑动窗口协议，有些人可能觉得接收方的处理逻辑过于简单粗暴而且有浪费资源之嫌，他们的理由是接收方在除了序列号为 n n n 的数据包被正确接收并且序列号为 n − 1 n-1 n−1 的数据包也已经被正确接收的所有其他情况下，都会直接将数据包丢弃。
实际上，接收方这么做是有其合理性的。如上所述11，接收方必须按照数据包序列号向上一层传递数据。假设序列号截至 n − 1 n-1 n−1 的数据包都已经被成功接收且传递至上一层，此时虽然接收方期望收到序列号为 n n n 的数据包，但是实际先到达的是序列号为 n + 1 n+1 n+1 的数据包。当然，接收方可以先将序列号为 n + 1 n+1 n+1 的数据包缓存下来，等到正确接收且向上一层传递了序列号为 n n n 数据包后，再对缓存的数据包进行处理。
然而，如果此时序列号为 n n n 的数据包发生丢包，那么根据滑动窗口协议的重传规则，序列号为 n n n 和 n + 1 n+1 n+1 的数据包都会被重传。因此，接收方可以直接丢弃先到达的序列号为 n + 1 n+1 n+1 的数据包。
上述机制的优点在于，接收方的压根不需要实现缓存数据包的机制，因为没有必要。因此，虽然发送方必须要维护其窗口的上下界以及其中 nextseqnum 的位置，但是接收方仅需要维护下一个期望收到数据包的序号 expectedseqnum 。
上述机制的缺点在于，如果直接丢弃序列号不是 expectedseqnum 的数据包，那么如果后续对该数据包的重传发生丢包或误码，此时又会进一步导致更多的报文重传发生。
为了更好地理解上述介绍的滑动窗口协议，下面通过一个示例来说明，示例中窗口的大小为 4 4 4 ：
下面是对上图简单说明：
- 由于窗口大小为 4 4 4 的限制，发送方在发送了序列号从 0 0 0 到 3 3 3 的数据包之后导致窗口已满，此时必须收到 ACK 之后才有可能继续进行数据包的发送；
- 当发送方收到 ACK0 和 ACK1 之后，窗口向右滑动，发送方又可以发送
pkt4和pkt5； - 在接收端，由于数据包
pkt2丢失，所以序列号为 3 3 3 、 4 4 4 和 5 5 5 的数据包都会被直接丢弃； - 在发送端，由于
pkt2超时，所以所有序列号在其之后的数据包都会被重传。
3.3 选择重传协议
对于上述滑动窗口协议，虽然其具有提高信道利用率的功能，但是当有一个数据包的传输有问题时，可能就需要重传很多个数据包。下面即将介绍的选择重传协议就是为了缓解这样的问题。
顾名思义，选择重传协议只会重传那些在传输中发生错误的数据包（如：丢包、误码、时延过长）。这种按需重传机制需要接收方针对每个成功接收的数据包发送 ACK 进行确认，而不是采用累积确认。
在选择重传协议中，同样使用宽度为 N N N 的窗口来限制信道中已发送但发送方未收到 ACK 确认的最大数据包个数；不同的是，相较于上述滑动协议，此时在窗口中将会有部分数据包已经收到了接收方的 ACK 应答。
下图展示了选择重传协议中数据包序列号的分布特点和相关含义：
在选择重传协议中，发送方会针对任何正确接收的数据包发送 ACK 应答，不管其序列号是否紧跟上一个正确接收数据包的序列号。如果接收方收到的数据包后，发现其序列号的确不是按序递增的，那么该数据包将会先被缓存下来，然后等到所有小于该序列号的数据包都正确接收之后，会一股脑将这批数据包按序向上一层传递。
下面针对选择重传协议的收发双方所应该响应的事件和应该执行的操作进行了总结：
-
发送方：
- 接收到来自上一层的待传输数据。该事件下，该协议和上述滑动窗口中发送方所应执行的操作一致，即发送方检查
nextseqnum，如果该值在窗口中则将数据打包后发出，否则对数据进行缓存或直接返回上一层。 - 计时器超时。该事件下，该协议仅会重传超时的数据包。另外需要特别注意的是，该协议下发送方针对每一个发出的数据包都会启动一个计时器。
- 接收 ACK 。
- 如果发送方收到接收方针对某个数据包的 ACK 应答且该应答对应的数据包序列号在窗口内，则发送方会将对应序列号的数据包标记为已被接收。
- 如果 ACK 应答所对应数据包的序列号等于
send_base，则窗口会向右滑动，且send_base会更新为所有已发送但未被确认的数据包中最小的序列号。 - 如果滑动窗口后，有来自上一层等待被发送的数据包且对应序列号落在了窗口之内，则这些数据包会被发送出去。
- 接收到来自上一层的待传输数据。该事件下，该协议和上述滑动窗口中发送方所应执行的操作一致，即发送方检查
-
接收方：
- 序列号在区间
[
rcv_base
,
rcv_base
+
N
−
1
]
[\text{rcv\_base},\text{ }\text{rcv\_base}+N-1]
[rcv_base, rcv_base+N−1] 内的数据包被正确接收。
- 如果该数据包的序列号位于窗口区间内部（不包括窗口的边界），那么一方面接收方会给发送方发送一个针对该数据包的 ACK 应答，而后如果这同时也是接收方第一次收到该数据包，那么该包会被缓存下来。
- 如果该数据包的序列号等于
rcv_base，那么该数据包以及所有先前被缓存下来且序列号连续（序列号从rcv_base开始）的一批数据包都会在剥离出数据之后被传递至上一层。接着接收方的窗口会向右滑动，滑动的距离和刚刚提及的数据包数据了一致。
- 序列号在区间 [ rcv_base − N , rcv_base − 1 ] [\text{rcv\_base}-N,\text{ }\text{rcv\_base}-1] [rcv_base−N, rcv_base−1] 内的数据包被正确接收。在这种情形下，即使接收方可能之前针对该数据包发送了 ACK 应答，此时也必须再次发送 ACK 应答。否则的话，可能会导致发送方的窗口永远无法向右滑动12。
- 其他所有情况。直接忽略数据包。
- 序列号在区间
[
rcv_base
,
rcv_base
+
N
−
1
]
[\text{rcv\_base},\text{ }\text{rcv\_base}+N-1]
[rcv_base, rcv_base+N−1] 内的数据包被正确接收。
为了使读者更好地理解以上论述，下面通过一个案例来展示选择重传协议是如何处理丢包场景的：
4. 总结
至此基本就是本文的全部内容，这篇文章通过循序渐进的方式，通过假定收发双方间的信道越来越复杂，逐步引入各种机制，最终基本实现了可靠且高效的数据传输协议，在此将本文提及的各种机制总结如下表：
| 机制 | 作用 |
|---|---|
| 校验和 | 用于探测数据包在传输过程中是否发生了误码。 |
| 计时器 | 用于在数据包或应答 ACK 发生丢包或者数据包传输时延过长时进行报文重传。 |
| 序列号 | 用于对收发双方之间的数据包进行编号。 |
| ACK 应答 | 用于接收方告知发送方某个或某几个数据包已经被正确接收。ACK 应答报文中通常包含其所对应的数据包序列号。 |
| NAK 应答 | 用于接收方告知发送方某个数据包未能被正确接收。NAK 应答报文中通常包含其所对应的数据包序列号。 |
| 窗口，管道化 | 通过允许最大不超过窗口大小个数据包同时发送，可以提高数据传输效率，这样的机制称为管道化传输。 |
-
需要注意的是，本文将自始至终假设数据包在信道或链路中被传递的顺序和其在发送端被发送的顺序是一致的，即虽然可能发生丢包，但是可靠的数据传输协议底层所依赖的信道或链路是不会改变数据包传递的顺序的。 ↩︎
-
这里
rdt全称为 reliable data transfer 即可靠数据传输，而 _send 表示被调用的是发送端的可靠数据传输服务。 ↩︎ -
为简单起见，本文仅讨论单向的数据传输，即数据从发送端到接收端，实际上发送端和接收端是对偶的概念。 ↩︎
-
由于图中收发双方都只有一个状态，因此这里状态转移前后都是同一个状态，后续当情况更复杂时将出现多个状态之间的相互转移。 ↩︎
-
这里数据包（packet）和数据（data）的概念可类比于带包装的快递和拆除包装的快递。 ↩︎
-
所谓误码这里指数据在信道或链路的传输过程中比特位由 0 0 0 跳变为 1 1 1 或者由 1 1 1 跳变为 0 0 0 。 ↩︎
-
需要注意的是，这里当发送方处于等待ACK 或者 NAK 应答的状态时，发送方是不能继续从上一层接受数据的，即
rdt_send(data)事件无法被触发，只有当发送方收到了 ACK 应答其才能转移到等待上层应用发起调用的状态。也就是说，发送方在确认接收方已经成功接收了最新的一个数据包之前是不会发送新的数据的，因此 rdt2.0 也被称为停止等待型协议（stop-and-wait protocol）。 ↩︎ ↩︎ -
实际上，这并不意味着 ACK 或 NAK 是否产生误码对发送方无影响，发送方还是需要知道收到应答报文内容究竟是 ACK 还是 NAK ，因为发送方接下来要据此做不同处理，即如果是 ACK ，即发送方将发送新的数据包，如果是 NAK ，发送方将进行报文重传。 ↩︎
-
值得一提的是，在 TCP 协议中，报文序列号并不是按照报文个数增加的，而是按照报文的字节数增加的。 ↩︎
-
在实际实现中，发送方一般会在这时候将数据进行缓存，或者采用一种同步机制（如：信号量、标志位）以实现只有当窗口未满时才可以调用
rdt_send()接口。 ↩︎ -
值得注意的是，由于接收方收到数据包之后是挨个将其中的数据剥离出来后传递至上一层，这就意味着如果序列号为 k k k 的数据包被正确接收且其中数据被传递至上一层，那么所有序列号小于 k k k 的数据包也都已经得到了正确地处理。 ↩︎ ↩︎
-
在选择重传协议中数据包序列号的分布特点和相关含义那张图中，如果接收方收到了序列号为
send_base的数据包而且也给发送方发送了 ACK ，但是该 ACK 发生了丢包，那么在计时器超时后发送方会重传该数据包，此时接收方可能再次收到该数据包，虽然之前接收方已经回复了 ACK ，但是整个过程中发送方是无从得知的，即如果接收方不再次针对这个数据包回复 ACK 的话，发送方就会反复重传该数据包，更重要的是发送方的窗口永远都不会向右滑动。 ↩︎