数据链路层课件

计算机网络

ComputerNetwork2023年1月2日计算机网络

ComputerNetwork2022年12课程目录第1章 概述第2章 物理层与数据通信基础第3章 数据链路层第4章 局域网第5章 网络层第6章 网络互联技术第7章 传输层第8章 应用层第9章 网络管理与信息安全第10章 网络新技术专题2计算机网络课程目录第1章 概述2计算机网络本章提纲3.1 数据链路层的功能3.2 差错检测和校正3.3 数据链路层协议3.4 协议描述与验证3.5 数据链路层协议举例第3章 数据链路层3计算机网络本章提纲3.1 数据链路层的功能第3章 数据链路层3计算3.1 数据链路层的功能

3.1.1帧同步3.1.2差错控制3.1.3流量控制3.1.4链路管理4计算机网络3.1 数据链路层的功能3.1.1帧同步4计算机网络3.1.1帧同步

帧同步：能从比特流中区分出帧的起始与终止。1、字节计数法以一个特殊字符表征一帧的起始，并以一个专门字段来标明帧内的字节数。2、使用字符填充的首尾定界符法用一些特定的字符来定界一帧的起始与终止。

数据的透明性3、使用比特填充的首尾定界符法以一组特定的比特模式(如01111110)来标志一帧的起始与终止。数据的透明性4、违法编码法借用违法编码序列来定界帧的起始与终止。

5计算机网络3.1.1帧同步帧同步：能从比特流中区分出帧的起始与终止3.1.2差错控制通信系统必须具备发现(即检测)差错的能力，并采取措施纠正它，使差错控制在所能允许的尽可能小的范围内，这就是差错控制过程，也是数据链路层的主要功能之一。反馈重发计时器帧序号6计算机网络3.1.2差错控制通信系统必须具备发现(即检测)差错的能3.1.3流量控制流量控制并不是数据链路层特有的功能，许多高层协议中也提供流量控制功能，只不过流量控制的对象不同而已。流量控制实际上是对发送方数据流量的控制，使其发送速率不超过接收方的接收速率。7计算机网络3.1.3流量控制流量控制并不是数据链路层特有的功能，3.1.4链路管理

链路管理功能主要是用于面向连接的服务。数据链路层连接的建立、维持和释放就称做链路管理。8计算机网络3.1.4链路管理链路管理功能主要是用于面向连接的服务。3.2 差错检测和校正

3.2.1传输差错的特性3.2.2奇偶校验3.2.3循环冗余校验3.2.4海明码9计算机网络3.2 差错检测和校正3.2.1传输差错的特性9计算机3.2.1传输差错的特性传输中的差错都是由于噪声引起的。噪声有两大类：一类是信道所固有的、持续存在的随机热噪声；另一类是由于外界特定的短暂原因所造成的冲击噪声。误码率编码效率差错控制的方式：自动请求重发（AutomaticReQuestforRepeat，ARQ）前向纠错(ForwardErrorCorrection，FEC)10计算机网络3.2.1传输差错的特性传输中的差错都是由于噪声引起的。噪3.2.2奇偶校验(1/2)奇偶校验的特点：奇偶校验码是一种通过增加冗余位使得码字中“1”的个数恒为奇数或偶数的编码方法,它是一种检错码。偶校验:ri=I1i⊕I2i⊕…⊕Ipi奇校验:ri=I1i⊕I2i⊕…⊕Ipi⊕1奇偶校验的分类：垂直奇偶校验

编码效率R=p/(p+1)

11计算机网络3.2.2奇偶校验(1/2)奇偶校验的特点：11计算机网络3.2.2奇偶校验(2/2)水平奇偶校验编码效率R=q/(q+1)

水平垂直奇偶校验编码效率R=pq/(p+1)(q+1)12计算机网络3.2.2奇偶校验(2/2)水平奇偶校验12计算机网络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)，即得冗余位。13计算机网络3.2.3循环冗余校验(1/3)它是一种检错码。13计算机3.2.3循环冗余校验(2/3)示例设信息位为1010001，即K(x)=x6+x4+1，取G(x)=x4+x2+x+1（对应的代码为10111），则x4K(x)=x10+x8+x4（对应的代码为10100010000），则所以冗余位为1101，

R(x)=x3+x2+1。T(X)=x4K(x)+R(x)=x10+x8+x4+

x3+x2+1

对应的发送代码为：1010001110114计算机网络3.2.3循环冗余校验(2/3)示例设信息位为101003.2.3循环冗余校验(3/3)检测方法：用发送端发送时采用的生成多项式G(x)来除接收到的码字多项式，若余式不为0，则传输有差错；否则，认为传输无差错。15计算机网络3.2.3循环冗余校验(3/3)检测方法：用发送端发送时采3.2.4海明码(1/3)也是一种可以纠正一位差错的编码。对于奇偶校验码，若信息位为an-1an-2…a1，加上一位偶校验位a0，在接收端校验时，可按关系式

S=

an-1

⊕

an-2

⊕

…⊕a0来计算，若S=0，则无错；若S=1，则有错。上式称为监督关系式，S称为校正因子。思想：增加冗余位，也相应地增加监督关系式和校正因子，就能表示更多的差错情况，包括具体定出是哪一位出错。理论依据：当信息位为k位，增加r个冗余位，构成n=k+r位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同的位置的一位错，则要求：2r≥k+r+1。16计算机网络3.2.4海明码(1/3)也是一种可以纠正一位差错的编码。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⊕a6S2S1S0000001010100011101110111错码位置无错a0错a1错a2错a3错a4错a5错a6错17计算机网络3.2.4海明码(2/3)生成过程：（假设k=4，则r取33.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）纠错（P68）特点：（1）编码效率为k/k+r（上例4/7）；（2）较容易实现，但只能纠正1位错。18计算机网络3.2.4海明码(3/3)（3）求出冗余位关系式18计算机3.3 数据链路层协议

3.3.1基本链路控制协议3.3.2滑动窗口协议19计算机网络3.3 数据链路层协议3.3.1基本链路控制协议193.3.1基本链路控制协议(1/8)

ARQ（AutomaticRepeatQuest，自动重发请求，也称“循环自动请求”）协议是数据链路层最基本的协议。它是指在接收站接收到一个包含出错数据的信息（帧）时，自动发出一个重传错帧的请求。

ARQ的作用原则是对出错的数据帧自动重发，它有三种形式：停等ARQ协议连续ARQ协议选择重传ARQ协议

20计算机网络3.3.1基本链路控制协议(1/8)ARQ（Automa3.3.1基本链路控制协议(2/8)

1、理想情况下的主机通信：完全理想化的数据传输要基于以下两个假定：假定1—链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定2—不管发送方以多快的速率发送数据，接收方总是来得及收下，并及时上交主机。数据链路层不需要协议就可以保证数据传输的正确。21计算机网络3.3.1基本链路控制协议(2/8)1、理想情况下的主机3.3.1基本链路控制协议(3/8)

2、停等ARQ协议：工作原理发送方发送一个数据帧后，必须停下来等待接收方的确认帧后才可以发送下一个数据帧；在接收方接收错误时，接收方则发一否认帧，要求发送方重发该帧；为防止发送的数据丢失，发送方内部设置一个定时器，当超过定时时间，而发送方仍未收到确认帧时，发送方重发该帧；为防止确认帧丢失而造成发送方重发同一数据帧，发送方给每一个数据帧带上一个序列号。22计算机网络3.3.1基本链路控制协议(3/8)2、停等ARQ协议：3.3.1基本链路控制协议(4/8)

停等ARQ协议的缺点：停等ARQ协议虽然保证了传输的安全可靠，但在传输过程中信道的吞吐量太低。23计算机网络3.3.1基本链路控制协议(4/8)停等ARQ协议的缺点3.3.1基本链路控制协议(5/8)

3、连续ARQ协议：工作原理连续ARQ是连续发送若干数据帧，如果发送方接收到接收端发回的确认帧，则继续发送；发送方在每发完一个数据帧后，就启动内部超时定时器，在设置的超时时间内未收到确认帧，则重发相应的数据帧。连续ARQ协议的工作示意图：24计算机网络3.3.1基本链路控制协议(5/8)3、连续ARQ协议：3.3.1基本链路控制协议(6/8)

连续ARQ协议的缺点：连续ARQ协议一方面因连续发送数据帧而提高了效率，但另一方面，在重传时又必须把原来已正确传送过的数据帧进行重传（但仅因这些数据帧之前有一个数据帧出了错），这样又使传送速率降低。由此可见，若传输信道的传输质量很差而误码率较大时，连续ARQ协议不一定优于停等ARQ协议。25计算机网络3.3.1基本链路控制协议(6/8)连续ARQ协议的缺点3.3.1基本链路控制协议(7/8)

4、选择重传ARQ协议：工作原理当接收方发现某帧出错后，其后继续送来的正确帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以与原来已存于缓冲区中的其余帧一并按正确的顺序递交高层。

选择重传ARQ协议的缺点：选择重发减少了浪费，但要求接收方有足够大的缓冲区空间，这在许多情况下是不够经济的。正因如此，选择重传ARQ协议在目前就远没有连续重传ARQ协议使用得那么广泛。今后存储器芯片的价格会更加便宜，选择重传ARQ协议还是有可能受到更多的重视。26计算机网络3.3.1基本链路控制协议(7/8)4、选择重传ARQ协3.3.1基本链路控制协议(8/8)

选择重传ARQ协议的工作示意图：以上三种重传方法各有利弊，停等ARQ协议最简单，但信道利用率最低；选择重传ARQ协议信道利用率最高，但它要求接收端的缓冲容量相当大；连续ARQ协议介于两者之间。在应用中应根据实际情况选择。27计算机网络3.3.1基本链路控制协议(8/8)选择重传ARQ协议的1、XON/XOFF在流量控制方面，可以从不同侧面采取不同的控制方案。最简单的方法就是增加接收端的缓冲存储空间，使得接收端可以缓存更多的数据。但这只是一种被动、消极的方法。因为，一方面系统不允许开设过大的缓冲空间；另一方面对于速率则显著失效，而且在传送大量数据的场合下，即使缓存空间再大也会出现不够的现象。目前普遍采取一种称之为“XON/XOFF”的发送控制字符的方案，通过控制字符来确定发送方是否继续发送数据，相比之下更主动、更积极、更有效。3.3.2XON/XOFF方案和滑动窗口协议(1/4)

28计算机网络1、XON/XOFF3.3.2XON/XOFF方案和滑动窗XON/XOFF的通信原理：XON/XOFF是一种异步通信协议，接收设备或计算机使用特殊字符来控制发送设备或计算机传送的数据流。当接收计算机不能继续接收数据时，发送一个XOFF控制字符告诉发送方停止传送；当传输可以恢复时，该计算机发送一个XON字符来通知发送方。3.3.2XON/XOFF方案和滑动窗口协议(2/4)

29计算机网络XON/XOFF的通信原理：3.3.2XON/XOFF方2、滑动窗口协议滑动窗口协议属异步双工传输模式。协议基本内容：发送的信息帧都有一个序号，从0到某个最大值，0～2n－1，一般用n个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小=上界-下界，大小可变。发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1。接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧。接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。

3.3.2XON/XOFF方案和滑动窗口协议(3/4)

30计算机网络2、滑动窗口协议3.3.2XON/XOFF方案和滑动窗口协3.3.2XON/XOFF方案和滑动窗口协议(4/4)

主要的滑动窗口协议：1比特滑动窗口协议（停等协议）退后n帧协议选择重传协议滑动窗口协议的工作原理示意图：31计算机网络3.3.2XON/XOFF方案和滑动窗口协议(4/4)主3.4 协议描述与验证

3.4.1有限状态机模型3.4.2Petri网模型32计算机网络3.4 协议描述与验证3.4.1有限状态机模型323.4.1有限状态机模型

有限状态机（FiniteStateMachine，FSM）是一种用来描述系统的常用方法。在这个模型中，系统被描述成有限的状态，在一定的前提条件下会发生一系列的输入事件，这些事件使得系统采取相应的动作，并从一个状态转换成另一个状态，称为状态的变迁或转换（Transition）。33计算机网络3.4.1有限状态机模型有限状态机（FiniteSt3.4.2Petri网模型

Petri网是由德国学者C.A.Petri首先提出的一种描述方法,它本质上也是一种有限状态机模型。Petri网的描述中有四种基本元素：位置(Place)—位置是一圆圈，表示可能进入的状态标记(Token)—位置中的小圆黑点，某个位置中有标记就表示已处于该状态变迁(Transition)—用一根直线段来表示,指明了该变迁发生的条件带箭头的弧线(Arc)—用弧线来表示,指明变迁产生的条件和变迁产生的结果34计算机网络3.4.2Petri网模型Petri网是由德国学者C.3.5 数据链路层协议举例

3.5.1数据链路层协议的分类3.5.2HDLC3.5.3SLIP和PPP35计算机网络3.5 数据链路层协议举例3.5.1数据链路层协议的3.5.1数据链路层协议的分类链路控制协议的分类：异步协议—以字符为独立的信息传输单位，在每个字符的起始处开始对字符内的比特实现同步，但字符与字符之间的间隔时间是不固定的(即字符之间是异步的)同步协议—以许多字符或许多比特组织成的数据块----帧为传输单位，在帧的起始处同步，使帧内维持固定的时钟。同步协议的分类：面向字符的同步协议

面向比特的同步协议面向字节计数的同步协议36计算机网络3.5.1数据链路层协议的分类链路控制协议的分类：36计3.5.2HDLC(1/2)

1、HDLC的操作方式：所谓操作方式，通俗地讲就是某站点是以主站点方式操作还是以从站方式操作，或者是二者兼备。

HDLC操作方式的类型：正常响应方式NRM(NormaResponsesMode)—这是一非平衡数据链路方式，有时也称非平衡正常响应方式，传输过程由主站启动。异步响应方式ARM(AsynchronousResponsesMode)—这也是一种非平衡数据链路操作方式，与NRM不同的是，ARM下的传输过程由从站启动。

异步平衡方式ABM(AsynchronousBalancedMode)—这是一种允许任何节点来启动传输的操作方式。为了提高链路传输效率，节点之间在两个方向上都需要有较高的信息传输量。37计算机网络3.5.2HDLC(1/2)1、HDLC的操作方式：3.5.2HDLC(2/2)

2、HDLC的帧格式：3、HDLC的帧类型：信息帧(I帧)—信息帧用于传送有效信息或数据，通常简称I帧。监控帧(S帧)—监控帧用于差错控制和流量控制，通常简称S帧。无编号帧(U帧)—无编号帧因其控制字段中不包含编号N(S)和N(R)而得名，简称U帧。U帧用于提供对链路的建立、拆除以及多种控制功能。

38计算机网络3.5.2HDLC(2/2)2、HDLC的帧格式：3.5.3SLIP和PPP(1/4)

用户接入Internet的常用方法：使用拨号电话线接入Internet使用专线接入

SLIP：串行线路SLIP（SerialLineInternetProtocol，SLIP）用于运行TCP/IP协议的面向字符的点对点串行连接，早在1984年就已经开始使用。

SLIP通常专门用于串行连接，有时候也用于拨号，使用的线路速率一般介于1200bit/s和19.2Kbit/s之间。主要用与低速的交互性业务。SLIP允许主机和路由器混合连接通信（主机-主机、主机-路由器、路由器-路由器都是SLIP网络通用的配置），因而非常有用。39计算机网络3.5.3SLIP和PPP(1/4)用户接入Inte3.5.3SLIP和PPP(2/4)

SLIP协议的缺点：SLIP没有差错检测的功能。通信的每一方必须事先知道对方的IP地址，这对拨号入网的用户是很不方便的。SLIP仅支持IP，而不支持其他的协议。SLIP并未成为Internet的标准协议。因此目前存在着多种互不兼容的版本，影响了不同网络的互联。

40计算机网络3.5.3SLIP和PPP(2/4)SLIP协议的缺3.5.3SLIP和PPP(3/4)

PPP协议的三部分：一个将IP数据报封装到串行链路的方法。PPP既支持异步链路（无奇偶校验的8比特数据），也支持面向比特的同步链路。一个用来建立、配置和测试数据链路连接的链路控制协议LCP（LinkControlProtocol），通信的双方可协商一些选项。一套网络控制协议NCP（NetworkControlProtocol），支持不同的网络层协议，如IP、OSI的网络层、DECnet及AppleTalk。41计算机网络3.5.3SLIP和PPP(3/4)PPP协议的三部3.5.3SLIP和PPP(4/4)

PPP协议的帧格式：PPP协议的特点：PPP协议是面向字符型的，所以它不能采用HDLC所使用的零比特插入法，而是使用一种特殊的字符填充。PPP不使用序号和确认，因此，PPP不提供可靠传输的服务。

42计算机网络3.5.3SLIP和PPP(4/4)PPP协议的帧格计算机网络

ComputerNetwork2023年1月2日计算机网络

ComputerNetwork2022年12课程目录第1章 概述第2章 物理层与数据通信基础第3章 数据链路层第4章 局域网第5章 网络层第6章 网络互联技术第7章 传输层第8章 应用层第9章 网络管理与信息安全第10章 网络新技术专题44计算机网络课程目录第1章 概述2计算机网络本章提纲3.1 数据链路层的功能3.2 差错检测和校正3.3 数据链路层协议3.4 协议描述与验证3.5 数据链路层协议举例第3章 数据链路层45计算机网络本章提纲3.1 数据链路层的功能第3章 数据链路层3计算3.1 数据链路层的功能

3.1.1帧同步3.1.2差错控制3.1.3流量控制3.1.4链路管理46计算机网络3.1 数据链路层的功能3.1.1帧同步4计算机网络3.1.1帧同步

帧同步：能从比特流中区分出帧的起始与终止。1、字节计数法以一个特殊字符表征一帧的起始，并以一个专门字段来标明帧内的字节数。2、使用字符填充的首尾定界符法用一些特定的字符来定界一帧的起始与终止。

数据的透明性3、使用比特填充的首尾定界符法以一组特定的比特模式(如01111110)来标志一帧的起始与终止。数据的透明性4、违法编码法借用违法编码序列来定界帧的起始与终止。

47计算机网络3.1.1帧同步帧同步：能从比特流中区分出帧的起始与终止3.1.2差错控制通信系统必须具备发现(即检测)差错的能力，并采取措施纠正它，使差错控制在所能允许的尽可能小的范围内，这就是差错控制过程，也是数据链路层的主要功能之一。反馈重发计时器帧序号48计算机网络3.1.2差错控制通信系统必须具备发现(即检测)差错的能3.1.3流量控制流量控制并不是数据链路层特有的功能，许多高层协议中也提供流量控制功能，只不过流量控制的对象不同而已。流量控制实际上是对发送方数据流量的控制，使其发送速率不超过接收方的接收速率。49计算机网络3.1.3流量控制流量控制并不是数据链路层特有的功能，3.1.4链路管理

链路管理功能主要是用于面向连接的服务。数据链路层连接的建立、维持和释放就称做链路管理。50计算机网络3.1.4链路管理链路管理功能主要是用于面向连接的服务。3.2 差错检测和校正

3.2.1传输差错的特性3.2.2奇偶校验3.2.3循环冗余校验3.2.4海明码51计算机网络3.2 差错检测和校正3.2.1传输差错的特性9计算机3.2.1传输差错的特性传输中的差错都是由于噪声引起的。噪声有两大类：一类是信道所固有的、持续存在的随机热噪声；另一类是由于外界特定的短暂原因所造成的冲击噪声。误码率编码效率差错控制的方式：自动请求重发（AutomaticReQuestforRepeat，ARQ）前向纠错(ForwardErrorCorrection，FEC)52计算机网络3.2.1传输差错的特性传输中的差错都是由于噪声引起的。噪3.2.2奇偶校验(1/2)奇偶校验的特点：奇偶校验码是一种通过增加冗余位使得码字中“1”的个数恒为奇数或偶数的编码方法,它是一种检错码。偶校验:ri=I1i⊕I2i⊕…⊕Ipi奇校验:ri=I1i⊕I2i⊕…⊕Ipi⊕1奇偶校验的分类：垂直奇偶校验

编码效率R=p/(p+1)

53计算机网络3.2.2奇偶校验(1/2)奇偶校验的特点：11计算机网络3.2.2奇偶校验(2/2)水平奇偶校验编码效率R=q/(q+1)

水平垂直奇偶校验编码效率R=pq/(p+1)(q+1)54计算机网络3.2.2奇偶校验(2/2)水平奇偶校验12计算机网络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)，即得冗余位。55计算机网络3.2.3循环冗余校验(1/3)它是一种检错码。13计算机3.2.3循环冗余校验(2/3)示例设信息位为1010001，即K(x)=x6+x4+1，取G(x)=x4+x2+x+1（对应的代码为10111），则x4K(x)=x10+x8+x4（对应的代码为10100010000），则所以冗余位为1101，

R(x)=x3+x2+1。T(X)=x4K(x)+R(x)=x10+x8+x4+

x3+x2+1

对应的发送代码为：1010001110156计算机网络3.2.3循环冗余校验(2/3)示例设信息位为101003.2.3循环冗余校验(3/3)检测方法：用发送端发送时采用的生成多项式G(x)来除接收到的码字多项式，若余式不为0，则传输有差错；否则，认为传输无差错。57计算机网络3.2.3循环冗余校验(3/3)检测方法：用发送端发送时采3.2.4海明码(1/3)也是一种可以纠正一位差错的编码。对于奇偶校验码，若信息位为an-1an-2…a1，加上一位偶校验位a0，在接收端校验时，可按关系式

S=

an-1

⊕

an-2

⊕

…⊕a0来计算，若S=0，则无错；若S=1，则有错。上式称为监督关系式，S称为校正因子。思想：增加冗余位，也相应地增加监督关系式和校正因子，就能表示更多的差错情况，包括具体定出是哪一位出错。理论依据：当信息位为k位，增加r个冗余位，构成n=k+r位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同的位置的一位错，则要求：2r≥k+r+1。58计算机网络3.2.4海明码(1/3)也是一种可以纠正一位差错的编码。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⊕a6S2S1S0000001010100011101110111错码位置无错a0错a1错a2错a3错a4错a5错a6错59计算机网络3.2.4海明码(2/3)生成过程：（假设k=4，则r取33.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）纠错（P68）特点：（1）编码效率为k/k+r（上例4/7）；（2）较容易实现，但只能纠正1位错。60计算机网络3.2.4海明码(3/3)（3）求出冗余位关系式18计算机3.3 数据链路层协议

3.3.1基本链路控制协议3.3.2滑动窗口协议61计算机网络3.3 数据链路层协议3.3.1基本链路控制协议193.3.1基本链路控制协议(1/8)

ARQ（AutomaticRepeatQuest，自动重发请求，也称“循环自动请求”）协议是数据链路层最基本的协议。它是指在接收站接收到一个包含出错数据的信息（帧）时，自动发出一个重传错帧的请求。

ARQ的作用原则是对出错的数据帧自动重发，它有三种形式：停等ARQ协议连续ARQ协议选择重传ARQ协议

62计算机网络3.3.1基本链路控制协议(1/8)ARQ（Automa3.3.1基本链路控制协议(2/8)

1、理想情况下的主机通信：完全理想化的数据传输要基于以下两个假定：假定1—链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。假定2—不管发送方以多快的速率发送数据，接收方总是来得及收下，并及时上交主机。数据链路层不需要协议就可以保证数据传输的正确。63计算机网络3.3.1基本链路控制协议(2/8)1、理想情况下的主机3.3.1基本链路控制协议(3/8)

2、停等ARQ协议：工作原理发送方发送一个数据帧后，必须停下来等待接收方的确认帧后才可以发送下一个数据帧；在接收方接收错误时，接收方则发一否认帧，要求发送方重发该帧；为防止发送的数据丢失，发送方内部设置一个定时器，当超过定时时间，而发送方仍未收到确认帧时，发送方重发该帧；为防止确认帧丢失而造成发送方重发同一数据帧，发送方给每一个数据帧带上一个序列号。64计算机网络3.3.1基本链路控制协议(3/8)2、停等ARQ协议：3.3.1基本链路控制协议(4/8)

停等ARQ协议的缺点：停等ARQ协议虽然保证了传输的安全可靠，但在传输过程中信道的吞吐量太低。65计算机网络3.3.1基本链路控制协议(4/8)停等ARQ协议的缺点3.3.1基本链路控制协议(5/8)

3、连续ARQ协议：工作原理连续ARQ是连续发送若干数据帧，如果发送方接收到接收端发回的确认帧，则继续发送；发送方在每发完一个数据帧后，就启动内部超时定时器，在设置的超时时间内未收到确认帧，则重发相应的数据帧。连续ARQ协议的工作示意图：66计算机网络3.3.1基本链路控制协议(5/8)3、连续ARQ协议：3.3.1基本链路控制协议(6/8)

连续ARQ协议的缺点：连续ARQ协议一方面因连续发送数据帧而提高了效率，但另一方面，在重传时又必须把原来已正确传送过的数据帧进行重传（但仅因这些数据帧之前有一个数据帧出了错），这样又使传送速率降低。由此可见，若传输信道的传输质量很差而误码率较大时，连续ARQ协议不一定优于停等ARQ协议。67计算机网络3.3.1基本链路控制协议(6/8)连续ARQ协议的缺点3.3.1基本链路控制协议(7/8)

4、选择重传ARQ协议：工作原理当接收方发现某帧出错后，其后继续送来的正确帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以与原来已存于缓冲区中的其余帧一并按正确的顺序递交高层。

选择重传ARQ协议的缺点：选择重发减少了浪费，但要求接收方有足够大的缓冲区空间，这在许多情况下是不够经济的。正因如此，选择重传ARQ协议在目前就远没有连续重传ARQ协议使用得那么广泛。今后存储器芯片的价格会更加便宜，选择重传ARQ协议还是有可能受到更多的重视。68计算机网络3.3.1基本链路控制协议(7/8)4、选择重传ARQ协3.3.1基本链路控制协议(8/8)

选择重传ARQ协议的工作示意图：以上三种重传方法各有利弊，停等ARQ协议最简单，但信道利用率最低；选择重传ARQ协议信道利用率最高，但它要求接收端的缓冲容量相当大；连续ARQ协议介于两者之间。在应用中应根据实际情况选择。69计算机网络3.3.1基本链路控制协议(8/8)选择重传ARQ协议的1、XON/XOFF在流量控制方面，可以从不同侧面采取不同的控制方案。最简单的方法就是增加接收端的缓冲存储空间，使得接收端可以缓存更多的数据。但这只是一种被动、消极的方法。因为，一方面系统不允许开设过大的缓冲空间；另一方面对于速率则显著失效，而且在传送大量数据的场合下，即使缓存空间再大也会出现不够的现象。目前普遍采取一种称之为“XON/XOFF”的发送控制字符的方案，通过控制字符来确定发送方是否继续发送数据，相比之下更主动、更积极、更有效。3.3.2XON/XOFF方案和滑动窗口协议(1/4)

70计算机网络1、XON/XOFF3.3.2XON/XOFF方案和滑动窗XON/XOFF的通信原理：XON/XOFF是一种异步通信协议，接收设备或计算机使用特殊字符来控制发送设备或计算机传送的数据流。当接收计算机不能继续接收数据时，发送一个XOFF控制字符告诉发送方停止传送；当传输可以恢复时，该计算机发送一个XON字符来通知发送方。3.3.2XON/XOFF方案和滑动窗口协议(2/4)

71计算机网络XON/XOFF的通信原理：3.3.2XON/XOFF方2、滑动窗口协议滑动窗口协议属异步双工传输模式。协议基本内容：发送的信息帧都有一个序号，从0到某个最大值，0～2n－1，一般用n个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小=上界-下界，大小可变。发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1。接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧。接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变。

3.3.2XON/XOFF方案和滑动窗口协议(3/4)

72计算机网络2、滑动窗口协议3.3.2XON/XOFF方案和滑动窗口协3.3.2XON/XOFF方案和滑动窗口协议(4/4)

主要的滑动窗口协议：1比特滑动窗口协议（停等协议）退后n帧协议选择重传协议滑动窗口协议的工作原理示意图：73计算机网络3.3.2XON/XOFF方案和滑动窗口协议(4/4)主3.4 协议描述与验证

3.4.1有限状态机模型3.4.2Petri网模型74计算机网络3.4 协议描述与验证3.4.1有限状态机模型323.4.1有限状态机模型

有限状态机（FiniteStateMachine，FSM）是一种用来描述系统的常用方法。在这个模型中，系统被描述成有限的状态，在一定的前提条件下会发生一系列的输入事件，这些事件使得系统采取相应的动作，并从一个状态转换成另一个状态，称为状态的变迁或转换（Transition）。75计算机网络3.4.1有限状态机模型有限状态机（FiniteSt3.4.2Petri网模型

Petri网是由德国学者C.A.Petri首先提出的一种描述方法,它本质上也是一种有限状态机模型。Petri网的描述中有四种基本元素：位置(Place)—位置是一圆圈，表示可能进入的状态标记(Token)—位置中的小圆黑点，某个位置中有标记就表示已处于该状态变迁(Transition)—用一根直线段来表示,指明了该变迁发生的条件带箭头的弧线(Arc)—用弧线来表示,指明变迁产生的条件和变迁产生的结果76计算机网络3.4.2Petri网模型Petri网是由德国学者C.3.5 数据链路层协议举例

3.5.1数据链路层协议的分类3.5.2HDLC3.5.3SLIP和PPP77计算机网络3.5 数据链路层协议举例3.5.1数据链路层协议的3.5.1数据链路层协议的分类链路控制协议的分类：异步协议—以字符为独立的信息传输单位，在每个字符的起始处开始对字符内的比特实现同步，但字符与字符之间的间隔时间是不固定的(即字符之间是异步的)