《计算机网络技术-第4章-数据链路层课件.ppt》由会员分享，可在线阅读，更多相关《计算机网络技术-第4章-数据链路层课件.ppt（93页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据链路层数据链路层ChapterFour本章教学提要本章教学提要教学目标：教学目标：理解数据链路层的功能与作用；理解数据链路层的功能与作用；理解数据链路层的功能与作用；理解数据链路层的功能与作用；了解常用的成帧方式；了解常用的成帧方式；了解常用的成帧方式；了解常用的成帧方式；理解差错控制的作用和原理；理解差错控制的作用和原理；理解差错控制的作用和原理；理解差错控制的作用和原理；理解流量控制的作用和原理；理解流量控制的作用和原理；理解流量控制的作用和原理；理解流量控制的作用和原理；了解了解了解了解HDLCHDLC协议的工作过程；协议的工作过程；协议的工作过程；协议的工作过程；理解数据链路层设备
2、与组件的作用与特性。理解数据链路层设备与组件的作用与特性。理解数据链路层设备与组件的作用与特性。理解数据链路层设备与组件的作用与特性。教学难点：教学难点：差错控制，滑动窗口协议差错控制，滑动窗口协议差错控制，滑动窗口协议差错控制，滑动窗口协议 教学时数：教学时数：4-64-64-64-6学时学时学时学时数据链路层概述数据链路层概述SectionOne本节驱动问题本节驱动问题为什么为什么在物理层之上要有数据链路层？在物理层之上要有数据链路层？什么样的结点属于相邻结点？什么样的结点属于相邻结点？数据链路层的简单模型数据链路层的简单模型局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器
3、R3电话网局域网主机 H1 向 H2 发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动完全理想化的数据传输完全理想化的数据传输数据链路层主机 A缓存主机 B数据链路AP2AP1缓存发送方接收方帧高层帧 假定假定假定假定 1 1：链路是理想的传输信道，所传送的任何数据链路是理想的传输信道，所传送的任何数据链路是理想的传输信道，所传送的任何数据链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。既不会出差错也不会丢失。既不会出差错也不会丢失。既不会出差错也不会丢失。假定
4、假定假定假定 2 2：不管发方以多快的速率发送数据，收方总是不管发方以多快的速率发送数据，收方总是不管发方以多快的速率发送数据，收方总是不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。来得及收下，并及时上交主机。来得及收下，并及时上交主机。来得及收下，并及时上交主机。这个假定就相当于认为：接收端向主机交付数据的速率永远这个假定就相当于认为：接收端向主机交付数据的速率永远这个假定就相当于认为：接收端向主机交付数据的速率永远这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。不会低于发送端发送数据的速率。不会低于发送端发送数据的速率。不会低于发送端发
5、送数据的速率。为什么需要数据链路层？为什么需要数据链路层？数据在物理传输过程可能损坏，尽管物理层采取了必要的数据在物理传输过程可能损坏，尽管物理层采取了必要的数据在物理传输过程可能损坏，尽管物理层采取了必要的数据在物理传输过程可能损坏，尽管物理层采取了必要的措施来减少信号传输过程中的噪声。措施来减少信号传输过程中的噪声。措施来减少信号传输过程中的噪声。措施来减少信号传输过程中的噪声。收发双方的接收和发送速率不匹配，会产生数据溢出，从收发双方的接收和发送速率不匹配，会产生数据溢出，从收发双方的接收和发送速率不匹配，会产生数据溢出，从收发双方的接收和发送速率不匹配，会产生数据溢出，从而引发数据丢失
6、；而引发数据丢失；而引发数据丢失；而引发数据丢失；物理层只关心原始比特流的传送，不考虑也不可能考虑所物理层只关心原始比特流的传送，不考虑也不可能考虑所物理层只关心原始比特流的传送，不考虑也不可能考虑所物理层只关心原始比特流的传送，不考虑也不可能考虑所传输信号的意义和信息的结构传输信号的意义和信息的结构传输信号的意义和信息的结构传输信号的意义和信息的结构不可能识别或判断数据在不可能识别或判断数据在不可能识别或判断数据在不可能识别或判断数据在传输过程中是否出现了损坏或丢失，更谈不上采取相应的传输过程中是否出现了损坏或丢失，更谈不上采取相应的传输过程中是否出现了损坏或丢失，更谈不上采取相应的传输过程
7、中是否出现了损坏或丢失，更谈不上采取相应的方法进行补救；方法进行补救；方法进行补救；方法进行补救；也就是说，只有物理层的功能是不够的。也就是说，只有物理层的功能是不够的。也就是说，只有物理层的功能是不够的。也就是说，只有物理层的功能是不够的。DTEDCEDCEDTEDCE数据链路层的功能数据链路层的功能数据链路层是为了克服物理层的物理传输质数据链路层是为了克服物理层的物理传输质数据链路层是为了克服物理层的物理传输质数据链路层是为了克服物理层的物理传输质量不足而存在的。量不足而存在的。量不足而存在的。量不足而存在的。其目的是为了实现两个其目的是为了实现两个其目的是为了实现两个其目的是为了实现两个
8、相邻节点间相邻节点间相邻节点间相邻节点间的无差错的无差错的无差错的无差错传输。传输。传输。传输。从分层的角度，数据链路层利用了物理层提从分层的角度，数据链路层利用了物理层提从分层的角度，数据链路层利用了物理层提从分层的角度，数据链路层利用了物理层提供的原始比特流传输服务，检测并校正物理供的原始比特流传输服务，检测并校正物理供的原始比特流传输服务，检测并校正物理供的原始比特流传输服务，检测并校正物理层的传输差错，控制数据的传输流量，使在层的传输差错，控制数据的传输流量，使在层的传输差错，控制数据的传输流量，使在层的传输差错，控制数据的传输流量，使在相邻节点之间构成一条无差错的数据链路，相邻节点之
9、间构成一条无差错的数据链路，相邻节点之间构成一条无差错的数据链路，相邻节点之间构成一条无差错的数据链路，从而向网络层提供从而向网络层提供从而向网络层提供从而向网络层提供可靠可靠可靠可靠的数据传输服务。的数据传输服务。的数据传输服务。的数据传输服务。何为相邻节点？何为相邻节点？相邻节点是指由同一物理链路直接连接的所有相邻节点是指由同一物理链路直接连接的所有相邻节点是指由同一物理链路直接连接的所有相邻节点是指由同一物理链路直接连接的所有节点。节点。节点。节点。点到点点到点(point to point)point to point)网网络环境中的两个节点；络环境中的两个节点；由同一物理线路连接的共
10、享由同一物理线路连接的共享介质环境中的节点；介质环境中的节点；位于不同物理线路上，位于不同物理线路上，但由第一层网络设备但由第一层网络设备（中继器或集线器）互（中继器或集线器）互连的节点；连的节点；数据链路与物理链路的区别数据链路与物理链路的区别“物理链路物理链路”：相邻结点之间的物理链路，中间相邻结点之间的物理链路，中间没有任何其他的交换结点。没有任何其他的交换结点。“数据链路数据链路”：在物理链路上加上必要的数据传在物理链路上加上必要的数据传输规程或协议后所形成的逻辑连接。输规程或协议后所形成的逻辑连接。控制着数据在逻辑链路上传输的规程控制着数据在逻辑链路上传输的规程或协议，被称为数据链路
11、层协议。或协议，被称为数据链路层协议。数据链路层要解决的主要问题数据链路层要解决的主要问题物理寻址物理寻址物理寻址物理寻址如何识别不同的相邻节点或确定一个接收如何识别不同的相邻节点或确定一个接收如何识别不同的相邻节点或确定一个接收如何识别不同的相邻节点或确定一个接收目标目标目标目标数据链路的建立、维持和释放数据链路的建立、维持和释放数据链路的建立、维持和释放数据链路的建立、维持和释放如何为相邻结点之如何为相邻结点之如何为相邻结点之如何为相邻结点之间的可靠数据传输提供必要的数据链路建立、维持和释间的可靠数据传输提供必要的数据链路建立、维持和释间的可靠数据传输提供必要的数据链路建立、维持和释间的可
12、靠数据传输提供必要的数据链路建立、维持和释放机制放机制放机制放机制数据流的定界数据流的定界数据流的定界数据流的定界如何提供一种机制使得接收方能识别如何提供一种机制使得接收方能识别如何提供一种机制使得接收方能识别如何提供一种机制使得接收方能识别数据流的开始与结束数据流的开始与结束数据流的开始与结束数据流的开始与结束差错控制与流量控制差错控制与流量控制差错控制与流量控制差错控制与流量控制如何实现可靠的数据传输如何实现可靠的数据传输如何实现可靠的数据传输如何实现可靠的数据传输如何将解决上述问题的机制或方法以协议的形式如何将解决上述问题的机制或方法以协议的形式如何将解决上述问题的机制或方法以协议的形式
13、如何将解决上述问题的机制或方法以协议的形式统一表达出来。统一表达出来。统一表达出来。统一表达出来。帧与成帧帧与成帧SectionTwo本节驱动问题本节驱动问题“帧帧”有什么作用？有什么作用？帧通常包括哪几部分？帧通常包括哪几部分？为什么要进行为什么要进行“成帧成帧”和和“拆帧拆帧”？如何区分不同的帧？如何区分不同的帧？帧帧(Frame)为了实现诸如差错控制、物理寻址和流量控制为了实现诸如差错控制、物理寻址和流量控制等功能，数据链路层首先要使自己所看到的数等功能，数据链路层首先要使自己所看到的数据是有意义的据是有意义的 除了要传送的用户数据外，还要提供关于除了要传送的用户数据外，还要提供关于寻址
14、、差错控制和流量控制等所必需的控制信寻址、差错控制和流量控制等所必需的控制信息，而不再是物理层的原始比特流。息，而不再是物理层的原始比特流。为此，数据链路层采用了被称为帧为此，数据链路层采用了被称为帧(frame)的的协议数据单元作为该层的数据传送逻辑单元。协议数据单元作为该层的数据传送逻辑单元。数据链路层协议的核心任务就是根据所要实现数据链路层协议的核心任务就是根据所要实现的数据链路层功能来规定帧的格式，即的数据链路层功能来规定帧的格式，即语法和语法和语义语义。帧的一般示意图帧的一般示意图帧中的语法成分被称为域或字段帧中的语法成分被称为域或字段(field)；帧浓缩了与数据链路层功能实现相关
15、的各种机制帧浓缩了与数据链路层功能实现相关的各种机制帧提高了数据处理和传输的效率帧提高了数据处理和传输的效率不同的数据链路层协议的帧格式可能会存在微小的区别。不同的数据链路层协议的帧格式可能会存在微小的区别。帧的开始帧的开始地址地址帧类型或长度帧类型或长度数据数据帧的结束帧的结束帧校验帧校验FCS帧的定界帧的定界用于寻址用于寻址差错控制差错控制帧头帧头帧尾帧尾帧的地址帧的地址帧中的地址属于物理或硬件地址帧中的地址属于物理或硬件地址 网卡地址网卡地址(局域网局域网)链路标识链路标识(广域网广域网)用于设备或机器的物理寻址用于设备或机器的物理寻址成帧与成帧与拆帧拆帧成帧成帧(Framing)：数据
16、链路层的封装，从网络层获得分组（Packet)后，加上必要的帧头与帧尾后交给物理层数据数据帧的开始帧的开始地址地址帧类型帧类型/长度长度帧头帧头帧的结束帧的结束帧校验帧校验FCS帧尾帧尾分组分组帧的开始帧的开始地址地址帧类型帧类型/长度长度数据数据帧的结束帧的结束帧校验帧校验FCS帧头帧头帧尾帧尾分组分组物理链路物理链路-原始比特流原始比特流确认自己是目标节点FCS 校验正确拆帧：数据链路层拆封，去掉发送端数据链路层所加的帧头和帧尾，从中分离出网络层所需的分组交给网络层.帧的定界帧的定界定界：标识帧的开始与结束定界：标识帧的开始与结束常用方法：常用方法：字符计数法字符计数法带字符填充的首尾界符
17、法带字符填充的首尾界符法带位填充的首尾标志法带位填充的首尾标志法字符计数法字符计数法在帧头中使用一个字段来标明帧内的字符数，在帧头中使用一个字段来标明帧内的字符数，通常该字段称为帧长字段。通常该字段称为帧长字段。如果发生传输错误，则可能更改帧长的值，从如果发生传输错误，则可能更改帧长的值，从而导致帧的同步出现问题。而导致帧的同步出现问题。该方法通常与下面介绍的其他方法结合使用。该方法通常与下面介绍的其他方法结合使用。6ABCDE5UVWX81234458三个帧的长度分三个帧的长度分别为别为6字节、字节、5字字节和节和8字节。字节。6ABCDE7UVWX81234458？首尾界符法首尾界符法每一
18、帧以每一帧以ASCII字符序列字符序列DLESTX开始，以开始，以DLEETX结束。结束。DLE为为“DataLinkEscape”的缩写，的缩写，STX意味着意味着“StartofText”，ETX代表代表“EndofText”。其缺点是成帧完全依赖于其缺点是成帧完全依赖于8位字符，而且若位字符，而且若数据部分也数据部分也出现了出现了DLESTX或或DLEETX，则接收端就会错误判断则接收端就会错误判断帧边界。帧边界。DLEDataDLESTXETX首尾界符法中的字符填充首尾界符法中的字符填充在首尾界符法中，由于数据中可能会出现在首尾界符法中，由于数据中可能会出现DLESTX或或DLEETX
19、，从而干扰帧的正常定界从而干扰帧的正常定界字符填充法可用于解决上述问题。即发送端在数据中所字符填充法可用于解决上述问题。即发送端在数据中所遇到的遇到的DLE前再插入一个附加的前再插入一个附加的DLE，而接收端则忽略而接收端则忽略两个连续两个连续DLE的前一个。的前一个。DataDLE STXDLE ETXDLEDLE ETXDLEDLE STXDLE首尾标记法首尾标记法每一帧使用一个特殊的位模式每一帧使用一个特殊的位模式“01111110”作为开始作为开始和结束标记。和结束标记。该位模式又称为该位模式又称为“flag”。位模式允许数据帧包含任意个数的比特，也允许每个位模式允许数据帧包含任意个数
20、的比特，也允许每个字符采用任意比特的编码。字符采用任意比特的编码。Data0111111001111110首尾标记法中的位填充首尾标记法中的位填充在首尾标记法中，由于数据中可能会出现与标记相同的在首尾标记法中，由于数据中可能会出现与标记相同的位串，从而干扰帧的正常定界位串，从而干扰帧的正常定界位填充法可用于解决上述问题。即发送端在数据中若遇位填充法可用于解决上述问题。即发送端在数据中若遇到到5个连续的个连续的“1”时，则在其后自动插队入一个时，则在其后自动插队入一个“0”。该技术简称该技术简称“逢五逢五1插插0”；接收端则忽略；接收端则忽略5个连续的个连续的“1”后面的后面的“0”，简称，简称
21、“逢五逢五1删删0”。Data0111111001111110111111111110011111100111111011111011111100零比特插入零比特插入/删除过程示例删除过程示例物理层编码违例法物理层编码违例法利用物理层信息编码中未用的电信号来作为帧的利用物理层信息编码中未用的电信号来作为帧的边界。边界。以以IEEE802局域网标准为例，其数据编码局域网标准为例，其数据编码采用曼彻斯特编码，在传输之前将数据位采用曼彻斯特编码，在传输之前将数据位“1”编码成高编码成高-低电平对，数据位低电平对，数据位“0”编码成低编码成低-高高电平对，并利用高电平对，并利用高-高电平对和低高电平对
22、和低-低电平对作为低电平对作为帧边界的特殊编码。帧边界的特殊编码。在实际应用中，数据链路层协议多数使用字符计在实际应用中，数据链路层协议多数使用字符计数法与其他方法相结合作为帧定界的方法数法与其他方法相结合作为帧定界的方法 差错控制差错控制SectionThree本节驱动问题本节驱动问题为什么要进行差错控制？为什么要进行差错控制？数数据据链链路路层层如如何何得得知知“帧帧”在在传传输输过过程程中出错了？中出错了？有哪些常用的机制？有哪些常用的机制？差错的类型、原因与衡量差错的类型、原因与衡量物理信道中所存在的各类噪声，会引起数据传物理信道中所存在的各类噪声，会引起数据传物理信道中所存在的各类噪
23、声，会引起数据传物理信道中所存在的各类噪声，会引起数据传输中的错误，误码率：输中的错误，误码率：输中的错误，误码率：输中的错误，误码率：P P P Pe e e e=错误接收的码元数错误接收的码元数错误接收的码元数错误接收的码元数/接收的码元总数接收的码元总数接收的码元总数接收的码元总数根据噪声产生原因的不同，差错分为根据噪声产生原因的不同，差错分为根据噪声产生原因的不同，差错分为根据噪声产生原因的不同，差错分为随机错和随机错和随机错和随机错和突发错。突发错。突发错。突发错。热噪声热噪声热噪声热噪声随机错随机错随机错随机错 冲击噪声（如冲击噪声（如冲击噪声（如冲击噪声（如EMIEMIEMIEM
24、I，RFIRFIRFIRFI）突发错突发错突发错突发错信道中的噪声是客观存在的信道中的噪声是客观存在的信道中的噪声是客观存在的信道中的噪声是客观存在的 不管信道质量多高，无论通过哪种类型传输介质或不管信道质量多高，无论通过哪种类型传输介质或不管信道质量多高，无论通过哪种类型传输介质或不管信道质量多高，无论通过哪种类型传输介质或信道进行数据传输，误码率都不可能是零信道进行数据传输，误码率都不可能是零信道进行数据传输，误码率都不可能是零信道进行数据传输，误码率都不可能是零差错控制差错控制差错控制：发现传输中的错误，并采取相应的差错控制：发现传输中的错误，并采取相应的差错控制：发现传输中的错误，并采
25、取相应的差错控制：发现传输中的错误，并采取相应的措施降低数据传输错误的影响。措施降低数据传输错误的影响。措施降低数据传输错误的影响。措施降低数据传输错误的影响。差错控制的核心：发送端对传送的数据信息加差错控制的核心：发送端对传送的数据信息加差错控制的核心：发送端对传送的数据信息加差错控制的核心：发送端对传送的数据信息加上与其满足一定关系的冗余码上与其满足一定关系的冗余码上与其满足一定关系的冗余码上与其满足一定关系的冗余码(校验码校验码校验码校验码)，形成，形成，形成，形成一个加强的、符合一定规律的发送序列。一个加强的、符合一定规律的发送序列。一个加强的、符合一定规律的发送序列。一个加强的、符合
26、一定规律的发送序列。接收端利用相同的规律进行检查从而发现错误接收端利用相同的规律进行检查从而发现错误接收端利用相同的规律进行检查从而发现错误接收端利用相同的规律进行检查从而发现错误校验码按校验错误能力的不同被分为：校验码按校验错误能力的不同被分为：校验码按校验错误能力的不同被分为：校验码按校验错误能力的不同被分为：纠错码纠错码纠错码纠错码 检错码检错码检错码检错码纠错码纠错码每个传输的分组带上足够的冗余信息，使每个传输的分组带上足够的冗余信息，使接收方不仅能发现传输中的错误，还能利接收方不仅能发现传输中的错误，还能利用纠错码中的信息自动纠正错误。用纠错码中的信息自动纠正错误。对应的差错控制措施
27、为自动向前纠错。对应的差错控制措施为自动向前纠错。汉明码（汉明码（Hamming code)Hamming code)为典型的纠错码，为典型的纠错码，具有很高的纠错能力。具有很高的纠错能力。有兴趣的同学请自行查找有关的参考资料，如有兴趣的同学请自行查找有关的参考资料，如有兴趣的同学请自行查找有关的参考资料，如有兴趣的同学请自行查找有关的参考资料，如AndrewAndrewAndrewAndrew著计算机网络（第著计算机网络（第著计算机网络（第著计算机网络（第4 4 4 4版）清华大学出版社。版）清华大学出版社。版）清华大学出版社。版）清华大学出版社。检错码检错码仅包含足以使接收端检发现差错的仅
28、包含足以使接收端检发现差错的冗余信息，使得接收方能发现传输冗余信息，使得接收方能发现传输中的错误，但不能自动纠正所发现中的错误，但不能自动纠正所发现的错误。的错误。常见的检错码有：常见的检错码有：奇偶校验码奇偶校验码奇偶校验码奇偶校验码 循环冗余校验码（循环冗余校验码（循环冗余校验码（循环冗余校验码（CRCCRCCRCCRC）奇偶校验奇偶校验水平奇偶校验水平奇偶校验：在面向字符的数据传输中，在每个字符的在面向字符的数据传输中，在每个字符的在面向字符的数据传输中，在每个字符的在面向字符的数据传输中，在每个字符的7 7 7 7位信息位信息位信息位信息码后附加一个校验位码后附加一个校验位码后附加一个
29、校验位码后附加一个校验位0 0 0 0或或或或1 1 1 1，使整个字符中，使整个字符中，使整个字符中，使整个字符中“1 1 1 1”的个数的个数的个数的个数构成奇数个（奇校验）或偶数个（偶校验）。构成奇数个（奇校验）或偶数个（偶校验）。构成奇数个（奇校验）或偶数个（偶校验）。构成奇数个（奇校验）或偶数个（偶校验）。垂直奇偶校验：垂直奇偶校验：在发送字符块的末尾附加一个校验字符，且该字符在发送字符块的末尾附加一个校验字符，且该字符在发送字符块的末尾附加一个校验字符，且该字符在发送字符块的末尾附加一个校验字符，且该字符中的第中的第中的第中的第i i i i位是针对所有字符的第位是针对所有字符的第
30、位是针对所有字符的第位是针对所有字符的第i i i i位所进行的校验。位所进行的校验。位所进行的校验。位所进行的校验。垂直水平奇偶校验垂直水平奇偶校验垂直奇偶校验和水平奇偶校验技术的综合。对每个垂直奇偶校验和水平奇偶校验技术的综合。对每个垂直奇偶校验和水平奇偶校验技术的综合。对每个垂直奇偶校验和水平奇偶校验技术的综合。对每个字符作水平校验，对整个字符块作垂直校验。字符作水平校验，对整个字符块作垂直校验。字符作水平校验，对整个字符块作垂直校验。字符作水平校验，对整个字符块作垂直校验。垂直水平奇校验的例子垂直水平奇校验的例子10001010字符字符1b1b2b3b4b5b6b7check11001
31、011字符字符211011010字符字符310101011字符字符410001010字符字符510001111字符字符510001010字符字符611101010字符字符700100000校验校验字符字符循环冗余校验循环冗余校验 循环冗余校验循环冗余校验循环冗余校验循环冗余校验 英文全称为英文全称为CyclicRedundancyCheck,简称简称CRC。工作原理工作原理工作原理工作原理多项式除法：多项式除法：被除多项式被除多项式=除式除式*商商+剩余多项式剩余多项式通信双方约定通信双方约定除式，该除式被称为生成多项式；除式，该除式被称为生成多项式；发送方将发送方将余式作为冗余信息发送给接收
32、方余式作为冗余信息发送给接收方接收方验证所收到的多项式能否为接收方验证所收到的多项式能否为生成多项式所整除，生成多项式所整除，以判断传输过程是否出错以判断传输过程是否出错。又称多项式校验又称多项式校验又称多项式校验又称多项式校验CRCCRC工作原理工作原理将待发送的二进制数序列将待发送的二进制数序列将待发送的二进制数序列将待发送的二进制数序列看成是一个多项式。看成是一个多项式。看成是一个多项式。看成是一个多项式。n n n n位位位位的数据序列对应的数据序列对应的数据序列对应的数据序列对应n-1n-1n-1n-1次多次多次多次多项式：项式：项式：项式：P(x)=aP(x)=an-1n-1x x
33、n-1n-1+a+an-2n-2x xn-2n-2 +a+a1 1x+ax+a0 0选定除式，被选作除式的选定除式，被选作除式的选定除式，被选作除式的选定除式，被选作除式的多项式称为生成多项式。多项式称为生成多项式。多项式称为生成多项式。多项式称为生成多项式。将将将将f(x)f(x)f(x)f(x)乘以乘以乘以乘以 G(x)G(x)G(x)G(x)的最高的最高的最高的最高幂次作为被除式，进行多幂次作为被除式，进行多幂次作为被除式，进行多幂次作为被除式，进行多项式除法项式除法项式除法项式除法。除法采用除法采用除法采用除法采用“加法不进位，加法不进位，加法不进位，加法不进位，减法不借位减法不借位减
34、法不借位减法不借位”的规则，即的规则，即的规则，即的规则，即相当于异或操作相当于异或操作相当于异或操作相当于异或操作。CRCCRC工作原理（续）工作原理（续）将所得到的余式多项式将所得到的余式多项式将所得到的余式多项式将所得到的余式多项式R(x)R(x)R(x)R(x)重新转换为二进制数，重新转换为二进制数，重新转换为二进制数，重新转换为二进制数，作为冗余码；作为冗余码；作为冗余码；作为冗余码；将冗余码作为校验字段的将冗余码作为校验字段的将冗余码作为校验字段的将冗余码作为校验字段的值，加在原传送数据后面，值，加在原传送数据后面，值，加在原传送数据后面，值，加在原传送数据后面，构成完整的发送序列
35、；构成完整的发送序列；构成完整的发送序列；构成完整的发送序列；接收方收到后，将完整的接收方收到后，将完整的接收方收到后，将完整的接收方收到后，将完整的接收序列用同样的生成多接收序列用同样的生成多接收序列用同样的生成多接收序列用同样的生成多项式去除。若余式为零，项式去除。若余式为零，项式去除。若余式为零，项式去除。若余式为零，则表示无差错；否则，说则表示无差错；否则，说则表示无差错；否则，说则表示无差错；否则，说明传输出现了错误。明传输出现了错误。明传输出现了错误。明传输出现了错误。或者，接收方收到后，将或者，接收方收到后，将或者，接收方收到后，将或者，接收方收到后，将数据字段用同样的生成多数据
36、字段用同样的生成多数据字段用同样的生成多数据字段用同样的生成多项式去除。若得到的余式项式去除。若得到的余式项式去除。若得到的余式项式去除。若得到的余式与校验字段的值一致，则与校验字段的值一致，则与校验字段的值一致，则与校验字段的值一致，则表示无差错；否则，说明表示无差错；否则，说明表示无差错；否则，说明表示无差错；否则，说明传输过程中出现了错误。传输过程中出现了错误。传输过程中出现了错误。传输过程中出现了错误。CRCCRC的例子的例子设所要发送的二进制数序列设所要发送的二进制数序列为为“110011”，该该6位数据序位数据序列对应的列对应的5次多项式为：次多项式为：P(x)=xP(x)=x5
37、5+x+x4 4+x+1+x+1假定选定的生成多项式为假定选定的生成多项式为G(x)=xG(x)=x4 4+x+x3 3+1+1则其相当于则其相当于1100111001，最高次，最高次数为数为4 4则被除多项式为：则被除多项式为：P(x)xP(x)x4 4 x x9 9+x+x8 8+x+x5 5+x+x4 4相当于相当于110011000000001100110000000011001110011110011000000000000111001110011001多项式除法后得到冗余码为多项式除法后得到冗余码为10011001，相应的完整发送序列，相应的完整发送序列为为110011100110
38、01CRC可以由软件或硬件来实可以由软件或硬件来实现，现多采用超大规模集成现，现多采用超大规模集成电路芯片以硬件方式实现。电路芯片以硬件方式实现。常见的常见的CRCCRC生成多项式生成多项式列入国际标准的常见生成多项式有：列入国际标准的常见生成多项式有：CRC-12CRC-12：G(x)=xG(x)=x1212+x+x1111+x+x3 3+x+x2 2+x+1+x+1CRC-16CRC-16：G(x)=xG(x)=x1616+x+x1515+x+x2 2+1+1CRC-CCITTCRC-CCITT：G(x)=xG(x)=x1616+x+x1212+x+x5 5+1+1CRC-32CRC-32
39、：G(x)=xG(x)=x3232+x+x2626+x+x2323+x+x2222+x+x1616 +x+x1212+x+x1111+x+x1010+x+x8 8+x+x7 7 +x+x5 5+x+x4 4+x+x2 2+x+1+x+1CRCCRC的检错能力的检错能力全部单个错全部单个错全部离散的二位错全部离散的二位错全部奇数个错全部奇数个错全部长度小于或等于全部长度小于或等于K K的突发错的突发错（K K为生成多项式的最为生成多项式的最高幂次）高幂次）以以1-1-（1/21/2）K-1K-1的概率检出长度为的概率检出长度为K+1K+1位的突发错位的突发错 举例：举例：K=16，能检查出小于或
40、等于能检查出小于或等于16位的所有的突位的所有的突发差错，并能以发差错，并能以1-（1/2）16-1=99.997的概率检查出长的概率检查出长度为度为17位的突发错，漏检概率为位的突发错，漏检概率为0.003%；K K越大，越大，CRCCRC的检错能力越强，但的检错能力越强，但FCSFCS字段的长度越长，字段的长度越长，校验成本越高。校验成本越高。帧检验序列帧检验序列 FCSFCS 在数据后面添加上的冗余码称为帧检验序列 FCS(Frame Check Sequence)。循环冗余检验 CRC 和帧检验序列 FCS并不等同。CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码。F
41、CS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的唯一方法。应当注意应当注意 仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接收端数据链路层接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）。要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。差错控制措施：反馈重发差错控制措施：反馈重发检错码不能自动纠正所发现的错误，需要提供一种与之检错码不能自动纠正所发现的错误，需要提供一种与之检错
42、码不能自动纠正所发现的错误，需要提供一种与之检错码不能自动纠正所发现的错误，需要提供一种与之相配套的错误纠正机制。相配套的错误纠正机制。相配套的错误纠正机制。相配套的错误纠正机制。反馈重发：当接收方检出错误的帧时，首先将错误帧丢反馈重发：当接收方检出错误的帧时，首先将错误帧丢反馈重发：当接收方检出错误的帧时，首先将错误帧丢反馈重发：当接收方检出错误的帧时，首先将错误帧丢弃，然后给发送方反馈信息，请求对方重发相应的帧。弃，然后给发送方反馈信息，请求对方重发相应的帧。弃，然后给发送方反馈信息，请求对方重发相应的帧。弃，然后给发送方反馈信息，请求对方重发相应的帧。又称自动请求重传（又称自动请求重传（
43、又称自动请求重传（又称自动请求重传（automatic repeat requestautomatic repeat requestautomatic repeat requestautomatic repeat request），），），），简简简简称称称称ARQARQARQARQ。可靠传输：差错检测、确认、重传机制可靠传输：差错检测、确认、重传机制可靠传输：差错检测、确认、重传机制可靠传输：差错检测、确认、重传机制ARQARQARQARQ的两种实现方法：的两种实现方法：的两种实现方法：的两种实现方法：停止等待方式停止等待方式停止等待方式停止等待方式、连续连续连续连续ARQARQARQARQ
44、方式方式方式方式 停止等待方式停止等待方式发送端在发出一帧之后停下来发送端在发出一帧之后停下来发送端在发出一帧之后停下来发送端在发出一帧之后停下来等待接收端的对所发送帧的确等待接收端的对所发送帧的确等待接收端的对所发送帧的确等待接收端的对所发送帧的确认认认认(acknowledgement)acknowledgement)acknowledgement)acknowledgement)。若发送方收到若发送方收到若发送方收到若发送方收到确认确认确认确认帧，表示接帧，表示接帧，表示接帧，表示接收方收方收方收方已正确已正确已正确已正确接收接收接收接收，发送方，发送方，发送方，发送方可可可可继继继继续
45、发送下一帧；续发送下一帧；续发送下一帧；续发送下一帧；若接收方收到了被损坏的数据若接收方收到了被损坏的数据若接收方收到了被损坏的数据若接收方收到了被损坏的数据帧，给发送方发送否认帧。帧，给发送方发送否认帧。帧，给发送方发送否认帧。帧，给发送方发送否认帧。停止等待方式停止等待方式(续续)Solution-Solution-Solution-Solution-超时重发机制超时重发机制超时重发机制超时重发机制:在发送方设置一个计时器在发送方设置一个计时器在发送方设置一个计时器在发送方设置一个计时器(timeout)timeout)timeout)timeout)，当发送一个帧之当发送一个帧之当发送一
46、个帧之当发送一个帧之后，就开始倒计时；若倒计时后，就开始倒计时；若倒计时后，就开始倒计时；若倒计时后，就开始倒计时；若倒计时结束确认帧还未到达，就默认结束确认帧还未到达，就默认结束确认帧还未到达，就默认结束确认帧还未到达，就默认为帧在传输过程中被丢失，主为帧在传输过程中被丢失，主为帧在传输过程中被丢失，主为帧在传输过程中被丢失，主动重新启动帧的发送动重新启动帧的发送动重新启动帧的发送动重新启动帧的发送 两种永远收不到确认帧的两种永远收不到确认帧的两种永远收不到确认帧的两种永远收不到确认帧的情况：情况：情况：情况：发送端所发送的数据帧在发送端所发送的数据帧在发送端所发送的数据帧在发送端所发送的数
47、据帧在传输过程被丢失传输过程被丢失传输过程被丢失传输过程被丢失接收端发送给发送方的确接收端发送给发送方的确接收端发送给发送方的确接收端发送给发送方的确认帧被丢失认帧被丢失认帧被丢失认帧被丢失 可能造成重复接收可能造成重复接收解决方法解决方法为帧编号为帧编号优点：比较简单。缺点：通信信道的利用率不高，也就是说，信道还远远没有被数据比特填满。连续连续ARQARQ方式方式在发送完一个数据帧后，不是停下来等待确在发送完一个数据帧后，不是停下来等待确在发送完一个数据帧后，不是停下来等待确在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧认帧，而是可以连续再发送若干个数据帧认帧，而
48、是可以连续再发送若干个数据帧认帧，而是可以连续再发送若干个数据帧为不同的帧加上序列号以作为帧的标识；为不同的帧加上序列号以作为帧的标识；为不同的帧加上序列号以作为帧的标识；为不同的帧加上序列号以作为帧的标识；由于减少了等待时间，整个通信的吞吐量就由于减少了等待时间，整个通信的吞吐量就由于减少了等待时间，整个通信的吞吐量就由于减少了等待时间，整个通信的吞吐量就提高了。提高了。提高了。提高了。帧传输出现差错时，有两种帧传输出现差错时，有两种帧传输出现差错时，有两种帧传输出现差错时，有两种反馈重发方式：反馈重发方式：反馈重发方式：反馈重发方式：拉回拉回拉回拉回(back to n)back to n
49、)back to n)back to n)选择重发选择重发选择重发选择重发(selective repeat)selective repeat)selective repeat)selective repeat)连续连续ARQARQ方式：拉回方式：拉回含义：含义：假定发送方连续发送了假定发送方连续发送了假定发送方连续发送了假定发送方连续发送了m m m m帧，而接收方在帧，而接收方在帧，而接收方在帧，而接收方在对收到的数据帧进行校验后发现第对收到的数据帧进行校验后发现第对收到的数据帧进行校验后发现第对收到的数据帧进行校验后发现第n n n n帧出错帧出错帧出错帧出错（n n n nm)m)m)
50、m)，于是接收方给发送方出错信息要，于是接收方给发送方出错信息要，于是接收方给发送方出错信息要，于是接收方给发送方出错信息要求发送方重发第求发送方重发第求发送方重发第求发送方重发第n n n n帧及第帧及第帧及第帧及第n n n n帧以后的所有帧。帧以后的所有帧。帧以后的所有帧。帧以后的所有帧。换言之，一旦接收方发现第换言之，一旦接收方发现第换言之，一旦接收方发现第换言之，一旦接收方发现第n n n n帧出错，则帧出错，则帧出错，则帧出错，则丢弃第丢弃第丢弃第丢弃第n n n n帧及第帧及第帧及第帧及第n n n n帧以后的所有帧。帧以后的所有帧。帧以后的所有帧。帧以后的所有帧。代价代价 信道