《计算机网络技术》课件-项目四：可靠传输机制

1.差错检测为什么需要差错检测课件制作人：谢钧谢希仁在传输过程中可能会产生比特差错：1可能会变成0而0也可能变成1。在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率

BER(BitErrorRate)。误码率与信噪比有很大的关系。为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。差错检测的基本原理课件制作人：谢钧谢希仁易出现比特差错的链路D数据数据检测出差错吗？是否EDC=差错检测码D=数据由差错校验保护，可能包括首部字段EDC=f(D)EDCD’

EDC’（逻辑上）差错检测的基本原理课件制作人：谢钧谢希仁易出现比特差错的链路D数据数据检测出差错吗？是否EDC=差错检测码D=数据由差错校验保护，可能包括首部字段EDC=f(D)差错检测不是100%可靠！

可能漏掉某些差错，但是非常少较长的EDC字段通常有更好的检测性能EDCD’

EDC’（逻辑上）差错检测的基本原理课件制作人：谢钧谢希仁易出现比特差错的链路D数据数据检测出差错吗？是否EDCD’

EDC’在帧的尾部设置一个差错检验字段存放整个帧（包含首部和数据）的差错检测码这个差错检验字段常称为帧检验序列（FrameCheckSequence，FCS）（逻辑上）差错检测的基本原理课件制作人：谢钧谢希仁易出现比特差错的链路D数据数据检测出差错吗？是否EDCD’

EDC’在数据链路层传送的帧中，广泛使用循环冗余检验CRC的检错技术。CRC检错性能高，并易于硬件实现。（逻辑上）循环冗余检验CRC设原始数据D

为d

位二进制数如果要产生r

位CRC校验码R，事先选定一个r+1位二进制位模式G(称为生成多项式，收发双方提前商定)，G

的最高和最低位为1将原始数据D

乘以2r

（相当于在D

后面添加r

个0），产生d+r

位二进制位模式，用G

对该位模式做模2除法，得到余数R（r

位，不足r

位前面用0补齐）即为CRC校验码课件制作人：谢钧谢希仁冗余码的计算举例课件制作人：谢钧谢希仁假定数据

D=101001(即d=6)设G=1101（即r=3）被除数是2rD=101001000

模2除法运算：商

Q=110101，余数

R=001把余数R作为冗余码添加在数据D的后面发送出去。发送的数据是：2rD+R，即：101001001，共(d+r)位。循环冗余检验的原理说明

110101

←

Q

(商)G(除数)→

1101101001000

←

2rD(被除数)

1101

1110

1101

0111

0000

1110

1101

0110

0000

1100

1101

001←R(余数)，作为FCS

接收端检验差错在接收端把接收到的数据除以同样的除数生成式G（模2运算），然后检查得到的余数，即进行CRC检验。若得出的余数R=0，则判定这个帧没有差错，就接受。若余数R

0，则判定这个帧有差错，就丢弃。只要经过严格的挑选，并使用位数足够多的除数G，那么出现检测不到的差错的概率就很小很小。课件制作人：谢钧谢希仁帧检验序列FCS课件制作人：谢钧谢希仁在数据后面添加上的冗余码称为帧检验序列

FCS(FrameCheckSequence)。循环冗余检验CRC和帧检验序列FCS并不等同。CRC是一种常用的检错方法，而FCS是添加在数据后面的冗余码。FCS可以用CRC这种方法得出，但CRC并非用来获得FCS的唯一方法。

应当注意使用CRC这样的差错检测技术，只能检测出帧在传输中出现了差错，并不能纠正错误。虽然任何差错检测技术都无法做到检测出所有差错，但通常我们认为：凡是接收端数据链路层通过差错检测并接受的帧，我们都认为这些帧在传输过程中产生差错的概率几乎为零。要想纠正传输中的差错可以使用冗余信息更多的纠错码进行前向纠错。通过纠错码能检测数据中出现差错的具体位置，从而纠正错误。这种方法开销非常大。通常采用下次课（可靠传输）将要讨论的确认重传机制来纠正传输中的差错，或者仅仅是丢弃检测到差错的帧，由上层协议去解决数据丢失的问题。课件制作人：谢钧谢希仁2.停止等待协议问题发送方和接收方通过一条双向不可靠（可能出现比特差错、分组丢失）信道连接。采取什么措施能够将数据从发送方可靠地传输到接收方？发送方接收方双向不可靠信道?可靠传输在不可靠的信道上实现可靠的数据传输为上层提供一条可靠的逻辑通道单向可靠信道可靠传输协议（发送方）可靠传输协议（接收方）上层实体上层实体双向不可靠信道常用方法：反馈与重传确认与否认发送方DATAACK接收方ttDATADATANAK丢弃重传数据帧确认帧否认帧ACK停止等待协议DATA超时重传ttDATAACKDATA发送方接收方DATA超时重传

超时计时器的重传时间应当比平均往返时间要稍微长一些！超时重传tt发送方接收方DATA

丢弃为了使协议实现起来更加简单，可以统一用超时重传来解决比特差错问题，而不使用NAK。DATAACKDATA超时重传确认丢失ttACKDATADATA发送方接收方超时重传

?重复数据也是一种错误！增加序号来识别重复帧！确认丢失ttACKDATA0DATA0重复帧，丢弃ACKDATA1发送方接收方ACKDATA0只用1比特序号的停等协议也称为比特交替协议超时重传

确认迟到/提前超时DATA0重复帧，丢弃发送方接收方超时

由于确认帧无序号，无法区分重复确认ACKDATA0ACKDATA1DATA0误认为重复帧，丢弃误认为DATA1已收到发送下一帧ACK误认为DATA0已收到发送下一帧DATA1重传确认帧也应该进行编号！确认迟到/提前超时DATA0重复帧，丢弃发送方接收方超时重传

ACK0DATA0ACK0DATA1DATA1正确接收，并确认忽略重复确认ACK1超时重传确认迟到/提前超时ttDATA0重复帧，丢弃发送方接收方超时重传

ACK0DATA0ACK0DATA1ACK1DATA0忽略重复确认比特交替协议发送方流程V(S)

0从上层实体取数据装配帧并放入缓存seq

V(S)发送并置定时器V(S)1V(S)等待ack=V(S)?超时收到确认否是发送方的发送序号：V(S)接收方的接收序号：V(R)数据帧序号：seq确认序号：ack比特交替协议接收方流程发送方的发送序号：V(S)接收方的接收序号：V(R)数据帧序号：seq确认序号：ackV(R)0从帧中取数据交上层实体发送确认帧ack1

V(R)发送确认帧ack

V(R)V(R)1V(R)等待seq=V(R)?收到数据否是检测到差错?丢弃是否丢弃可靠传输的机制差错检测确认超时重传否认重传（一般不采用）序号（数据帧序号和确认号）采用反馈和重传机制的可靠传输协议常称为自动重传请求ARQ(AutomaticRepeatreQuest)协议。可靠传输的模型重传、编号、确认都是由可靠传输协议实体实现的，上层实体完全无需关心！单向可靠信道可靠传输协议可靠传输协议上层实体上层实体双向不可靠信道停等协议的信道利用率TDRTTATD+RTT+TAB数据帧确认tt数据帧确认RTT(Round-TripTime):往返时延TA信道利用率

=发送有效数据时间总时间当往返时延相对发送时延较大时，停止等待协议的信道利用率是很低的。流水线方式连续ARQ协议B连续发送分组而不等待确认ttA确认如果发送方和接收方之间的链路会造成帧失序（先发送的帧可能会比后发送的帧后到达），比特交替停止等待协议，会不会出现协议错误地收下或丢弃数据的情况？举例说明，并思考如何改进协议来解决该问题。思考题停止等待协议3.滑动窗口协议:Go-back-N停等协议信道利用率低TDRTTATD+RTT+TAB数据帧确认tt数据帧确认RTT(Round-TripTime):往返时延TA当往返时延相对发送时延较大时，停止等待协议的信道利用率是很低的。流水线方式连续ARQ协议B连续发送分组而不等待确认ttA确认由于信道上一直有数据不间断地传送，这种传输方式可获得很高的信道利用率。发送方连续发送分组可能会使接收方或网络来不及处理，必须采取措施限制发送方连续发送分组的个数。滑动窗口协议123456789101112(a)发送窗口是发送方可以连续发送的分组序号范围发送窗口(b)收到分组1的确认后发送窗口向前滑动向前123456789101112发送窗口通过设置发送窗口来限制发送方的发送速率发送窗口大小是已发送但还没有收到确认的最大分组数如果发送完窗口内的分组还没有收到确认则必须等待可以发送新的分组滑动窗口的作用发送方接收方发送DATA0发送DATA1发送DATA2发送DATA3发送ACK0发送ACK1发送ACK2发送ACK3发送DATA4发送DATA5发送DATA6发送DATA7信道利用率是停止等待协议的4倍！tt窗口大小为4：出现差错情况发送方接收方发送DATA0发送DATA1发送DATA2发送DATA3?滑动窗口协议：Go-Back-N协议选择重传协议Go-back-N（回退N帧）协议发送方接收方发送DATA0发送DATA1发送DATA2发送DATA3发送ACK0发送ACK1丢弃失序分组，发送ACK1发送DATA4发送DATA5发送DATA2发送DATA3接收方只接收按序到达的分组！(接收窗口大小为1)超时重传丢弃失序分组，发送ACK1丢弃失序分组，发送ACK1发送DATA4发送DATA5累积确认：ACKn表示，DATAn以及以前的分组都已正确接收！接收窗口为[0]接收窗口：接收方允许接收的分组序号的范围接收窗口为[2]发送窗口为[0,1,2,3]发送窗口为[1,2,3,4]由于接收方只接收按序到达的分组，一旦某个分组出现差错（超时），其后连续发送的所有分组都要被重传:Go-Back-N发送ACK2Go-back-N（回退N帧）协议发送方接收方发送DATA0发送DATA1发送DATA2发送DATA3发送ACK0发送ACK1发送ACK2发送ACK3发送DATA4发送DATA5发送DATA6发送DATA7超时前收到ACK2,表示分组0,1,2都已正确接收累积确认：ACKn表示，DATAn以及以前的分组都已正确接收！Go-back-N（回退N帧）协议采用滑动窗口机制。发送方的发送窗口大小为N，可连续发送序号在发送窗口内的分组01OPTION02OPTION接收方的接收窗口大小为1，只按序接收分组。当收到序号错误的分组，接收方将其丢弃并重传最近按序接收分组的确认03OPTION发送方采用超时机制来重传出现差错或丢失的分组。一旦某个分组超时，其后连续发送的所有分组都要被重传04OPTION接收方采用累积确认的方式。接收方对分组n的确认，表明接收方已正确接收到分组n及以前的所有分组。只修改了连续序号停止等待协议的发送方算法，将发送窗口大小由1改为N考虑Go-back-N协议，当接收方收到序号错误的分组，如果仅仅将它们丢弃而不对最近按序接收的分组进行确认，会出现什么错误情况？请画图举例说明。思考题滑动窗口协议:Go-back-N4.滑动窗口协议:选择重传回顾Go-back-N协议采用滑动窗口机制。发送方的发送窗口大小为N，可连续发送序号在发送窗口内的分组01OPTION02OPTION接收方的接收窗口大小为1，只按序接收分组。当收到序号错误的分组，接收方将其丢弃并重传最近按序接收分组的确认03OPTION发送方采用超时机制来重传出现差错或丢失的分组。一旦某个分组超时，其后连续发送的所有分组都要被重传04OPTION接收方采用累积确认的方式。接收方对分组n的确认，表明接收方已正确接收到分组n及以前的所有分组。选择重传协议GBN相对简单，但一个分组的差错可能引起大量分组的重传，这些分组可能已经被接收方正确接收了，但由于未按序到达而被丢弃。01OPTION02OPTION显然GBN对这些分组的重传是对通信资源的极大浪费。03OPTION为进一步提高性能，可设法只重传出现差错