一文带你看可靠数据传输协议RDT前后三个版本的原理关系以及有限状态机的解释

时间:2024-02-23 11:23:41

自学计算机网络系列,如果如果出现错误,还请给大佬指正。

写在前面:这里是小王成长日志,一名普通在校大学生,想成学习之余将自己的学习笔记分享出来,记录自己的成长轨迹,帮助可能需要的人,平时博客内容主要是一些系统的学习笔记,项目实战笔记,一些技术的探究和自己的一些思考。欢迎大家关注,你们的每一个评论点赞关注我都会仔仔细细去看的。有任何问题欢迎交流,我会尽我所能帮助大家的,共创CSDN美好环境。


0.引入

  • 可靠数据传输的问题并不仅仅在运输层出现,也会在链路层以及应用层出现,网络中会出现很多"一般性问题",但可靠数据传输在其中尤为重要。
  • 可靠数据传输提供的服务:数据可以通过一条可靠的信道进行传输 。 借助于可靠信道,传输数据比特就不会受到损坏(由 0 变为 1 ,或者相反)或丢失,而且所有数据都是按照其发送顺序迸行交付
  • 接下来贯穿我们讨论始终的一个假设是分组将以它们发送的次序进行交付,某些分组可能会丢失;这就是说,底层信道将不会对分组重排序 。
  • 定义明晰:
    有限状态机,(英语:Finite-state machine, FSM),又称有限状态自动机,简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。接下来我们会不断讨论实现可靠数据传输的发送方和接收方的有限状态机。

1. 经完全可靠信道的可靠数据传输: rdt 1.0

1.1) rdt1.0中的假设与两个有限状态机的图例

首先假设底层信道是完全可靠的,这种情况下的协议是非常简单的,直接上图

在这里插入图片描述

  • 上图显示了 rdt 1. 0 发送方和接收方的有限状态机( Finile- State Machine , FSM) 的定义 。
  • rdt 的发送端通过 rdt_send ( data) 事件接受来自较高层的数据,产生一个包含该数据的分组(经由 make_pkt( data) 动作) ,并将分组发送到信道中
  • 接收端, rdt通过 rdt_rcv( packet) 事件从底层信道接收一个分组,从分组中取出数据(经由 extract ( packet , data) 动作) ,并将数据上传给较高层(通过 deliver_data( data) 动作) 。

1.2) 总结

在这个简单的协议中,一个单元数据与一个分组没差别 。 而且,所有分组是从发送方流向接收方;有了完全可靠的信道,接收端就不需要提供任何反馈信息给发送方,因为不必担心出现差错!注意到我们也已经假定了接收方接收数据的速率能够与发送方发送数据的速率一样’快。因此,接收方没有必要请求发送方慢一点!

2. 经具有比特差错信道的可靠数据传输: rdt 2.0

2.1) rdt2.0中的假设

在rdt 2.0中,我们假设分组中的比特可能受损(这很正常,并且通常出现在网络的物理部件中),我们继续假定所有发送的分组(虽然可能受损)仍按其顺序被接收。

所以对于受损的分组,我们需要重传,这就是一个计算机网络环境中很重要的协议-自动重传请求(Automatic Repeal reQuest , ARQ)协议(基于重传机制的可靠数据传输协议)

与ARQ相配合一起处理比特差错我们还需要另外三种协议功能:

    1. 差错检测
      - 使接收方可以检测并可能纠正分组中的比特差错 。
      - 典型的差错检测和纠错技术有UDP的检验和。关于检验和部分可以在我另一篇博客的结尾处找到,介绍了计算方式以及出现的原因。
    1. 接收方反馈
      • 我们的rdt 2.0 协议将从接收方向发送方回送 ACK 与 NAK 分组 。 并且理论上这些分组只需要一个比特长;如用0表示 NAK ,用 l 表示 ACK。
    1. 重传
      • 接收方收到有差错的分组时,发送方将重传该分组文 。

rdt2.0中的两个有限状态机

在这里插入图片描述

发送端具有两个状态
  • 左边:当产生 rdt_send (data) 事件时,发送方将产生一个包含待发送数据的分组 (sndpkt) ,带有检验和,然后经由 udt_send( sndpkt) 操作发送该分组 。

  • 右边:发送方协议等待来自接收方的 ACK 或AK 分组 。

    • 如果收到一个 ACK 分组(图 中符号 rdt_rcv( rcvpkt) && IsACK( rcvpkt) 对应该事件) ,则发送方知道最近发送的分组已被正确接收,因此协议返回到等待来向上层的数据的状态 。
    • 如果收到一个 NAK 分组,该协议重传最后一个分组并等待战收方为响应重传分组而回送的 ACK 和 NAK 。
  • 我们需要注意到:发送端在等待ACK或者NAK回复分组时不能从上层获得更多的数据

接收端仍只具有一个状态
  • 当分组到达时,接收方要么回答一个 ACK ,要么回答一个 NAK ,这取决于收到的分组是再受损

    • 这会导致一个致命的缺陷- ACK或者NAK分组丢失!
  • ACK或者NAK分组丢失处理的方法

    • 可能的解决办法

      • 发送方发报询问

        • 又要一种新的分组
      • 增加足够的检验和比特,使发送方不仅可以检测差错,还可恢复差错 。

        • 对于会产生差错但不丢失分组的信道,这就可以直接解决问题 。
      • 在未接受或者ACK/NAK分组比特丢失的情况下,发送方直接重传当前数据分组

        • 造成冗余分组( duplicate packet)
        • 接收方不知道它上次所发送的 ACK 或 NAK是否被发送方正确地收到。因 此它无法事先知道接收到的分组是新的还是一次重传 !
    • 实际的解决办法

      • 为确认(ACK/NAK)分组中添加新的字段,对其进行编号,发送方(接收ACK/NAK)对序号进行检查即可
      • 因此我们就有了修订版的rdt2.1

rdt2.1中的两个有限状态机

在这里插入图片描述
在这里插入图片描述

发送方
  • 其状态数是2.0的两倍

    • 因为其需要反映出目前(由发送方)正发送的分组或(在接收方)希望接收的分组的序号是0还是1
    • 发送或期望接收 0 号分组的状态中的动作与发送或期望接收 l 号分组的状态中的动作是相似的;唯一的不同是序号处理的方法不同 。
  • 使用的是从接收方到发送方的肯定确认和否定确认

    • 对应序号的发送NAK或者以前序号的ACK(冗余ACK)能起到一样的作用
  • 与2.0的细微区别

    • 接收方必须包括由一个 ACK 报文所确认的分组序号(这可以通过在接收方 FSM 中,在 make_pkt()中包括参数 ACK 0 或 ACK 1来实现)
    • 发送方必须检查接收到的 ACK 报文中被确认的分组序号(这可通过在发送方 FSM 中,在 isACKO 中包括参数 0 或 1 来实现)。
  • rdt2.2发送方图例
    在这里插入图片描述

3 . 经具有比特差错的丢包信道的可靠数据传输: rdt 3. 0(比特交替协议)

rdt3.0中的假设

在3.0中我们不仅假设比特会受损,并且假设底层信道也会丢包(这很正常),所以3.0中我们必须解决检测以及处理丢包的情况
对于丢包情况的检测以及丢包后的动作我们做如下考虑:

  • 方法1: 等待一定时间未收到应收到的响应则重传该分组

    • 确实有效

    • 应该等待的时间应该至少是发送方与接收方之间的一个往返时延(可能会包括在中间路由器的缓冲时延)加上接收方处理一个分组所需的时间 。

    • 但这种等待一定时间就重传也可能发生问题:

      • 1.最坏情况下的最大时延是很难确定的,确定的因素很少
      • 2.可能需要等一段较长的时间
      • 3.产生冗余数据分组( duplicate data packeL)- 我们之前提到的的序号可以处理这一问题
  • 方法2:倒计数定时器(countdown timer)

    • 在一个给定的时间量过期后,可中断发送方 。
    • 因此,发送方需要能做到:
      • ①每次发送一个分组(包括第一次分组和重传分组)时,便启动一个定时器。
      • ②响应定时器中断(采取适当的动作) 。
      • ③终止定时器
    • 这也是rdt3.0中实际采用的"检测"丢包的方式,而我们处理丢包情况的措施,很明显就是重传。

rdt3.0中有限状态机的图例

在这里插入图片描述

rdt3.0中存在的问题

我们现在讨论的rdt协议仍然存在一个比较严重的问题,效率不够,即我们需要等到前一个报传完并且回复完状态确认接收才能传送下一个分组,这会造成很大的浪费,解决方法就是流水线!在这种模式中我们将会一次发送多个分组,在多个分组都被确认的情况下再发送接下来几个分组,具体细节敬请期待。

4.有关文章推荐:


没搞清运输层的UDP协议? -哎呀, 咋来这看就好了啊


一文带你看懂多路复用与多路分


都看到这里了,各位哥哥姐姐叔叔阿姨给小王点个赞 关个注 留个言吧,和小王一起成长吧,你们的关注是对我最大的支持。
有事没事进来看看吧 : 小王的博客目录索引


如果以上内容有任何不准确或遗漏之处,或者你有更好的意见,就在下面留个言让我知道吧-我会尽我所能来回答。