3-3数据链路层(流量控制)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,课题：停止等待协议、连续ARQ协议、滑动窗口协议,目的要求：掌握停止等待协议、连续ARQ协议、滑动窗口协议,教学重点：停止等待协议、滑动窗口协议,教学难点：发送窗口和接收窗口,教学课时：2课时,教学方法：多媒体,1,停止等待协议,1 完全理想化的数据传输,数据链路层,主,机,A,缓存,主,机,B,数据链路,AP,2,AP,1,缓存,发送方,接收方,帧,高层,帧,2,完全理想化的数据传输所基于的两个假定,假定 1： 链路是理想的传输信道，所传送的任何数据既不会出差错也不会丢失。,假定 2： 不管发方以多快的速率发送数据，收方总是来得及收下，并及时上交主机。,这个假定就相当于认为：接收端向主机交付数据的速率永远不会低于发送端发送数据的速率。,3,2 具有最简单流量控制的数据链路层协议,现在去掉上述的第二个假定。但是，仍然保留第一个假定，即主机 A 向主机 B传输数据的信道仍然是无差错的理想信道。然而现在不能保证接收端向主机交付数据的速率永远不低于发送端发送数据的速率。,由收方控制发方的数据流，乃是计算机网络中流量控制的一个基本方法。,4,具有最简单流量控制的数据链路层协议算法,在发送结点：,(1) 从主机取一个数据帧。,(2) 将数据帧送到数据链路层的发送缓存。,(3) 将发送缓存中的数据帧发送出去。,(4) 等待。,(5) 若收到由接收结点发过来的信息(此信息,的格式与内容可由双方事先商定好)，则,从主机取一个新的数据帧，然后转到(2)。,5,具有最简单流量控制的数据链路层协议算法（续）,在接收结点：,(1) 等待。,(2) 若收到由发送结点发过来的数据帧，,则将其放入数据链路层的接收缓存。,(3) 将接收缓存中的数据帧上交主机。,(4) 向发送结点发一信息，表示数据帧已,经上交给主机。,(5) 转到(1)。,6,两种情况的对比（传输均无差错）,A,B,DATA,DATA,DATA,DATA,送主机 B,送主机 B,送主机 B,送主机 B,A,B,DATA,送主机 B,DATA,送主机 B,时,间,不需要流量控制,需要流量控制,7,3 实用的停止等待协议,时,间,A,B,DATA0,送,主,机,ACK,DATA1,送,主,机,ACK,(a) 正常情况,A,B,DATA0,DATA0,送,主,机,ACK,(c) 数据帧丢失,重,传,t,out,丢,失,！,A,B,DATA0,送,主,机,ACK,DATA0,丢,弃,ACK,(d) 确认帧丢失,重,传,t,out,丢,失,！,A,B,DATA0,NAK,DATA0,送,主,机,ACK,(b) 数据帧出错,重,传,出错,四种情况,8,超时计时器的作用,结点A发送完一个数据帧时，就启动一个超时计时器(timeout timer)。,计时器又称为定时器。,若到了超时计时器所设置的重传时间,t,out,而仍收不到结点 B 的任何确认帧，则结点 A 就重传前面所发送的这一数据帧。,一般可将重传时间选为略大于“从发完数据帧到收到确认帧所需的平均时间”。,9,解决重复帧的问题,使每一个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加 1。,若结点 B 收到发送序号相同的数据帧，就表明出现了重复帧。这时应丢弃重复帧，因为已经收到过同样的数据帧并且也交给了主机 B。,但此时结点 B 还必须向 A 发送确认帧 ACK，因为 B 已经知道 A 还没有收到上一次发过去的确认帧 ACK。,10,帧的编号问题,任何一个编号系统的序号所占用的比特数一定是有限的。因此，经过一段时间后，发送序号就会重复。,序号占用的比特数越少，数据传输的额外开销就越小。,对于停止等待协议，由于每发送一个数据帧就停止等待，因此用一个比特来编号就够了。,一个比特可表示 0 和 1 两种不同的序号。,11,帧的发送序号,数据帧中的发送序号 N(S) 以 0 和 1 交替的方式出现在数据帧中。,每发一个新的数据帧，发送序号就和上次发送的不一样。用这样的方法就可以使收方能够区分开新的数据帧和重传的数据帧了。,12,可靠传输,虽然物理层在传输比特时会出现差错，但由于数据链路层的停止等待协议采用了有效的检错重传机制，数据链路层对上面的网络层就可以提供可靠传输的服务。,13,连续 ARQ 协议,1 连续 ARQ 协议的工作原理,在发送完一个数据帧后，不是停下来等待确认帧，而是可以连续再发送若干个数据帧。,如果这时收到了接收端发来的确认帧，那么还可以接着发送数据帧。,由于减少了等待时间，整个通信的吞吐量就提高了。,14,连续 ARQ 协议的工作原理,DATA0,DATA1,DATA2,DATA3,DATA4,DATA5,重传 DATA2,重传 DATA3,ACK1,ACK2,ACK1 确认 DATA0,ACK2 确认 DATA1,DATA2 出错，丢弃,DATA3 不按序，丢弃，重传 ACK2,DATA4 不按序，丢弃，重传 ACK2,DATA5 不按序，丢弃，重传 ACK2,ACK3,ACK3 确认 DATA2,ACK4 确认 DATA3,ACK4,重传 DATA5,重传 DATA4,超,时,重,传,时,间,A,B,t,out,送交主机,送交主机,?,ACK2,ACK2,ACK2,15,需要注意：,(1) 接收端只按序接收数据帧。虽然在有差错的 2号帧之后接着又收到了正确的 3 个数据帧，但接收端都必须将这些帧丢弃，因为在这些帧前面有一个 2 号帧还没有收到。虽然丢弃了这些不按序的无差错帧，但应重复发送已发送过的最后一个确认帧（防止确认帧丢失）。,(2) ACK1 表示确认 0 号帧 DATA0，并期望下次收到 1 号帧；ACK2 表示确认 1 号帧 DATA1，并期望下次收到 2 号帧。依此类推。,16,需要注意：,(3) 结点 A 在每发送完一个数据帧时都要设置该帧的超时计时器。如果在所设置的超时时间内收到确认帧，就立即将超时计时器清零。但若在所设置的超时时间到了而未收到确认帧，就要重传相应的数据帧（仍需重新设置超时计时器）。,在等不到 2 号帧的确认而重传 2 号数据帧时，虽然结点 A 已经发完了 5 号帧，但仍必须向回走，将 2号帧及其以后的各帧全部进行重传。连续 ARQ 又称为Go-back-N ARQ，意思是当出现差错必须重传时，要向回走 N 个帧，然后再开始重传。,17,需要注意：,(4) 以上讲述的仅仅是连续 ARQ 协议的工作原理。协议在具体实现时还有许多的细节。例如，用一个计时器就可实现相当于,N,个独立的超时计时器的功能。,18,2 连续 ARQ 协议的吞吐量,可以很方便地导出连续 ARQ 协议的吞吐量公式。,19,3 滑动窗口的概念,发送端和接收端分别设定发送窗口和接收窗口 。,发送窗口用来对发送端进行流量控制。,发送窗口的大小,W,T,代表在还没有收到对方确认信息的情况下发送端最多可以发送多少个数据帧。,20,0,1,2,3,4,5,6,7,0,1,2,发送窗口,W,T,不允许发送这些帧,允许发送 5 个帧,(a),0,1,2,3,4,5,6,7,0,1,2,不允许发送这些帧,还允许发送 4 个帧,W,T,已发送,(b),0,1,2,3,4,5,6,7,0,1,2,不允许发送这些帧,W,T,已发送,(c),0,1,2,3,4,5,6,7,0,1,2,不允许发送这些帧,还允许发送,3 个帧,W,T,已发送,已发送,并已收到确认,(d),21,接收端设置接收窗口,在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。,若接收到的数据帧落在接收窗口之外，则一律将其丢弃。,在连续 ARQ 协议中，接收窗口的大小,W,R,= 1。,只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。,每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。,22,不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,W,R,准备接收 0 号帧,(a),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,W,R,准备接收,1 号帧,已收到,(b),不允许接收这些帧,0,1,2,3,4,5,6,7,0,1,2,W,R,准备接收 4 号帧,已收到,(c),23,滑动窗口的重要特性,只有在接收窗口向前滑动时（与此同时也发送了确认），发送窗口才有可能向前滑动。,收发两端的窗口按照以上规律不断地向前滑动，因此这种协议又称为滑动窗口协议。,当发送窗口和接收窗口的大小都等于 1时，就是停止等待协议。,24,发送窗口的最大值,当用,n,个比特进行编号时，若接收窗口的大小为 1，则只有在发送窗口的大小,W,T, 2,n, 1,时，连续 ARQ 协议才能正确运行。,例如，当采用 3 bit 编码时，发送窗口的最大值是 7 而不是 8。,25,3.4 选择重传 ARQ 协议,可加大接收窗口，先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。,选择重传 ARQ 协议可避免重复传送那些本来已经正确到达接收端的数据帧。,但我们付出的代价是在接收端要设置具有相当容量的缓存空间。,对于选择重传 ARQ 协议，若用,n,比特进行编号，则接收窗口的最大值受下式的约束,W,R,2,n,/2,(3-18),26,作业：请思考连续ARQ协议是否一定优于停止等待协议？滑动窗口协议是什么控制机制？,27,教学总结：本讲讲解滑动窗口协议。下一讲讲解介质访问控制子层。,28,