【计算机网络】如何实现可靠数据传输?

用户头像
烫烫烫个喵啊
关注
发布于: 2020 年 07 月 12 日
【计算机网络】如何实现可靠数据传输?

在讨论TCP协议之前,要先谈一谈可靠数据传输的原理。因为可靠数据传输的实现问题不仅在运输层出现,也会在链路层、应用层出现。TCP所采用的,正是即将描述的内容。



要做到可靠传输,至少要实现以下几点

  1. 差错检测。需要一种机制能使接受方检查出接收到的分组是否出现了差错。

  2. 接收方反馈。发送方为了了解接收方是否正确的接受了分组,唯一途径就是让接受方提供明确的反馈信息给发送方。对于正确接收到某一个分组,将回复一个肯定确认(ACK),如果收到一个受损的分组,将回复一个否定确认(NAK)。

  3. 重传。接收方收到有差错的分组的时候,发送方将重传该分组。

  4. 对分组编号。如果一个ACK或NACK分组受损,发送方将无法知道接收方是否正确接收了上一块发送的数据。 如果进行重传,那么接收方根本不知道它上次发送的ACK或NAK是否被发送方正确的接收到,因此它无法预先地知道接收到的分组是一个新的分组还是上个分组的重传。 一个简单的解决方法是对分组进行编号,接收方只要检查分组的需要就知道是否是一次重传。

  5. 冗余ACK。对于收到受损的分组,接收方将发送一个NAK。如果不发送NAK,而是对上次接收正确的分组发送一个ACK,我们也能实现与NAK一样的效果。发送方收到对同一个分组的两个ACK后,就知道接收方没有正确收到被确认两次的分组的后面的分组。



比特交替协议

  比特交替协议是一个停等协议。所谓停等协议就是指发送方在接收到ACK或NAK之前不会发送一个新的分组。由于同时最多只会传送一个分组,所以比特交替协议对信道的利用率是非常低的。



流水线协议



   比特交替协议是一个功能正确的协议,但并非人人都对它的性能满意。解决这种问题的一个简单办法是允许发送方发送多个分组而无需等待确认。如果发送方可以在等待确认之前发送3个报文,其利用率也将提高3倍。由于许多从发送方向接收方输送的分组可以被看成是填充到一条流水线中,故这种技术被称为流水线



流水线协议对可靠数据传输带来以下影响:

  1. 必须增加序号范围。对于比特交替协议,序号只用一个比特就足够了,而流水线协议则需要更大的序号范围。

  2. 协议的发送方和接收方都必须缓存多个分组。发送方和接收方都需要能缓冲哪些已发送但没有确认的分组。

  3. 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失、损坏、超时的分组。解决流水线差错恢复的两种基本办法是:回退N步(Go-Back-N,GBN) 和*选择重传(Selective Repeat,SR)*。



回退N步

  在回退N步(GBN)协议中,运行发送方发送多个分组(当有多个分组可用时)而不需确认等待,但它也受限于在流水线中未确认的分组数不能超过某个最大允许数N



  下图显示了发送方看到的GBN协议的序号范围。我们将基序号(base)定义为最早的未确认分组的序号,将下一个序号(nextseqnum)定义为最小的未使用序号(即下一个待发分组的序号),则可以将序号范围分隔成四段。

  • [0,base - 1] 段内的序号对应于已经发送并被确认的分组。

  • [base,nextseqnum] 段内定义为已经发送但未被确认的分组。

  • [nextseqnum,base + N - 1] 段内的序号用于哪些要被立即发送的分组,如果有数据来自上层的话。

  • 最后,大于或等于 base + N 的序号是不能被使用的,直到当前流水线中未被确认的分组(特别是序号为base的分组)已得到确认为止。





   哪些已被发送但还未被确认的分组的序号范围可以被看成是一个序号范围长度为 N 的窗口。随着协议的运行,该窗口的序号空间向前滑动。因此, N 常被称为窗口长度,GBN协议也常被称为滑动窗口协议



  为什么要限制分组的数目为 N 呢,为什么不允许这些分组为无限制的数目呢?之后会说到,流量控制是对发送方施加限制的原因之一



  这里有一个GBN协议的交互式程序,可以去感受一下过程。

GBN 发送方

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

  • 上层的调用。当上层调用 rdt_send() 时,发送方首先检查发送窗口是否已满,即是否有 N 个已发送但未被确认的分组。如果窗口未满,则生产一个分组并将其发送,并相应地更新变量。如果窗口已满,发送方只需要拒绝该数据并通知上层即可,或自己将数据缓存下来。

  • 收到一个ACK。在GBN协议中,对序号为 n 的分组的确认采取累计确认的方式,表明接收方已正确收到序号为 n 的以前的且包括 n 在内的所有分组。所以发送方可以直接提取出ACK中的序列号,并令base向前滑动此序列号个长度。

  • 超时事件。协议的名字就来源于出现丢失和时延过长分组时发送方的行为。如果超时,发送方将重传所有已发送但未被确认过的分组。





GBN 接收方

  GBN接收方的动作也很简单。如果一个序号为 n 的分组被正确接收到,并且按序(即上次交付给上层的数据是序号为 n - 1 的分组,即序号为 n 的之前的分组都已被正确接收),则接收方为分组 n 发送一个 ACK,并且将该分组中的数据部分交付到上层。在所有其它情况下,接收方丢弃该分组,并为最近按序接收的分组重新发送 ACK。





  在GBN协议中,接收方丢弃所有失序分组,看起来有点愚蠢和浪费,但这样做也是有理由的。假定现在接收方期望接收分组 n ,而分组 n + 1却到了。因为数据必须按序交付给上层,接收方可以缓存分组 n + 1,然后在它收到并交付分组 n 后,再将该分组交付给上层。然而,如果分组 n 丢失,那么该分组和分组 n + 1将被发送方根据GBN重传规则而重传。因此,接收方只需要丢弃分组 n + 1即可。这种方法的优点就是接受方特别简单,只需要维护下一个按序接收的分组的序号。



选择重传

  使用GBN协议的确解决了部分问题,但当其窗口长度和带宽时延都很大时,单个分组的差错就能引起GBN重传大量分组,许多分组根本没有必要重传。随着信道差错的增加,流水线可能会被这些不必要重传的分组所充斥。



   顾名思义,选择重传(SR)协议通过让发送方仅重传那些它怀疑接收方出错(即丢失或受损)的分组而避免了不必要的重传。下图显示了SR协议发送方和接收方看到的序号空间。

  这里有一个SR协议的交互式程序,可以去感受一下过程。



##### SR发送方的事件与动作

1. 从上层收到数据。当从上层收到数据后,SR发送方检查下一个可用于该分组的序号,如果位于发送窗口内,则将数据打包并发送;否则就像GBN一样,要么将数据缓存,要么拒绝并将其返回给上层。

2. 超时。定时器再次被用来防止丢失分组。但在SR中,每个分组都需要拥有自己的逻辑定时器

3. 收到ACK。如果收到ACK,倘若该分组序号在窗口内,则将那个被确认的分组标记为已接收。如果该分组的序号为send_base,则将窗口基序号向前移动到具有最小序号的未确认分组处。



SR接收方的事件与动作
  1. 序号在 [rcv_base, rcv_base + N - 1] 内的分组被正确接收。在此情况下,一个ACK将会送给发送方,如果该分组以前没接受过,则缓存该分组。如果该序号为 rcv_base,则该分组及以前缓存的序号连续的分组交付给上层。然后 rcv_base 向前移动到具有最小序号的未确认分组。

  2. 序号在 [rcv_base - N, rcv_base - 1] 内的分组被正确接收。在此情况下,必须产生一个ACK,即使是接收方以前已确认过的分组。如果分组 sendbase 的ACK没有从接收方传回发送方,那么发送方最终将因超时重传分组sendbase。显然接收方已经收到过这个分组,若果不确认该分组,则发送窗口永远不能向前移动。这说明了SR协议的一个重要方面:对于哪些分组已经被正确接收,哪些没有,发送方和接收方并不是总能看到相同的结果,对于SR协议而言,这意味着发送方和接收方的窗口并不总是一致。例如上图的序号空间。

  3. 其他情况,忽略该分组。



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



  由于SR协议的发送方和接收方窗口缺乏同步,当我们面对有限序号范围的现实时,会出现错误。考虑下面的例子。在情况a中,分组0是一个重传,在情况b中,分组0实际上是一次重传,而接收方把它当做一个新分组。因此这两种情况,接收方无法区分是一次重传还是一个新分组。





   为避免这种情况,我们希望避免接收方窗口的前缘(即序列号“最高”的那一个)环绕在序列号空间中并与后缘(发送者窗口中序列号“最低”的那一个)重叠。也就是说,序列号空间必须足够大,以适合整个接收方窗口和整个发送者窗口,而不存在这种重叠条件。所以我们需要确定在任何给定的时间,接收和发送窗口可以覆盖多大范围的序列号。



   由于SR发送方和接收方的窗口不会同步,那么我们可以假设最坏的一种情况,即上图中的 b):假设窗口为N,发送方一次性发送了N个分组,且接收方的ACK全部丢失,那么发送方的窗口比接收方的窗口慢N。假设接收窗口最低的序列号是 m,它的窗口是[m,m+N-1],发送方的窗口将是[m-N,m-1]。由于发送方无法收到这些N个 ACK,于是将重发这些窗口里的分组。发送方窗口的下边缘是m-N,而接收器窗口的前缘是m+N-1。因此,为了使接收者窗口的前缘不与发送者窗口的后缘重叠,序列号空间必须足够大以容纳2N个序列号。





分组的重排序问题

   到此为止,我们讨论的情况都是基于分组在发送方和接收方之间的信道中不会被重新排序。这在发送方与接收方由单段物理线路相连的情况下,通常是一个合理的假设。然而,当连接两端的信道是一个网络时,分组重新排序是可能会发生的。分组重新排序的一个表现就是:一个具有序号或确认号 x 的分组的旧副本可能会出现,即使发送方或接收方的窗口都没有包含 x 。



  对于分组重新排序,信道可被看成基本上是在缓存分组,并在将来任意时刻自然地释放这些分组。由于序号可以被重新使用,那么必须小心,以免出现这样的冗余分组。



   实际应用中采用的办法是,确保一个序号不被重新使用,直到发送方“确信”任何先去发送的序号为 x 的分组都不再网络中为止。通过假定一个分组在网络中的“存活”时间不会超过某个固定最大时间来做到这一点,这个值叫做MSL(maximum sequence lefttime)在高速网络的TCP扩展中,最长的分组寿命被假定为大约 3 分钟。



发布于: 2020 年 07 月 12 日 阅读数: 31
用户头像

烫烫烫个喵啊

关注

后端工程师 2019.03.20 加入

还未添加个人简介

评论

发布
暂无评论
【计算机网络】如何实现可靠数据传输?