【计算机网络】数据链路层(二):差错检测和纠正

2023-11-04

帧同步虽然可以区分每个数据帧的起始和结束,但是还没有解决数据正确传输的两方面问题:一、如果有帧出现了错误?二、如果有帧丢失了?这都是数据链路层确保向网络层提供可靠数据传输服务解决的问题,也就是数据链路层的差错控制功能。

要实现差错控制功能,就必须具备两种能力:一是具备发现差错的能力,二是具备纠正错误的能力。

一、差错检测

在数据链路层检测数据传输错误的方法一般是通过对差错编码进行校验来实现,常见的有奇偶校验码(PCC)和循环冗余校验(CRC)。PCC就不用多说了,在最后设置一个奇偶校验位。循环冗余校验是一种根据传输或保存的数据而产生固定位数校验码的方法,主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者储存之前计算出来并且附加到数据后面,然后接收端进行检验确定数据是否发生变化。


二、差错纠正

1、反馈检测法就是在接收端接收完一帧数据后,向发送端发送所接收到的完整数据帧,发送端在收到接收端发送的反馈信息后,通过对比保存在缓存中原来该帧的数据来判断接收端是否正确接收到了该数据帧,如果判断出了错,则发送端向接收端发送一个DEL字符及相应的帧信息,提示接收端删除对应的帧,然后重发该帧;否则表示接收端已正确接收了对应帧。但是如果传输过程中数据全部丢失的话,这种方法就无效了,因为接收端没有接收到这帧数据,自然也就不会向发送端发送反馈信息。为了解决这个问题,通常在数据发送时引入计时器来限定接收端发回反馈信息的时间间隔。当发送端发送一帧数据的同时启动计时器,若在限定时间间隔内没有收到接收端的反馈信息,即计时器超时,则可认为传输的对应帧出错,或丢失,继而发送端知道需要重发该帧,同时,为了避免同一帧数据可能被多次重复传送(计时器规定时间外到达),引发接收端多次收到同一帧并将其递交给网络层的危险,采用对发送的帧进行编号的方法,即同一个帧的编号是一样的,这样接收端便能从帧编号来区分是否是新来的帧。


2、空闲重发请求方案

可以看出,“反馈检测法”中一帧数据会在信道中至少往返传输两次,传输效率低,事实上一般并没有采用这种差错控制方法。而是采用一种称为“自动重发请求”的方法。其实现原理就是先让发送端将要发送的数据帧附加一定的校验码(PCC或CRC等)一起发送,接收端则根据检错码对数据帧进行错误检测,若发现错误,就返回请求重发的响应(不用返回全部的帧,一个信号即可),发送端收到请求重发的响应后,便重新发送该数据帧。

空闲重发请求方案又称停-等(stop andwait)法,该方案规定发送端每发送一帧后就要停下来,然后等待接收端发来的确认消息,仅当接收端确认ACK信息后才继续发送下一数据帧。如果收到的是否认(NACK)消息,表示接收端的数据有错,请求发送端重发,另外,计时器超时时,发送端也会重发对应的帧。

      

回退N帧策略的基本原理是:如果发送端一共发送了n个数据帧(编号从0,一直到n-1),但收到接收端发来的ACK确认帧中少了某一个或几个帧的ACK确认帧(数据帧丢失或ACK帧丢失,最终造成ACK确认帧不连续),亦或者是接收到某一帧时检测出有错,接收端发送一个NACK否认帧给发送端,或者计时器超时,则发送端可以判断接收端最后一个正确接收的帧编号,然后从缓存空间的重发表中重发所收到的最后一个ACK帧序号以后的所有帧。

打个简单的比方,就是小孩子数数,从1数到100 空闲重发请求差错控制方案的具体实现过程如下:

1)发送端每次仅将当前数据帧作为待确认帧保留在缓冲存储器中,当发送端开始发送数据帧时,随即启动计时器。

2)当接收端收到这个数据帧时,先利用帧中附带的检错码进行校验,确认无差错后,即向发送端返回一个确认消息,当检测到该帧有错误时,向发送端返回一个否认帧,同时丢弃该帧。

3)如果发送端在计时器中规定的时间内收到来自接收端的确认消息,即将计时器清零,清楚缓存中的待确认帧,然后才开始下一数据帧的发送,若发送端在规定时间内未收到来自接收端的确认消息(计时器超时),则重发存放于缓冲器中的待确认数据帧。

上面的实现可以通俗的解释为,一个小孩子学数数,从1到10,他一个一个数字的数,说一个,然后你点头说对,然后他又继续往下数。你的点头就是确认信号。没点头,就继续数该数的正确数字,直到你点头。


回顾上面的空闲重发请求差错控制方案。他每传送一个数据帧都要有一个等待时间(称为占空时间),信道的有效利用率低,占空时间与传送一个帧的全部时间的比例,称为占空比,数据帧越短,占空比越大,也就意味着信号的利用率越低,所以对于较短的数据帧传送,效率低下,而对于较长的数据帧,虽然信号利用率高了,但是出错的概率也越大,会出现多次重发,必须等待这一帧正确才传输下一帧,也会降低传输效率。


3、连续重发请求方案

连续重发请求方案是指发送端可以连续发送一系列数据帧(也不总是不断地发送,具体可以连续发送多少个帧,要视双方的缓存空间大小,即窗口大小而定),即不用等前一帧被确认便可继续发送下一帧,效率大大提高。同时,在这个连续发送的过程中也可以接受来自接收端的响应消息(确认帧或否认帧),发送端同样可以对传输出错的数据帧(否认帧或计时器超时的帧)进行重发。

连续重发请求方案有两种处理策略:回退N帧(GO-DACK-N)策略和选择重发(selective repeat)策略。

1、回退N帧策略,数到45时,跳过了几个数,直接数56,57,58……,然后你就要他从出错的那个数(本来是数46的)重新开始数,尽管后面的57,58……是正确的,但是还得再从出错的那个重新数数,这就是回退N帧策略的差错控制原理。

示意图:


结合上面示意图,分析下“回退N帧”策略中的数据处理流程

1)理想情形下的数据处理

也就是数据帧和确认帧都不发生差错或丢失的情形,数据帧传输一切顺利:

    1、发送端连续发送数据帧,而不等待任何数据帧的ACK帧返回,前面提到的“空闲重发请求方案”则需要等待数据帧的ACK帧返回,才能继续发送下一帧

    2、发送端在重发表中保存所发送的每个数据帧的备份(以防出错需要重发)

    3、接收端对每一个正确收到的数据帧返回一个ACK帧,ACK帧中包括对应帧的编号

    4、接收端保存一个接收(次序)表,包含最后正确收到的数据帧的编号(知道出错的是哪一帧)

    5、当发送端收到相应数据帧的ACK帧后,发送端即从重发表中删除该数据帧。

2)  存在帧差错情形下的数据处理

帧差错包括这样几种情形:数据帧在接收端检测出错,数据帧或响应帧在传输过程中出现丢失的差错。

1、  假设发送的第N+1个帧发生了差错,接收端要么检测出第N+1帧有错,要么发现没有接收到N+1帧,反而接收到了第N+2帧或第N+3帧,或后边其他帧;

2、  出现这种情况时,接收端立即返回一个相应的未正确接收的否认帧NACK(N+1),预示接收端最后正确收到的是第N帧(N+1帧的前一帧),同时对后面每个失序的数据帧,接收端都会产生相应的NACK帧,否则如果所发送的NACK(N+1)正好丢失或出错,将产生死锁,即发送端不停地发送新的帧,同时等待对第N+1帧的确认,而接收端不停地清除后继的帧,当然可以通过超时机制或者流量控制来避免死锁的发生。

3、发送端在收到NACK(N+1)帧,或者收到了NACK(N+2)、NACK(N+3)……帧时,从重发表中重发第N+1帧或者对应的NACK帧中序号所对应的帧,同时接收端清除所有失序的帧(从第N+2帧或者对应NACK帧中序号所对应的帧开始,直到重新正确接收到重发的第N+1或者对应NACK帧中序号所对应的帧)。换句话说只要出错的那帧没有正确的接收到重发的该帧,那么这中间接收的所有帧,即使都是正确的,接收端也都会清除,可以看出,这是个大大降低传输效率的地方。

4、接收端重新收到第N+1帧,或者对应的NACK帧中序号所对应的帧,接收端就继续操作。

通过上面的原理剖析,相比于空闲重发请求方案,回退N帧可以连续发送数据帧而提高传输效率,但是其出错在重发时必须把原来已正确传输过的数据帧再次发送,仅仅是因为这些正确数据帧前面的某个数据帧或确认帧发生了差错,这样无疑降低了传输效率。所以当通信链路的传输质量很差,误码率较大时,回退N帧策略就没什么优势了,因为这时可能要重传大量的数据帧。


2、选择重发策略

算法总是不断改进的,针对上面的弊端,后来提出了效率更高的连续重发请求差错控制策略——选择重发策略。这个主要是针对上面回退N帧差错控制策略作出的改进:当接收端发现某帧出错后,其后继发来的正确帧虽然不能立即递交给接收端的“网络层”,但接收端仍可接收下来,先存放在一个缓冲区中,同时通过向发送端发送NACK否认帧,要求发送端重发出错的那一帧,一旦收到重新发来的正确帧后,就可以与原来已存于缓冲区中的其余帧一起按正确的顺序递交给网络层。

选择重发策略规定,当发送端收到包含出错帧序号的NACK帧时,据此序号从重发表中选择出相应帧的备份,直接插入到发送帧队列的前面给予重发,因为重发表的帧重发是按FIFO的机制进行排列的,插在前面是为了最先重发,避免了对后继正确数据帧的多余重发,使得传输效率明显提高了。

示意图如下:


结合上面示意图,分析下“选择重发”策略中的数据处理流程

1)数据帧出现差错情形下的数据处理

当数据帧有差错(包括接收端检测到所接收的数据帧有差错,或者有数据帧丢失)时。

    1、发送端连续发送多个数据帧,接收端对每个已正确接受的数据帧返回一个ACK帧,假如第N+1个帧出现差错或丢失,如果检测到第N+1个帧有错误,则向发送端返回一个否认NACK(N+1)帧,如果一直到收到第N+2个数据帧时还没收到第N+1帧,则表明该帧已丢失,接收端不产生任何动作,对于已正确接收的数据帧,如第N帧,N+2帧……,仍会向发送端返回确认ACK帧。

    2、当发送端收到来自接收端的否认NACK帧(N+1)或收到第N+2帧的ACK帧时,会检测出其失序(因为按顺序,在收到ACK(N+2)帧之前应该是收到ACK(N+1)帧),得知第N+1帧没有被确认,将第N+2帧从重发表中清除,并在继续发送后继数据帧之前重发第N+1帧(FIFO机制)

可以看出,选择重发策略下只需发送有错的帧,而不会向回退N帧策略那样发送从有错帧开始后面所有的帧,显然减少了信号资源浪费,提高了传输效率,但要求发送端和接收端都有足够大缓冲区空间,以便存储多个帧的重发表(发送端的备份)和预提交数据帧(接收端准备递交给网络层)。速度和空间的矛盾性。

2)响应帧出现差错情形下的数据处理

在响应帧(包括确认ACK帧和否认NACK帧)出现差错时,也就是本应接收的是第N个帧的响应帧却接收到了第N+1个帧的响应帧情形下

    1、当发送端已接收到了第N-1个帧的ACK帧,接下来应该收到的是第N个帧的ACK帧,而偏偏收到的是第N+1个帧的ACK帧;

    2、发送端在收到ACK(N+1)帧后,检测出在重发表中第N个帧都还没收到ACK帧,因此认为第N个帧出现了差错(事实上并不是这样的,接收端已经收到,只是发送端,没有收到返回的ACK帧),重发第N帧;

   3、接收端在收到发送端重发的第N个帧,搜索接收表并确定第N个帧已被正确接收,因此认定这个重发的第N帧是重复的,于是删除这个重发的第N帧,并返回一个ACK(N)给发送端,以使发送端从重发表中删除第N帧,这样就达到了响应帧出现差错时的错误纠正。


流量控制

流量控制包含两方面的含义:一是发送端的数据发送速度与接收端的数据接收速度要匹配,否则接收端来不及接收就会造成数据在传输过程中的丢失,就是计算机系统中CPU寄存器,内存等之间数据传输速度控制协调一样。二是发送端的数据发送速度要与线路上的承载速率(与线路信道带宽有关)相匹配,否则也会造成数据在传输过程中的丢失,河流决堤就是这个道理。

对于数据链路层来说控制的是相邻两节点之间数据链路上的流量。

在数据通信中,由于通信双方各自使用的设备工作速率和缓冲存储的空间的差异,可能会出现发送端发送能力大于接收端接受能力的现象,如不加以控制,势必会造成帧的丢失。在数据链路层上的“流量控制”功能实际上是对发送端数据传输速率的控制,使其数据发送速率不超过接收端所能承受的数据接收能力。考虑到接收端还需要对来自物理层的比特流进行一系列的处理,如帧封装,向发送端发送返回确认帧等,所以通常是要使发送端的发送速率略小于接收端的数据处理能力。

在数据链路层中进行流量控制的方案有两种:一是基于反馈的流量控制方案,二是基于速率的流量控制方案。

1、基于反馈的流量控制方案

即接收端在接收到一个数据帧后,要向发送端发送一个确认帧,表示发送端可以继续向他发送数据了。就是发送端在发送一帧数据后必须等待接收端返回确认响应消息,然后才能发送下一帧数据。接收端是通过检查帧的校验序列(FCS),无错则发送确认帧,否则不发送返回消息,表示该帧已出错,要求重发。

根据上面,如果数据帧或确认帧丢失时,双方会无休止的等待,解决这一问题的方法就是发送后使用定时器,和前面提到的差错控制方案一样。

2、基于速率的流量控制方案

“基于速率的流量控制方案”是基于窗口滑动机制的速率控制方案,它规定发送端一次可以发送多少个数据帧,限制了发送端的数据传输速率,而无须接收端发回确认帧。

可以看出,事实上一些差错控制方案本身就具有一定的流量控制功能,如前面介绍的空闲重发请求方案。


“滑动窗口机制”中的“窗口”是指发送端和接收端的缓存空间大小,“滑动”的意思是指缓存空间中存放的未处理帧数是变化的,发送端在收到确认帧后会删除原来保存在缓存中的待重发帧,而接收端向网络层提交一个帧后也会删除原来保存在缓存中的帧。


参考资料:

《深入理解计算机网络》

《TCP/IP.协议一》               



本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

【计算机网络】数据链路层(二):差错检测和纠正 的相关文章

  • iOS证书添加设备UDID,运行自定义基座(图文)

    登录苹果开发者账户 Apple Developer 进入账户 进入第二项证书设置 选择设备设置 点击添加新设备 在这里填写设备信息 注册新设备 在这里查看自己的证书 点击对应证书 进入证书页面 点击右边蓝色编辑按钮 选择对应设备 注册的新设

随机推荐

  • ubuntu下使用yocto制作龙芯文件系统

    一 下载yocto代码 poky下载得到poky openembedded配方下载得到meta openembedded目录 MIPS架构配方下载得到meta img目录 git clone git git yoctoproject org
  • 第97天学习打卡(Spring Boot 初识Spring Boot)

    微服务阶段 javase OOP mysql 持久化 html css js jquery 框架 视图 框架不熟练 css不好 javaweb 独立开发MVC三层架构的网站 原始 ssm 框架 简化了我们的开发流程 配置也开始较为复杂 wa
  • Java中if-else和switch-case

    计算机的任何简单或复杂的程序都可以由三种基本结构组成 顺序结构 按照程序编写的顺序 从上到下依次执行 选择结构 根据某个条件进行判断后 选择其中一个分支执行 循环结构 反复执行某个或某些操作 直到条件为假时才停止循环 条件判断结构 1 if
  • CSS命名规范——BEM思想(非常赞的规范)

    人们问我最多的问题之一是在CSS类名中 和 是什么意思 它们的出现是源于BEM和Nicolas Gallagher BEM的意思就是块 block 元素 element 修饰符 modifier 是由Yandex团队提出的一种前端命名方法论
  • 软件研发过程中的5种最常见的图

    一 背景 软件研发过程中 我们常有如下的困惑 有时我们需要设计一个较大型的业务系统 或者做一个开源项目 我们该如何将这个系统的整体功能 逻辑细节一层层描述清楚呢 我们接手了一个大型复杂的系统 该如何一点点从宏观到微观的去梳理整个功能流转的脉
  • Apache APISIX Dashboard 任意命令执行批量编写工具

    Apache APISIX Dashboard远程命令执行漏洞 CVE 2021 45232 漏洞描述 Apache APISIX 是一个动态 实时 高性能的 API 网关 提供负载均衡 动态上游 灰度发布 服务熔断 身份认证 可观测性等丰
  • Verilog 层次化文件设计——彩灯控制器

    Verilog 层次化文件设计是通过顶层文件 调用的子模块来完成代码功能的实现 这里的顶层文件可以理解为是实体电路中的连线步骤 而子模块就是电路元件 本文采用文本形式编写顶层文件 设置顶层文件先打开文件界面显示所有文件 再选择你要设置为顶层
  • 第四十章、PyQt显示部件:QGraphicsView图形视图和QGraphicsScene图形场景简介及应用案例

    专栏 Python基础教程目录 专栏 使用PyQt开发图形界面Python应用 专栏 PyQt入门学习 老猿Python博文目录 老猿学5G博文目录 一 概述 Designer中的Graphics View部件是个图形视图部件 对应类为QG
  • 使用Tor遇到的错误

    Tor 在启动期间退出 这可能是您的 torrc 文件存在错误 Tor 或系统其他程序存在问题 或者硬件问题 在您解决此问题并重新启动 Tor 前 Tor 浏览器将不会启动 答 Windows安装Tor后 会在桌面留下文件夹 Tor 删除后
  • 金士顿 DT101 G2 8GU盘量产全过程图解(群联篇)(2)

    首先用芯片无忧或群联量产工具版本选择查看器 APExample getinfo 读出U盘的 MP ver 固件版本 固件日期 版本 控制芯片制造商是群联 芯片型号为ps2250 以便正确选择使用的量产工具 如下图1 这是从群联量产工具版本选
  • CVE-2021-41773漏洞复现

    1 安装debian系统 首先我选择的系统是debian10版本 也可以在别的系统完成复现 我想一个纯净版 所有重新安装了一个系统 安装步骤简单展示一下 1 创建虚拟机 点击下一步 导入镜像 自己选安装的位置以及虚拟机的名称 安装过程需要设
  • sql语句合集大全(个人总结)

    查找emp表 select from emp 查找emp表的sal select a SAL from emp a 查找emp表的ename select a ename from emp a emp表的sal 10 select a SA
  • 六大设计原则--迪米特法则【Low Of Demeter】

    声明 本文内容是从网络书籍整理而来 并非原创 定义 迪米特法则也叫做最少知识原则 Least Knowledge Principle 指一个对象应该对其他对象有最少的了解 通俗的讲 一个类对自己需要耦合或者调用的类应该知道的最少 你类内部是
  • idea打包springboot项目并部署至服务器

    idea打包springboot项目并部署至服务器 Step1 如果项目没有webapp或web目录 Step2 将springboot导成jar包 Step3 将springboot部署至云服务器 Step1 如果项目没有webapp或w
  • GCP: AppEngine(GAE)的使用

    一 基本概念 在全托管式的无服务器平台上构建可扩缩性极强的应用 将应用从零无缝扩容到全球级规模 而不用费心管理底层基础架构 得益于零服务器管理和零配置部署 开发者可以专注于构建出色的应用 省去管理开销 App Engine 支持多种主流开发
  • 使用ab进行并发压测SSL read failed (5) - closing connection错误

    最近在进行并发压测 在c参数特别大的时候 测试过程中出现SSL read failed 5 closing connection错误 研究好久没有找到瓶颈 但在换了一台测试服务器后 这个问题没有出现 所以基本可以确定是测试服务器产生的瓶颈
  • Java中整型数据的进制书写

    问题描述 我觉得这是一个比较有趣的事情 我觉得大多数初学者在编程过程中都不会在源代码里用除了十进制的其它进制写常量 但是当我在做leetcode的 回文数字 一题时 写了个测试样例 以为int 0343可以被识别为343 从而被识别成回文数
  • combo 添加listeners,使用 initComponent、constructor 的区别

    LocationCombo Ext extend Ext form ComboBox initComponent function var config name loactionCombo hiddenName loactionCombo
  • Unity 使用Final IK实现拟真调整物体IK动画

    文章目录 IK部分 需求 何为IK 参考资料 Final IK概述 手部IK效果 IK交互 拿取与双手调整效果 演示视频 IK部分 需求 NPC拿起物体 指定转向放到指定位置 要求动作尽可能自然 贴近真实 何为IK 谈IK之前先讲一下正向运
  • 【计算机网络】数据链路层(二):差错检测和纠正

    帧同步虽然可以区分每个数据帧的起始和结束 但是还没有解决数据正确传输的两方面问题 一 如果有帧出现了错误 二 如果有帧丢失了 这都是数据链路层确保向网络层提供可靠数据传输服务解决的问题 也就是数据链路层的差错控制功能 要实现差错控制功能 就