五.流量控制与可靠传输机制
较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要工作。
数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。
数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。
传输层流量控制手段：接收端给发送端一个窗口公告。
1.流量控制的方法
2.可靠传输、滑动窗口、流量控制
Summary:
2.1停止-等待协议
2.1.1.为什么要有停止-等待协议?
除了比特出差错，底层信道还会出现丢包问题。为了实现流量控制。
丢包：物理线路故障、设备故障、病毒攻击、路由信息 错误等原因，会导致数据包的丢失。
2.1.2.研究停等协议的前提?
虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据（发送方），一方接收数据 （接收方）。 因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传送的。 “停止-等待”就是每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。
2.1.3.停等协议有几种应用情况？
无差错情况&有差错情况
2.1.4停等协议性能分析
2.2.1信道利用率
Sunnmary:
六.后退N帧协议(GBN协议)
1.停止-等待协议的弊端
2.滑动窗口
3.GBN发送方必须响应的三件事
3.1上层的调用
上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送；如果窗口已满，发送方只需将数据返回给上层，暗示上层窗口已满。上层等一会再发送。(实际实现中，发送方可以缓存这些数据，窗口不满时再发送帧)。
3.2收到了一个ACK
GBN协议中，对n号帧的确认采用累积确认的方式，标明接收方已经收到号帧和它之前的全部帧。
3.3超时事件
协议的名字为后退N帧/回退N帧，来源于出现丢失和时延过长帧时发送方的行为。就像在停等协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有已发送但未被确认的帧。
4.GBN接收方要做的事
如果正确收到n号帧，并且按序，那么接收方为n帧发送一个ACK，并将该帧中 的数据部分交付给上层
这句话的意思是:假如现在收到了0 1 2号帧 收到4 5号帧,4,5就丢弃掉,收到0,1,2号后,需要等待接受3号帧
其余情况都丢弃帧，并为最近按序接收的帧重新发送ACK。接收方无需缓存任 何失序帧，只需要维护一个信息：expectedseqnum（下一个按序接收的帧序 号）
5.运行中的GBN
6.滑动窗口长度
7.GBN协议性能分析
优点
因连续发送数据帧而提高了信道利用率
缺点
在重传时必须把原来已经正确传送的数据帧重传，是传送效率降低。
Summary:
1.累积确认（偶尔销带确认）2.接收方只按顺序接收帧，不按序无情丢弃3.确认序列号最大的、按序到达的帧4.发送窗口最大为(2^n)-1，接收窗口大小为1
七.选择重传协议(SR)
1.滑动窗口
2.SR发送方必须响应的三件事
2.1上层的调用
从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧；否 则就像GBN一样，要么将数据缓存，要么返回给上层之后再传输。
2.2收到了一个ACK
如果收到ACK，加入该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收。如果该帧序号是窗口 的下界（最左边第一个窗口对应的序号），则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了 并且有序号在窗口内的未发送帧，则发送这些帧。
2.3超时事件
每个帧都有自己的定时器，一个超时事件发生后只重传一个帧。
3.SR接收方要做的事
4.运行中的SR
5.滑动窗口长度
6.SR协议重点总结
习题
1.从滑动窗口的观，点看，当发送窗口为1、接收窗口也为1时，相当于ARQ的(C)方式.A.回退N帧ARQB.选择重传ARQC.停止-等待D.连续ARQ
停止等待协议的工作原理是：发送方每发送一帧，都要等待接收方的应答信号，之后才能发送下一帧；接收方每接收一帧，都要反馈一个应答信号，表示可接收下一帧，如果接收方不反馈应答信号，那么发送方必须一直等待。
2.在简单的停止等待协议中，当帧出现丢失时，发送端会永远等待下去，解决这种死锁现象的办法是(D)A.差错校验B.帧序号C.NAK机制D.超时机制
在停止等待协议中，发送端设置了计时器，在一个帧发送之后，发送端等待确认，如果在计时器计满时仍未收到确认，那么再次发送相同的帧，以免陷入永久的等待。
3.一个信道的数据传输速率为4kb/s,单向传播时延为30s,如果使停止等待协议的信道最大利用率达到80%，那么要求的数据帧长度至少为(D)。A.160bitB.320bitC.560bitD.960bit
设C为数据传输速率，L为帧长，R为单程传播时延，停止-等待协议的信道最大利用率为(LC/(L/C+2)=L/(L+2RC=L/(L+2×30ms×4kb/s)=80%,得出L=960bit。
4.数据链路层采用后退N帧协议方式，进行流量控制和差错控制，发送方已经发送了编号0~6的帧。计时器超时时，只收到了对1、3和5号顿的确认，发送方需要重传的帧的数目是(A).A.1B.2C.5D.6
GBN一般采用累计确认，因此收到了对5号帧的确认意味着接收方已收到1~5号帧，因此发送方仅需要重传6号帧。
5.【2009統考真题】数据链路层采用了后退N顿（GBN)协议，发送方已经发送了编号为0~7的帧。计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是(C)。A.2B.3C.4D.5
在后退N帧协议中，当接收方检测到某个帧出错后，会简单地丢弃该帧及所有的后续帧，发送方超时后需重传该数据帧及所有的后续帧。这里应注意，连续ARQ协议中，接收方一般采用累计确认的方式，即接收方对按序到达的最后一个分组发送确认，因此本题中收到3的确认帧就表示编号为0,1,2,3的帧已接收，而此时发送方未收到1号帧的确认只能代表确认帧在返回的过程中丢失，而不代表1号帧未到达接收方。因此需要重传的帧为编号是4,5,6,7的帧。
6.数据链路层采用了后退N帧的（GBN)协议，如果发送宙口的大小是32，那么至少需要(C)位的序列号才能保证协议不出错。A.4B.5C.6D.7
在后退N帧的协议中，序列号个数不小于MAX_SEQ+1,题中发送窗口的大小是32，那么序列号个数最少应该是33个。所以最少需要6位的序列号才能达到要求。
7.【2012统考真题】两台主机之间的数据链路层采用后退N帧协议(GBN)传输数据，数据传输速率为16kb/s,单向传播时延为270ms,数据帧长度范围是128~512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序列的比特数至少为(B).A.5B.4C.3D.2
数据帧长度是不确定的，范围是128一512B,但在计算至少窗口大小时，为了保证无论数据帧长度如何变化，信道利用率都能达到最高，应以最短的帧长计算。如果以512B计算，那么求得的最小帧序号数在128B的帧长下，达不到最高信道利用率。首先计算出发送一帧的时间128×8/16×10)=64ms:发送一帧到收到确认为止的总时间为64+270×2+64=668ms;这段时间总共可以发送668/64=10.4帧，发送这么多帧至少需要用4位比特进行编号。
8.若采用后退N帧的ARQ协议进行流量控制，帧编号字段为7位，则发送窗口的最大长度为(C)。A.7B.8C.127D.128
接收窗口整体向前移动时，新窗口中的序列号和旧窗口的序列号产生重叠，致使接收方无法区别发送方发送的帧是重发帧还是新帧，因此在后退W帧的ARQ协议中，发送窗口W_T≤2^n-1。本题中n=7,因此发送窗口的最大长度是127。
9.【2011统考真题】数据链路层采用选择重传协议（SR)传输数据，发送方已发送0~3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是(B)。A.1B.2C.3D.4
选择重传协议中，接收方逐个确认正确接收的分组，不管接收到的分组是否有序，只要正确接收就发送选择ACK分组进行确认。因此选择重传协议中的ACK分组不再具有累积确认的作用。对于这一点，要特别注意与GBN协议的区别。此题中只收到1号帧的确认，0、2号帧超时，由于对1号帧的确认不具累计确认的作用，因此发送方认为接收方未收到0、2号帧，于是重传这两帧。
10.一个使用选择重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大接收窗口是(B)。A.15B.16C.31D.32
在选择重传协议中，若采用比特对帧进行编号，为避免接收端向前移动窗口后，新的窗口与旧的窗口产生重叠，接收窗口的最大尺寸应该不超过序号范围的一半，即W_R≤2^n-1。因此选B。
11.对于窗口大小为的滑动窗口，最多可以有（B)帧已发送但没有确认.A.0B.n-1C.nD.n/2
在连续ARQ协议中，发送窗口的大小≤窗口总数-1。例如，窗口总数为8，编号为0一7，假设这8个帧都已发出，下一轮又发出编号0~7的8个帧，接收方将无法判断第二轮发的8个帧到底是重传帧还是新帧，因为它们的序号完全相同。另一方面，对于回退N帧协议，发送窗口的大小可以等于窗口总数一1，因为它的接收窗口大小为1，所有的帧保证按序接收。因此对于窗口大小为n的滑动窗口，其发送窗口大小为1，即最多可以有1帧已发送但没有确认。
12.对无序接收的滑动窗口协议，若序号位数为，则发送窗口最大尺寸为（D)。A.2^n-1B.2nC.2n-1D.2^n
本题并未直接告知使用的是选择重传协议，而是通过间接方式给出的。题目说无序接收的滑动窗口协议，说明接收窗口大于1，所以得出数据链路层使用的是选择重传协议，而选择重传协议的发送窗口最大尺寸为2^n-1。
网络异常，图片无法展示|
C D A
1)发送窗口大小为7意味着发送方在没有收到确认之前可以连续发送7个帧，由于发送方A已经发送编号为0~3的四个帧，下一个帧将是编号为4的帧。
2)当帧的序号长度为k比特时，对于选择重传协议，为避免接收端向前移动窗口后，新的窗口与旧的窗口产生重叠，接收窗口的最大尺寸应该不超过序列号范围的一半，即W≤2。
3)设发送窗口为[L,U],发送窗口大小的初始值为W,发送窗口的大小应该大于等于0，但小于等于W,所以有0≤U-L+1≤W。因此L≥(U-W+1)mod2^k。
14.【2014统考真题】主机甲与主机乙之间使用后退N帧协议（GBN)传输数据，甲的发送窗口尺寸为1000，数据帧长为1000字节，信道带宽为100Mb/s,乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲、乙之间的单向传播时延是50ms,则甲可以达到的最大平均数据传输速率约为（C)。A.10Mb/sB.20Mb/sC.80Mb/sD.100Mb/s
考虑制约甲的数据传输速率的因素。首先，信道带宽能直接制约数据的传输速率，传输速率一定是小于等于信道带宽的：其次，主机甲、乙之间采用后退N帧协议，那么因为甲、乙主机之间采用后退N帧协议传输数据，要考虑发送一个数据到接收到它的确认之前，最多能发送多少数据，甲的最大传输速率受这两个条件约束，所以甲的最大传输速率是这两个值中小的那一个。甲的发送窗口的尺寸为1000，即收到第一个数据的确认之前，最多能发送1000个数据帧，也就是发送
1000×1000B=1B的内容，而从发送第一个帧到接收到它的确认的时间是一个帧的发送时延加上往返时延，即1000B/100Mb/s+50ms+50ms=0.10008s,此时的最大传输速率为1MB/0.10008s≈10B/s=80Mb/s。信道带宽为100Mb/s,所以答案为min{80Mb/s,100Mb/s}=80Mb/s,选C。
15.【2018统考真题】主机甲采用停止-等待协议向主机乙发送数据，数据传输速率是3kb/s,单向传播时延是200ms,忽略确认顿的传输时延。当信道利用率等于40%时，数据帧的长度为()。A.240比特B.400比特C:480比特D.800比特
信道利用率=传输帧的有效时间传输帧的周期。假设帧的长度为x比特。对于有效时间，应该用帧的大小除以数据传输速率，即x/(3kb/s)。对于帧的传输周期，应包含4部分：帧在发送端的发送时延、帧从发送端到接收端的单程传播时延、确认帧在接收端的发送时延、确认帧从接收端到发送端的单程传播时延。这4个时延中，由于题目中说“忽略确认帧的传输时延”，因此不计算确认帧的发送时延（注意区分传输时延和传播时延的区别，传输时延也称发送时延，和传播时延只有一字之差)。所以帧的传输周期由三部分组成：首先是帧在发送端的发送时延x/(3kb/s),其次是帧从发送端到接收端的单程传播时延200ms,最后是确认帧从接收端到发送端的单程传播时延200ms,三者相加可得周期为x/(3kb/s)+400ms。代入信道利用率的公式，求出x=800bit。答案选D。
16.【2020统考真题】假设主机甲采用停等协议向主机乙发送数据帧，数据帧长与确认帧长均为1000B,数据传输速率是10kb/s,单项传播延时是200s。则甲的最大信道利用率为(D)。A.80%B.66.7%C.44.4%D.40%
发送数据顿和确认帧的时间均为t=1000x8b/10kb/s=800ms。
发送周期为T=800ms+200ms+800ms+200ms=2000ms。
信道利用率为/T×100%=800/2000=40%
