数据链路层课件

《数据链路层课件》由会员分享，可在线阅读，更多相关《数据链路层课件（42页珍藏版）》请在金锄头文库上搜索。

1、计算机网络 Computer Network,2019年4月20日,2,计算机网络,课程目录,第1章 概述 第2章 物理层与数据通信基础 第3章 数据链路层 第4章 局域网 第5章 网络层 第6章 网络互联技术 第7章 传输层 第8章 应用层 第9章 网络管理与信息安全 第10章 网络新技术专题,3,计算机网络,本章提纲,3.1 数据链路层的功能 3.2 差错检测和校正 3.3 数据链路层协议 3.4 协议描述与验证 3.5 数据链路层协议举例,第3章 数据链路层,4,计算机网络,3.1 数据链路层的功能,3.1.1 帧同步 3.1.2 差错控制 3.1.3 流量控制 3.1.4 链路管理,5

2、,计算机网络,3.1.1 帧同步,帧同步：能从比特流中区分出帧的起始与终止。 1、字节计数法 以一个特殊字符表征一帧的起始，并以一个专门字段来标明帧内的字节数。 2、使用字符填充的首尾定界符法 用一些特定的字符来定界一帧的起始与终止。 数据的透明性 3、使用比特填充的首尾定界符法 以一组特定的比特模式(如01111110)来标志一帧的起始与终止。 数据的透明性 4、违法编码法 借用违法编码序列来定界帧的起始与终止。,6,计算机网络,3.1.2 差错控制,通信系统必须具备发现(即检测)差错的能力，并采取措施纠正它，使差错控制在所能允许的尽可能小的范围内，这就是差错控制过程，也是数据链路层的主要功

3、能之一 。 反馈重发 计时器 帧序号,7,计算机网络,3.1.3 流量控制,流量控制并不是数据链路层特有的功能，许多高层协议中也提供流量控制功能，只不过流量控制的对象不同而已。 流量控制实际上是对发送方数据流量的控制，使其发送速率不超过接收方的接收速率。,8,计算机网络,3.1.4 链路管理,链路管理功能主要是用于面向连接的服务。 数据链路层连接的建立、维持和释放就称做链路管理。,9,计算机网络,3.2 差错检测和校正,3.2.1 传输差错的特性 3.2.2 奇偶校验 3.2.3 循环冗余校验 3.2.4 海明码,10,计算机网络,3.2.1 传输差错的特性,传输中的差错都是由于噪声引起的。噪

4、声有两大类：一类是信道所固有的、持续存在的随机热噪声；另一类是由于外界特定的短暂原因所造成的冲击噪声。 误码率 编码效率 差错控制的方式 ： 自动请求重发（Automatic ReQuest for Repeat，ARQ） 前向纠错(Forward Error Correction，FEC),11,计算机网络,3.2.2 奇偶校验(1/2),奇偶校验的特点： 奇偶校验码是一种通过增加冗余位使得码字中“1”的个数恒为奇数或偶数的编码方法,它是一种检错码。 偶校验:ri=I1iI2iIpi 奇校验: ri=I1iI2iIpi1 奇偶校验的分类： 垂直奇偶校验 编码效率 R=p/(p+1),12,计

5、算机网络,3.2.2 奇偶校验(2/2),水平奇偶校验 编码效率 R=q/(q+1) 水平垂直奇偶校验 编码效率 R=pq/(p+1)(q+1),13,计算机网络,3.2.3 循环冗余校验(1/3),它是一种检错码。 思想：任何一个由二进制数位串组成的代码都可以和一个只含0和1两个系数的多项式建立一一对应的关系。 k位信息位对应于一个k-1次多项式K(x)，r位冗余位对应于一个r-1次多项式R(x)，生成的n=k+r位码字则对应于一个n-1次多项式T(x)。 生成方法：发送方和接收方依据一事先约定的r次生成多项式G(x) （最高项xr和最低项的系数为1），用G(x)去除xrK(x)得到的余式就

6、是R(x)，即得冗余位。,14,计算机网络,3.2.3 循环冗余校验(2/3),示例 设信息位为1010001，即K(x)= x6+x4+1，取G(x)= x4+x2+x+1（对应的代码为10111），则x4 K(x)= x10+x8+x4（对应的代码为10100010000），则 所以冗余位为1101， R(x)= x3+x2+1。 T(X)= x4 K(x)+ R(x)= x10+x8+x4 + x3+x2+1 对应的发送代码为：10100011101,15,计算机网络,3.2.3 循环冗余校验(3/3),检测方法：用发送端发送时采用的生成多项式G(x)来除接收到的码字多项式，若余式不为0

7、，则传输有差错；否则，认为传输无差错。,16,计算机网络,3.2.4 海明码(1/3),也是一种可以纠正一位差错的编码。 对于奇偶校验码，若信息位为an-1an-2a1，加上一位偶校验位a0，在接收端校验时，可按关系式 S = an-1 an-2 a0来计算，若S=0，则无错；若S=1，则有错。上式称为监督关系式，S称为校正因子。 思想：增加冗余位，也相应地增加监督关系式和校正因子，就能表示更多的差错情况，包括具体定出是哪一位出错。 理论依据：当信息位为k位，增加r个冗余位，构成n=k+r位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同的位置的一位错，则要求：2rk

8、+r+1。,17,计算机网络,3.2.4 海明码(2/3),生成过程：（假设k=4，则r取3，信息位a6a5a4a3，冗余位a2a1a0） （1）构造监督关系式表 （2）写出监督关系式 由上表可知，a2 、a4 、a5 或a6的一位错都应使S2=1，所以 S2=a2 a4 a5 a6 同理 S1=a1 a3 a5 a6 S0=a0 a3 a4 a6,18,计算机网络,3.2.4 海明码(3/3),（3）求出冗余位关系式 令S0 、S1 和S2为0，即可求出a0 、a1和a2： a2 = a4 a5 a6 a1 = a3 a5 a6 a0 = a3 a4 a6 示例（P69 表3.2） 纠错（P

9、68 ） 特点： （1）编码效率为k/k+r （上例4/7 ）； （2）较容易实现，但只能纠正1位错。,19,计算机网络,3.3 数据链路层协议,3.3.1 基本链路控制协议 3.3.2 滑动窗口协议,20,计算机网络,3.3.1 基本链路控制协议(1/8),ARQ（Automatic Repeat Quest，自动重发请求，也称“循环自动请求”）协议是数据链路层最基本的协议。它是指在接收站接收到一个包含出错数据的信息（帧）时，自动发出一个重传错帧的请求。 ARQ的作用原则是对出错的数据帧自动重发，它有三种形式： 停等ARQ协议 连续ARQ协议 选择重传ARQ协议,21,计算机网络,3.3.1

10、 基本链路控制协议(2/8),1、理想情况下的主机通信： 完全理想化的数据传输要基于以下两个假定： 假定1链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。 假定2不管发送方以多快的速率发送数据，接收方总是来得及收下，并及时上交主机。 数据链路层不需要协议就可以保证数据传输的正确。,22,计算机网络,3.3.1 基本链路控制协议(3/8),2、停等ARQ协议： 工作原理 发送方发送一个数据帧后，必须停下来等待接收方的确认帧后才可以发送下一个数据帧；在接收方接收错误时，接收方则发一否认帧，要求发送方重发该帧；为防止发送的数据丢失，发送方内部设置一个定时器，当超过定时时间，而发送方仍未

11、收到确认帧时，发送方重发该帧；为防止确认帧丢失而造成发送方重发同一数据帧，发送方给每一个数据帧带上一个序列号。,23,计算机网络,3.3.1 基本链路控制协议(4/8),停等ARQ协议的缺点： 停等ARQ协议虽然保证了传输的安全可靠，但在传输过程中信道的吞吐量太低。,24,计算机网络,3.3.1 基本链路控制协议(5/8),3、连续ARQ协议： 工作原理 连续ARQ是连续发送若干数据帧，如果发送方接收到接收端发回的确认帧，则继续发送；发送方在每发完一个数据帧后，就启动内部超时定时器，在设置的超时时间内未收到确认帧，则重发相应的数据帧。 连续ARQ协议的工作示意图：,25,计算机网络,3.3.1

12、 基本链路控制协议(6/8),连续ARQ协议的缺点： 连续ARQ协议一方面因连续发送数据帧而提高了效率，但另一方面，在重传时又必须把原来已正确传送过的数据帧进行重传（但仅因这些数据帧之前有一个数据帧出了错），这样又使传送速率降低。由此可见，若传输信道的传输质量很差而误码率较大时，连续ARQ协议不一定优于停等ARQ协议。,26,计算机网络,3.3.1 基本链路控制协议(7/8),4、选择重传ARQ协议： 工作原理 当接收方发现某帧出错后，其后继续送来的正确帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以与

13、原来已存于缓冲区中的其余帧一并按正确的顺序递交高层。 选择重传ARQ协议的缺点： 选择重发减少了浪费，但要求接收方有足够大的缓冲区空间，这在许多情况下是不够经济的。正因如此，选择重传ARQ协议在目前就远没有连续重传ARQ协议使用得那么广泛。今后存储器芯片的价格会更加便宜，选择重传ARQ协议还是有可能受到更多的重视。,27,计算机网络,3.3.1 基本链路控制协议(8/8),选择重传ARQ协议的工作示意图： 以上三种重传方法各有利弊，停等ARQ协议最简单，但信道利用率最低；选择重传ARQ协议信道利用率最高，但它要求接收端的缓冲容量相当大；连续ARQ协议介于两者之间。在应用中应根据实际情况选择。,

14、28,计算机网络,1、XON/XOFF 在流量控制方面，可以从不同侧面采取不同的控制方案。最简单的方法就是增加接收端的缓冲存储空间，使得接收端可以缓存更多的数据。但这只是一种被动、消极的方法。因为，一方面系统不允许开设过大的缓冲空间；另一方面对于速率则显著失效，而且在传送大量数据的场合下，即使缓存空间再大也会出现不够的现象。 目前普遍采取一种称之为“XON/XOFF”的发送控制字符的方案，通过控制字符来确定发送方是否继续发送数据，相比之下更主动、更积极、更有效。,3.3.2 XON/XOFF方案和滑动窗口协议(1/4),29,计算机网络,XON/XOFF 的通信原理： XON/XOFF是一种异

15、步通信协议，接收设备或计算机使用特殊字符来控制发送设备或计算机传送的数据流。当接收计算机不能继续接收数据时，发送一个XOFF控制字符告诉发送方停止传送；当传输可以恢复时，该计算机发送一个XON字符来通知发送方。,3.3.2 XON/XOFF方案和滑动窗口协议(2/4),30,计算机网络,2、滑动窗口协议 滑动窗口协议属异步双工传输模式。 协议基本内容： 发送的信息帧都有一个序号，从0到某个最大值，02n1，一般用n个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小=上界-下界，大

16、小可变。发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1。 接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧。接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。,3.3.2 XON/XOFF方案和滑动窗口协议(3/4),31,计算机网络,3.3.2 XON/XOFF方案和滑动窗口协议(4/4),主要的滑动窗口协议 ： 1比特滑动窗口协议（停等协议） 退后n帧协议 选择重传协议 滑动窗口协议的工作原理示意图：,32,计算机网络,3.4 协议描述与验证,3.4.1 有限状态机模型 3.4.2 Petri网模型,33,计算机网络,3.4.1 有限状态机模型,有限状态机（Finite State Machine，FSM）是一种用来描述系统的常用方法。在这个模型中，系统被