可靠数据传输服务续

发表于 | 分类于
字数统计: 12k

经过 前文的介绍，我们已经有了一个可以在『存在比特差错的丢包信道』上进行可靠数据传输（reliable data transfer）的协议——rdt3.0。同时我们也发现 rdt3.0 并不完善，它是一个停等（stop-and-wait）协议，还存在性能方面的问题待优化。

由停等到流水线

为了评价停等行为对性能的影响，可以考虑一种只有两台主机的理想化场合，一台主机位于美国西海岸，另一台位于美国东海岸，如图 3-17 所示。这两个端系统之间的光速往返传播时延 RTT（Round-Trip Time） 大约为 30 毫秒
。假定彼此通过一条发送速率 R 为 1Gbps (每秒 10⁹ 比特）的信道相连。包括首部字段和数据的分组 L 长 1000 字节（8000 比特），发送一个分组进入 1Gbps 链路实际所需时间是：

$$T𝗍𝗋𝖺𝗇𝗌=\frac{L}{R}=\frac{8000 bit}{10⁹ bit/s}=8µs$$

图 3-17 停等协议与流水线协议

图 3-18a 显示了对于该停等协议，如果发送方在 t=0 时刻开始发送分组，经过 t=L/R=8µs 后，最后 1 比特数据进入了发送端信道。该分组经过 15ms 后到达接收端，最后 1 比特在时刻 T=RTT/2 + L/R= 15.008ms 时到达接收方。为了简化起见，假设 ACK 分组很小（以便我们可以忽略其发送时间），接收方一旦收到一个数据分组的最后 1 比特后立即发送 ACK，ACK 在时刻 t = RTT + L/R =30.008ms 时到达发送方。此时，发送方可以发送下一个报文。因此，在 30.008ms 内，发送方的发送只用了 0.008ms。如果我们定义发送方（或信道）的利用率 (utilization) 为：发送方实际忙于将发送比特送进信道的那部分时间与发送时间之比，图 3-18a 中的分析表明了停等协议有着非常低的发送方利用率 U𝗌𝚎𝗇𝚍𝚎𝚛：

$$U𝗌𝚎𝚗𝚍𝚎𝚛=\frac{L/R}{RTT+L/R}=\frac{0.008 ms}{30.008 ms}=0.00027$$

图 3-18 停等和流水线发送

也就是说，发送方只有万分之 2.7 的时间是忙的。

从其他角度来看，发送方在 30.008m 内只能发送 1000 字节，有效的吞吐量仅为 267kbps，即使有 1Gbps 的链路可用！这是一个形象的网络协议限制底层网络硬件所提供的能力的示例。而且，我们还忽略了在发送方和接收方的底层协议处理时间，以及可能出现在发送方与接收方之间的路由器上的处理与排队时延。考虑到这些因素，其性能将更加糟糕。

解决这个问题的一个简单方法是：不用停等方式运行，允许发送方发送多个分组而无需等待确认。

图 3-18b 显示，如果发送方可以在等待确认之前发送 3 个报文，其利用率基本上提高了 3 倍。因为从『发送方』向『接收方』输送的分组可以被看做是填充到一条流水线中，故这种技术被称为流水线（pipelining）。流水线技术对可靠数据传输协议带来的影响如下：

  • 必须增加序号范围。
    • 因为每个输送中的分组（不计算重传的）必须有一个唯一的序号，而且存在多个在输送中未确认的报文。
  • 协议的发送方和接收方两端必须缓存多个分组。
    • 发送方最低限度应当能缓存那些已发送但还没有收到确认的分组。
    • 接收方也需要缓存那些已正确接收的分组。
  • 所需序号范围和对缓存的要求取决于数据传输协议如何处理丢失、损坏及延时过大的分组。
    • 解决流水线的差错恢复有两种基本方法：回退 N 步（Go-Back-N，GBN）和选择重传（Selective Repeat，SR）。

Go-Back-N

滑动窗口协议

在回退 N 步协议中，允许发送方发送多个分组而无需等待确认，但它受限于在流水线中未确认的分组数不能超过最大允许数 N。

图 3-19 显示了发送方看到的 GBN 协议的序号范围。如果我们将基序号（base）定义为最早的未确认分组的序号，将下一个序号（nextseqnum）定义为最小的未使用序号（即下一个待发分组的序号），则可将序号范围分割成 4 段。[0, base-1] 段内的序号对应于已经发送而且被确认的分组。[base, nextseqnum - 1] 段内对应已经发送但未被确认的分组。[nextseqnum, base + N - 1] 段内的序号用于那些要被立即发送的分组。最后，大于等于 base + N 的序号是不能使用的，直到流水线中未被确认的分组（特别是序号为 base 的分组）已得到确认为止。

图 3-19 在 GBN 中发送方看到的序号

那些已被发送但还未被确认的分组的序号范围可以被看成是一个长度为 N 的窗口。随着协议的运行，该窗口在序号空间向前滑动。因此，N 常被称为窗口长度（window size），GBN 协议也常被称为滑动窗口协议 (
sliding-window protocol)。

在实践中，一个分组的序号是放在分组首部的一个固定长度的字段中。如果分组序号字段的比特数是 k，则该序号范围是 [0, 2ᵏ - 1] 。在一个有限的序号范围内，所有涉及序号的运算必须使用模 2ᵏ 运算（可将序号空间看作是一个长度为 2ᵏ 的环，其中序号 2ᵏ - 1 紧挨着序号 0）。前面讲过，rdt3.0 序号字段为 1 比特，其序号范围是 [0, 1] （而 TCP 的序号字段有 32 比特）。

发送方 FSM

图 3-20 GBN 发送方的扩展 FSM 描述

GBN 发送方必须响应三种类型的事件：

  • 上层的调用。
    • 当上层调用 rdt_send 时，发送方首先检查发送窗口是否已满，即是否有 N 个已发送但未被确认的分组。
    • 如果窗口未满，则产生一个分组并将其发送，并相应地更新变量。如果窗口已满，发送方只需将数据返回给上层，并指示上层该窗口已满，然后上层可能会过会儿再试。
    • 在实践中，发送方更可能缓存这些数据，或者使用同步机制（如一个信号量或标志）控制上层在窗口不满时才调用 rdt_send。
  • 收到一个 ACK。
    • 在 GBN 协议中，对序号为 n 的分组的 ACK 确认采取累积确认（cumulative acknowledgment）的方式，表明接收方已正确接收到序号为 n 的之前（包括 n ）的所有分组。
  • 超时事件。
    • 协议的名字 GBN 来源于『当出现丢失或时延过长的分组时发送方的行为』。
    • 就像在停等协议中那样，定时器将再次用于恢复数据或确认分组的丢失。如果出现超时，发送方重传所有已发送但还未被确认过的分组。
    • 图 3-20 中的发送方仅使用一个定时器，它可被当作是最早的已发送但未被确认的分组所使用的定时器。
    • 如果收到一个 ACK，且存在已发送但未被确认的分组，则定时器被重置。如果不存在已经发送但未被确认的分组，则定时器被终止。

接收方 FSM

图 3-21 GBN 接收方的扩展 FSM 描述

在 GBN 中，接收方的动作也很简单：

  • 如果一个序号为 n 的分组被正确接收到，并且按序（即上次交付给上层的数据是序号为 n-1 的分组），则接收方为分组 n 发送一个 ACK，并将该分组中的数据交付到上层。
  • 在所有其他情况下，接收方丢弃该分组，并为最近按序接收的分组重新发送 ACK。
    • 因为一次交付给上层一个分组，如果分组 k 已接收并交付，则所有比 k 小的分组也已经交付。因此，使用累积确认是 GBN 的一个自然选择。

在 GBN 协议中，接收方丢弃所有失序分组。尽管丢弃一个正确接收（但失序）的分组有点愚蠢和浪费，但这样做是有理由的。前面讲过，接收方必须按序将数据交付给上层。

假定现在期望接收分组 n，而分组 n+1 却到了。因为数据必须按序交付，接收方可能缓存分组 n+1，然后在它收到并交付分组 n 后，再将该分组交付到上层。然而，如果分组 n 丢失，则该分组及分组 n+1 最终将被发送方根据 GBN 重传规则而进行重传。因此，接收方只需丢弃分组 n+1 即可。这种方法的优点是接收缓存简单，接收方不需要缓存任何失序分组。因此，虽然发送方必须维护窗口的上下边界及 nextseqnum 在该窗口中的位置，但接收方只需要维护下一个按序接收的分组的序号即可。该值保存在 expectedseqnum 变量中（如图 3-21 中接收方 FSM 所示）。当然，丢弃一个正确接收的分组的缺点是随后对该分组的重传也许会丢失或出错，可能需要更多的重传。

运行中的 GBN

图 3-22 给出了窗口长度为 4 的 GBN 协议的运行情况。因为该窗口长度的限制，发送方发送分组 0-3，在继续发送之前，必须等待一个或多个分组被确认。当接收到每一个连续的 ACK（例如 ACK 0 和 ACK
1）时，该窗口便向前滑动，发送方就可以发送新的分组（分组 4 和分组 5）。在接收方，分组 2 丢失，因此分组 3、4、5 被发现是失序分组而被丢弃。

图 3-22 运行中的 GBN

Selective Repeat

GBN 大批量重传的问题

在图 3-17 中，GBN 协议允许发送方用多个分组『填充流水线』，因此缓解了停等协议中信道利用率低的问题。然而，GBN 协议在某些情况下也存在着性能问题。尤其是当窗口长度和带宽时延的乘积很大时，在流水线中更为严重（因为分组更多）。单个分组的差错就能够引起 GBN 重传大批分组，但许多分组根本没有必要重传。随着信道差错率的增加，流水线可能会被这些不必要重传的分组所充斥。想象一下，在我们口述消息的例子中，如果每次有一个单词含糊不清，其前后 1000 个单词（假设窗口长度为 1000）被重传的情况。此次口述将会由于这些反复重传的单词而变慢。

顾名思义，选择重传（SR）协议通过让发送方仅重传那些它怀疑在接收方出错（即丢失或受损）的分组来避免不必要的重传。这种『按需重传』要求接收方逐个地确认正确接收的分组。再次用窗口长度 N
来限制流水线中未完成、未被确认的分组数。然而与 GBN 不同的是，发送方已经收到了对窗口中某些分组的 ACK。图 3-23 显示了 SR 发送方和接收方看到的序号空间。

图 3-23 SR 发送方与接收方的序号空间

SR sender

SR 发送方的事件与动作：

  • 上层的调用。
    • 当从上层接收到数据后，SR 发送方检查下一个可用于该分组的序号。如果序号位于发送方的窗口内，则将数据打包并发送；否则就像在 GBN 中一样，要么将数据缓存，要么将其返回给上层以便以后传输。
  • 收到一个 ACK。
    • 如果收到 ACK，假如该分组序号在窗口内，则 SR 发送方将那个被确认的分组标记为已接收。如果该分组的序号等于
      send_base（窗口基序号），则将窗口基序号向前移动到具有最小序号的未确认分组处。如果窗口移动了并且有序号落在窗口内的未发送分组，则发送这些分组。
  • 超时事件。
    • 定时器被用于恢复数据或确认分组的丢失。然而，现在每个分组必须拥有其自己的逻辑定时器，因为超时发生后只能发送一个分组。

SR receiver

SR 接收方的事件与动作：

  • 序号在 [rcv_base, rcv_base + N - 1] 内的分组被正确接收。
    • 收到的分组落在接收方的窗口内，回复一个 ACK 给发送方。
    • 如果该分组以前没收到过，则缓存该分组。如果该分组的序号等于接收窗口的基序号，则将该分组以及之前缓存的序号连续的（起始于 rcv_base 的）分组交付给上层。例如图 3-26，当收到一个序号为 rcv_base = 2
      的分组时，该分组及分组 3、4 、5 可一起交付给上层。
  • 序号在 [rev_base - N, rev_base - 1] 内的分组被正确收到。
    • 在此情况下，必须产生一个 ACK，即使该分组是接收方以前已确认过的分组。
  • 其它情况。
    • 忽略该分组。

图 3-26 SR 操作

SR 窗口不一致的问题

注意 SR receiver 中的第二步很重要，接收方重新确认（而不是忽略）已收到过的那些序号小于当前窗口基序号的分组。这种重新确认是必要的。

例如图 3-23 中所示的发送方和接收方的序号空间，如果分组 send_base 的 ACK 没有从接收方传播回发送方，则发送方最终将重传分组 send_base，即使接收方已经收到了该分组。如果接收方不确认该分组，则发送方窗口将永远不能向前滑动！这个例子说明了 SR 协议的一个重要特性：对于哪些分组已经被正确接收、哪些没有，发送方和接收方并不总是能看到相同的结果。这就意味着发送方和接收方的窗口并不总是一致。

当我们面对有限序号范围的情况时，发送方和接收方窗口间缺乏同步会产生严重的后果。下面例子中包括了 4 个分组序号，序号分别是 0、1、2、3 且窗口长度为 3。假定发送了分组 0 至 2，并在接收方被正确接收且确认了。此时，接收方窗口落在第 4、5、6 分组上，其序号分别为 3、0、1。现在请大家站在接收方的立场，考虑以下两种情况:

  • 在第一种情况下（如图 3-27a 所示），前 3 个分组的 ACK 丢失，因此发送方重传这些分组。接收方下一步要接收序号为 0 的分组（老的数据分组）。
  • 在第二种情况下（如图 3-27b 所示），前 3 个分组的 ACK 都被正确交付。因此发送方向前移动窗口并发送第 4、5、6 个分组，其序号分别为 3、0、1。但序号为 3 的分组丢失了，序号为 0 的分组先到达（新的数据分组）。

图 3-27 SR 接收方窗口太大的困境：是一个新分组还是一次重传

因为接收方只能观察到它从信道中收到的以及它向信道中发出的报文序列。就上述示例而言，图 3-27 中的两种情况是等价的。接收方没有办法区分序号为 0 的分组是第 1 个分组的重传还是第 5 个分组的初次传输。显然，**
窗口长度比序号空间小 1 时协议无法正常工作**。那窗口必须多小呢？

窗口长度必须小于等于序号空间大小的一半。

总结

可靠数据传输机制及其用途

机制 用途和说明
校验和 用于检测分组在传输过程中产生的比特错误。
流水线 允许发送方发送多个分组而无需等待确认。
定时器 用于超时重传一个分组，因为该分组或其 ACK 可能在信道中丢失了。
序号 接收方根据序号可以检测出丢失或重复的分组。
窗口 发送方被限制仅发送那些序号落在一个指定范围内的分组。
ACK 接收方告诉发送方某个分组已被正确地接收到。（确认报文通常携带着被确认的分组的序号；确认可以是逐个的或累积的，这取决于协议。）
NAK 接收方告诉发送方某个分组未被正确地接收到。（否定确认报文通常携带着未被正确接收的分组的序号。）

信道重排序分组的问题

我们曾假定分组在发送方与接收方之间的信道中没有被重新排序。这在发送方与接收方由单段物理线路相连的情况下，是一个合理的假设。然而，当连接两端的信道是一个网络时，分组重新排序是可能发生的。

分组重新排序的一个表现就是：一个具有序号或确认号 x 的分组的旧副本可能会再次出现，即使发送方或接收方的窗口中都没有包含 x。此时信道可被看做是在缓存分组，并在将来任意时刻释放出这些分组。由于序号可以被重新使用，那么必须小心，以免出现这样的冗余分组。

实践中采用的方法是：序号 x 能否被重新使用，需要发送方『确信』任何先前发送的序号为 x 的分组都不再在网络中为止。通过假定一个分组在网络中『存活』的时间不会超过某个 最大时间量 来做到这一点。

Mac 电脑用 sysctl net.inet.tcp.msl 命令查看，单位毫秒

引用