第2讲协议设计(差错控制技术)

1、2022年6月19日星期日差错控制技术2-1 网网 络络 协协 议议 工工 程程 第第 2 讲：协议设计讲：协议设计2022年6月19日星期日差错控制技术2-2第第 2 讲：协议设计讲：协议设计2.1 协议模型协议模型2.2 协议设计的基本内容协议设计的基本内容2.3 协议设计方法协议设计方法2.4 差错控制技术差错控制技术2.5 流量控制技术流量控制技术2022年6月19日星期日差错控制技术2-3差错控制技术：内容提纲差错控制技术：内容提纲2.4.1 差错类型差错类型2.4.2 差错检测技术差错检测技术2.4.3 差错控制技术差错控制技术2.4.4 差错控制与层次的关系差错控制与层次的关系2

2、022年6月19日星期日差错控制技术2-4差错控制：概述差错控制：概述v网络通信的目的是通过网络在应用进程间传输网络通信的目的是通过网络在应用进程间传输信息，任何数据丢失或损坏都将对通信双方产信息，任何数据丢失或损坏都将对通信双方产生重要的影响。生重要的影响。 v差错控制差错控制是指在网络通信过程中发现是指在网络通信过程中发现(检测检测)差差错，并采取措施纠正，把差错限制在错，并采取措施纠正，把差错限制在所允许所允许的的尽可能小的范围内的技术和方法。尽可能小的范围内的技术和方法。 v差错控制的目的是为了差错控制的目的是为了提高数据传输的可靠性提高数据传输的可靠性，但是任何一种差错控制方法均但是

3、任何一种差错控制方法均不可能纠正所有不可能纠正所有可能出现的差错。可能出现的差错。 2022年6月19日星期日差错控制技术2-5差错控制：概述差错控制：概述 (续续)v差错控制主要有两种途径：差错控制主要有两种途径：硬件途径硬件途径。这种途径选用高可靠性的设备和传输媒。这种途径选用高可靠性的设备和传输媒体体(如光纤如光纤)及相应的辅助措施及相应的辅助措施(如如屏蔽屏蔽)来提高传输的来提高传输的可靠性。可靠性。 软件途径软件途径。这种途径通过通信协议来实现差错控制。这种途径通过通信协议来实现差错控制。在通信协议中，通过差错控制编码在通信协议中，通过差错控制编码(包括检错码和前包括检错码和前向纠错

4、码向纠错码)实现的差错检测、肯定确认、超时重传、实现的差错检测、肯定确认、超时重传、否认重传、选择重传等措施来实现差错控制。否认重传、选择重传等措施来实现差错控制。 2022年6月19日星期日差错控制技术2-6差错类型差错类型v根据差错发生的位置，分为三种类型：根据差错发生的位置，分为三种类型：通信链路差错通信链路差错指有关通信链路上故障、干扰造成的传输错误问题指有关通信链路上故障、干扰造成的传输错误问题 路由差错路由差错 有关传输报文在路由过程中阻塞、丢失、死锁以及有关传输报文在路由过程中阻塞、丢失、死锁以及报文顺序错而造成传输的差错问题报文顺序错而造成传输的差错问题通信结点差错通信结点差错

5、 有关通信中某结点的资源限制、环境条件或文本不有关通信中某结点的资源限制、环境条件或文本不符、协议同步关系以及操作错误、硬件故障等，可符、协议同步关系以及操作错误、硬件故障等，可能影响通信链路的正确联接或正常通常的错误中断能影响通信链路的正确联接或正常通常的错误中断等问题等问题 2022年6月19日星期日差错控制技术2-7差错类型（续）差错类型（续）v根据差错的表现形式根据差错的表现形式 ，可分为四类（）：，可分为四类（）：失真失真(Distortion) 定义：被传送信息中的一个或多个比特发生了改定义：被传送信息中的一个或多个比特发生了改变，或者被传送的信息中插入了一些新的信息变，或者被传送

6、的信息中插入了一些新的信息(这种情况也称为这种情况也称为“插入插入(Insertion)”) 主要原因：主要原因：网络中物理干扰网络中物理干扰(如线路噪声如线路噪声)发送者和接收者之间的失步发送者和接收者之间的失步入侵者的故意攻击入侵者的故意攻击结点中的硬件故障和软件差错等结点中的硬件故障和软件差错等 解决方法：各种校验方法来检测解决方法：各种校验方法来检测 2022年6月19日星期日差错控制技术2-8差错类型（续）差错类型（续）v根据差错的表现形式根据差错的表现形式 ，可分为四类，可分为四类（）丢失丢失(Deletion) 定义：网络将被传输的信息丢弃定义：网络将被传输的信息丢弃 主要原因：

7、主要原因：噪声脉冲对某个帧的破坏程度太大，以致接收方不知噪声脉冲对某个帧的破坏程度太大，以致接收方不知道这个帧已经被传输；道这个帧已经被传输；发送者和接收者之间的失步；发送者和接收者之间的失步；流量控制或拥塞控制措施不当时因资源不够而被中间流量控制或拥塞控制措施不当时因资源不够而被中间结点或接收者丢弃；结点或接收者丢弃；因接收者检测到信息被损坏而主动将其丢弃等因接收者检测到信息被损坏而主动将其丢弃等 解决方法：用序号、计时器和确认共同检测，通解决方法：用序号、计时器和确认共同检测，通过重传的方法来纠正错误过重传的方法来纠正错误 2022年6月19日星期日差错控制技术2-9差错类型（续）差错类型

8、（续）v根据差错的表现形式根据差错的表现形式 ，可分为四类，可分为四类（）重复重复(Duplication) 定义：多次收到同样的信息定义：多次收到同样的信息 主要原因：主要原因：是差错控制机制本身，如果发送方错误地认为数据丢是差错控制机制本身，如果发送方错误地认为数据丢失了，因而重传了它，就可能造成接收方收到重复的失了，因而重传了它，就可能造成接收方收到重复的信息信息 路由选择机制引起的重复帧，如使用基于扩散的路由路由选择机制引起的重复帧，如使用基于扩散的路由选择策略选择策略(如洪泛法如洪泛法) 解决方法：用序号来检测这种错误，用丢弃重复解决方法：用序号来检测这种错误，用丢弃重复的数据来纠正

9、错误。的数据来纠正错误。2022年6月19日星期日差错控制技术2-10差错类型（续）差错类型（续）v根据差错的表现形式根据差错的表现形式 ，可分为四类，可分为四类（）失序失序(Reordering) 定义：定义：数据到达接收方的顺序与发送方发送的顺数据到达接收方的顺序与发送方发送的顺序不一致序不一致 主要原因：主要原因：采用自适应的路由选择策略，分组在网络中传送时可采用自适应的路由选择策略，分组在网络中传送时可能有多条路由而引起的后发先到能有多条路由而引起的后发先到 重传丢失的数据也可能导致数据不按序到达重传丢失的数据也可能导致数据不按序到达解决方法：解决方法：把乱序的数据先存储下来，使得以后

10、能把它们存放在把乱序的数据先存储下来，使得以后能把它们存放在正确的位置上；正确的位置上；丢弃乱序的数据，然后按数据丢失来处理丢弃乱序的数据，然后按数据丢失来处理 。2022年6月19日星期日差错控制技术2-11第第 讲：内容提纲讲：内容提纲2.4.1 差错类型差错类型2.4.2 差错检测技术差错检测技术2.4.3 差错控制技术差错控制技术2.4.4 差错控制与层次的关系差错控制与层次的关系2022年6月19日星期日差错控制技术2-12差错检测技术：概述差错检测技术：概述v检查收到的数据是否正确的方法和技术检查收到的数据是否正确的方法和技术通常情况下，我们所说的差错检测是指检测收到的通常情况下，

11、我们所说的差错检测是指检测收到的数据是否被损坏，而不包括对数据丢失、重复、乱数据是否被损坏，而不包括对数据丢失、重复、乱序等差错的检测序等差错的检测在这样的前提下，差错检测技术所采取的方法一般在这样的前提下，差错检测技术所采取的方法一般是各种检验和技术，如奇偶检验，循环冗余检验等是各种检验和技术，如奇偶检验，循环冗余检验等, ,本节主要介绍这方面的技术本节主要介绍这方面的技术v差错检测是差错控制的基础差错检测是差错控制的基础 2022年6月19日星期日差错控制技术2-13差错检测技术：原理差错检测技术：原理E, E：差错检验码：差错检验码对比对比接收器接收器数据数据 EE = f(Data)数

12、据数据 EE = f(Data)发送器发送器数据数据f: 差错检验函数差错检验函数问题：问题：为什么总是将检验码放在帧的尾部？为什么总是将检验码放在帧的尾部？2022年6月19日星期日差错控制技术2-14差错检测技术差错检测技术一、奇偶检验一、奇偶检验(Parity Check) 2022年6月19日星期日差错控制技术2-15奇偶检验奇偶检验v奇偶检验在数据的尾部附加上奇偶检验位，使奇偶检验在数据的尾部附加上奇偶检验位，使得码字中比特得码字中比特“1”的个数保持为奇数的个数保持为奇数(奇检验奇检验)或偶数或偶数(偶检验偶检验) v被广泛用于诸如计算机的异步串行口通信中被广泛用于诸如计算机的异步

13、串行口通信中v三种类型：三种类型：垂直冗余检验垂直冗余检验(VRC：Vertical Redundancy Checking)纵向冗余检验纵向冗余检验(LRC：Longitudinal Redundancy Checking)纵向垂直冗余检验纵向垂直冗余检验 2022年6月19日星期日差错控制技术2-16奇偶检验：奇偶检验：垂直冗余检验v 原理：原理：将整个发送的信息分为长度为将整个发送的信息分为长度为p位的若干段，如位的若干段，如q段，段，每段后面按每段后面按“1”的个数为奇数或偶数的规律加上一位奇的个数为奇数或偶数的规律加上一位奇偶位，其有偶位，其有(p * q) 个信息位，每段由个信息位

14、，每段由p位构成，共位构成，共q列列(段段)v 通常通常p值等于一个字符的长度，因此有时也将垂直冗余检值等于一个字符的长度，因此有时也将垂直冗余检验称为验称为字符奇偶检验字符奇偶检验。v 可以用硬件或软件方法来实现连续半加运算，且可以边发可以用硬件或软件方法来实现连续半加运算，且可以边发送边产生检验位，并插入发送。在接收时边接收边进行检送边产生检验位，并插入发送。在接收时边接收边进行检验并除去检验位验并除去检验位v 能检测出每列中的能检测出每列中的所有奇数个位的错所有奇数个位的错，但检测不出，但检测不出偶数个偶数个位的错位的错。对于突发错误而言，奇数位错与偶数位错的概率。对于突发错误而言，奇数

15、位错与偶数位错的概率差不多是相等的，因而对差错的漏检率接近于差不多是相等的，因而对差错的漏检率接近于50%50%。 2022年6月19日星期日差错控制技术2-17奇偶检验：奇偶检验：垂直冗余检验D = 1 0 0 0 1 0 0 0A = 1 0 0 0 0 0 1 0T = 1 0 1 0 1 0 0 1A = 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1垂直奇偶校验纵向奇偶校验2022年6月19日星期日差错控制技术2-18奇偶检验：奇偶检验：纵向冗余检验v原理：原理：对各个信息段的相应位水平进行编码，对各个信息段的相应位水平进行编码，对应每一行产生一个奇偶检验位。这种附加

16、的对应每一行产生一个奇偶检验位。这种附加的水平基础上检验字符的技术，使用了和垂直冗水平基础上检验字符的技术，使用了和垂直冗余检验同样的奇偶性。余检验同样的奇偶性。 v漏检率要比垂直冗余检验低。不但可以检测出漏检率要比垂直冗余检验低。不但可以检测出各段同一位上的奇数位错，而且可以检测出突各段同一位上的奇数位错，而且可以检测出突发长度小于等于发长度小于等于p的所有突发错误（的所有突发错误（Why?Why?）因为可以安排发送顺序使得因为可以安排发送顺序使得在可见突发长度小于等于在可见突发长度小于等于p的突发错误必然分布在不同的突发错误必然分布在不同行中，每行一位，所以可以行中，每行一位，所以可以检测

17、出来检测出来 2022年6月19日星期日差错控制技术2-19奇偶检验：奇偶检验：纵向冗余检验D = 1 0 0 0 1 0 0 0A = 1 0 0 0 0 0 1 0T = 1 0 1 0 1 0 0 1A = 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1垂直奇偶校验纵向奇偶校验2022年6月19日星期日差错控制技术2-20奇偶检验：奇偶检验：纵向冗余检验v实现复杂：实现时不能在发送过程中边产生奇实现复杂：实现时不能在发送过程中边产生奇偶检验位，边插入发送，而必须要等到要发送偶检验位，边插入发送，而必须要等到要发送的完整信息块到齐后，才能产生检验位，因而的完整信息块到齐后，

18、才能产生检验位，因而一定要使用记忆寄存器。一定要使用记忆寄存器。2022年6月19日星期日差错控制技术2-21奇偶检验：奇偶检验：垂直纵向冗余检验v 同时进行垂直冗余检验和纵向冗余检验同时进行垂直冗余检验和纵向冗余检验v 能检测出所有能检测出所有3位或位或3位以下的错误位以下的错误(因为此时至少在某因为此时至少在某一行或某一列上为一位错一行或某一列上为一位错)、奇数位错奇数位错、突发长度小于突发长度小于等于等于(p+1)的突发错的突发错以及很大以及很大一部分偶数位错一部分偶数位错。v 还可以还可以纠正部分差错，纠正部分差错，例如仅在某一行和某一列中有例如仅在某一行和某一列中有奇数位错时，就可以

19、确定错误的位置就在该行和该列奇数位错时，就可以确定错误的位置就在该行和该列的交叉处，从而得以纠正。的交叉处，从而得以纠正。 v 此外，当某一行出现偶数个错时，虽然纵向冗余检验此外，当某一行出现偶数个错时，虽然纵向冗余检验不能发现，但在其垂直冗余检验中还是可以被检测出不能发现，但在其垂直冗余检验中还是可以被检测出来。只有当有错的各行和各列中出错位数均为偶数时，来。只有当有错的各行和各列中出错位数均为偶数时，才不可能被发现。才不可能被发现。 2022年6月19日星期日差错控制技术2-22奇偶检验：奇偶检验：垂直纵向冗余检验D = 1 0 0 0 1 0 0 0A = 1 0 0 0 0 0 1 0

20、T = 1 0 1 0 1 0 0 1A = 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1垂直奇偶校验纵向奇偶校验2022年6月19日星期日差错控制技术2-23奇偶检验：小结奇偶检验：小结v使用奇偶检验并不是十分安全，因为噪声脉冲使用奇偶检验并不是十分安全，因为噪声脉冲的长度经常足以破坏一个以上的比特，特别是的长度经常足以破坏一个以上的比特，特别是在数据率较高的情况下。在数据率较高的情况下。 v低速率的串行口通信协议，如低速率的串行口通信协议，如RS232接口，常接口，常采用奇偶检验方法来检测错误采用奇偶检验方法来检测错误。v一般情况下，垂直冗余检验主要用于异步传输，一般情况

21、下，垂直冗余检验主要用于异步传输，且一列对应一个字符。且一列对应一个字符。v而纵向冗余检验则常用于同步传输，通常是把而纵向冗余检验则常用于同步传输，通常是把一串字符作为一个块传送，字符之间没有时间一串字符作为一个块传送，字符之间没有时间间隔，产生一个附加的字符跟在块的后面。间隔，产生一个附加的字符跟在块的后面。 2022年6月19日星期日差错控制技术2-24差错检测技术差错检测技术二、二、循环冗余检验循环冗余检验(CRC) 2022年6月19日星期日差错控制技术2-25CRC检验：原理检验：原理 1101010110Q 商 除数P110101 1010001101000002nM 被除数 11

22、0101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110R 余数q 数据：M=1010001101q 除数P（生成多项式）= X5+X4+X2+1q 模 2 运算：加法不进位，减法 和加法是一样的，例如： 1111 + 1010 = 0101q 冗余码称为帧检验序列 FCSq 接收端运算：XnM(X) + R(X) / P(X) = Q(X)q 有错：R(X) !=0q 问题：R(X) 等于0是否就不定没有错吗？q 常见多项式：o CRC-16 = X16+X15+X2+1o CRC-CCI

23、TT = X16+X12+X5+1o CRC-32 = X32+X26+X23+ X22+X16+X12+ X11+X10+X8+ X7+X5+X4+ X2+X+12022年6月19日星期日差错控制技术2-26CRC检验：检错率检验：检错率vCRC检验的漏检率是比较低的。检验的漏检率是比较低的。CRC-CCITT检验可以检测出所有的双比特差错，长度为检验可以检测出所有的双比特差错，长度为17比特的数据中的比特的数据中的99.997%的突发错误，长度大的突发错误，长度大于于17比特的数据中的比特的数据中的99.998%的突发错误。的突发错误。v采用采用CRCCRC检验的著名协议：检验的著名协议：

24、数据链路层协议数据链路层协议HDLCHDLC采用的就是采用的就是CRC-CCITTCRC-CCITT检验。检验。IBMIBM的的BisyncBisync协议中采用的是协议中采用的是CRC-16CRC-16检验检验以太网帧和光纤分布式数据接口标准以太网帧和光纤分布式数据接口标准(FDDI)(FDDI)中则采中则采用的是用的是CRC-32CRC-32检验。检验。 2022年6月19日星期日差错控制技术2-27CRC检验：实现检验：实现vCRC检验的编码需要花费不少的时间，因此计检验的编码需要花费不少的时间，因此计算检验和可能会降低协议的性能。算检验和可能会降低协议的性能。v为了提高协议的性能，通常

25、采用为了提高协议的性能，通常采用硬件方法硬件方法(移移位寄存器位寄存器)或或查检验和表查检验和表(预先计算出检验和放预先计算出检验和放在表中，使用时查表即可在表中，使用时查表即可)的软件方法来实现。的软件方法来实现。 2022年6月19日星期日差错控制技术2-28CRC检验：源代码检验：源代码vAT&T Bell实验室的实验室的Don Mitchell所写的一个计所写的一个计算算CRC检验和，并生成检验和表的程序检验和，并生成检验和表的程序Crc_init.cCrc_init.c: : 创建检验和表创建检验和表(crc_table(crc_table)Checksum(s, n)Che

26、cksum(s, n)查表生成检验和。输入参数查表生成检验和。输入参数s s为被为被检验的数据，检验的数据，n n为数据长度为数据长度( (单位为字节单位为字节) )。函数返。函数返回值为被检验的数据的检验和。回值为被检验的数据的检验和。 2022年6月19日星期日差错控制技术2-29crc_init.cmain(argc, argv) int argc; char *argv; unsigned long crc, poly; int n, i; sscanf(argv1, “%lo”,&poly); if (poly & 0 xffff0000) fprintf(stder

27、r, “polynomial is too largen”); exit(1); printf(“/*n * CRC 0 %on * /n”,poly); printf(“static unsigned short crc_table256 = n”;2022年6月19日星期日差错控制技术2-30crc_init.c (Cont.)for (n =0; n256; n+) crc = n; if (n% 8 = =0) printf(“ “); for ( i = 0; i =1; crc = poly; else crc =1; printf(“0 x%x, “,crc); if ( n &

28、amp;8 = = 7) printf (“n”); printf(“);nn”); exit(0); 2022年6月19日星期日差错控制技术2-31crc_init.c: examplesv$ crc_init 05401 crc_12.h 创建基于创建基于CRC-12的检验和表，并保存在文件的检验和表，并保存在文件crc_12.h中中 v$ crc_init 0120001 crc_16.h 创建基于创建基于CRC-16的检验和表，并保存在文件的检验和表，并保存在文件crc_16.h中中 v$ crc_init 0102010 crc_ccitt.h 创建基于创建基于CRC-CCITT的检

29、验和表，并保存在文件的检验和表，并保存在文件crc_ccitt.h 中中2022年6月19日星期日差错控制技术2-32Checksum(s,n): 源码源码unsigned short cksum(s,n) register unsigned char *s; register int n; register unsigned int crc; for (crc = 0; n 0; n-) crc = crc_table(crc *s+) & 0 xff (crc 8); return crc;2022年6月19日星期日差错控制技术2-33差错检测技术差错检测技术三、三、UUCP检验和

30、检验和 2022年6月19日星期日差错控制技术2-34UUCP检验和检验和vUNIX操作系统中的操作系统中的uucp应用程序中的计算检验应用程序中的计算检验和方法，与和方法，与CRC检验比较类似检验比较类似v比较简单，有点类似于散列方法，其漏检率比比较简单，有点类似于散列方法，其漏检率比CRCCRC要高一些，而且计算同样的检验和，它所花要高一些，而且计算同样的检验和，它所花的时间比查表计算的时间比查表计算CRCCRC检验和的方法要多一些。检验和的方法要多一些。 2022年6月19日星期日差错控制技术2-35UUCP检验和：源码检验和：源码cksum(scksum(s, n), n) regis

31、ter char register char * *s;s; register n; register n; register short sum; register short sum; register unsigned short t; register unsigned short t; register short x; register short x; sum = -1; x = 0; sum = -1; x = 0; do do if (sum 0) sum =1; sum+ if (sum 0) sum =1; sum+ else sum = 1; else sum = 1;

32、 t = sum; sum += (unsigned) t = sum; sum += (unsigned) * *s+ & 0377; x += sumn;s+ & 0377; x += sumn; if (unsigned short) sum = t) sum = x; if (unsigned short) sum 0); while (-n 0); return (sum); return (sum); 2022年6月19日星期日差错控制技术2-36差错检测技术差错检测技术四、四、算术检验和算术检验和(Arithmetic Checksum) 2022年6月19日星期

33、日差错控制技术2-37算术检验和算术检验和v尽管可以通过前面介绍的查表的方法或特殊硬尽管可以通过前面介绍的查表的方法或特殊硬件的方法计算检验和来缩短处理时间件的方法计算检验和来缩短处理时间，但：，但：v对于允许一定程度的漏检率的应用场合，对于允许一定程度的漏检率的应用场合，可以可以采用比采用比CRC检验要简单且又能够发现比较严重检验要简单且又能够发现比较严重的传输错误的方法来进行差错检测。的传输错误的方法来进行差错检测。vJohn Fletcher John Fletcher 在在19821982提出了这样一种差错检提出了这样一种差错检测方法，称为测方法，称为算术检验和算术检验和只需用到加法和

34、取模操作，只需用到加法和取模操作，且算法特别简单且算法特别简单 2022年6月19日星期日差错控制技术2-38Arithmetic ChecksumvError detection at the higher layer is usually done by ordinary arithmetic operations.This is simpler in software but somewhat less effective than a CRC.vStandard technique is to view packet as sequence of k numbers of n bits

35、 each, say x1, x2,., xk.vChecksum is then the n bit number x1+x2+.+xk using ordinary arithmetic with no carry.2022年6月19日星期日差错控制技术2-39Arithmetic Checksum (Cont.)vAlternatively, checksum might be 2n bits; first n bits is (sum) x1+x2+.+xk and second n bits is (sum of sum) x1+2x2+3x3+.+kxk.vExample: In

36、TCP, n=16, checksum is 16 bits and ones complement of the sum.vIn ISBN, the data are radix 10 digits, checksum is radix 11 digit (with 10 represented as X) and is (sum of sum of all digits)/11.2022年6月19日星期日差错控制技术2-40算术检验和：源码算术检验和：源码vISO的类的类4运输协议运输协议(TP4) 中的实现源代码：中的实现源代码： unsigned short cksum(s, n) r

37、egister unsigned char *s; register int n; register int c0=0, c1=0; do c0 = (c0 + *s+) % 255; c1 = (c0 + c1) %255; while (-n 0); return (unsigned short) (c1 11 + 1 =12，而且编号而且编号1=1, 2=2, 3=1+2, 4=4,5=1+4, 6=2+4, 7=1+2+4, 8=8, 9=1+8, 10=2+8, 11=1+2+8, 于是有：于是有： (1) (1) + (3) + (5) + (7) + (9) + (11) (2)

38、 (2) + (3) + (6) + (7) + (10) + (11)(4) (4) + (5) + (6) + (7) (8) (8) + (9) + (10) + (11) v 注意：在每个检验位的形成表达式中，除自身的编号外，注意：在每个检验位的形成表达式中，除自身的编号外，其余都是信息位的编号，因此只要信息位是确定的，检其余都是信息位的编号，因此只要信息位是确定的，检验位也可以唯一地确定。验位也可以唯一地确定。 2022年6月19日星期日差错控制技术2-51Hamming Code (Cont.)v 10个个7位位ASCII字符使用海明编码形成的字符使用海明编码形成的10位码字，其中

39、位码字，其中数据位在数据位在3、5、6、7、9、10和和11位，编号为位，编号为1、2、4、8的位是检验位。的位是检验位。字符：字符：H，ASCII编码：编码：1001000 ，海明码：，海明码：00110010000 字符：字符：a， ASCII编码：编码：1100001 ，海明码：，海明码：10111001001 字符：字符：m，ASCII编码：编码：1101101 ，海明码：，海明码：11101010101 字符：字符：i， ASCII编码：编码：1101001 ，海明码：，海明码：01101011001 字符：字符：n， ASCII编码：编码：1101110 ，海明码：，海明码：011

40、01010110 字符：字符：g， ASCII编码：编码：1100111 ，海明码：，海明码：01111001111 字符：字符：c， ASCII编码：编码：1100011 ，海明码：，海明码：11111000011 字符：字符：o， ASCII编码：编码：1101111 ，海明码：，海明码：10101011111 字符：字符：d， ASCII编码：编码：1100100 ，海明码：，海明码：11111001100 字符：字符：e， ASCII编码：编码：1100101 ，海明码：，海明码：00111000101 2022年6月19日星期日差错控制技术2-52HammingCode (Cont.

41、)v 当一码字到达时，接收方将计数器清当一码字到达时，接收方将计数器清0。 v 然后接收方检测每个检验位然后接收方检测每个检验位D(这里的这里的D是检验位的编是检验位的编号号)，看是否具有正确的奇偶性。，看是否具有正确的奇偶性。 如果第如果第D位奇偶性不对，则计数值加位奇偶性不对，则计数值加D， 若所有检验位被检查过后，计数器值仍为若所有检验位被检查过后，计数器值仍为0，这个码字就作为，这个码字就作为有效码字接受。有效码字接受。 假如计数器值不为假如计数器值不为0，则该值就是出错位的编者编号。，则该值就是出错位的编者编号。 例如，若检测位例如，若检测位1、2和和8错误，则第错误，则第11位就变

42、反，因为它是唯位就变反，因为它是唯一被第一被第1、2和和8位检测的位。位检测的位。 v 海明码的信息余量很大海明码的信息余量很大( (前面的例子：前面的例子：7+4)7+4)，因而编码，因而编码效率低。大大增加了数据通信的开销效率低。大大增加了数据通信的开销2022年6月19日星期日差错控制技术2-53检错重传与纠错检错重传与纠错v一般使用检错重传，特别是在数据链路层以上一般使用检错重传，特别是在数据链路层以上的各层协议。的各层协议。v在有些协议中，将检错码和纠错码结合起来一在有些协议中，将检错码和纠错码结合起来一起使用，增强差错控制的能力，如起使用，增强差错控制的能力，如ATM AAL1协议

43、中的差错检测机制协议中的差错检测机制。2022年6月19日星期日差错控制技术2-54差错检测技术差错检测技术七、七、关于被检验的数据的讨论关于被检验的数据的讨论 2022年6月19日星期日差错控制技术2-55被保护对象的选择被保护对象的选择v有些协议中，是对整个数据单元有些协议中，是对整个数据单元(帧、分组、帧、分组、报文，或统称为报文，或统称为PDU)进行检验和保护，进行检验和保护，v而另一些协议则只需要对数据单元的首部而另一些协议则只需要对数据单元的首部(控控制部分制部分)或首部中的某个字段进行检验和保护。或首部中的某个字段进行检验和保护。v选择被保护对象的选择被保护对象的主要依据是什么？

44、主要依据是什么？协议提供的功能，协议提供的功能，下层协议提供的服务的特点下层协议提供的服务的特点以及性能上的要求等以及性能上的要求等 2022年6月19日星期日差错控制技术2-56现有协议的例子现有协议的例子v HDLC，点对点数据传输协议点对点数据传输协议 ，整帧整帧(不包括首尾标志字段不包括首尾标志字段) v PPP，Internet中的点对点协议中的点对点协议，整帧整帧 v IP，网际互连网际互连，首部首部v TCP，面向连接的可靠的端到端数据传输服务面向连接的可靠的端到端数据传输服务，整个整个TPDU (计算检验和时要加上一个伪首部计算检验和时要加上一个伪首部)v UDP，无连接的不可

45、靠的端到端数据传输服务无连接的不可靠的端到端数据传输服务，整个整个TPDU (计算检验和时要加上一个伪首部计算检验和时要加上一个伪首部)，检验和可选检验和可选 v ATM协议协议 ，传输传输ATM信元信元 ，信元首部信元首部v ATM AAL1，支持实时的、面向连接的支持实时的、面向连接的CBR数据传输服务数据传输服务，首部中的序号计数器字段的首部中的序号计数器字段的CRC检验，整个首部的奇偶检验。检验，整个首部的奇偶检验。可选的负载字段的可选的负载字段的FEC。 2022年6月19日星期日差错控制技术2-57现有协议的例子（现有协议的例子（Cont.）v ATM AAL2 ，传输实时、低速率

46、可变长度的短分组，支持话传输实时、低速率可变长度的短分组，支持话音业务音业务 ，首部首部 v ATM AAL3/4 ，支持可变比特率以及面向连接和无连接的服支持可变比特率以及面向连接和无连接的服务务 ，整个整个SAR-PDU v ATM AAL5 ，传输高速数据传输高速数据(AAL3/4(AAL3/4的简化版的简化版) ) ，整个整个CS-PDU v 帧中继帧中继 ，高速数据传输高速数据传输 ，整帧整帧2022年6月19日星期日差错控制技术2-58思考题思考题2-10 请解释上述协议采用的差错检测方法及选择请解释上述协议采用的差错检测方法及选择的被操作对象的理由。的被操作对象的理由。2-11

47、是否在所有协议中，检验和生成函数的输入是否在所有协议中，检验和生成函数的输入只有被保护数据？请举例说明，并作出解释。只有被保护数据？请举例说明，并作出解释。2022年6月19日星期日差错控制技术2-59差错控制技术：内容提纲差错控制技术：内容提纲2.4.1 差错类型差错类型2.4.2 差错检测技术差错检测技术2.4.3 差错控制技术差错控制技术2.4.4 差错控制与层次的关系差错控制与层次的关系2022年6月19日星期日差错控制技术2-60差错控制技术：概述差错控制技术：概述v上一节我们已详细介绍了用于检测信息被上一节我们已详细介绍了用于检测信息被“损损坏坏”的各种检测技术的各种检测技术v本节

48、我们主要介绍本节我们主要介绍“丢失丢失”、“重复重复”、“失失序序”等错误的检测技术以及各种差错的恢复技等错误的检测技术以及各种差错的恢复技术。术。 v这些技术涉及的概念主要有：这些技术涉及的概念主要有：确认确认 (Ack)计时器计时器 (Timer)重传重传 (Retransmit)序号序号 (Sequence Number)2022年6月19日星期日差错控制技术2-61差错控制技术差错控制技术一、确认一、确认(Acknowledge) 2022年6月19日星期日差错控制技术2-62确认确认v确认确认(ack)是接收者显式地通知发送者所发送的是接收者显式地通知发送者所发送的特定数据的接收情况

49、特定数据的接收情况v被确认的对象主要有哪些？被确认的对象主要有哪些？PDU字节字节v确认的情况：确认的情况：已正确到达，已正确到达，还没有收到，还没有收到，收到但有错收到但有错(相当于没有收到相当于没有收到) 2022年6月19日星期日差错控制技术2-63确认确认(续续)v确认分为三种类型：确认分为三种类型： 肯定确认肯定确认(Ack)指示数据已正确收到指示数据已正确收到否定确认否定确认(Nak)指示数据丢失指示数据丢失(没收到或收到但有错误没收到或收到但有错误) 选择确认选择确认(Select Ack)既指示已正确接收的数据既指示已正确接收的数据PDU，又指示哪些数据，又指示哪些数据PDU还

50、没有正确收到还没有正确收到 2022年6月19日星期日差错控制技术2-64确认确认(续续)v两种发送方式：两种发送方式：独立确认独立确认指用一个确认指用一个确认PDUPDU来携带确认信息来携带确认信息 独立确认随时可以发送独立确认随时可以发送另一种是另一种是应答携带应答携带(piggybacking) 将确认信息放在数据将确认信息放在数据PDU中发送中发送可以提高协议的效率，但要求接收方有数据发送可以提高协议的效率，但要求接收方有数据发送时才能发送确认时才能发送确认v通常在一种协议中，这两种确认形式均存在通常在一种协议中，这两种确认形式均存在 2022年6月19日星期日差错控制技术2-65确认

51、（续）确认（续）v 如何标识被确认的对象？如何标识被确认的对象？用被确认的数据用被确认的数据PDU或字节或字节的序号来标识的序号来标识否定和肯定确认由一个序号构成否定和肯定确认由一个序号构成如果否定确认或肯定确认的语义是表示所给定的序号之前的如果否定确认或肯定确认的语义是表示所给定的序号之前的所有序号所有序号( (包括或不包括本序号包括或不包括本序号) )的数据的数据PDU都已被成功地接都已被成功地接收了，则该确认又称为收了，则该确认又称为累计确认累计确认。 选择确认信息中包含多个序号，其格式可以有以下几种：选择确认信息中包含多个序号，其格式可以有以下几种： 表。表中含有一组序号，要么代表丢失

52、的数据表。表中含有一组序号，要么代表丢失的数据PDU，或者代，或者代表正确接收的数据表正确接收的数据PDU。范围。范围用序号区间来表示，在区间内的序号要么代表丢范围。范围用序号区间来表示，在区间内的序号要么代表丢失的数据失的数据PDUPDU，或者代表正确接收的数据，或者代表正确接收的数据PDUPDU。 位图。用一个比特组来表示确认，其中每一个比特位代表一位图。用一个比特组来表示确认，其中每一个比特位代表一个序号，它被置位表示它所代表的数据个序号，它被置位表示它所代表的数据PDU是否已正确收到。是否已正确收到。此外，这种方法还需要一个序号，指明该位图的偏移量。此外，这种方法还需要一个序号，指明该

53、位图的偏移量。 2022年6月19日星期日差错控制技术2-66(a) 肯 定 确 认(b) 否 定 确 认(c) 选 择 确 认firstnlastn,nfirst,nn,n(1)first,n-1 n,nfirst,n-1n,lastfirst,n i,j,.,(2)(3)(4)(5)(6)表 示 已 正 确 收 到 序 号 对 应 的 帧表 示 尚 未 收 到 序 号 对 应 的 帧first = 第 1个 发 送 的 序 号 last = 最 后 发 送 的 序 号 i,j=序 号 区 间2022年6月19日星期日差错控制技术2-67确认（续）确认（续）v产生一个确认产生一个确认PDU的

54、触发机制的触发机制：在接收了在接收了n个数据个数据PDU之后，接收者产生一个确认之后，接收者产生一个确认PDU； 发送者产生一个信号，请求产生一个确认发送者产生一个信号，请求产生一个确认PDU。信。信号可以随同一个数据号可以随同一个数据PDU一起传递（一起传递（例：例：HDLC中中的什么字段？的什么字段？），也可以是一个专用的控制），也可以是一个专用的控制PDU。接收者直到数据接收者直到数据PDU不连续到达时，才产生一个确不连续到达时，才产生一个确认认PDU； 接收者周期性地产生确认接收者周期性地产生确认PDU，与数据，与数据PDU的到来的到来无关；无关； 接收者重复收到同一个数据接收者重复收

55、到同一个数据PDU，接收者发送确认，接收者发送确认PDU，防止确认丢失；，防止确认丢失； 接收者在发送的数据中携带确认信息。接收者在发送的数据中携带确认信息。 2022年6月19日星期日差错控制技术2-68确认：思考题确认：思考题2-12 分析分析TCP协议采用的确认机制（提示：参考协议采用的确认机制（提示：参考相关相关RFC）或）或 分析分析ATM的信令协议采用的确认的信令协议采用的确认机制。机制。2-13 试分析高速传输协议与低速传输协议所采用试分析高速传输协议与低速传输协议所采用的确认机制上的差别。要求：先从原理上说明，的确认机制上的差别。要求：先从原理上说明，然后举例说明。然后举例说明

56、。2022年6月19日星期日差错控制技术2-69差错控制技术差错控制技术二、计时器二、计时器(Timer) 2022年6月19日星期日差错控制技术2-70计时器计时器v为什么需要计时器？为什么需要计时器？如果携带确认信息的确认如果携带确认信息的确认PDU或数据或数据PDU丢失，则丢失，则发送方无法知道发送的发送方无法知道发送的PDU的接收情况。的接收情况。 这将导致：这将导致：对于可靠通信协议而言，占用发送方缓存对于可靠通信协议而言，占用发送方缓存由于流量控制而不能发送新的由于流量控制而不能发送新的PDU发送方一直处于等待状态，死锁发送方一直处于等待状态，死锁计时器：计时器：检测确认检测确认P

57、DU或重传请求信号的丢失或重传请求信号的丢失2022年6月19日星期日差错控制技术2-71计时器（续）计时器（续）v计时器的超时值如何设置？计时器的超时值如何设置？是一个非常复杂及难解决的问题是一个非常复杂及难解决的问题依赖于依赖于PDU的住返时间的住返时间（RTT）RTTRTT与网络负载和路由选择策略有很大的关系，通常与网络负载和路由选择策略有很大的关系，通常情况下是一个动态变化的量情况下是一个动态变化的量动态估计动态估计往返时间和重传计时器的定时值的算法比较多往返时间和重传计时器的定时值的算法比较多RFC793RFC793中定义的中定义的TCPTCP算法算法MillsMills算法算法(M

58、ills, 1983)(Mills, 1983)EdgeEdge算法算法(Edge, 1984)(Edge, 1984)KarnKarn和和PatridgePatridge的算法的算法(Karn and Patridge(Karn and Patridge, 1987), 1987)Jacobson/KarelJacobson/Karel的算法的算法(Jacobson, 1988) (Jacobson, 1988) 2022年6月19日星期日差错控制技术2-72计时器（续）计时器（续）v计时器的超时值如何设置？（续）计时器的超时值如何设置？（续）如果超时计时器的超时值设置不当，如果超时计时器的

59、超时值设置不当，会导致什么后果？会导致什么后果？连续大量的数据重传连续大量的数据重传严重情况下将加剧网络的拥塞程度，出现更多数据严重情况下将加剧网络的拥塞程度，出现更多数据丢失丢失 如果超时值设置太长，出现数据丢失而得不到即时如果超时值设置太长，出现数据丢失而得不到即时纠正，也会降低协议的性能纠正，也会降低协议的性能2022年6月19日星期日差错控制技术2-73计时器（续）计时器（续）v为了差错控制的目的，一个协议中往往存在多个为了差错控制的目的，一个协议中往往存在多个计时器计时器OSIOSI类类4 4运输协议：运输协议：发起计时器发起计时器：CR(CR(建连请求建连请求) TPDU) TPD

60、U重传重传重传重传CCCC计时器计时器：CC (CC (连接证实连接证实)TPDU)TPDU重传重传重传计时器重传计时器：DT (DT (数据数据)TPDU)TPDU重传重传加速重传计时器加速重传计时器：ED(ED(加速数据加速数据) TPDU) TPDU重传重传释放计时器释放计时器：DR(DR(断连请求断连请求) TPDU) TPDU重传重传放弃加速计时器放弃加速计时器：最后检查未被确认的：最后检查未被确认的ED TPDUED TPDU静止计时器静止计时器：运输连接保持静止状态的最大时间：运输连接保持静止状态的最大时间 窗口计时器窗口计时器：重传：重传AK(AK(确认确认) TPDU) TPDU的最大时间间隔的最大时间间隔参照计时器参照计时器