第4-2讲差错控制技术

内容提纲1概述2

差错类型3

差错检测技术4

差错控制技术5差错控制与网络层次的关系1第一页，共49页。第一页，共49页。差错控制：概述网络通信的目的是通过网络在应用进程间传输信息，任何数据丢失或损坏都将对通信双方产生重要的影响。差错控制是指在网络通信过程中发现（检测）差错，并采取措施纠正，把差错限制在所允许的尽可能小的范围内的技术和方法。差错控制的目的是为了提高数据传输的可靠性，但是任何一种差错控制方法均不可能纠正所有可能出现的差错。2第二页，共49页。第二页，共49页。差错类型（续）根据差错的表现形式，可分为四类（１）：失真(Distortion)定义：被传送信息中的一个或多个比特发生了改变，或者被传送的信息中插入了一些新的信息，后一种情况也称为“插入(Insertion)”主要原因：网络中物理干扰（如线路噪声）发送者和接收者之间的失步入侵者的故意攻击结点中的硬件故障和软件差错等解决方法：各种校验方法来检测3第三页，共49页。第三页，共49页。差错类型（续）根据差错的表现形式，可分为四类（２）丢失(Deletion)定义：网络将被传输的信息丢弃主要原因：噪声脉冲对某个帧的破坏程度太大，以致接收方不知道这个帧已经被传输；发送者和接收者之间的失步；流量控制或拥塞控制措施不当时因资源不够而被中间结点或接收者丢弃；因接收者检测到信息被损坏而主动将其丢弃等解决方法：用序号、计时器和确认共同检测，通过重传的方法来纠正错误4第四页，共49页。第四页，共49页。差错类型（续）根据差错的表现形式，可分为四类（３）重复(Duplication)定义：多次收到同样的信息主要原因：是差错控制机制本身，如果发送方错误地认为数据丢失了，因而重传了它，就可能造成接收方收到重复的信息路由选择机制引起的重复帧，如使用基于扩散的路由选择策略(如洪泛法)解决方法：用序号来检测这种错误，用丢弃重复的数据来纠正错误。5第五页，共49页。第五页，共49页。差错类型（续）根据差错的表现形式，可分为四类（４）失序(Reordering)定义：数据到达接收方的顺序与发送方发送的顺序不一致

主要原因：采用自适应的路由选择策略，分组在网络中传送时可能有多条路由而引起的后发先到

中间结点缓存或转发出错重传丢失的数据也可能导致数据不按序到达解决方法：把乱序的数据先存储下来，使得以后能把它们存放在正确的位置上；丢弃乱序的数据，然后按数据丢失来处理。6第六页，共49页。第六页，共49页。差错检测技术：概述检查收到的数据是否正确通常情况下，我们所说的差错检测是指检测收到的数据是否被损坏，而不包括对数据丢失、重复、乱序等差错的检测在这样的前提下，差错检测技术所采取的方法一般是各种检验和技术，如奇偶检验，循环冗余检验等,本节主要介绍这方面的技术差错检测是差错控制的基础

7第七页，共49页。第七页，共49页。差错检测技术：原理E,E’：差错检验码对比接收器数据EE'=f(Data)数据EE=f(Data)发送器数据f:差错检验函数问题：为什么将检验码放在帧的尾部？8第八页，共49页。第八页，共49页。奇偶检验奇偶检验在数据的尾部附加上奇偶检验位，使得码字中比特“1”的个数保持为奇数(奇检验)或偶数(偶检验)被广泛用于诸如计算机的异步串行口通信中三种类型：垂直冗余检验(VerticalRedundancyChecking，VRC)水平（纵向）冗余检验(LongitudinalRedundancyChecking，LRC)垂直水平冗余检验

9第九页，共49页。第九页，共49页。奇偶检验：垂直冗余检验原理：将整个发送的信息分为长度为p位的若干段，如q段，每段后面按“1”的个数为奇数或偶数的规律加上一位奇偶位，其有(pq)个信息位，每段由p位构成，共q段。通常p值等于一个字符的长度，因此有时也将垂直冗余检验称为字符奇偶检验。可以用硬件或软件方法来实现连续半加（不考虑进位）运算，且可以边发送边产生检验位，并插入检验位发送。在接收时边接收边进行检验并除去检验位能检测出每行中的所有奇数个位的错，但检测不出偶数个位的错。对于突发错误而言，奇数位错与偶数位错的概率差不多是相等的，因而对差错的漏检率接近于50%。

10第十页，共49页。第十页，共49页。奇偶检验：水平冗余检验原理：对各个信息段的相应位水平进行编码，对应每一列产生一个奇偶检验位。这种水平基础上检验字符的技术，使用了和垂直冗余检验同样的奇偶性。

漏检率要比垂直冗余检验低。不但可以检测出各段同一位上的奇数位错，而且可以检测出突发长度小于等于p的所有突发错误（Why?）突发长度小于等于p的突发错误必然分布在不同列中，每列一位，所以可以检测出来

11第十一页，共49页。第十一页，共49页。奇偶检验：垂直水平冗余检验同时进行垂直冗余检验和纵向冗余检验能检测出所有3位或3位以下的错误(因为此时至少在某一行或某一列上为一位错)、奇数位错、突发长度小于等于(p+1)的突发错。还可以纠正部分差错，例如仅在某一行和某一列中有1位错时，就可以确定错误的位置就在该行和该列的交叉处，从而得以纠正。

此外，能检测很大一部分偶数位错。当某一行出现偶数个错时，虽然垂直冗余检验不能发现，但在其纵向冗余检验中还是可以被检测出来；反之亦然。只有当有错的各行和各列中出错位数均为偶数时，才不可能被发现。

12第十二页，共49页。第十二页，共49页。CRC检验：原理CRC是数据通信中进行错误检查和纠正的一种重要方法，易于编码和解码，对随机和突发错码均能以较低冗余度实施检查。方法：发端产生一个循环冗余检验码，附在信息位后面发到收端，收端按照与发端同样的算法进行检验，若有错，需要重发。线性码：由k位信息码和r位检验码构成，每位检验码都是前面某些信息码元的模2和（即按照线性关系相加），码长n=k+r。线性码特点：封闭性（任意两个码字相加仍可得到一个码字）和循环型（一个码字作任意循环移位得到的仍是码字）。13第十三页，共49页。第十三页，共49页。CRC检验：示例

1101010110←Q

商除数P→1101011000←XrM被除数

110101111011

110101111010

110101111110

110101101100

110101110010

11010101110←R

余数

数据：M=1010001101

除数P（生成多项式）=X5+X4+X2+X0XrM(X)=P(X)Q(X)+R(X)

模2运算：加法不进位，减法和加法一样，例如：1111+1010=0101

冗余码（R(X)）称为帧检验序列FCST(X)=XrM(X)+R(X)称为循环码接收端运算：[XrM(X)+R(X)]/P(X)=Q(X)，有错：余数R(X)!=0；无错：余数R(X)=0，去掉尾部r位便得到信息码

问题：R(X)等于0就肯定没有错吗？常见多项式：

CRC-CCITT=X16+X12+X5+1；CRC-16=X16+X15+X2+1CRC-12=X12+X11+X3+X2+X+1CRC-32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1（信息多项式）14第十四页，共49页。第十四页，共49页。算术检验和（因特网检验和）尽管可以通过前面介绍的查表方法或特殊硬件方法计算检验和来缩短处理时间，但：对于允许一定程度漏检率的应用场合，可以采用比CRC检验简单且又能够发现比较严重的传输错误的方法来进行差错检测。JohnFletcher在1982提出了这样一种差错检测方法，称为算术检验和只需用到加法和取模操作算法特别简单

一些因特网协议（TCP、UDP和IP）使用这种方法，强调易实现性和简单性15第十五页，共49页。第十五页，共49页。ArithmeticChecksumErrordetectionatthehigherlayerisusuallydonebyordinaryarithmeticoperations.ThisissimplerinsoftwarebutsomewhatlesseffectivethanCRC.Standardtechniqueistoviewpacketassequenceofknumbersofnbitseach,sayx1,x2,...,xk.Checksumisthenthenbitnumberx1+x2+...+xkusingordinaryarithmeticwithnocarry.16第十六页，共49页。第十六页，共49页。ArithmeticChecksum(Cont.)Alternatively,checksummightbe2nbits;firstnbitsis(sum)x1+x2+...+xkandsecondnbitsis(sumofsum)x1+2x2+3x3+...+kxk.Example:n=16,checksumis16bits.Checksum=x1+x2+...+xk，接收端计算x1+x2+...+xk+Checksum=0，则没有错误。17第十七页，共49页。第十七页，共49页。UDP协议的差错检测10011→153.1900001→8.10410101→171.30000111000001011→16.1100000→0和1700000→150000010000111111→108700000→1300000→1500000→0（检验和）0101010001000101→数据01010→数据01001→数据0100011100000000→数据和0（填充）1001011011101011→求和得出的结果01101→检验和153.19.8.104171.3.16.11全0171510871315全0数据数据数据数据数据数据数据全012字节伪首部7字节数据填充按二进制反码运算求和将得出的结果求反码两个数进行二进制反码求和的运算规则是从低位到高位逐列进行计算。0和0相加是0，0和1相加是1，1和1相加是0但要产生一个进位1，加到下一列。最高位相加后产生的进位则进到最低位，也就是循环进位。18第十八页，共49页。第十八页，共49页。UDP协议的差错检测10011→153.1900001→8.10410101→171.30000111000001011→16.1100000→0和1700000→150000010000111111→108700000→1300000→1500000→0（检验和）0101010001000101→数据01010→数据01001→数据0100011100000000→数据和0（填充）1001011011101011→求和得出的结果01101→检验和153.19.8.104171.3.16.11全0171510871315全0数据数据数据数据数据数据数据全012字节伪首部7字节数据填充按二进制反码运算求和将得出的结果求反码19第十九页，共49页。第十九页，共49页。TCP协议的差错检测检验和字段检验的范围包括首部和数据这两部分。和UDP用户数据报一样，在计算检验和时，要在TCP报文段的前面加上12字节的伪首部。伪首部的格式与UDP用户数据报的伪首部一样。但应将伪首部第6个字段中的17改为6（TCP的协议号是6），将第5字段中的UDP长度改为TCP长度。TCP必须进行检验(UDP可选)。20第二十页，共49页。第二十页，共49页。前向纠错技术前向纠错：在每个要发送的数据块附加足够的冗余信息(纠错码)，使接收方能够推导出发送方实际发送的应该是什么样的比特串。前面介绍的纵向垂直冗余检验就具有纠错功能。汉明码(HammingCode)一般情况下，使用差错检测技术检测出传输错误后，通常使用重传（请求重传和超时重传）的方法来纠正。

为什么需要前向纠错(ForwardErrorCorrection,FEC)？21第二十一页，共49页。第二十一页，共49页。前向纠错技术在有些场合下，不适合或不能使用重传的方法，例如：

很长的传输时延：例如，空间探测器与地面控制中心之间的通信，可能没有足够的时间来重传没有反向信道：在单向广播系统中，根本不能发送重传请求。

高的比特差错率：重传帧以及请求重传帧出错的概率都非常高，使得重传难以实现

某些实时性应用发端的信息无法存储22第二十二页，共49页。第二十二页，共49页。被保护对象的选择有些协议中，是对整个数据单元（帧、分组、报文，或统称为PDU）进行检验和保护，而另一些协议则只需要对数据单元的首部(控制部分)或首部中的某些字段进行检验和保护。选择被保护对象的主要依据是：协议提供的功能下层协议提供的服务的特点性能上的要求等

23第二十三页，共49页。第二十三页，共49页。思考题1

请说明上述协议采用的差错检测方法及选择的被保护对象的理由。2

是否在所有协议中，检验和生成函数的输入只有被保护数据？请举例说明，并作出解释。24第二十四页，共49页。第二十四页，共49页。差错控制技术一、确认(Acknowledge)25第二十五页，共49页。第二十五页，共49页。确认确认(ack)是接收者显式地通知发送者所发送的特定数据的接收情况被确认的对象主要有PDU字节确认的情况：已正确到达，还没有收到，收到但有错（相当于没有收到）

26第二十六页，共49页。第二十六页，共49页。确认(续)确认分为三种类型：

肯定确认(Ack)指示数据已正确收到否定确认(Nak)指示数据丢失（没收到或收到但有错误）

选择确认(SelectAck)既指示已正确接收的数据，又指示哪些数据还没有正确收到

27第二十七页，共49页。第二十七页，共49页。确认(续)两种发送方式：独立确认指用一个确认PDU来携带确认信息独立确认随时可以发送另一种是捎带确认(piggybacking)将确认信息放在数据PDU中发送可以提高协议的效率，但要求接收方有数据发送时才能发送确认通常在一种协议中，这两种确认形式均存在。28第二十八页，共49页。第二十八页，共49页。确认（续）如何标识被确认的对象？用被确认的PDU或字节的序号来标识否定和肯定确认通常包含一个序号如果确认的语义表示给定序号之前的所有序号(包括或不包括本序号)的数据都已被成功接收，则该确认又称为累计确认。

选择确认信息中包含多个序号，其格式可以有以下几种：

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

29第二十九页，共49页。第二十九页，共49页。确认：思考题3

讨论TCP协议采用的确认机制（考虑收到正确数据、错误数据、数据丢失、重复、失序等情况）并分析确认机制的效率。4

试分析高速传输协议与低速传输协议所采用的确认机制上的差别（如帧中继和X.25）。30第三十页，共49页。第三十页，共49页。差错控制技术二、计时器(Timer)31第三十一页，共49页。第三十一页，共49页。计时器为什么需要计时器？如果携带确认信息的确认PDU或数据PDU丢失，则发送方无法知道发送的PDU的接收情况。这将导致：对于可靠通信协议而言，占用发送方缓存由于流量控制而不能发送新的PDU发送方一直处于等待状态，死锁计时器：检测确认PDU或重传请求信号的丢失32第三十二页，共49页。第三十二页，共49页。计时器（续）计时器的超时值如何设置？是一个非常复杂和难解决的问题，依赖于住返时间（RTT）RTT与网络负载和路由选择策略有很大的关系，通常情况下是一个动态变化的量动态估计往返时间和重传计时器定时值的算法Mills算法(Mills,1983)Edge算法(Edge,1984)Karn和Patridge的算法(KarnandPatridge,1987)Jacobson/Karel的算法(Jacobson,1988)如果超时计时器的超时值设置不当，会导致过短，导致连续大量的数据重传，严重情况下将加剧网络拥塞，甚至出现拥塞崩溃如果超时值设置太长，出现数据丢失而得不到及时纠正，则会降低协议的性能

33第三十三页，共49页。第三十三页，共49页。计时器（续）为了差错控制的目的，一个协议中往往存在多个计时器（续）TCP协议：重传计时器：控制丢失的或丢弃的报文段

冻结计时器：一条连接一个冻结计时器。当发送端的TCP收到一个窗口大小为零(让发送端停止发送)的确认时，就启动冻结计时器。

保活计时器：在某些实现中，用来防止在两个TCP端点之间的连接长期处于空闲

时间等待计时器：在连接终止期间使用。当TCP关闭一个连接时，它并不认为这个连接马上就真正关闭。在时间等待期间中，连接还处于一种中间过渡状态。

34第三十四页，共49页。第三十四页，共49页。计时器：思考题5

请以TCP为例，详细讨论在设置计时器的超时值时应考虑哪些问题。35第三十五页，共49页。第三十五页，共49页。差错控制技术三、重传(Retransmit)36第三十六页，共49页。第三十六页，共49页。重传指发送者重传由确认所指出的数据PDU或重传计时器超时未收到确认的数据PDU。基于滑动窗口的重传方法：回退n帧(Go-back-N)接收方直接丢弃所有不按序到达的数据PDU。发送方从第一个否定确认或超时时所指序号的数据PDU开始，重传所有后续数据PDU。

选择重传(selectiverepeat)发送方只重传否定确认、选择确认和计时器超时指出的那些数据PDU37第三十七页，共49页。第三十七页，共49页。重传（续）实际协议中的重传机制比较复杂，主要是计时器的超时间隔很难确定。

TCP的重传机制重传机制是TCP中最重要和最复杂的问题之一。TCP每发送一个报文段，就设置一次计时器。只要计时器设置的重传时间到而还没有收到确认，就要重传这一报文段。TCP的下层往往是一个互连网环境。发送的报文段可能只经过一个高速率的局域网，也可能经过多个低速率的广域网，并且数据报所选择的路由也可能会发生变化

需要一种动态自适应算法38第三十八页，共49页。第三十八页，共49页。差错控制技术四、序号(SequenceNumber)39第三十九页，共49页。第三十九页，共49页。序号为什么需要序号？为了检测数据PDU的重复、失序和丢失，需要对数据PDU进行无二义性的编号，该编号称为数据PDU的序号编号通常是按照请求服务者传递SDU的次序进行的。这些SDU被放入PDU中进行传输。

序号有三种不同的产生方式：SDU序号：对每个SDU都编上序号，从SDU序号得到PDU的序号。如果该SDU被携带在多个数据PDU中时，还应附加一个SDU数据块号PDU序号：对PDU连续编号，不管它们携带的SDU数据量。

字节序号：一个SDU的每个字节都编号，PDU的序号来自于它所携带的SDU的第1个字节的序号或最后1个字节的序号。

40第四十页，共49页。第四十页，共49页。序号（续）一个重要的问题：如何防止序号重复？使用非常大的序号空间。这个序号空间大到使得在数据单元从这一端传送到另一端的最大可能的迟延时间L内，所有从源点发送出去的新的数据单元都具有不同的序号。在开始一个新的连接时，可以使数据单元的起始序号为上次连接中最后使用过的序号加1。每次连接开始数据单元都使用同样的起始序号，但必须使新的连接推迟开始，如至少在上次的连接释放后推迟时间L。

赋给每个连接一个标号，或者称为连接序号。对于一个给定连接中的每一个数据单元都附上连接序号。当新建一个连接时，就换上一个新的序号(如socket)。41第四十一页，共49页。第四十一页，共49页。序号（续）序号空间的大小与信道特点、确认方法、流量控制方法和PDU数据字段长度有关如果信道的质量比较好，则序号空间要求比较大，从而可以连续发送多个数据单元，提高协议效率采用周期性确认，序号空间就不一定要很大在停止等待协议中，只需要0和1两个序号即可一般来说，序号空间的大小与数据字段长度成反比序号是确认和重传的基础，此外序号还可用于流量控制。42第四十二页，共49页。第四十二页，共49页。差错控制技术：思考题6简要说明确认、计时器、重传、序号之间的