第3章数据链路层课件.ppt

计算机网络计算机网络Computer Network2024年9月21日课程目录课程目录n第1章概述n第2章物理层与数据通信基础n第第3章章数据链路层数据链路层n第4章局域网n第5章网络层n第6章网络互联技术n第7章传输层n第8章应用层n第9章网络管理与信息安全n第10章网络新技术专题2计算机网络计算机网络本章提纲本章提纲n3.1 数据链路层的功能 n3.2 差错检测和校正 n3.3 数据链路层协议 n3.4 协议描述与验证 n3.5 数据链路层协议举例 第第3章章 数据链路层数据链路层 3计算机网络计算机网络3.1 数据链路层的功能数据链路层的功能 n3.1.1 帧同步 n3.1.2 差错控制 n3.1.3 流量控制 n3.1.4 链路管理 4计算机网络计算机网络3.1.1 帧同步帧同步 n帧同步：能从比特流中区分出帧的起始与终止1、字节计数法 n以一个特殊字符表征一帧的起始，并以一个专门字段来标明帧内的字节数2、使用字符填充的首尾定界符法 n用一些特定的字符来定界一帧的起始与终止 n数据的透明性3、使用比特填充的首尾定界符法 n以一组特定的比特模式(如01111110)来标志一帧的起始与终止。

n数据的透明性4、违法编码法 n借用违法编码序列来定界帧的起始与终止 5计算机网络计算机网络3.1.2 差错控制差错控制n通信系统必须具备发现(即检测)差错的能力，并采取措施纠正它，使差错控制在所能允许的尽可能小的范围内，这就是差错控制过程，也是数据链路层的主要功能之一 n反馈重发n计时器n帧序号6计算机网络计算机网络3.1.3 流量控制流量控制 n流量控制并不是数据链路层特有的功能，许多高层协议中也提供流量控制功能，只不过流量控制的对象不同而已n流量控制实际上是对发送方数据流量的控制，使其发送速率不超过接收方的接收速率 7计算机网络计算机网络3.1.4 链路管理链路管理 n链路管理功能主要是用于面向连接的服务n数据链路层连接的建立、维持和释放就称做链路管理 8计算机网络计算机网络3.2 差错检测和校正差错检测和校正 n3.2.1 传输差错的特性 n3.2.2 奇偶校验 n3.2.3 循环冗余校验 n3.2.4 海明码 9计算机网络计算机网络3.2.1 传输差错的特性传输差错的特性n传输中的差错都是由于噪声引起的噪声有两大类：一类是信道所固有的、持续存在的随机热噪声；另一类是由于外界特定的短暂原因所造成的冲击噪声。

n误码率n编码效率n差错控制的方式 ：n自动请求重发（Automatic ReQuest for Repeat，ARQ） n前向纠错(Forward Error Correction，FEC) 10计算机网络计算机网络3.2.2 奇偶校验奇偶校验(1/2)n奇偶校验的特点：n奇偶校验码是一种通过增加冗余位使得码字中“1”的个数恒为奇数或偶数的编码方法,它是一种检错码n偶校验:ri=I1i⊕I2i⊕…⊕Ipin奇校验: ri=I1i⊕I2i⊕…⊕Ipi⊕1n奇偶校验的分类：n垂直奇偶校验 n编码效率 R=p/(p+1) R=p/(p+1) 11计算机网络计算机网络3.2.2 奇偶校验奇偶校验(2/2)n水平奇偶校验 n编码效率 R=q/(q+1) R=q/(q+1) n水平垂直奇偶校验n编码效率 R=pq/(p+1)(q+1) R=pq/(p+1)(q+1)12计算机网络计算机网络3.2.3 循环冗余校验循环冗余校验(1/3)n它是一种检错码n思思想想：任何一个由二进制数位串组成的代码都可以和一个只含0和1两个系数的多项式建立一一对应的关系。

nk位信息位对应于一个k-1次多项式K(x)，r位冗余位对应于一个r-1次多项式R(x)，生成的n=k+r位码字则对应于一个n-1次多项式T(x)n生生成成方方法法：发送方和接收方依据一事先约定的r次生成多项式G(x) （最高项xr和最低项的系数为1），用G(x)去除xrK(x)得到的余式就是R(x)，即得冗余位13计算机网络计算机网络3.2.3 循环冗余校验循环冗余校验(2/3)n示示例例 设信息位为1010001，即K(x)= x6+x4+1，取G(x)= x4+x2+x+1（ 对 应 的 代 码 为 10111） ， 则 x4 K(x)= x10+x8+x4（n所以冗余位为1101， R(x)= x3+x2+1 T(X)= x4 K(x)+ R(x)= x10+x8+x4 + x3+x2+1 14计算机网络计算机网络3.2.3 循环冗余校验循环冗余校验(3/3)n检检测测方方法法：用发送端发送时采用的生成多项式G(x)来除接收到的码字多项式，若余式不为0，则传输有差错；否则，认为传输无差错15计算机网络计算机网络3.2.4 海明码海明码(1/3)n也是一种可以纠正一位差错的编码。

n对于奇偶校验码，若信息位为an-1an-2…a1，加上一位偶校 验 位 a0， 在 接 收 端 校 验 时 ， 可 按 关 系 式 S = an-1 ⊕ an-2 ⊕ … ⊕ a0来计算，若S=0，则无错；若S=1，则有错上式称为监督关系式监督关系式，S称为校正因子校正因子n思思想想：：增加冗余位，也相应地增加监督关系式和校正因子，就能表示更多的差错情况，包括具体定出是哪一位出错n理理论论依依据据：：当信息位为k位，增加r个冗余位，构成n=k+r位码字若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同的位置的一位错，则要求：2r≥k+r+116计算机网络计算机网络3.2.4 海明码海明码(2/3)n生生成成过过程程：：（（假设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 海明码海明码(3/3)（3）求出冗余位关系式令S0 、、S1 和S2为0，即可求出a0 、a1和a2： a2 = a4 ⊕ a5 ⊕ a6 a1 = a3 ⊕ a5 ⊕ a6 a0 = a3 ⊕ a4 ⊕ a6 n示例示例（P69 表3.2）n纠错纠错（P68 ）n特点：（1）编码效率为k/k+r （上例4/7 ）；（2）较容易实现，但只能纠正1位错。

18计算机网络计算机网络3.3 数据链路层协议数据链路层协议 n3.3.1 基本链路控制协议 n3.3.2 滑动窗口协议 19计算机网络计算机网络3.3.1 基本链路控制协议基本链路控制协议(1/8) nARQ（Automatic Repeat Quest，自动重发请求，也称“循环自动请求”）协议是数据链路层最基本的协议它是指在接收站接收到一个包含出错数据的信息（帧）时，自动发出一个重传错帧的请求n ARQ的作用原则是对出错的数据帧自动重发，它有三种形式：n停等ARQ协议n连续ARQ协议n选择重传ARQ协议 20计算机网络计算机网络3.3.1 基本链路控制协议基本链路控制协议(2/8) 1、理想情况下的主机通信：n完全理想化的数据传输要基于以下两个假定：n假定1—链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失n假定2—不管发送方以多快的速率发送数据，接收方总是来得及收下，并及时上交主机n数据链路层不需要协议就可以保证数据传输的正确21计算机网络计算机网络3.3.1 基本链路控制协议基本链路控制协议(3/8) 2、停等ARQ协议：n工作原理n发送方发送一个数据帧后，必须停下来等待接收方的确认帧后才可以发送下一个数据帧；在接收方接收错误时，接收方则发一否认帧，要求发送方重发该帧；为防止发送的数据丢失，发送方内部设置一个定时器，当超过定时时间，而发送方仍未收到确认帧时，发送方重发该帧；为防止确认帧丢失而造成发送方重发同一数据帧，发送方给每一个数据帧带上一个序列号。

22计算机网络计算机网络3.3.1 基本链路控制协议基本链路控制协议(4/8) n停等ARQ协议的缺点：n停等ARQ协议虽然保证了传输的安全可靠，但在传输过程中信道的吞吐量太低23计算机网络计算机网络3.3.1 基本链路控制协议基本链路控制协议(5/8) 3、连续ARQ协议：n工作原理n连续ARQ是连续发送若干数据帧，如果发送方接收到接收端发回的确认帧，则继续发送；发送方在每发完一个数据帧后，就启动内部超时定时器，在设置的超时时间内未收到确认帧，则重发相应的数据帧n连续ARQ协议的工作示意图：24计算机网络计算机网络3.3.1 基本链路控制协议基本链路控制协议(6/8) n连续ARQ协议的缺点：n连续ARQ协议一方面因连续发送数据帧而提高了效率，但另一方面，在重传时又必须把原来已正确传送过的数据帧进行重传（但仅因这些数据帧之前有一个数据帧出了错），这样又使传送速率降低由此可见，若传输信道的传输质量很差而误码率较大时，连续ARQ协议不一定优于停等ARQ协议25计算机网络计算机网络3.3.1 基本链路控制协议基本链路控制协议(7/8) 4、选择重传ARQ协议：n工作原理n当接收方发现某帧出错后，其后继续送来的正确帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。

一旦收到重新传来的帧后，就可以与原来已存于缓冲区中的其余帧一并按正确的顺序递交高层 n选择重传ARQ协议的缺点：n选择重发减少了浪费，但要求接收方有足够大的缓冲区空间，这在许多情况下是不够经济的正因如此，选择重传ARQ协议在目前就远没有连续重传ARQ协议使用得那么广泛今后存储器芯片的价格会更加便宜，选择重传ARQ协议还是有可能受到更多的重视26计算机网络计算机网络3.3.1 基本链路控制协议基本链路控制协议(8/8) n选择重传ARQ协议的工作示意图：n以上三种重传方法各有利弊，停等ARQ协议最简单，但信道利用率最低；选择重传ARQ协议信道利用率最高，但它要求接收端的缓冲容量相当大；连续ARQ协议介于两者之间在应用中应根据实际情况选择27计算机网络计算机网络1、XON/XOFFn在流量控制方面，可以从不同侧面采取不同的控制方案最简单的方法就是增加接收端的缓冲存储空间，使得接收端可以缓存更多的数据但这只是一种被动、消极的方法因为，一方面系统不允许开设过大的缓冲空间；另一方面对于速率则显著失效，而且在传送大量数据的场合下，即使缓存空间再大也会出现不够的现象n目前普遍采取一种称之为“XON/XOFF”的发送控制字符的方案，通过控制字符来确定发送方是否继续发送数据，相比之下更主动、更积极、更有效。

3.3.2 XON/XOFF方案和滑动窗口协议方案和滑动窗口协议(1/4) 28计算机网络计算机网络nXON/XOFF 的通信原理：nXON/XOFF是一种异步通信协议，接收设备或计算机使用特殊字符来控制发送设备或计算机传送的数据流当接收计算机不能继续接收数据时，发送一个XOFF控制字符告诉发送方停止传送；当传输可以恢复时，该计算机发送一个XON字符来通知发送方 3.3.2 XON/XOFF方案和滑动窗口协议方案和滑动窗口协议(2/4) 29计算机网络计算机网络2、滑动窗口协议n滑动窗口协议属异步双工传输模式n协议基本内容：n发送的信息帧都有一个序号，从0到某个最大值，0～2n－1，一般用n个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号发送窗口大小=上界-下界，大小可变发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1n接收端有一个接收窗口，大小固定，但不一定与发送窗口相同接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。

序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1接收窗口大小不变 3.3.2 XON/XOFF方案和滑动窗口协议方案和滑动窗口协议(3/4) 30计算机网络计算机网络3.3.2 XON/XOFF方案和滑动窗口协议方案和滑动窗口协议(4/4) n主要的滑动窗口协议 ：n1比特滑动窗口协议（停等协议） n退后n帧协议 n选择重传协议 n滑动窗口协议的工作原理示意图：：31计算机网络计算机网络3.4 协议描述与验证协议描述与验证 n3.4.1 有限状态机模型 n3.4.2 Petri网模型 32计算机网络计算机网络3.4.1 有限状态机模型有限状态机模型 n有限状态机（Finite State Machine，FSM）是一种用来描述系统的常用方法在这个模型中，系统被描述成有限的状态，在一定的前提条件下会发生一系列的输入事件，这些事件使得系统采取相应的动作，并从一个状态转换成另一个状态，称为状态的变迁或转换（Transition）33计算机网络计算机网络3.4.2 Petri网模型网模型 nPetri网是由德国学者C.A.Petri首先提出的一种描述方法,它本质上也是一种有限状态机模型。

nPetri网的描述中有四种基本元素 ：n位置(Place)—位置是一圆圈，表示可能进入的状态 n标记(Token)—位置中的小圆黑点，某个位置中有标记就表示已处于该状态 n变迁(Transition)—用一根直线段来表示,指明了该变迁发生的条件 n带箭头的弧线(Arc)—用弧线来表示,指明变迁产生的条件和变迁产生的结果 34计算机网络计算机网络3.5 数据链路层协议举例数据链路层协议举例 n3.5.1 数据链路层协议的分类 n3.5.2 HDLC n3.5.3 SLIP和PPP 35计算机网络计算机网络3.5.1 数据链路层协议的分类数据链路层协议的分类n链路控制协议的分类：n异步协议—以字符为独立的信息传输单位，在每个字符的起始处开始对字符内的比特实现同步，但字符与字符之间的间隔时间是不固定的(即字符之间是异步的) n同步协议—以许多字符或许多比特组织成的数据块----帧为传输单位，在帧的起始处同步，使帧内维持固定的时钟 n同步协议的分类： n面向字符的同步协议 n面向比特的同步协议n面向字节计数的同步协议36计算机网络计算机网络3.5.2 HDLC (1/2) 1、HDLC的操作方式：n所谓操作方式，通俗地讲就是某站点是以主站点方式操作还是以从站方式操作，或者是二者兼备。

nHDLC操作方式的类型：n正常响应方式NRM(Norma Responses Mode) —这是一非平衡数据链路方式，有时也称非平衡正常响应方式，传输过程由主站启动 n异步响应方式ARM(Asynchronous Responses Mode) —这也是一种非平衡数据链路操作方式，与NRM不同的是，ARM下的传输过程由从站启动 n异步平衡方式ABM(Asynchronous Balanced Mode) —这是一种允许任何节点来启动传输的操作方式为了提高链路传输效率，节点之间在两个方向上都需要有较高的信息传输量 37计算机网络计算机网络3.5.2 HDLC (2/2) 2、、HDLC的帧格式的帧格式 ：3、、HDLC的帧类型的帧类型 ：：n信息帧(I帧)—信息帧用于传送有效信息或数据，通常简称I帧 n监控帧(S帧)—监控帧用于差错控制和流量控制，通常简称S帧 n无编号帧(U帧)—无编号帧因其控制字段中不包含编号N(S)和N(R)而得名，简称U帧U帧用于提供对链路的建立、拆除以及多种控制功能 38计算机网络计算机网络3.5.3 SLIP和和PPP (1/4) n用户接入Internet的常用方法：n使用拨号线接入Internet n使用专线接入 nSLIP：n串行线路SLIP（Serial Line Internet Protocol，SLIP）用于运行TCP/IP协议的面向字符的点对点串行连接，早在1984年就已经开始使用。

nSLIP通常专门用于串行连接，有时候也用于拨号，使用的线路速率一般介于1200bit/s和19.2Kbit/s之间主要用与低速的交互性业务 nSLIP允许主机和路由器混合连接通信（主机-主机、主机-路由器、路由器-路由器都是SLIP网络通用的配置），因而非常有用39计算机网络计算机网络3.5.3 SLIP和和PPP (2/4) nSLIP协议的缺点：nSLIP没有差错检测的功能 n通信的每一方必须事先知道对方的IP地址，这对拨号入网的用户是很不方便的 nSLIP仅支持IP，而不支持其他的协议 nSLIP并未成为Internet的标准协议因此目前存在着多种互不兼容的版本，影响了不同网络的互联 40计算机网络计算机网络3.5.3 SLIP和和PPP (3/4) nPPP协议的三部分：n一个将IP数据报封装到串行链路的方法PPP既支持异步链路 （无奇偶校验的 8比特数据），也支持面向比特的同步链路n一个用来建立、配置和测试数据链路连接的链路控制协议LCP（Link Control Protocol），通信的双方可协商一些选项n一套网络控制协议NCP（Network Control Protocol），支持不同的网络层协议，如IP、OSI的网络层、DECnet及AppleTalk 。

41计算机网络计算机网络3.5.3 SLIP和和PPP (4/4) nPPP协议的帧格式：nPPP协议的特点：nPPP协议是面向字符型的，所以它不能采用HDLC所使用的零比特插入法，而是使用一种特殊的字符填充 nPPP不使用序号和确认，因此，PPP不提供可靠传输的服务 42计算机网络计算机网络。