五章节数据链路控制及其协议.ppt

《五章节数据链路控制及其协议.ppt》由会员分享，可在线阅读，更多相关《五章节数据链路控制及其协议.ppt（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、五章节数据链路控制及其协议 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望主要内容5.15.1定义和功能定义和功能定义和功能定义和功能5.1.15.1.1定义定义定义定义5.1.25.1.2为网络层提供服务为网络层提供服务为网络层提供服务为网络层提供服务5.1.35.1.3成帧成帧成帧成帧5.1.45.1.4差错控制差错控制差错控制差错控制5.1.55.1.5流量控制流量控制流量控制流量控制5.25.2错误检测和纠正错误检测和纠正错误检测和纠正错误检测和纠正5.2

2、.15.2.1纠错码纠错码纠错码纠错码5.2.25.2.2检错码检错码检错码检错码5.35.3基本的数据链路层协议基本的数据链路层协议基本的数据链路层协议基本的数据链路层协议 5.3.1 5.3.1无约束单工协议无约束单工协议无约束单工协议无约束单工协议 5.3.2 5.3.2单工停等协议单工停等协议单工停等协议单工停等协议 5.3.3 5.3.3有噪声信道的单工协议有噪声信道的单工协议有噪声信道的单工协议有噪声信道的单工协议5.45.4滑动窗口协议滑动窗口协议滑动窗口协议滑动窗口协议 5.4.1 5.4.1一比特滑动窗口协议一比特滑动窗口协议一比特滑动窗口协议一比特滑动窗口协议 5.4.2

3、5.4.2退后退后退后退后n n帧协议帧协议帧协议帧协议 5.4.3 5.4.3选择重传协议选择重传协议选择重传协议选择重传协议5.55.5协议说明与验证协议说明与验证协议说明与验证协议说明与验证 5.5.1 5.5.1通信协议中的形式化描述技术通信协议中的形式化描述技术通信协议中的形式化描述技术通信协议中的形式化描述技术 5.5.2 5.5.2有限状态机模型有限状态机模型有限状态机模型有限状态机模型 5.5.3 5.5.3PetriPetri网模型网模型网模型网模型5.65.6常用的数据链路层协议常用的数据链路层协议常用的数据链路层协议常用的数据链路层协议5.6.15.6.1高级数据链路控制

4、规程高级数据链路控制规程高级数据链路控制规程高级数据链路控制规程 HDLC HDLC5.6.25.6.2X.25X.25的链路层协议的链路层协议的链路层协议的链路层协议LAPBLAPB5.6.35.6.3InternetInternet数据链路层协议数据链路层协议数据链路层协议数据链路层协议5.6.45.6.4ATMATM数据链路层协议数据链路层协议数据链路层协议数据链路层协议5.1 定义和功能（1）5.1.1 5.1.1 定义定义定义定义n n要解决的问题要解决的问题要解决的问题要解决的问题 如何在有差错的线路上，进行无差错传输。如何在有差错的线路上，进行无差错传输。如何在有差错的线路上，进

5、行无差错传输。如何在有差错的线路上，进行无差错传输。n nISOISO关于数据链路层的定义关于数据链路层的定义关于数据链路层的定义关于数据链路层的定义 数据链路层的目的是为了提供功能上和规程上的方法，以便建数据链路层的目的是为了提供功能上和规程上的方法，以便建数据链路层的目的是为了提供功能上和规程上的方法，以便建数据链路层的目的是为了提供功能上和规程上的方法，以便建立、维护和释放网络实体间的数据链路。立、维护和释放网络实体间的数据链路。立、维护和释放网络实体间的数据链路。立、维护和释放网络实体间的数据链路。n n结点（结点（结点（结点（nodenode）：网络中的主机（）：网络中的主机（）：网

6、络中的主机（）：网络中的主机（hosthost）和路由器）和路由器）和路由器）和路由器（routerrouter）称为结点）称为结点）称为结点）称为结点n n链路（链路（链路（链路（linklink）：通信路径上连接相邻结点的通信信道称为）：通信路径上连接相邻结点的通信信道称为）：通信路径上连接相邻结点的通信信道称为）：通信路径上连接相邻结点的通信信道称为链路。链路。链路。链路。n n数据链路层协议定义了一条链路的两个结点间交换的数据数据链路层协议定义了一条链路的两个结点间交换的数据数据链路层协议定义了一条链路的两个结点间交换的数据数据链路层协议定义了一条链路的两个结点间交换的数据单元格式，以

7、及结点发送和接收数据单元的动作。单元格式，以及结点发送和接收数据单元的动作。单元格式，以及结点发送和接收数据单元的动作。单元格式，以及结点发送和接收数据单元的动作。5.1 定义和功能（2）n n端到端（端到端（端到端（端到端（end to endend to end）与点到点（）与点到点（）与点到点（）与点到点（point to point to pointpoint）从源结点（从源结点（从源结点（从源结点（source nodesource node）到目的结点）到目的结点）到目的结点）到目的结点（destination nodedestination node）的通信称为端到端通信，通）的

8、通信称为端到端通信，通）的通信称为端到端通信，通）的通信称为端到端通信，通信路径（信路径（信路径（信路径（pathpath）可能由多个链路组成。）可能由多个链路组成。）可能由多个链路组成。）可能由多个链路组成。在相邻结点间的一条链路上的通信称为点到点通信。在相邻结点间的一条链路上的通信称为点到点通信。在相邻结点间的一条链路上的通信称为点到点通信。在相邻结点间的一条链路上的通信称为点到点通信。n n虚拟数据通路，实际数据通路虚拟数据通路，实际数据通路虚拟数据通路，实际数据通路虚拟数据通路，实际数据通路 Fig.3-1Fig.3-15.1 定义和功能（2）n n数据链路控制规程数据链路控制规程数据

9、链路控制规程数据链路控制规程 为使数据能迅速、正确、有效地从发送点到达接收点为使数据能迅速、正确、有效地从发送点到达接收点为使数据能迅速、正确、有效地从发送点到达接收点为使数据能迅速、正确、有效地从发送点到达接收点所采用的控制方式。所采用的控制方式。所采用的控制方式。所采用的控制方式。n n数据链路层协议应提供的最基本功能数据链路层协议应提供的最基本功能数据链路层协议应提供的最基本功能数据链路层协议应提供的最基本功能 数据在数据链路上的正常传输（建立、维护和释放）数据在数据链路上的正常传输（建立、维护和释放）数据在数据链路上的正常传输（建立、维护和释放）数据在数据链路上的正常传输（建立、维护和

10、释放）定界与同步，也处理透明性问题定界与同步，也处理透明性问题定界与同步，也处理透明性问题定界与同步，也处理透明性问题 差错控制差错控制差错控制差错控制 顺序控制顺序控制顺序控制顺序控制 流量控制流量控制流量控制流量控制5.1 定义和功能（3）5.1.2 为网络层提供服务为网络层提供服务n n为网络层提供三种合理的服务为网络层提供三种合理的服务无确认无连接服务，无确认无连接服务，无确认无连接服务，无确认无连接服务，适用于适用于适用于适用于n n误码率很低的线路，错误恢复留给高层；误码率很低的线路，错误恢复留给高层；误码率很低的线路，错误恢复留给高层；误码率很低的线路，错误恢复留给高层；n n实

11、时业务实时业务实时业务实时业务n n大部分局域网大部分局域网大部分局域网大部分局域网有确认无连接服务，有确认无连接服务，有确认无连接服务，有确认无连接服务，适用于不可靠的信道，如无线适用于不可靠的信道，如无线适用于不可靠的信道，如无线适用于不可靠的信道，如无线网。网。网。网。有确认有连接服务有确认有连接服务有确认有连接服务有确认有连接服务5.1 定义和功能（4）5.1.3 5.1.3 成帧（成帧（成帧（成帧（FramingFraming）n n将比特流分成离散的帧，并计算每个帧的校验和。将比特流分成离散的帧，并计算每个帧的校验和。将比特流分成离散的帧，并计算每个帧的校验和。将比特流分成离散的帧

12、，并计算每个帧的校验和。n n成帧方法：成帧方法：成帧方法：成帧方法：字符计数法字符计数法字符计数法字符计数法n n在帧头中用一个域来表示整个帧的字符个数在帧头中用一个域来表示整个帧的字符个数在帧头中用一个域来表示整个帧的字符个数在帧头中用一个域来表示整个帧的字符个数n n缺点：若计数出错，对本帧和后面的帧有影响。缺点：若计数出错，对本帧和后面的帧有影响。缺点：若计数出错，对本帧和后面的帧有影响。缺点：若计数出错，对本帧和后面的帧有影响。n nFig.3-3Fig.3-3 带字符填充的首尾字符定界法带字符填充的首尾字符定界法带字符填充的首尾字符定界法带字符填充的首尾字符定界法n n起始字符起始

13、字符起始字符起始字符 DLE STX DLE STX，结束字符，结束字符，结束字符，结束字符DLE ETXDLE ETXn n字符填充字符填充字符填充字符填充n nFig.3-4Fig.3-4n n缺点：局限于缺点：局限于缺点：局限于缺点：局限于8 8位字符和位字符和位字符和位字符和ASCIIASCII字符传送。字符传送。字符传送。字符传送。5.1 定义和功能（5）带位填充的首尾标记定界法带位填充的首尾标记定界法带位填充的首尾标记定界法带位填充的首尾标记定界法n n帧的起始和结束都用一个特殊的位串帧的起始和结束都用一个特殊的位串帧的起始和结束都用一个特殊的位串帧的起始和结束都用一个特殊的位串“

14、01111110”“01111110”，称为标记，称为标记，称为标记，称为标记(flag)(flag)n n“0”“0”比特插入删除技术比特插入删除技术比特插入删除技术比特插入删除技术n nFig.3-5Fig.3-5 物理层编码违例法物理层编码违例法物理层编码违例法物理层编码违例法n n只适用于物理层编码有冗余的网络只适用于物理层编码有冗余的网络只适用于物理层编码有冗余的网络只适用于物理层编码有冗余的网络n n802 LAN802 LAN：Manchester encoding or Differential Manchester encoding or Differential Manch

15、ester encoding Manchester encoding 用用用用high-low pair/low-high high-low pair/low-high pairpair表示表示表示表示1/01/0，high-high/low-lowhigh-high/low-low不表示数据，可以用不表示数据，可以用不表示数据，可以用不表示数据，可以用来做定界符。来做定界符。来做定界符。来做定界符。n n注意：在很多数据链路协议中，使用字符计数法注意：在很多数据链路协议中，使用字符计数法注意：在很多数据链路协议中，使用字符计数法注意：在很多数据链路协议中，使用字符计数法和一种其它方法的组合。

16、和一种其它方法的组合。和一种其它方法的组合。和一种其它方法的组合。5.1 定义和功能（6）5.1.4 5.1.4 差错控制差错控制差错控制差错控制n n一般方法：接收方给发送方一个反馈（响应）。一般方法：接收方给发送方一个反馈（响应）。一般方法：接收方给发送方一个反馈（响应）。一般方法：接收方给发送方一个反馈（响应）。n n出错情况出错情况出错情况出错情况 帧（包括发送帧和响应帧）出错；帧（包括发送帧和响应帧）出错；帧（包括发送帧和响应帧）出错；帧（包括发送帧和响应帧）出错；帧（包括发送帧和响应帧）丢失帧（包括发送帧和响应帧）丢失帧（包括发送帧和响应帧）丢失帧（包括发送帧和响应帧）丢失n n通

17、过计时器和序号保证每帧最终交给目的网络层通过计时器和序号保证每帧最终交给目的网络层通过计时器和序号保证每帧最终交给目的网络层通过计时器和序号保证每帧最终交给目的网络层仅一次是数据链路层的一个主要功能。仅一次是数据链路层的一个主要功能。仅一次是数据链路层的一个主要功能。仅一次是数据链路层的一个主要功能。5.1.5 5.1.5 流量控制流量控制流量控制流量控制n n基于反馈机制基于反馈机制基于反馈机制基于反馈机制n n流量控制主要在传输层实现流量控制主要在传输层实现流量控制主要在传输层实现流量控制主要在传输层实现5.2 错误检测和纠正（1）n n差错出现的特点：随机，连续突发（差错出现的特点：随机

18、，连续突发（差错出现的特点：随机，连续突发（差错出现的特点：随机，连续突发（burstburst）n n处理差错的两种基本策略处理差错的两种基本策略处理差错的两种基本策略处理差错的两种基本策略 使用纠错码：发送方在每个数据块中加入足够的冗余信息，使用纠错码：发送方在每个数据块中加入足够的冗余信息，使用纠错码：发送方在每个数据块中加入足够的冗余信息，使用纠错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误。使得接收方能够判断接收到的数据是否有错，并能纠正错误。使得接收方能够判断接收到的数据是否有错，并能纠正错误。使得接收方能够判断接收到的数据是否有

19、错，并能纠正错误。使用检错码：发送方在每个数据块中加入足够的冗余信息，使用检错码：发送方在每个数据块中加入足够的冗余信息，使用检错码：发送方在每个数据块中加入足够的冗余信息，使用检错码：发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，但不能判断哪使得接收方能够判断接收到的数据是否有错，但不能判断哪使得接收方能够判断接收到的数据是否有错，但不能判断哪使得接收方能够判断接收到的数据是否有错，但不能判断哪里有错。里有错。里有错。里有错。5.2.15.2.1纠错码纠错码纠错码纠错码n n码字（码字（码字（码字（codewordcodeword）：一个帧包括）：一个帧包括

20、）：一个帧包括）：一个帧包括mm个数据位，个数据位，个数据位，个数据位，r r个个个个校验位，校验位，校验位，校验位，n=m+rn=m+r，则此，则此，则此，则此n n比特单元称为比特单元称为比特单元称为比特单元称为n n位码字。位码字。位码字。位码字。n n海明距离（海明距离（海明距离（海明距离（Hamming distanceHamming distance）：两个码字之间）：两个码字之间）：两个码字之间）：两个码字之间不同的比特位数目。不同的比特位数目。不同的比特位数目。不同的比特位数目。5.2 错误检测和纠正（2）例：例：例：例：0000000000 0000000000 与与与与00

21、000111110000011111的海明距离为的海明距离为的海明距离为的海明距离为5 5 如果两个码字的海明距离为如果两个码字的海明距离为如果两个码字的海明距离为如果两个码字的海明距离为d d，则需要，则需要，则需要，则需要d d个单比特错就可以把一个个单比特错就可以把一个个单比特错就可以把一个个单比特错就可以把一个码字转换成另一个码字；码字转换成另一个码字；码字转换成另一个码字；码字转换成另一个码字；为了检查出为了检查出为了检查出为了检查出d d个错（单比特错），需要使用海明距离为个错（单比特错），需要使用海明距离为个错（单比特错），需要使用海明距离为个错（单比特错），需要使用海明距离为

22、d+1 d+1 的的的的编码；编码；编码；编码；为了纠正为了纠正为了纠正为了纠正d d个错，需要使用海明距离为个错，需要使用海明距离为个错，需要使用海明距离为个错，需要使用海明距离为 2d+1 2d+1 的编码；的编码；的编码；的编码；n n最简单的例子是奇偶校验，在数据后填加一个奇偶位最简单的例子是奇偶校验，在数据后填加一个奇偶位最简单的例子是奇偶校验，在数据后填加一个奇偶位最简单的例子是奇偶校验，在数据后填加一个奇偶位（parity bitparity bit）例：使用偶校验（例：使用偶校验（例：使用偶校验（例：使用偶校验（“1”“1”的个数为偶数）的个数为偶数）的个数为偶数）的个数为偶数

23、）10110101101101011011010111011010111011000110110001101100010101100010 奇偶校验可以用来检查单个错误。奇偶校验可以用来检查单个错误。奇偶校验可以用来检查单个错误。奇偶校验可以用来检查单个错误。5.2 错误检测和纠正（3）n n设计纠错码设计纠错码设计纠错码设计纠错码 要求：要求：要求：要求：mm个信息位，个信息位，个信息位，个信息位，r r个校验位，纠正单比特错；个校验位，纠正单比特错；个校验位，纠正单比特错；个校验位，纠正单比特错；对对对对2 2mm个有效信息中任何一个，有个有效信息中任何一个，有个有效信息中任何一个，有个有

24、效信息中任何一个，有n n个与其距离为个与其距离为个与其距离为个与其距离为1 1的无效码字，的无效码字，的无效码字，的无效码字，因此有：因此有：因此有：因此有：(n+1)2(n+1)2mm 2 2n n 利用利用利用利用 n=m+r n=m+r，得到，得到，得到，得到(m+r+1)(m+r+1)2 2r r 给定给定给定给定mm，利用该式可以得出校正单比特误码的校验位数目的下，利用该式可以得出校正单比特误码的校验位数目的下，利用该式可以得出校正单比特误码的校验位数目的下，利用该式可以得出校正单比特误码的校验位数目的下界界界界n n海明码海明码海明码海明码 码位从左边开始编号，从码位从左边开始编

25、号，从码位从左边开始编号，从码位从左边开始编号，从“1”“1”开始；开始；开始；开始；位号为位号为位号为位号为2 2的幂的位是校验位，其余是信息位；的幂的位是校验位，其余是信息位；的幂的位是校验位，其余是信息位；的幂的位是校验位，其余是信息位；每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）每个校验位使得包括自己在内的一些位的奇偶值为偶数（或奇数）。为看清数据位为看清数据位为看清数据位为看清数据位k k对哪些校验位有影响，将对哪些校验位有影响，将对哪些校验位有影响，将对

26、哪些校验位有影响，将k k写成写成写成写成2 2的幂的和。的幂的和。的幂的和。的幂的和。例：例：例：例：11=1+2+811=1+2+85.2 错误检测和纠正（4）n n海明码工作过程海明码工作过程海明码工作过程海明码工作过程 每个码字到来前，接收方计数器清零；每个码字到来前，接收方计数器清零；每个码字到来前，接收方计数器清零；每个码字到来前，接收方计数器清零；接收方检查每个校验位接收方检查每个校验位接收方检查每个校验位接收方检查每个校验位k(k=1,2,4)k(k=1,2,4)的奇偶值是否正的奇偶值是否正的奇偶值是否正的奇偶值是否正确；确；确；确；若第若第若第若第 k k 位奇偶值不对，计数

27、器加位奇偶值不对，计数器加位奇偶值不对，计数器加位奇偶值不对，计数器加 k k；所有校验位检查完后，若计数器值为所有校验位检查完后，若计数器值为所有校验位检查完后，若计数器值为所有校验位检查完后，若计数器值为0 0，则码字有效；若计数，则码字有效；若计数，则码字有效；若计数，则码字有效；若计数器值为器值为器值为器值为mm，则第，则第，则第，则第mm位出错。位出错。位出错。位出错。若校验位若校验位若校验位若校验位1 1、2 2、8 8出错，则第出错，则第出错，则第出错，则第1111位变反。位变反。位变反。位变反。Fig.3-6Fig.3-6n n使用海明码纠正突发错误使用海明码纠正突发错误使用海

28、明码纠正突发错误使用海明码纠正突发错误 可采用可采用可采用可采用k k个码字（个码字（个码字（个码字（n=m+rn=m+r）组成组成组成组成 k k n n 矩阵，按列发送，矩阵，按列发送，矩阵，按列发送，矩阵，按列发送，接收方恢复成接收方恢复成接收方恢复成接收方恢复成 k k n n 矩阵矩阵矩阵矩阵 krkr个校验位，个校验位，个校验位，个校验位，kmkm个数据位，可纠正最多为个数据位，可纠正最多为个数据位，可纠正最多为个数据位，可纠正最多为k k个的突发性连续个的突发性连续个的突发性连续个的突发性连续比特错。比特错。比特错。比特错。1 2 3 4 5 6 7 8 9 10 11 1 1

29、1 1 1 2 2 2 2 2 4 4 4 8 8 85.2 错误检测和纠正（5）5.2.2 5.2.2 检错码检错码检错码检错码n n使用纠错码传数据，效率低，适用于不可能重传的场合；使用纠错码传数据，效率低，适用于不可能重传的场合；使用纠错码传数据，效率低，适用于不可能重传的场合；使用纠错码传数据，效率低，适用于不可能重传的场合；大多数情况采用检错码加重传。大多数情况采用检错码加重传。大多数情况采用检错码加重传。大多数情况采用检错码加重传。n n循环冗余码（循环冗余码（循环冗余码（循环冗余码（CRCCRC码，多项式编码）码，多项式编码）码，多项式编码）码，多项式编码）11000111000

30、1，表示成多项式，表示成多项式，表示成多项式，表示成多项式 x x5 5+x+x4 4+1+1n n生成多项式生成多项式生成多项式生成多项式G(x)G(x)发方、收方事前商定；发方、收方事前商定；发方、收方事前商定；发方、收方事前商定；生成多项式的高位和低位必须为生成多项式的高位和低位必须为生成多项式的高位和低位必须为生成多项式的高位和低位必须为1 1 生成多项式必须比传输信息对应的多项式短。生成多项式必须比传输信息对应的多项式短。生成多项式必须比传输信息对应的多项式短。生成多项式必须比传输信息对应的多项式短。n nCRCCRC码基本思想码基本思想码基本思想码基本思想 校验和（校验和（校验和（

31、校验和（checksumchecksum）加在帧尾，使带校验和的帧的多项式能被）加在帧尾，使带校验和的帧的多项式能被）加在帧尾，使带校验和的帧的多项式能被）加在帧尾，使带校验和的帧的多项式能被G(x)G(x)除尽；收方接收时，用除尽；收方接收时，用除尽；收方接收时，用除尽；收方接收时，用G(x)G(x)去除它，若有余数，则传输出去除它，若有余数，则传输出去除它，若有余数，则传输出去除它，若有余数，则传输出错。错。错。错。5.2 错误检测和纠正（6）n n校验和计算算法校验和计算算法校验和计算算法校验和计算算法 设设设设G(x)G(x)为为为为 r r 阶，在阶，在阶，在阶，在帧的末尾加帧的末尾

32、加帧的末尾加帧的末尾加 r r 个个个个0 0，使帧为，使帧为，使帧为，使帧为m+rm+r位，位，位，位，相应多项式为相应多项式为相应多项式为相应多项式为x xr rM(x)M(x)；按模按模按模按模2 2除法用对应于除法用对应于除法用对应于除法用对应于G(x)G(x)的位串去除对应于的位串去除对应于的位串去除对应于的位串去除对应于x xr rM(x)M(x)的位的位的位的位串；串；串；串；按模按模按模按模2 2减法从对应于减法从对应于减法从对应于减法从对应于x xr rM(x)M(x)的位串中减去余数（等于或小的位串中减去余数（等于或小的位串中减去余数（等于或小的位串中减去余数（等于或小于于

33、于于r r位），结果就是要传送的带校验和的多项式位），结果就是要传送的带校验和的多项式位），结果就是要传送的带校验和的多项式位），结果就是要传送的带校验和的多项式T(x)T(x)。Fig.3-7Fig.3-7n nCRCCRC的检错能力的检错能力的检错能力的检错能力 发送：发送：发送：发送：T(x)T(x)；接收：；接收：；接收：；接收：T(x)+E(x)T(x)+E(x)；余数余数余数余数(T(x)+E(x)/G(x)=0+(T(x)+E(x)/G(x)=0+余数余数余数余数(E(x)/(E(x)/G(x)G(x)若若若若 余数余数余数余数(E(x)/G(x)=0(E(x)/G(x)=0，则

34、差错不能发现；否则，可，则差错不能发现；否则，可，则差错不能发现；否则，可，则差错不能发现；否则，可以发现。以发现。以发现。以发现。5.2 错误检测和纠正（7）如果只有单比特错，即如果只有单比特错，即如果只有单比特错，即如果只有单比特错，即E(x)=xE(x)=xi i，而，而，而，而G(x)G(x)中至少有两项，中至少有两项，中至少有两项，中至少有两项，余数余数余数余数(E(x)/G(x)(E(x)/G(x)0 0，所以可以查出单比特错；，所以可以查出单比特错；，所以可以查出单比特错；，所以可以查出单比特错；如果发生两个孤立单比特错，即如果发生两个孤立单比特错，即如果发生两个孤立单比特错，即

35、如果发生两个孤立单比特错，即E(x)=xE(x)=xi i+x+xj j=x=xj j(x(xi-ji-j+1)1)，假定，假定，假定，假定G(x)G(x)不能被不能被不能被不能被x x整除，那么能够发现两个比特错的充分条整除，那么能够发现两个比特错的充分条整除，那么能够发现两个比特错的充分条整除，那么能够发现两个比特错的充分条件是：件是：件是：件是：x xk k+1+1不能被不能被不能被不能被G(x)G(x)整除整除整除整除(k (k i-j)i-j)；如果有奇数个比特错，即如果有奇数个比特错，即如果有奇数个比特错，即如果有奇数个比特错，即E(x)E(x)包括奇数个项，包括奇数个项，包括奇数

36、个项，包括奇数个项，G(x)G(x)选选选选(x+1)(x+1)的倍数就能查出奇数个比特错；的倍数就能查出奇数个比特错；的倍数就能查出奇数个比特错；的倍数就能查出奇数个比特错；具有具有具有具有r r个校验位的多项式能检查出所有长度个校验位的多项式能检查出所有长度个校验位的多项式能检查出所有长度个校验位的多项式能检查出所有长度 r r 的突发性差错。长的突发性差错。长的突发性差错。长的突发性差错。长度为度为度为度为k k的突发性连续差错（并不表示有的突发性连续差错（并不表示有的突发性连续差错（并不表示有的突发性连续差错（并不表示有k k个单比特错）可表示为个单比特错）可表示为个单比特错）可表示为

37、个单比特错）可表示为 x xi i (x(xk-1k-1+1)+1)，若，若，若，若G(x)G(x)包括包括包括包括x x0 0项，且项，且项，且项，且 k-1 k-1小于小于小于小于G(x)G(x)的阶，的阶，的阶，的阶，则则则则 余数余数余数余数(E(x)/G(x)(E(x)/G(x)0;0;如果突发差错长度为如果突发差错长度为如果突发差错长度为如果突发差错长度为 r+1 r+1，当且仅当突发差错和，当且仅当突发差错和，当且仅当突发差错和，当且仅当突发差错和G(x)G(x)一样时，一样时，一样时，一样时，余数余数余数余数(E(x)/G(x)E(x)/G(x)=0=0，概率为，概率为，概率为

38、，概率为1/21/2r-1r-1;长度大于长度大于长度大于长度大于 r+1 r+1的突发差错或几个较短的突发差错发生后，坏帧的突发差错或几个较短的突发差错发生后，坏帧的突发差错或几个较短的突发差错发生后，坏帧的突发差错或几个较短的突发差错发生后，坏帧被接收的概率为被接收的概率为被接收的概率为被接收的概率为 1/2 1/2r r。5.2 错误检测和纠正（8）n n四个多项式已成为国际标准四个多项式已成为国际标准CRC-12 CRC-12=x=x1212+x+x1111+x+x3 3+x+x2 2 +x+1+x+1CRC-16 CRC-16=x=x1616+x+x1515+x+x2 2+1+1CR

39、C-CCITT CRC-CCITT=x=x1616+x+x1212+x+x5 5+1+1CRC-32CRC-32n n硬件实现硬件实现CRC校验校验网卡网卡网卡网卡NICNIC（Network Interface CardNetwork Interface Card）5.3 基本的数据链路层协议（1）5.3.1 无约束单工协议（无约束单工协议（An Unrestricted Simplex Protocol）n n工作在理想情况，几个前提：工作在理想情况，几个前提：单工传输单工传输单工传输单工传输发送方无休止工作（要发送的信息无限多）发送方无休止工作（要发送的信息无限多）发送方无休止工作（要发

40、送的信息无限多）发送方无休止工作（要发送的信息无限多）接收方无休止工作（缓冲区无限大）接收方无休止工作（缓冲区无限大）接收方无休止工作（缓冲区无限大）接收方无休止工作（缓冲区无限大）通信线路（信道）不损坏或丢失信息帧通信线路（信道）不损坏或丢失信息帧通信线路（信道）不损坏或丢失信息帧通信线路（信道）不损坏或丢失信息帧n n工作过程工作过程发送程序发送程序发送程序发送程序:取数据，构成帧，发送帧；取数据，构成帧，发送帧；取数据，构成帧，发送帧；取数据，构成帧，发送帧；接收程序：等待，接收帧，送数据给高层接收程序：等待，接收帧，送数据给高层接收程序：等待，接收帧，送数据给高层接收程序：等待，接收帧

41、，送数据给高层Fig.3-9Fig.3-95.3 基本的数据链路层协议（2）5.3.2 5.3.2 单工停等协议（单工停等协议（单工停等协议（单工停等协议（A Simplex Stop-and-A Simplex Stop-and-Wait ProtocolWait Protocol）n n增加约束条件：接收方不能无休止接收。增加约束条件：接收方不能无休止接收。增加约束条件：接收方不能无休止接收。增加约束条件：接收方不能无休止接收。n n解决办法：接收方每收到一个帧后，给发送方回解决办法：接收方每收到一个帧后，给发送方回解决办法：接收方每收到一个帧后，给发送方回解决办法：接收方每收到一个帧后，

42、给发送方回送一个响应。送一个响应。送一个响应。送一个响应。n n工作过程工作过程工作过程工作过程 发送程序：取数据，成帧，发送帧，等待响应帧；发送程序：取数据，成帧，发送帧，等待响应帧；发送程序：取数据，成帧，发送帧，等待响应帧；发送程序：取数据，成帧，发送帧，等待响应帧；接收程序：等待，接收帧，送数据给高层，回送响应接收程序：等待，接收帧，送数据给高层，回送响应接收程序：等待，接收帧，送数据给高层，回送响应接收程序：等待，接收帧，送数据给高层，回送响应帧。帧。帧。帧。Fig.3-10Fig.3-105.3 基本的数据链路层协议（3）5.3.3 5.3.3 有噪声信道的单工协议（有噪声信道的单

43、工协议（有噪声信道的单工协议（有噪声信道的单工协议（A Simplex Protocol A Simplex Protocol for a Noisy Channelfor a Noisy Channel）n n增加约束条件：信道（线路）有差错，信息帧可能损坏或增加约束条件：信道（线路）有差错，信息帧可能损坏或增加约束条件：信道（线路）有差错，信息帧可能损坏或增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。丢失。丢失。丢失。n n解决办法：出错重传。解决办法：出错重传。解决办法：出错重传。解决办法：出错重传。n n带来的问题：带来的问题：带来的问题：带来的问题：什么时候重传什么时候重传

44、什么时候重传什么时候重传 定时定时定时定时 响应帧损坏怎么办（重复帧）响应帧损坏怎么办（重复帧）响应帧损坏怎么办（重复帧）响应帧损坏怎么办（重复帧）发送帧头中放入序号发送帧头中放入序号发送帧头中放入序号发送帧头中放入序号 为了使帧头精简，序号取多少位为了使帧头精简，序号取多少位为了使帧头精简，序号取多少位为了使帧头精简，序号取多少位 1 1位位位位n n发方在发下一个帧之前等待一个肯定确认的协议叫做发方在发下一个帧之前等待一个肯定确认的协议叫做发方在发下一个帧之前等待一个肯定确认的协议叫做发方在发下一个帧之前等待一个肯定确认的协议叫做PARPAR（Positive Acknowledgemen

45、t with Positive Acknowledgement with RetransmissionRetransmission）或）或）或）或ARQARQ（Automatic Repeat Automatic Repeat reQuestreQuest）5.3 基本的数据链路层协议（4）n n工作过程工作过程工作过程工作过程 Fig.3-11Fig.3-11n n注意协议注意协议注意协议注意协议3 3的漏洞的漏洞的漏洞的漏洞 由于确认帧中没有序号，超时时间不能太短，否则协议失败。因由于确认帧中没有序号，超时时间不能太短，否则协议失败。因由于确认帧中没有序号，超时时间不能太短，否则协议失败。

46、因由于确认帧中没有序号，超时时间不能太短，否则协议失败。因此假设协议此假设协议此假设协议此假设协议3 3的发送和接收严格交替进行。的发送和接收严格交替进行。的发送和接收严格交替进行。的发送和接收严格交替进行。Fig.3-11Fig.3-11（与教材不同）的实现是正确的，确认帧有序号（与教材不同）的实现是正确的，确认帧有序号（与教材不同）的实现是正确的，确认帧有序号（与教材不同）的实现是正确的，确认帧有序号发送接收001ACKACK5.4 滑动窗口协议（1）n n单工单工单工单工 全双工全双工全双工全双工n n捎带捎带捎带捎带/载答（载答（载答（载答（piggybackingpiggybacki

47、ng）：暂时延迟待发）：暂时延迟待发）：暂时延迟待发）：暂时延迟待发确认，以便附加在下一个待发数据帧的技术。确认，以便附加在下一个待发数据帧的技术。确认，以便附加在下一个待发数据帧的技术。确认，以便附加在下一个待发数据帧的技术。优点：充分利用信道带宽，减少帧的数目意味着减少优点：充分利用信道带宽，减少帧的数目意味着减少优点：充分利用信道带宽，减少帧的数目意味着减少优点：充分利用信道带宽，减少帧的数目意味着减少“帧到达帧到达帧到达帧到达”中断；中断；中断；中断；带来的问题：复杂。带来的问题：复杂。带来的问题：复杂。带来的问题：复杂。n n本节的三个协议统称滑动窗口协议，都能在实际本节的三个协议统

48、称滑动窗口协议，都能在实际本节的三个协议统称滑动窗口协议，都能在实际本节的三个协议统称滑动窗口协议，都能在实际（非理想）环境下正常工作，区别仅在于效率、（非理想）环境下正常工作，区别仅在于效率、（非理想）环境下正常工作，区别仅在于效率、（非理想）环境下正常工作，区别仅在于效率、复杂性和对缓冲区的要求。复杂性和对缓冲区的要求。复杂性和对缓冲区的要求。复杂性和对缓冲区的要求。5.4 滑动窗口协议（2）n n滑动窗口协议（滑动窗口协议（滑动窗口协议（滑动窗口协议（Sliding Window ProtocolSliding Window Protocol）工作原）工作原）工作原）工作原理：理：理：理

49、：发送的信息帧都有一个序号，从发送的信息帧都有一个序号，从发送的信息帧都有一个序号，从发送的信息帧都有一个序号，从0 0到某个最大值，到某个最大值，到某个最大值，到某个最大值，0 20 2n n-1-1，一般用一般用一般用一般用n n个二进制位表示；个二进制位表示；个二进制位表示；个二进制位表示；发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示窗口。发送窗口的上界表

50、示要发送的下一个帧的序号，下界表示窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小未得到确认的帧的最小编号。发送窗口大小未得到确认的帧的最小编号。发送窗口大小未得到确认的帧的最小编号。发送窗口大小=上界上界上界上界-下界，大小下界，大小下界，大小下界，大小可变；可变；可变；可变；发送端每发送一个帧，序号取上界值，上界加发送端每发送一个帧，序号取上界值，上界加发送端每发送一个帧，序号取上界值，上界加发送端每发送一个帧，序号取上界值，上界加1 1；每接收到一个正；每接收到一个正；每接收到一个正；每