【网络】计算机网络笔记——可靠的数据传输原理

【网络】计算机网络笔记——可靠的数据传输原理

在计算机网络的数据传输的过程中可能遇到数据的损坏问题:

  • 分组的数据(bit)在传输过程中发生损坏,部分从 1 变成了 0 或者从 0 变成了 1
  • 分组在传输过程中丢失,如到达中转路由器时,由于其输入队列已满,导致该分组被丢弃
  • 分组未按照发送顺序到达接收方

因此,为了实现在一个不可靠的下层的基础上实现一个可靠的传输(如 TCP 协议在不可靠的 IP 协议的基础上实现的可靠传输协议),我们需要在该层建立一个可靠的数据传输协议,它可以使得数据通过一条可靠的信道进行传输,并且不会受到损坏或丢失,并且所有数据都是按发送顺序进行交付。

下面就让我们讨论一下可靠数据传输协议

可靠数据传输协议 rdt(Reliable Data Transfer)

rdt 1.0

rdt 1.0 的特点就是它认为底层的信道是可靠的,完全信任下层的信道,不会进行任何的处理措施,只负责数据的发送和接收。有了完全可靠的下层信道,接收方就不需要提供任何反馈信息给发送方。

rdt 2.0

显然 rdt 1.0 假设的情景过于理想,实际的下层信道中,分组中的数据是可能受损的。因此引入了 rdt 2.0,它引入了肯定确认(ACK)和否定确认(NAK)。接收方收到数据后,判断数据是否受损,根据具体情况返回 ACK 或 NAK 分组(下面简称反馈分组)给发送方。

发送方收到反馈分组后,若为 NAK 则进行数据的重传,直到收到 ACK 为止。

rdt 2.1

看似 rdt 2.1 不存在什么问题了,但实际上还需要考虑到我们的反馈分组实际上也是有可能受损的,因此我们在数据分组中又引入一个新字段——数据分组的编号。

这样,接收方发现数据不完整时,仍然会发送 NAK 给发送方,发送方则会重发数据。

而如果收到的数据完整但序号不是自己等待的序号,则会给发送方发送 ACK + 收到的序号,这样发送方发现收到的反馈分组中的序号不是正确的序号的话,则会重发数据。

rdt 2.2

rdt 2.2 是基于 rdt 2.1 的基础上的改良,由于同时使用 ACK 与 NAK 两种讯息比较费力,因此它去掉了 NAK,接收方必须发送一个由 ACK 及分组序号构成的 ACK 分组,发送方必须检查收到的 ACK 分组中被确认的分组序号。

比如发送方发出 0 号数据,收到的却是 ACK 1,则说明需要重发。

接收方等待 0 号数据,却发现等到的是 1 号数据或是不完整数据,则说明出错了,会发送 ACK 1 给发送方,从而提示发送方需要进行重发。

rdt 3.0

前面的 rdt 2.2 看起来貌似完美解决了分组损失的问题,但它没有考虑到丢包这一情况,因此引入了 rdt 3.0,它在 rdt 2.2 的基础上引入了一个倒数计时器,接收方发送数据时便会启动这个计时器,直到收到对应编号的 ACK 分组,否则计时器时间到了则会进行数据的重发。

比如发送了 1 号数据,它只会等待 1 号的 ACK 分组,如果收到的不是 1 号的分组,计时器仍会继续倒计时,直到时间到,数据进行重发。

流水线可靠数据传输协议

前面提到的 rdt 3.0 已经是一个功能正确的可靠数据传输协议了,它可以在分组损失、丢包、超时等情况下保证数据的可靠传输。但它的性能是一个很大的问题,因为它是一个停等协议。也就是要等到一个分组确认发送完毕后才会开始下一个分组的发送。

这样的设计会对网络的性能造成极大的浪费,因此我们需要解决这个问题。

一个解决这种性能问题的简单策略是不再使用停等的方式进行,允许发送方发送多个分组而不用等待确认。这就是我们这里要提到的流水线可靠数据传输协议。这种流水线会带来以下的影响:

  • 需要增加序号范围。因为输送中的分组必须有个唯一的序号,且可能有多个输送中未确认的报文。
  • 协议发送方和接收方必须缓存多个分组,发送方需要能缓存那些已发送但仍未确认的分组。接收方可能需要缓存那些正确接收的分组。

需要的序号范围和缓冲大小取决于如何处理丢失、损坏及超时的分组。解决这种流水线差错恢复有两种方法:

  1. 回退 N 步(GBN)
  2. 选择重传(SR)

回退 N 步(GBN)协议

在回退 N 步(GBN)协议中,允许发送方发送多个分组,不需要等待确认,但未确认的分组数不能超过最大允许数 N。

看到下面的图,将分组分为了下面四类,未确认分组不能超过最大允许数 N。我们可以把 baseNum 到 baseNum + N 看做是一个窗口。随着传输的进行,窗口在逐渐向后移动,因此 N 一般被称作窗口长度,而 GBN 协议也被称为滑动窗口协议

image-20190322135847810

为什么我们要限制这些被发送未确认及未发送的分组数最大值为 N 呢?流量控制就是其中的一点原因,这些原因我们会在后面慢慢揭开。

一般我们的分组序号是放在固定长度的字段中的,因此假设它占据了 k bit 的字段,则这个分组序号的范围就是 [0, 2^k – 1]。

发送方

GBN 协议的发送方必须响应三种事件:

  • 上层调用。上层调用时,发送方先检查窗口是否已满,若未满则产生分组并发送,否则将数据返回给上层,告诉上层数据已满,让它过一会再试。其实一般情况下发送方会缓存这些数据,等到窗口空闲时再发送。或者是使用同步机制(如信号量或标志)允许上层在窗口不满时再调用请求
  • 接收 ACK。在 GBN 协议中,序号为 n 的分组的确认采用累积确认的方式,说明接收方正确接收序号为 n 的包括 n 在内的所有分组。
  • 超时事件。为了处理丢失和发送时间过长的问题,仍然采用了定时器。如果出现超时,发送方重传所有已发送但未被确认过的分组。如果收到了一个 ACK,但仍有已发送但未被确认的分组,则定时器被重新启动。如果没有已发送但未被确认的分组,则定时器被终止。

接收方

GBN 协议的接收方会丢弃所有失序分组,如果一个序号为 n 的分组被接收,并且按序,则会发送 ACK,否则该分组会被直接丢弃。正是因为如此,若第 k 个分组被成功交付,则序号小于 k 的所有分组都已成功交付。

这样的设计可能会有些蠢,比如一些成功接收但失序的分组就没有必要丢弃。但这样的方法可以使得接收缓存变得简单,不需要缓存任何失序分组。因此虽然发送方需要维护窗口上下边界以及下一个发送的分组在窗口中的位置,但是接收方就只需要维护下一个接收的分组和序号。

选择重传(SR)协议

GBN 协议允许发送方用多个分组来填充流水线,但其仍存在一些性能问题。窗口长度和带宽的延时都比较大的时候,流水线具有很多分组的情况下这种情况十分明显。一些失序但是数据成功传输的分组实际上完全没有必要重传,当信道的差错率比较大时,流水线就会被大量这类没有必要重传的分组充斥。

选择重传(SR)协议让发送方仅仅重传那些怀疑在接收方受损或是丢失的分组,从而避免不必要的重传。它同样使用 N 来限制未被确认或未完成的分组数。

image-20190322173136387

发送方

SR 协议的发送方会相应如下的事件:

  • 从上层收到数据。从上层收到数据后,会检查下一个可用于该分组的序号,若位于发送方窗口内,则打包数据并发送。否则会像 GBN 一样要么缓存,要么返回给上层以便之后传输。
  • 接收 ACK。收到 ACK,若分组序号位于窗口内,则 SR 协议会将那个分组标记为已接收。若该分组序号为第一个已发送未确认的分组,则窗口会向后移动到最小的未确认分组处。若窗口移动并且有落在窗口内的未发送分组,则发送该分组。
  • 超时事件。仍然会用到之前的定时器,但是每个分组会具有自己的逻辑定时器,超时发送发生后只能发送一个分组。可以使用单个的硬件定时器模拟多个逻辑定时器。

接收方

SR 协议的接收方会确认一个正确接收的分组,不管其是否按序。失序的分组将会被缓存直到所有丢失的分组(序号更小的分组)都被收到为止。此时才能将一批分组按序交付给上层。

下面是 SR 协议的接收方会相应的事件:

  • 序号在窗口内的数据被正确接收。此时,收到的分组落在了接收方的窗口内,选择 ACK 被回送给发送方。若该分组之前未收到过,则缓存该分组。若分组序号等于接收窗口的第一个未确认分组序号,则该分组及之前缓存的序号连续的分组会被交付给上层。之后接收窗口会按向后移动的编号向上交付这些分组。
  • rcv_base 为窗口的第一个,序号在 [rcv_base-N,rcv_base-1] 内的分组被正确收到。这种情况下必须产生一个 ACK,即使接收方以前已确认过的分组。(重新确认已收到的分组)
  • 其他情况。忽略该分组

总结

下面让我们来总结一下可靠数据传输机制和它们的用途:

  • 检验和机制:用于检测一个分组传输中的 bit 错误
  • 定时器:用于超时/重传一个分组,可能因为该分组在信道中丢失或超时。
  • 序号:将发送方流向接收方的数据按顺序分号,检测接收分组序号间的空隙可以发现丢失的分组,检测相同序号可以发现一个分组的冗余副本。
  • 确认:接收方告诉发送方一组分组已被正确接收到,通常携带着一个分组或多个分组的序号。
  • 否定确认:接收方告诉发送方一个分组未被正确接收到,通常携带未被正确接收的分组的序号。
  • 窗口、流水线:发送方被限制仅发送序号落在一定范围内的分组。通过允许一次发送多个分组但未被确认,发送方利用率可以相比停等协议大幅提升。窗口长度可以根据接收方接收和缓存报文的能力、网络中的拥塞程度来进行设置。

参考资料

《计算机网络——自顶向下方法》

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: