计算机网络课件第3章 数据链路层

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

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

2、计算机网络-刘桂江3.1.1 帧同步 帧同步：能从比特流中区分出帧的起始与终止。1、字节计数法 以一个特殊字符表征一帧的起始，并以一个专门字段来标明帧内的字节数。2、使用字符填充的首尾定界符法 用一些特定的字符来定界一帧的起始与终止。 数据的透明性C countdata特殊字符特殊字符定义数据部定义数据部分的字节数分的字节数1帧帧 1帧帧CdataC特殊字符特殊字符CD转义字符转义字符6/41计算机网络-刘桂江3.1.1 帧同步 3、使用比特填充的首尾定界符法 以一组特定的比特模式(如01111110)来标志一帧的起始与终止。数据的透明性4、违法编码法 借用违法编码序列来定界帧的起始与终止。例

3、: 在物理层，若用曼彻斯特编码时，高低表示”1”,低高表示”0” ，则可用高高或低低表示起止。 01111110data01111110011111101帧帧0111110100100110107/41计算机网络-刘桂江3.1.2 差错控制通信系统必须具备发现(即检测)差错的能力，并采取措施纠正它，使差错控制在所能允许的尽可能小的范围内，这就是差错控制过程，也是数据链路层的主要功能之一 。反馈重发计时器帧序号ABdataack防止死等待防止死等待防止重复帧多次被接防止重复帧多次被接收方交给它的上一层收方交给它的上一层8/41计算机网络-刘桂江3.1.3 流量控制 流量控制就是对发送方发送数据的

4、流量进行控制，使其发送速率不超过接收方的接收速率。 流量控制并不是数据链路层特有的功能，许多高层协议中也提供流量控制功能，只不过流量控制的对象不同而已。9/41计算机网络-刘桂江3.1.4 链路管理 数据链路层连接的建立、维持和释放就称做链路管理。 链路管理功能主要是用于面向连接的服务。10/41计算机网络-刘桂江3.2 差错检测和校正 3.2.1 传输差错的特性 3.2.2 奇偶校验 3.2.3 循环冗余校验 3.2.4 海明码 11/41计算机网络-刘桂江3.2.1 传输差错的特性传输中的差错都是由于噪声引起的。噪声有两大类：一类是信道所固有的、持续存在的随机热噪声；另一类是由于外界特定的

5、短暂原因所造成的冲击噪声。误码率编码效率检错码和纠错码差错控制的方式 ：自动请求重发（ARQ） 前向纠错(FEC) 12/41计算机网络-刘桂江3.2.2 奇偶校验(1/2)奇偶校验的特点：奇偶校验码是一种通过增加冗余位使得码字中“1”的个数恒为奇数或偶数的编码方法,它是一种检错码。偶校验: r=I1I2Ip奇校验: r=I1I2Ip1奇偶校验的分类：垂直奇偶校验 编码效率 R=p/(p+1) r1 r2 rq r1 r2 rq 冗余位冗余位 13/41计算机网络-刘桂江3.2.2 奇偶校验(2/2)水平奇偶校验 编码效率 R=q/(q+1) 水平垂直奇偶校验编码效率 R=pq/(p+1)(q

6、+1)14/41计算机网络-刘桂江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)得到的余式就是R(x)，即得冗余位。15/41计算机网络-刘桂江3.2.3 循环冗余校验(2/3)示 例 设 信 息 位 为1010001，即K(x)

7、= x6+x4+1，取G(x)= x4+x2+x+1（对应的代码为10111），则x4 K(x)= x10+x8+x4（所以冗余位为1101， R(x)= x3+x2+1。 T(X)=x4K(x)+R(x)= x10+x8+x4 + x3+x2+1 16/41计算机网络-刘桂江3.2.3 循环冗余校验(3/3)检测方法：接收端用接收到的码字多项式除以生成多项式G(x)，若余式不为0，则传输有差错；否则，认为传输无差错。17/41计算机网络-刘桂江3.2.4 海明码(1/4)是一种可以纠正一位差错的编码。对于奇偶校验码，若信息位为an-1an-2a1，加上一位偶校验位a0，在接收端校验时，可按关

8、系式 S = an-1 an-2 a0来计算，若S=0，则无错；若S=1，则有错。上式称为监督关系式，S称为校正因子。思想：增加冗余位，也相应地增加监督关系式和校正因子，就能表示更多的差错情况，包括具体定出是哪一位出错。Richard W Hamming 18/41计算机网络-刘桂江3.2.4 海明码(2/4)理论依据：当信息位为k位，增加r个冗余位，构成n=k+r位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同的位置的一位错，则要求：2rk+r+1。生成过程：（假设k=4，则r取3，信息位a6a5a4a3，冗余位a2a1a0）（1）构造监督关系式表S2S1S000

9、0001010100011101110111错码位置错码位置无错无错a0错错a1错错a2错错a3错错a4错错a5错错a6错错19/41计算机网络-刘桂江3.2.4 海明码(3/4)（2）写出监督关系式由上表可知，a2 、a4 、a5 或a6的一位错都应使S2=1， 所以令 S2=a2 a4 a5 a6 同理 S1=a1 a3 a5 a6 S0=a0 a3 a4 a6（3）求出冗余位关系式令S0 、S1 和S2为0，即可求出a0 、a1和a2： a2 = a4 a5 a6 a1 = a3 a5 a6 a0 = a3 a4 a6 示例（P69 表3.2）20/41计算机网络-刘桂江3.2.4 海明

10、码(4/4)纠错 在接收端收到每个码字后,按监督关系式算出校正因子,若它们全为“0”,则认为无错;若不全为“0”,在一位错的情况下,可查监督关系式表来判定是哪一位错,从而纠正之。（示例 P68 ）特点：（1）编码效率为k/k+r （上例4/7 ）；（2）较容易实现，但只能纠正1位错。21/41计算机网络-刘桂江3.3 数据链路层协议 3.3.1 基本链路控制协议 3.3.2 滑动窗口协议 22/41计算机网络-刘桂江3.3.1 基本链路控制协议(1/7) ARQ（自动重发请求）协议是数据链路层最基本的协议。它是指在接收站接收到包含出错数据的信息（帧）时，自动发出重传错帧的请求。ARQ的作用原则

11、是对出错的数据帧自动重发，它有三种形式：停等ARQ协议连续ARQ协议选择重传ARQ协议 23/41计算机网络-刘桂江3.3.1 基本链路控制协议(2/7) 1、停等ARQ协议：工作原理发送方发送一个数据帧后，必须停下来等待接收方的确认帧后才可以发送下一个数据帧；在接收方接收错误时，接收方则发一否认帧，要求发送方重发该帧；为防止发送的数据丢失，发送方内部设置一个定时器，当超过定时时间，而发送方仍未收到确认帧时，发送方重发该帧；为防止确认帧丢失而造成接收方接收并递交重复帧，要求发送方给每一个数据帧带上一个序列号。24/41计算机网络-刘桂江3.3.1 基本链路控制协议(3/7) 停等ARQ协议的缺

12、点：停等ARQ协议虽然保证了传输的安全可靠，但在传输过程中信道的利用率太低。25/41计算机网络-刘桂江3.3.1 基本链路控制协议(4/7) 2、连续ARQ协议：工作原理连续ARQ是连续发送若干数据帧，如果发送方接收到接收端发回的确认帧，则继续发送；发送方在每发完一个数据帧后，就启动内部计时器，在设置的超时时间内未收到该帧的确认帧，则重发该数据帧及其后的N帧，故又称为回退N协议。26/41计算机网络-刘桂江3.3.1 基本链路控制协议(5/7) 连续ARQ协议的缺点：连续ARQ协议一方面因连续发送数据帧而提高了效率，但另一方面，在重传时又必须把原来已正确传送过的数据帧进行重传（但仅因这些数据

13、帧之前有一个数据帧出了错），这样又使传送速率降低。由此可见，若传输信道的传输质量很差而误码率较大时，连续ARQ协议不一定优于停等ARQ协议。27/41计算机网络-刘桂江3.3.1 基本链路控制协议(6/7) 3、选择重传ARQ协议：工作原理当接收方发现某帧出错后，其后继续送来的正确帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以与原来已存于缓冲区中的其余帧一并按正确的顺序递交高层。 28/41计算机网络-刘桂江3.3.1 基本链路控制协议(7/7) 选择重传ARQ协议的缺点：选择重传减少了浪费，但要求接

14、收方有足够大的缓冲区空间，这在许多情况下是不够经济的。以上三种协议各有利弊，停等ARQ协议最简单，但信道利用率最低；选择重传ARQ协议信道利用率最高，但它要求接收端的缓冲容量相当大；连续ARQ协议介于两者之间。29/41计算机网络-刘桂江发送的信息帧都有一个序号，从0到某个最大值，02n1，一般用n个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小=上界-下界，大小可变。发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1。接收端有一个接收窗口，大小固定，

15、但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的序号最小的帧。接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。 3.3.2 滑动窗口协议(1/2) 30/41计算机网络-刘桂江3.3.2 滑动窗口协议(2/2) 主要的滑动窗口协议 ：停等协议 回退n协议 选择重传协议 滑动窗口协议的工作原理示意图：协议协议发送窗口发送窗口接收窗口接收窗口停等协议停等协议11回退回退n协议协议11选择重传协议选择重传协议1131/41计算机网络-刘桂江3.4 协议描述与验证 3.4.1 有

16、限状态机模型 3.4.2 Petri网模型 32/41计算机网络-刘桂江3.4.1 有限状态机模型 有限状态机（Finite State Machine，FSM）是一种用来描述系统的常用方法。在这个模型中，系统被描述成有限的状态，在一定的前提条件下会发生一系列的输入事件，这些事件使得系统采取相应的动作，并从一个状态转换成另一个状态，称为状态的变迁或转换（Transition）。33/41计算机网络-刘桂江3.4.2 Petri网模型 Petri网是由德国学者首先提出的一种描述方法,它本质上也是一种有限状态机模型。 Petri网的描述中有四种基本元素 ：位置(Place)位置是一圆圈，表示可能进

17、入的状态 标记(Token)位置中的小圆黑点，某个位置中有标记就表示已处于该状态 变迁(Transition)用一根直线段来表示,指明了该变迁发生的条件 带箭头的弧线(Arc)用弧线来表示,指明变迁产生的条件和变迁产生的结果 34/41计算机网络-刘桂江3.5 数据链路层协议举例 3.5.1 数据链路层协议的分类 3.5.2 HDLC 3.5.3 SLIP和PPP 35/41计算机网络-刘桂江3.5.1 数据链路层协议的分类链路控制协议的分类：异步协议 以字符为独立的信息传输单位，在每个字符的起始处开始对字符内的比特实现同步，但字符与字符之间的间隔时间是不固定的(即字符之间是异步的)。 同步协

18、议以帧为传输单位，在帧的起始处同步，使帧内维持固定的时钟。 同步协议的分类： 面向字符的同步协议 面向比特的同步协议面向字节计数的同步协议36/41计算机网络-刘桂江3.5.2 HDLC (1/2) 1、HDLC的操作方式：所谓操作方式，通俗地讲就是某站点是以主站点方式操作还是以从站方式操作，或者是二者兼备。 HDLC操作方式的类型：正常响应方式这是一非平衡数据链路方式，有时也称非平衡正常响应方式，传输过程由主站启动。 异步响应方式这也是一种非平衡数据链路操作方式，传输过程由从站启动。 异步平衡方式这是一种允许任何节点来启动传输的操作方式。37/41计算机网络-刘桂江3.5.2 HDLC (2

19、/2) 2、HDLC的帧格式 ：3、HDLC的帧类型 ：信息帧(I帧)信息帧用于传送有效信息或数据。 监控帧(S帧)监控帧用于差错控制和流量控制。 无编号帧(U帧)无编号帧因其控制字段中不包含编号N(S)和N(R)而得名。U帧用于提供对链路的建立、拆除以及多种控制功能。 38/41计算机网络-刘桂江3.5.3 SLIP和PPP (1/4) 1、SLIP协议：串行线路网际协议SLIP用于运行TCP/IP协议的面向字符的点对点串行连接，早在1984年就已经开始使用。 SLIP通常专门用于路由器和路由器之间的串行连接，有时候也用于家庭主机和ISP的路由器之间的拨号连接，使用的线路速率一般介于1200

20、bit/s和之间。主要用于低速的交互性业务。 39/41计算机网络-刘桂江3.5.3 SLIP和PPP (2/4) SLIP协议的缺点：SLIP没有差错检测的功能。 通信的每一方必须事先知道对方的IP地址，这对拨号入网的用户是很不方便的。 SLIP仅支持IP，而不支持其他的协议。 SLIP并未成为Internet的标准协议。因此目前存在着多种互不兼容的版本，影响了不同网络的互联。 40/41计算机网络-刘桂江3.5.3 SLIP和PPP (3/4) 2、PPP协议PPP协议的三个组成部分：一个将IP数据报封装到串行链路的方法。一个用来建立、配置和测试数据链路连接的链路控制协议LCP（Link Control Protocol），通信的双方可协商一些选项。一套网络控制协议NCP（Network Control Protocol），支持不同的网络层协议，如IP、IPX 。 41/41计算机网络-刘桂江3.5.3 SLIP和PPP (4/4) PPP协议的帧格式：PPP协议的特点：PPP协议是面向字符型的，所以它不能采用HDLC所使用的零比特插入法，而是使用一种特殊的字符填充。 PPP不使用序号和确认，因此，PPP不提供可靠传输的服务。