首页 > 其他分享 >3.4 可靠数据传输原理

3.4 可靠数据传输原理

时间:2024-10-31 16:21:37浏览次数:4  
标签:重传 ACK 可靠 发送 3.4 分组 序号 数据传输 接收

以下全文为《计算机网络 自顶向下方法》(第8版) 3.4小节的总结。

rdt: reliable data transfer

udt: unreliable data transfer

下方有限状态机图片中横线上方表示事件event,下方表示操作action。

3.4.1 构造可靠数据传输协议

    1. 经完全可靠信道的可靠数据传输:rdt1.0

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

    3. 经具有比特差错的丢包信道的可靠数据传输:rdt3.0

3.4.2 流水线可靠数据传输协议

3.4.3 回退N步

3.4.4 选择重传

 

3.4.1 构造可靠数据传输协议

1. 经完全可靠信道的可靠数据传输:rdt1.0

因信道可靠,所以发送方只有一个状态:等待来自上层的调用。当发生rdt_send(data)事件时,即被上层调用时,将数据分组并发送。

同样地,接收方只有一个状态:等待来自下层的调用。当发生rdt_rcv(data)事件时,即被下层调用时,将数据提取出来,并传输给上层。

 

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

考虑底层信道会出现比特差错的情况,即传输过程中0变成1,1变成0这种错误。此时,接收方会给发送方发送一条确认信息。如果接收到的数据是正确的,则发送ACK,如果是错误的,则发送NAK。如果发送方接收到NAK,则重发这个数据。在计算机网络环境中,基于这样重传机制的可靠数据传输协议称为自动重传请求协议(Automatic Repeat reQuest, ARQ)。ARQ协议需要另外三种协议功能来处理存在比特差错的情况:差错检测、接收方反馈、重传。

如下图所示,此时发送方有两种状态:等待上层调用和等待ACK或者NAK。假设初始状态为等待上层调用。那么当发生rdt_send(data)事件时,发送方将数据分组,此时报文中还添加了检验和(checksum),然后将报文发送。然后发送方的状态转移到等待ACK或NAK。在这个状态下,如果发生rdt_rcv(rcvpkt)事件,并且rcvpkt中包含NAK,那么重新发送报文,并停留在该状态,直到接收到的rcvpkt中包含ACK,使得状态转移回等待上层调用。此时不进行任何操作,因此横线下方用Λ表示。

值得注意的是,当发送方处于等待ACK或NAK状态时,不接受来自上层的调用。因此rdt2.0被称为停等协议(stop-and-wait)。

 

此时,接收方还是只有一个状态:等待来自下层的调用。当发生rdt_rcv(data)事件,并且接收到的报文有差错,则发送NAK。如果接收到的报文没有差错,则提取数据并向上传输,以及发送ACK。

 

rdt2.0存在一个致命的缺陷:如果接收方发送给发送方的ACK或者NAK受损,怎么办呢?假设发送方接收到不明确的ACK的话也重传,那么对于接收方而言,它分不清接收到的数据是重传(它发送过ACK确认的)还是新的数据。

处理这个问题的一种简单方法是在数据分组中添加一个新字段,让发送方对其数据分组编号。将数据分组的序号也一起发送过去。通过序号,接收方就可以分得清数据是重传的还是新的。

对于停等协议,1bit序号就足够了。下图是rdt2.1发送方的状态机。因为加上了1bit序号,因此发送方有四种状态。假设等待来自上层调用0是初始状态,当rdt_send(data)事件发生时,将数据分组,并且此时除了检验和之外,还加入了序号0,然后发送报文。发送方状态转移到等待0的ACK或者NAK状态。在此状态下,当rdt_rcv(rcvpkt)事件发生,并且接收到的数据受损或者数据中包含NAK,则重传数据,并停留在该状态。如果接收到的数据没有受损并且其中包含ACK,则转移到等待来自上层调用1的状态。其余状态和事件同理。

 

下图是rdt2.1接收方的状态机。接收方有两种状态:等待下层调用0和等待下层调用1。以等待下层调用0为例,当rdt_rcv(rcvpkt)事件发生,并且rcvpkt没有受损以及rcvpkt中有序号0,那么提取数据,并传输给上层,给发送方返回ACK和检验和,接收方状态转移为等待下层调用1。

此外,在等待下层调用0状态时,当rdt_rcv(rcvpkt)事件发生,并且rcvpkt受损了,那么给发送方给回NCK和检验和,状态停留在这里。

当rdt_rcv(rcvpkt)事件发生,并且rcvpkt没有受损以及rcvpkt中有序号1,那么意味着不是接收方想要的数据,仍停留在这个状态,给发送方返回ACK和检验和。

 

从上面的分析可见,在rdt2.1中,序号和ACK/NAK其实是冗余的,只要有ACK和序号就够了,不需要有NAK。因此rdt2.2就把NAK去掉了。其发送方和接收方的状态机如下图所示。

 

3. 经具有比特差错的丢包信道的可靠数据传输:rdt3.0

除比特受损外,底层信道还会丢包。针对丢包问题,引入一个定时器。发送方做到:

  • 每次发送一个分组(包括第一次分组和重传分组)时,启动一个定时器;
  • 响应定时器中断;
  • 终止定时器。

rdt3.0的发送方的状态机如下图所示。与rdt2.2一样有四种状态。当处于等待上层调用0的状态时,发生rdt_send(data)事件,那么发送方将数据分组,加入序号0和检验和。然后将分组发送,并启动定时器。状态转移到等待ACK0。但是如果在等待上层调用0的状态时,发生rdt_rcv(rcvpkt)事件,则不进行任何操作,因为是停等协议。

当处于等待ACK0的状态时,发生rdt_rcv(rcvpkt)事件,并且rcvpkt有损坏或者其中包含序号1的ACK,则仍停留在这个状态,不进行任何操作。如果发生超时事件(timeout),则重传报文并重新启动定时器。但仍停留在该状态。如果发生rdt_rcv(rcvpkt)事件,并且报文没有损坏以及其中包含序号0的ACK,那么停止定时器,并转移到等待上层调用1的状态。

其他两个状态同理。

 

 rdt3.0的接收方的状态机与rdt2.2接收方的状态机相同。

 

3.4.2 流水线可靠数据传输协议

停等协议会严重降低信道的利用率,因为大部分时间发送方都处于等待ACK的状态。解决问题的方法是不以停等方式运行,允许发送方发送多个分组而无须等待确认。这种技术被称为流水线。流水线技术对可靠数据传输协议带来如下影响:

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

 

3.4.3 回退N步(GO BACK N, GBN)

关于GBN,可以先看两个动图。

 GBN1

 GBN2

 

可见,通过基序号(base)、下一个序号(nextseqnum)和窗口长度N,将发送方的缓存划分为四个部分,如下图所示。GBN也因为被称为滑动窗口协议。

GBN发送方的FSM状态图如下图所示。当上层调用rdt_send(data)时,发送方首先检查发送窗口是否已满:if(nextseqnum < base + N)。如果窗口已满,发送方只需将数据返回给上层,隐式地指示上层该窗口已满。如果窗口未满,则产生一个分组并将其发送,并相应地更新变量。

当收到一个ACK时,在GBN协议中,对序号为n的分组的确认采用累积确认的方式。表明接收方已正确接收到序号n及前面的所有分组了。如果收到一个ACK,但仍有已发送但未被确认的分组,则定时器被重新启动。如果没有已发送但未被确认的分组,则停止该定时器。

当发生超时事件,发送方重传所有已发送但还未被确认的分组。

GBN接收方的FSM状态图如下图所示。如果一个序号为n的分组被正确接收到,并且是按序接收的,则接收方为分组n发送一个ACK,并将该分组中的数据部分交付给上层。除此之外,接收方丢弃该分组,并为最近按序接收的分组重新发送ACK。此处值得注意的是,如果分组k被正确收到,意味着分组k前面的分组都已经被正确接收了。

 

3.4.4 选择重传(selective repeat, SR)

可先通过以下两个动图,对比着观察GBN的问题,以及SR的特点 

GBN

SR

可以发现,GBN会导致单个分组的差错引起重传大量分组,许多分组根本没必要重传。随着信道差错率的增加,流水线可能会被这些不必要重传的分组所充斥。而SR仅让发送方重传那些它怀疑在接收方出错的分组,从而避免了不必要的重传。

首先来看下SR接收方做了哪些改变,如下图所示。SR接收方将确认一个正确接收的分组而不管其是否有序。失序的分组将被缓存直到所有丢失分组(即序号更小的分组)皆被收到为止,这时才将一批分组按序交付给上层。

因此,接收方的事件与操作如下:

  • 当序号在[rcv_base, rcv_base+N-1]内的分组被正确接收时,一个选择ACK返回给发送方。如果该分组以前没有收到过,则缓存该分组。如果该分组的序号等于接收窗口的基序号,则该分组以及前面缓存的序号连续的分组交付给上层。
  • 当序号在[rcv_base-N, rcv_base-1]内的分组被正确接收时,一个选择ACK返回给发送方。
  • 除上述外的其他事件,都忽略该分组。

发送方的事件与操作如下:

  • 当从上层接收到数据时,检查下一个可用于该分组的序号。如果序号位于发送方的窗口内,则将数据打包并发送;否则将数据返回给上层或缓存起来。
  • 当发生超时事件时,现在每个分组都有其自己的定时器了,因此超时事件发生后,单独重传这个分组。
  • 当接收到ACK时,若该分组的序号在窗口内,则将这个分组标记为已接收。如果该分组的序号等于send_base,则窗口滑动到具有最小序号的未确认分组处,如果窗口移动后,窗口内有未发送的分组,则发送这些分组。

关于SR,值得注意的是,窗口长度必须小于或等于序号空间的一半。即如果窗口长度是N,序号空间是M,那么N<M/2,否则会发生接收方不知道发送方发送的是前一个序号K的分组,还是后一个序号K的分组。 

 

标签:重传,ACK,可靠,发送,3.4,分组,序号,数据传输,接收
From: https://www.cnblogs.com/larissa-0464/p/18501493

相关文章

  • 稳定可靠的 LED 灯恒流驱动控制芯片
    AP5103是一款效率高,稳定可靠的LED灯恒流驱动控制芯片,内置高精度比较器,固定关断时间控制电路,恒流驱动电路等,特别适合大功率LED恒流驱动。AP5103采用ESOP8封装,散热片内置接SW脚,通过调节外置电流检测的电阻值来设置流过LED灯的电流,支持外加电压线性调光,最大电流3.5A。......
  • 鸿蒙IME Kit高级开发:共享沙箱机制与输入法数据传输
    本文旨在深入探讨华为鸿蒙HarmonyOSNext系统(截止目前API12)的技术细节,基于实际开发实践进行总结。主要作为技术分享与交流载体,难免错漏,欢迎各位同仁提出宝贵意见和问题,以便共同进步。本文为原创内容,任何形式的转载必须注明出处及原作者。HarmonyOS的IMEKit不仅提供了基础......
  • 鸿蒙IME Kit高级开发:共享沙箱机制与输入法数据传输
    本文旨在深入探讨华为鸿蒙HarmonyOSNext系统(截止目前API12)的技术细节,基于实际开发实践进行总结。主要作为技术分享与交流载体,难免错漏,欢迎各位同仁提出宝贵意见和问题,以便共同进步。本文为原创内容,任何形式的转载必须注明出处及原作者。HarmonyOS的IMEKit不仅提供......
  • 论软件的可靠性设计
    一、正文在2020年10月,我公司主要服务于大型地产行业的数字化建设的软件服务商,某知名地产行业委托我公司构建一个成本测算系统。本项目由我负责项目的规划、设计及开发,并且担任架构师一职,主要完成项目的需求分析、架构设计、主导团队完成开发工作。该项目的背景是地产集团公司......
  • 使用不可靠来源的住宅代理的风险
    许多代理用户知道住宅代理的好处,但很少有人知道使用不可靠来源的住宅代理的风险。缺乏这方面的知识对于使用不可靠IP的人和拥有这些IP的人来说都是危险的。因此,我们将讨论透明代理来源的重要性以及使用不可靠代理的危险。这样,您就可以专注于您的项目,而不必担心使用不可靠......
  • 【数据资产化】数据资产入表——成本可靠计量
            在当今的商业环境中,数据的价值已经超越了传统的资产类别,成为企业竞争的关键资源。随着数据资产化的概念逐渐被接受和实践,企业如何对这些资产进行有效的计量和会计处理,成为了一个亟待解决的问题。特别是在资产确认的过程中,成本的可靠计量成为了一个核心条件,它直......
  • grpc的数据传输格式protobuf你了解吗?
    文章目录前言一、grpc为什么要选择protobuf?二、Varint编码2.1字节序2.2定长编码2.3变长编码2.4有符号数的编码三.EncodingTag例子解析字段嵌套的情况repeated字段注意四:Decoding参考资料总结前言本文档主要讲解protobuf中基础的编码规则。先整体描述protobuf数......
  • 如何评估Mechanize和Poltergeist爬虫的效率和可靠性?
    Mechanize和Poltergeist是Ruby语言中两个流行的爬虫库,它们各自有着独特的优势和应用场景。Mechanize轻量级且易于使用,而Poltergeist则能够处理JavaScript,使得爬取动态内容成为可能。然而,如何评估这些爬虫的效率和可靠性,成为了开发者们必须面对的问题。本文将探讨评估Mechan......
  • 半导体晶圆厂如何保持 可靠安全又高效的跨网文件交换?
    晶圆厂是半导体产业链最重要的一环,它位于半导体制造的中游,在这个过程中,IC设计公司将芯片设计正式进行投产,晶圆厂制造晶圆后,再应用于下游的汽车、手机、通信等不同行业。 半导体晶圆厂为了数据安全,通常会进行网络隔离,对于大型晶圆厂,网络隔离会非常细致,如晶圆厂会基于防火墙、网......
  • 13.4K+ Star!DeepFace:一个轻量级人脸识别和面部属性分析库
    DeepFace简介DeepFace[1]是一个用于Python的轻量级人脸识别和面部属性分析(年龄、性别、情绪和种族)库。DeepFace利用深度学习进行人脸识别和分析,它通过封装多种先进的人脸识别模型,提供了一个简单易用的接口。用户无需深入了解背后的复杂过程,只需通过简单的函数调用来实现......