流量传输与可靠传输

流量控制

我们在前面的流量控制中学习到流量控制涉及对链路上的帧的发送速率的控制，以便使接收方能够有足够的缓冲时间来接收每一个帧。例如：在面向帧的自动重传请求系统中，当待确认帧的数量增加时，有可能就会超出缓冲存储空间而造成过载。此时流量控制的基本方法是由接收方控制发送方发送数据的速率，常见的方法有两种：①停止-等待协议②滑动窗口协议

停止-等待协议流量控制原理

在停止-等待协议中每发送一个帧，都要等待接收方的应答信号，之后才能发送下一个帧，接收方每接收一个正确信息的帧，都要反馈一个应答信号，表示可以接收下一个帧，如果接收方不反馈应答信号或者应答信号在传输过程中丢失，那么发送方就必须一直等待应答信号。这种协议的原理很简单，每次只允许发送一个帧，然后就陷入等待接收方确认信息的过程中，因此传输的效率很低。

思考：已经有差错检测机制了，为什么还需要停-等协议？

帧除了出现比特差错（可以直接被校验和检测）以外，还可能出现帧错，即底层信道出现了丢包问题，此时需要停-等协议来实现流量控制。

思考：研究停-等协议的前提？它属于哪一层的协议？

虽然现在常用全双工通信方式，即双方可以同时发送消息，但是这里为了方便讨论，仅考虑一方发送数据（发送方）和接收数据（接收方）。因为是在讨论可靠传输的原理，因此并不考虑数据是在哪一个层次上传送。在不同的参考书中，停-等协议以及滑动窗口协议被分别划分到了数据链路层、网络层或者传输层等。

思考：停-等协议有几种应用情况?

两种：①无差错情况②有差错情况。所谓的无差错情况就是理想情况，即传送的帧不会丢失并且数据必定无错误，此时的传送情况如下图：

而在实际的传输中，经常会伴随着差错的出现因此有差错情况的传送更加普遍：

我们从上图可以看出在有差错情况下的停-等协议中加入了计时器功能，当发送帧在中途丢失时或者接收的数据帧有错误时接收方都不会发送应答信息，当经过一个时钟周期后计时器可以报错给发送方请求重发从而解决收发双方陷入死循环的情况。

同时帧到达接收方后可能发生了数据的错误而被接收方丢弃，此时帧也需要重发，因此发送方在发送了一个帧后并不会立刻丢弃这个副本，而是保留这个帧的副本以便重发之需，只有当接收到应答信息ACK后才会丢弃这个已发送帧的副本。

思考：还有没有其他可能出现的差错情况？

当然有，可能ACK会发生丢失，此时如下图：

或者还有可能出现ACK迟到的问题：

此时发送方已经成功接收到了重传以后的0帧的ACK0了并且开始下一个1帧的发送了，此时却刚刚收到之前迟到的ACK0，此时发现要等待接收的应答消息ACK序列号和接收到的应答信息ACK序列号不同那么就丢弃继续等待正确的ACK序列号。

思考：停-等协议仅仅使用了0和1可以完成所有的数据帧的传输吗？

当然可以，因为在停-等协议中我们是一帧一帧的发送，因此我们只需要将当前帧和下一个帧区分开即可，因此一个用0一个用1就可以完美的区分当前帧和下一帧。

思考：序列号相同的帧数据一定相同？

很明显不是。我们要透彻理解序列号的作用，他不是一个独一无二的标识唯一帧的标志，而仅仅是区分当前发送帧和下一个要发送帧的。比如现在有如下帧A,B,C,D，我们从0开始标号，那么它们的序列号分别是0(A)，1(B)，0©，1(D)即A和D的序列号都是0，因此序列号不同的数据帧数据可能是不同的。ACK的序列号同理。

思考：接收双方的特定总结？

• 接收方必须是收到正确数据的帧时才会发送应答信息，当收到重复的正确帧时丢弃重复的帧并且由于此时这个重复帧也是正确的数据，因此接收方也会发送应答信息
• 接收方每次发送的应答信息都是最近一次成功接收到的正确数据帧的序列号
• 发送方有以下状态
  1. 发送一个帧后会先保留帧的副本，然后等待与发送帧的序列号相同的ACK，当收到的ACK序列号和要等待的相同，那么发送成功，丢弃这个刚刚发送的帧的副本
  2. 发送一个帧后会先保留帧的副本，然后等待与发送帧的序列号相同的ACK，当发生了帧丢失或者帧数据错误时，由于接收方会保持沉默，因此计时器超时后发送方重发刚刚的帧
  3. 发送一个帧后会先保留帧的副本，然后等待与发送帧的序列号相同的ACK，当收到的ACK序列号和要等待的不同时，说明此时出现了ACK迟到的情况，因此这个序列号不对的ACK是上一个已经成功完成传输的帧的应答信息，发送方直接丢弃这个序列号不对的ACK，继续等待正确的ACK抵达

思考：将数据帧信息错误的情况改进为下面这种方式是否合理？

我们发现在帧发生比特错误的情况下接收方并不会应答导致了很长时间的等待出现，那么我们能不能将其改进，让接收方应答，此时收发双方的特点变成了这样，请问是否合理？

• 接收方无论是否接收到了正确的帧数据，都要传达一个应答信息，这个应答信息是他最近接收到的正确的帧的序列号
• 接收方只有对正确无误的数据帧进行接收，而对于由比特错误的帧要丢弃，但是仍然会发送一个应答信息，显然这个应答信息是上一个正确的数据帧的序列号
• 发送方有两个状态：
  1. 等待接收的ACK序列号和已发送的帧的序列号相同时，说明刚刚发送的帧无错误在抵达接收方后被成功接收了
  2. 等待接收的ACK序列号和已发送的帧的序列号不同时，说明刚刚发送的帧有错误在抵达接收方后被丢弃了，此时需要重传刚刚发送的帧

我们乍一看感觉没有毛病呀😀，这种对策可以有效减少因比特翻转导致的帧数据错误时的等待时间，但是实际上上面这种策略时有很大缺陷的，即他会导致和下面的ACK迟到情况区分不开而造成一系列的错误链式反应：

如果按照上面的策略，那么此时发送方接收到这个迟到的ACK0时会误认为刚刚发送的1帧错误了而导致发送方又要重传1帧。而对于之前的策略，发送方接收到这个迟到的ACK时是直接丢弃的，这样就不会出现发送方重传1帧的情况了，因此这种优化策略是错误的。即接收方收到错误的数据帧时保持沉默是必要且正确的最优策略。

思考：停-等协议的优缺点？

很明显停-等协议的优点就是原理简单，实现起来很容易，但是缺点过于明显，无论是帧丢失还是帧的数据错误都会触发很长时间的等待僵局从而造成信道利用率过低：

信道利用率公式：

$$信道利用率=传输时间/传输周期$$

即

$$信道利用率=（L/R)/T=T_D/T_D+RTT+T_A$$

这里我们从时间角度对信道利用率进行了定义：即对发送方而言，值指发送方在一个发送周期的时间内，有效的发送数据所需要的时间占整个发送周期的比率。并且信道吞吐率与信道利用率有如下关系：

$$信道吞吐率=信道利用率×发送方的发送速率$$

例题

一个信道的数据传输了为4kb/s，单向传播时延为30ms，如果使停止-等待协议的信道最大利用率达到80%，要求数据帧的长度至少为多少字节？

我们设数据帧的长度为L，那么有以下公式：

$$80\%=(L/4)/(L/4+2×30ms)$$

可以解得L=960bit=120B,因此数据帧的长度至少为120字节。

滑动窗口协议流量控制原理

我们思考一下能否对停-等协议进行优化，上面的策略之所以传输效率低有两方面的原因：①一次性只传输一个帧导致效率低②错误全依赖于计时器超时重发机制，接收方不会主动报错造成长时间的等待。

我们前面讲过了接收方对于错误信息不能主动报错这是为了和迟到ACK加以区分，因此我们只能着眼于第一个缺陷加以优化，此时我们可以借鉴流水线的机制：

流水线协议

在停-等协议中并没有使用流水线机制，因此传输的过程图如下图，传输效率低：

而我们可以引入流水线机制如下图，此时传输效率就大大提升了：

可以看到效率提升了将近40倍，因此我们再引入了流水线机制后就提出了一个新的流量控制策略–滑动窗口协议

思考：滑动窗口协议加入了流水线机制后和停-等协议有什么区别？

在介绍滑动窗口之前，首先我们从序列号和收发双方的缓冲区大小就可以比较出区别了。由于停-等协议一次只发送一个帧，因此只有当前发送的一个帧和下一个要发送的帧需要加以区分，因此只需要序列号0和1即可，但是很明显在滑动窗口中由于使用了流水线机制，一个RTT中会有许多个帧在同时传输，因此仅仅用0和1肯定是不够的了，我们需要扩充序列号范围，相应的收发双方的缓冲区大小也要从1扩大。

滑动窗口协议

在任意时刻，发送方都维持一组连续的允许发送的帧的序号，称为发送窗口，同时接收方也维持一组连续的允许接收帧的序号，称为接收窗口。发送窗口用来对发送方进行流量控制，而发送窗口的大小Wt代表在还未收到对方确认信息的情况下发送方最多还可以发送多少个数据帧。同理，在接收端设置接收窗口是为了控制可以接收那些数据帧和不可以接收那些数据帧。在接收方，只有收到的数据正确的帧的序号落入接收窗口内时，才允许将该数据帧收下。如果接收到的数据正确的帧在接收窗口之外或者接收到的帧数据发生了错误，则一律丢弃。如下图：

对于接收方窗口，大小可以自定义，这里我们给出接收窗口大小Wr为1的图:

发送端每收到一个确认帧，发送窗口就向前滑动一个帧的位置，当发送窗口内没有可以发送的帧（即窗口内的帧全部都是已发送但未收到确认的帧）时，发送方就会停止发送，直到收到接收方发送的确认帧使窗口一移动，窗口内有可以发送的帧后，才开始继续发送。而接收端收到正确数据帧后，将窗口向后移动一个位置，并发回确认帧，若收到的正确数据帧落在接收窗口外，一律丢弃。

我们还可以总结出如下规律：

• 只有接收窗口向前滑动（同时接收方发送了确认帧）时，发送窗口才有可能（只有发送方收到确认帧后才一定）向前滑动
• 从滑动窗口的概念看，停止-等待协议、后退N帧协议（GBN）和选择重传协议（SR）都是滑动窗口协议的一种形式，只是窗口大小和确认帧的形式上有所区别
  1. 停止-等待协议：发送窗口大小=1，接收窗口大小=1
  2. 后退N帧协议：发送窗口大小>1，接收窗口大小=1
  3. 选择重传协议：发送窗口大小>1，接收窗口大小>1
• 接收窗口大小为1时，可以保证帧的有序接收
• 数据链路层的滑动窗口协议中，窗口的大小在传输过程中是固定的（一定要注意与传输层的滑动窗口区分开来，传输层的滑动窗口大小是动态变化的）

可靠传输机制

数据链路层的可靠传输通常使用确认个超时重传两种机制来完成。确认是一种无数据的控制帧，这种控制帧使得接收方可以让发送方知道那些内容被正确接收。有些情况下为了提高传输效率，将确认捎带在一个回复帧中，称为稍待确认。超时重传是指发送方在发送某个数据帧后就开启一个计时器，在一定时间内如果没有得到发送的数据帧的确认帧，那么就重新发送该数据帧，知道发送成功为止。

自动重传请求（ARQ）通过接收方请求发送方重传出错的数据帧来恢复出错的帧，是通信中用于处理信道所带来差错的方法之一。传统的自动重传请求分为3种，即①停止-等待ARQ②后退N帧ARQ③选择重传ARQ。后两种协议是滑动窗口技术与请求重发技术的结合，由于窗口尺寸开到足够大时，帧在线路上可以连续地流动，因此又称为连续ARQ协议。在数据链路层，流量控制和可靠传输是交织在一起的。

单帧滑动窗口与停止-等待协议

前面我们已经详细的介绍了停-等协议的运作原理了，实际上就是单帧滑动窗口的工作过程，他的发送窗口大小和接收窗口大小都为1。

对于帧的丢失和帧的数据错误的情况，停-等协议中接收方都是保持沉默不发送任何消息，待计时器超时后自动触发发送方重传帧。而对于已经成功接收的帧，窗口会向前滑动一个帧的位置，但是此时如果他有接收到正确的重复的该帧，那么由于此时这个帧的序列号已经不再接收窗口内部了，因此他会丢弃这个帧，但是同时这也意味着之前的确认帧并没有正确的被发送方接收，为了能够保证发送方的窗口能够正常滑动，接收方需要重发一下之前的确认帧：

由于单帧滑动滑动窗口中每次只发送一个帧，因此序列号仅用0和1两个数即可，也就是序列号占用1bit二进制位即可，因此此时的帧的序列标志位长度为1bit。

在停止-等待协议中，如果连续出现相同发送序号的数据帧时，说明发送端进行了超时重传，意味着①数据帧在传输信道中丢失了或者②确认帧在传输信道中丢失了亦或者是③信道中干扰太大，很不幸发送的数据帧一直连续在传输信道中出现数据错误。

在停止-等待协议中，如果连续出现相同序号的确认帧时，表示接收端一直在收到重复的数据正确的帧，那么也就意味着确认帧一直没能正确的抵达发送方。

由于此协议的信道利用率过低，因此为了克服这一个缺点，产生了另外两个更加高效的后退N帧协议和选择重传协议。

多帧滑动窗口与后退N帧协议（GBN）

在后退N帧式ARQ中，发送方无须在收到上一个帧的ACK后才能开始发送下一帧，而是可以连续发送帧。当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧。或者当发送方发送了N个帧后，如果发现N个帧的前一个帧在计时器超时后仍未返回确认信息，则该帧被判定为出错或者丢失，此时发送方不得不重传该出错帧及随后的N个帧。也就是说，接收方只允许按顺序接收帧。

发送方窗口划分

我们来规定一下后面讲解时GBN发送方窗口的定义：

在GBN发送方窗口中我们将其分成四个区域，其中send_base指向的是窗口的最末端，nextseqnum指向的是窗口的最前端。两者之间（包括这两个边缘端存储的帧）时窗口的大小，内部的黄色部分是已经发送出去的帧但是还没有收到确认帧的部分，而蓝色部分是还可以发送帧的部分。send_base左端的绿色部分是已经成功发送并且收到确认消息的部分，而nextseqnum右侧的白色部分就是暂时存储到发送方缓存区等待发送的部分，只有当窗口滑动到这部分时，这部分白色区域会变成蓝色区域即有资格等待发送了。而黄色部分伴随着窗口滑动会变成绿色部分即收到确认帧后的部分。

GBN发送方必须响应的三件事

在了解GBN协议实现的过程之前，我们先来说明GBN发送方必须响应的三件事：

1. 上层的调用：上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送，如果窗口已满，那么发送方只需将数据返回给上层，暗示上层窗口已满，请上层等待一段时间后在发送。（但是在实际的实现中，发送方是可以缓存这些数据的即上面图示中的白色区域，窗口不满时在发送帧）
2. 收到一个ACK(n)：在GBN协议中，对n号帧的确认采用累积确认的方式，即ACK(n)表示接收方已经顺序接收到n号帧及他以前的全部帧。
3. 超时时间：协议的名字为后退N帧，来源于出现丢失和时延过长帧时发送方的行为，就像在停-等协议中一样，定时器会再次用于恢复数据帧或确认帧的丢失。如果确认出现超时，发送方会重传所有已发送但是还未被确认的帧。

GBN接收方要做的事

同样的GBN协议中接收方也有必须响应的事情：

1. 如果正确到n号帧，并且按序，那么接收方为n帧发送一个ACK(n)确认帧给发送方改制发送方前n号帧（包括第n号帧)都已经成功接收，并将该帧中的数据部分交付给上层。
2. 其余情况下错误或者未按序抵达的帧一律丢弃，并为最近按序接收的帧重新发送ACK，接收方无需缓存任何失序帧（毕竟他的接收窗口仅为1），只需要维护一个信息：expectdseqnum(下一个按序接收的帧序号)

静态图讲解

如上图是一个GBN协议的具体工作图，这里假设的发送窗口大小是9，那么上图所演示的工作步骤如下：

1. 首先发送方一次性发送窗口内所有未发送的帧即0-8号帧（上图从左往右看时间线，因此算一次性发送但是还是有顺序的，0-8号帧肯定是0号帧先出窗口，然后1,2…8）
2. 然后接收方进行接收，他陆续的接收0,1，然后发现抵达的2号帧数据错误，因此会像停-等协议中的发送方一样丢弃错误的2号帧后保持沉默，但是一段时间接收方检查发现1号之前的帧都以按序成功接收，因此发送ACK(1)。(这里为了方便演示，每一次成功接收都发送ACK。)
3. 紧接着3,4,5,6,7,8都陆续抵达，但是由于接收方为正确收到2号帧，因此接收方的窗口就停在了2号位置，又因为接收窗口大小仅为1，因此后面陆续抵达的帧都不能被缓存起来，只能全部被丢弃。
4. 然后就陷入了僵局，双方都在等待对方的消息，接收方等待发送方的正确的2号帧，发送方收到了之前接收方发送的ACK(1)后知道0和1都已经成功被接收，因此窗口向前滑动2个帧，即此时send_base指向了2，nextseqnum指向了10，然后继续等待收到的ACK确认帧。
5. 长时间没有ACK消息，用来记录第一组帧的发送计时器超时了此时发送方必须相应打破僵局，他发现此时send_base指向了2，因此他发送此时窗口内部所有已发送未被确认的帧即2-8号帧，一定要注意9和10号帧虽然此时也已经进入了发送端的滑动窗口内，但是仍然不能发送只能等待下一组发送。
6. 接收方如愿以偿接收到了正确的2号帧，然后继续接收3-10号帧，在一段时间检查后发现前10个帧都已经顺序接收了因此又发送ACK(10)。
7. 发送方收到ACK(10)，知道0-10都已经成功的发送，窗口继续滑动，send_base指向11，nextseqnum指向了19，然后发送方重置计时器发送11-19号帧

动态图讲解

可能上面的不太好理解，这里我们再给出一种动图的讲解：

我们这里演示的时候假设发送方的发送窗口大小为4，我们可以看到起初发送0-4帧，而2号帧丢失了，那么此时接收方的接收窗口停在了2号帧的位置，即使收到了正确的3和4号帧也是直接抛弃的。然后发送了ACK(1)因此发送方窗口滑动，起始端移动到了2号帧，待计时器超时后发送方重新发送之前发送过但是未确认的2-4号帧**，一定要注意即使此时5,6号帧在发送方发送窗口内也是不能跟着这组发送的，必须等待下一组**。然后接收方正确接收了2-4号帧后发送了ACK(4)，发送方接收到ACK(4)以后发送窗口继续向前滑动，此时send_base指向了5，nextseqnum指向了8，然后发送方此时重置计时器后再次发送新的一组帧即5-8号。

之前所讲解是发送方发送的2号帧丢失的情况，而现在上图所演示的在接收方全部正常接收0-4号帧以后，返还的ACK2丢失的情况，我们可以看到虽然ACK2丢失了，但是ACK3和ACK4都成功抵达了发送方，根据GBN协议对ACK是累计确认的机制，发送方可以判断出0-4号帧都已经被成功接收了，因此sned_base直接滑动到了5号。

规律总结

我们从上面的步骤中可以总结出一下几个特点：

1. 接收方仍然是在收到错误帧保持沉默，不会主动报告发送方错误帧序列号，而是选择使用超时机制解决这种情况，原因和之前讲解的停-等协议一样为了能够与ACK迟到情况区分
2. GBN协议一次性发送一组帧，但是实际上这组帧并不是同时抵达接收方，还是有一定的时间差，而接收方也刚好利用这段时间差为每一个抵达的帧进行接收前的差错检测和丢弃错误帧、发送ACK等操作。但是从宏观角度上来看好像发送方一次性"同时"发送了许多帧，而接收方一次性"同时"接收了许多帧，但是微观上实际接收窗口仅为1，只是在不断的滑动而已。
3. GBN协议中个发送方仅仅需要使用一个计时器为每一次一组的帧计时即可再ACK的帮助下和send_base指引下顺利找到下一次发送一组帧的起始序列号
4. 接收方发送的确认消息携带的序列号是按序抵达的最大的帧的序列号

发送方状态转换图

上图是发送方的一次传输的状态转换图，我们来再分析一下伪代码描述的过程：

1. 首先一开始send_base为1，nextseqnum也为1，即此时发送方还没有收到上层传递下来的数据，因此并不需要缓冲任何数据
2. 然后顺时针看，rdt_send(data)表示上层向数据链路层的发送方传递了数据data,发送方进行判断发现窗口的nextsqnum<send_base+N,则说明窗口还没有放足够的数据（这里的N是窗口大小）即还有蓝色区域可以盛放数据，因此发送方接收上层传递的数据并且存储到蓝色区域即等待发送的区域并对数据帧进行编号,然后发送这些数据，并且此时send_base==nextseqnum==1即发送方窗口还在起始状态，此时他发送了数据data因此需要启动计时器start_timer同时将nextseqnum++因为此时data占据了一个帧位，nextseqnum不再为1。否则说明窗口不够大或者已满，即蓝色区域不能盛放上层传递下来的数据，那么发送方暂时拒绝接收数据暗示上层窗口暂时已满无法承载了refuse_data(data)等待一段时间后再重复此步骤。
3. 然后到达第三个状态，即不断的发送许多组数据帧，并且每次发送一组帧的时候都需要重启计时器start_timer，如果超时了那么就重复此步骤，由于nextseqnum再次状态过程中并未发生变化，因此这个状态表示的是发送方不断重传发送但是还未被确认的帧
4. 当收到确认消息rdt_rcv(rcvpkt)并且确认消息正确无误notcorrupt(rcvpkt)，那么窗口就可以滑动了即base=getacknum(rcvpkt)+1。如果base==nextseqnum，那么说明所有已发送待确认的帧都已经成功接收，即又一波帧全部完成了传输，那么就可以停止计时器了stop_timer，否则还要继续重传那些发送带还没有被确认的分组并且重启计时器start_timer
5. 最终就是所有的帧都已经成功发送并被接收端接收

接收方状态转换图

上图是接收方的一次传输的状态转换图，我们来再分析一下伪代码描述的过程：

1. 起初期待的接收帧的序列号就是1即expectedseqnum=1同时制作ACK(1)的消息，由于ACK也可能发生位数反转等错误，因此在制作ACK的时候也需要加上校验和sndpkt=make_pkt(expectedseqnum,ACK,chksum)
2. 然后就是在一段时间后默认default自动发送ACK消息给发送方udt_send(sndpkt)
3. 当接收到帧rdt_rcv(rcvpkt)并且帧无损坏notcurrupt(rcvpkt)并且抵达的帧的序列号是期望的序列号即按该帧的序列号是按序抵达的在接收窗口内的hasseqnum(rcvpkt,expectedseqnum)那么接收方就整理最近接收到的顺序的帧数据并打包extract(rcvpkt,data)然后交付给上层deliver_data(data)同时继续制作ACK确认消息sndpkt=make_pkt(expectedseqnum,ACK,chksum)并发送给发送方udt_send(sndpkt)同时滑动接收窗口expectedseqnum++

发送窗口大小限制

我们知道在GBN协议中接收窗口就是1，那么发送窗口大小可以随便定义吗，实际上是不可以的。如果采用n比特二进制位对帧进行编号，那么发送窗口的大小应该始终小于等于编号标志位所能表示的最大值2^n-1，即有以下公式：

$$1≤W_T+1≤2^n$$

思考：为什么要满足上式规律？

如果不满足上面的公式，那么就会造成接收方无法分辨新帧和旧帧，比如假设用3位来对帧序号编码，那么最大值就是7，因此发送窗口的最大值为7，但是假设此时发送窗口大小为8。那么初始时发送方一次性发送0-7号八个数据帧，因为发送窗口已满，因此暂停发送。假设这8个数据帧都已经正确到达接收端，并且对每一个数据帧，接收端都能发送出确认帧，那么现在下面这两种情况将无法区分：

• 第一种情况：所有确认帧都能够正确的到达发送端，那么此时发送端滑动窗口后将会发送新的8个数据，但是编号还是0-7。
• 第二种情况：所有确认帧都丢失了，那么经过一段时间后计时器超时，发送端重发之前发送的8个旧数据帧序号也是0-7。

显然这两种情况的0-7编号的数据帧所包含的数据时不同的，但是接收方此时却不能区分，因此不满足上面的规律是不行的。假设此时满足规律将窗口大小设为了7，那么此时第一种情况新发送的数据帧编号将不再是0-7而是8,0,1,2,3,4,5,6显然就可以和第二种情况的0-7区分开来了。

GBN性能分析

首先我们不难看出后退N帧协议通过连续发送数据帧肯定是提高了信道的利用率同时仅仅需要一个计时器实现起来比较简单，但是另一方面在重传时必须把原来已经传送正确的数据帧进行重传（仅仅因为这些数据帧的前面有一个数据帧出了错），这种做法既使传送效率降低了同时又造成了极大的资源郎芬。由此可见当信道的传输质量很差导致误码率较大时，GBN协议并不是最优策略，可能性能上还不如停止-等待协议。为了解决这一缺陷，又提出了选择重传机制。

例题

数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为0-7的帧，如果发送方只收到了0,2,3号帧的确认，则发送方需要重放的帧数是？

重发帧数是4，即序号为4,5,6,7的帧。虽然此时窗口滑动后8,9,10,11已经在窗口内部的待发区域，但是超时造成的重传只会重传发送过但还未被确认的帧即4,5,6,7号帧。

多帧滑动窗口与选择重传协议（SR）

为了进一步提高信道的利用率，可以设法只重传出现错误的数据帧或者计时器超时的数据帧，但是此时我们就必须加大接受窗口大小，以便接收方可以暂时缓存收下那些序号不连续但是仍然处在接受窗口的数据帧（即错误帧后面的正确数据帧不会被丢弃了，而是可以被暂时存储在接受窗口内部）。当等待所缺的序号的数据帧收到后就可以和后面暂时存储的数据帧组成一组连续序号的帧组了，此时接收方再将其一并上交给上层，这就是选择重传ARQ协议。

很明显，此时再使用一个计时器肯定是不够的了，选择重传ARQ协议要对每一个数据帧单独计时，因此需要很多个计时器，一般计时器的数量与发送窗口大小相同。并且在选择重传协议中使用了一个更加有效的差错处理策略，即一旦接收方怀疑帧出错，就会发送一个NAK给发送方，要求发送方对NAK指定的数据帧进行重传（了解即可，一般讲解和做题时还是默认接收方对错误帧保持沉默）。

发送方、接收方窗口划分

在讲解GBN协议中我们只介绍了发送方窗口的划分，这是因为GBN协议中的接收方窗口大小仅仅为1，但是在SR协议中发送方和接收方窗口大小都不为1，并且通常情况下发送窗口和接收窗口大小相同，下面是SR协议对窗口的区域划分：

在SR协议中发送窗口的划分和GBN的发送窗口划分规则相同，不再介绍。这里我们详细了解一下接受窗口的划分，同样的，接受窗口也划分为4部分，其中rcv_base指向的是缺少的希望获得的序号的数据帧。而离散形势的红色部分是乱序到达，即在错误帧或者丢失帧序号后面的正确帧存储。蓝色部分是还可以接收的乱序帧的区域。白色区域就是不能接收的区域。

上图是另一种形式对窗口功能的介绍。

SR发送方必须响应的三件事

在了解SR协议实现的过程之前，我们先来说明GBN发送方必须响应的三件事：

1. 上层的调用：从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送该帧。否则就像GBN一样要么暂时缓存数据，要么返回给上层暗示上层窗口暂时已满。

2. 收到一个ACK：在SR中对ACK采取单一确认机制，即ACKn只表示第n号帧被成功接收。如果发送方收到了ACKn，且该帧号n在窗口内，则SR发送方将那个被确认的帧标记为已接收然后丢弃这个帧的副本。如果这个帧序号是窗口的下界（最左边第一个窗口的序号），那么窗口向前滑动到具有最小序号未被确认的帧处。如果窗口移动了以后并且有序号在窗口内的等待发送的帧，那么就发送这些帧。

   

3. 超时事件：每一个帧都有自己的定时器，一个超时事件只会触发该超时帧的重传。

思考：GBN和SR发送方触发重传的响应事件相同吗？

不相同，在GBN中窗口滑动后即使内部有可以发送的待发送帧，也不会发送，而是必须等待之前的那一组发送的帧全部被确认后才会再发送一组新的帧，当窗口滑动后还有之前发送后未被确认的帧，那么超时后就只重传之前未被确认的帧，新加入的帧必须等待下一波发送。而在SR协议中，只要窗口滑动后内部有新的待发送帧出现，就可以发送了，而当有某个帧超时时也只是重传超时帧而已。我们可以用下面的语句概括两者的特点：GBN一组一组发送，SR一个一个发送。

SR接收方要做的事

同样的SR协议中接收方也有必须响应的事情，SR接收方将确认一个正确接受的帧而不管这个帧是否按序抵达。失序的帧将被缓存，并返回给发送方一个该帧的确认帧即收谁确认谁，知道所有帧（即序号最小的帧）皆被收到为止，这时才将一批帧按序交付给上层，然后向前滑动窗口。

如果收到了窗口序号外（小于窗口下界的帧），那么就意味着出现了确认帧ACK丢失的情况，因此导致了发送方误以为接收方还没有成功接收该帧因此出现了这种情况，此时只需要返回一个该帧的ACK即可。

思考：为什么停-等协议和SR协议在ACK丢失时要重传ACK而GBN却不需要？

原因很简单，SR和停-等协议都是单帧确认机制，而GBN是累计确认机制，即GBN中接收方即使ACKn没有成功抵达发送方，但是ACK(n+1)抵达发送方时也可以向发送方传达n号帧被成功接收。但是在停-等协议和SR中只有ACKn抵达发送方才能想发送方传达n号帧被接收。

静态图讲解

上图是一个发送窗口和接受窗口都为4的SR工作流程，我们具体分析一下：

1. 首先发送方发送0-3号帧，但是2号帧在信道传输过程中丢失了，但是0,1,3号帧都成功抵达了，此时接受窗口接收0,1,3号帧并且发送ACK0,ACK1和ACK3同时窗口向前滑动但是只能滑动到rcv_base指向2号帧的位置，因此接收方还没有成功接收到2号帧
2. 发送方收到3个确认帧以后同样进行窗口滑动滑动到send_base指向2的位置并且将1,3号帧的位置标记为已接收确认帧状态，因为2号帧的确认消息还没有接收到，但是此时窗口内又加入了新的等待发送的4号和5号帧，因此4和5号号帧可以发送了，发送方发送4号和5号帧
3. 接收方还有位置可以接收4号和5号帧，因此接收4号和5号帧并返还ACK4和ACK5，但是由于期待的2号帧还是没有接收到，因此窗口仍然不会滑动并且此时窗口已经满了，此时即使抵达6,7…号帧，接收方也不会再接收了只能等待2号帧了
4. 发送方收到了4号帧和5号帧的确认消息后发现窗口也已经满了并且由于2号帧的确认消息还是没有抵达因此send_base还是只能呆在2号帧位置，此时他的发送窗口也已经满了不能继续发送新的帧了，因此发送方只能等待2号帧的确认帧了
5. 双方陷入僵局，都在等待对方的消息
6. 一段时间后2号计时器超时，触发发送方重传2号帧，发送方重新发送2号帧打破僵局
7. 接收方收到2号帧，将2-5号帧一并上交给上层，同时滑动窗口，rcv_base移动到了6号帧的位置等待接收6,7,…号帧
8. 发送方终于收到了2号帧的确认消息，滑动窗口向前滑动到send_base指向6号帧的位置同时发送6,7,8,9号帧
9. 最终一直循环上面的过程完成所有数据帧的传输

动态图讲解

我们同样给出SR的动态图演示：

上图演示的是在发送过程2号帧丢失的过程，我们可以看见接收方还是接收了丢失帧2号帧后面抵达的3号帧，而不是像GBN一样直接丢弃3号帧。发送方收到确认帧滑动窗口后有可以发送的新的帧就会立刻发送也不会像GBN那样必须等待所有之前发送的帧都被确认后才能发送新的待确认的帧。

上图演示的是SR中ACK2丢失的情况，此时发送方即使收到了ACK3和ACK4也不能确认2号帧被成功接收，因此窗口滑动只能移动到2号帧的位置，待超时后重传2号帧。

规律总结

我们从上面的步骤中可以总结出一下几个特点：

1. 接收方仍然是在收到错误帧保持沉默，不会主动报告发送方错误帧序列号，而是选择使用超时机制解决这种情况
2. SR协议一次性发送一组帧，但是实际上这组帧并不是同时抵达接收方，还是有一定的时间差，而接收方也刚好利用这段时间差为每一个抵达的帧进行接收前的差错检测和丢弃错误帧、发送ACK等操作。但是从宏观角度上来看好像发送方一次性"同时"发送了许多帧，而接收方一次性"同时"接收了许多帧。
3. SR协议中发送方需要为每一和帧都单独设置一个计时器，然后借助ACK消息判断未被确认的帧，并且在超时时只重传某个出错帧或者某个超时帧
4. 接收方发送的确认消息携带的序列已接收的帧的序号，未必是按序抵达的

发送窗口与接收窗口大小限制

同样的，在SR中发送窗口和接收窗口的大小也不能随便定义，需要满足一定的规律。他们需要满足的规律就是发送方和接收方的窗口内部都不能出现序列号相同而数据不同的帧，因此有以下规律：

$$1≤W_T+W_R≤2^n$$

如果Wt==Wr，那么我们可以进一步推得如下规律：

$$W_{Tmax}=W_{Rmax}=2^{n-1}$$

思考：为什么要满足上式规律？

原理和GBN中介绍的一样。如果不满足上式，就会出现接收方无法区分旧帧和新帧，如上图编号最大值为4，但是收发窗口大小却设置为了3，那么此时

$$W_T+W_R=6>4=窗口极限值$$

很明显没有满足限制公式，因此此时上图的这两种情况第二个0号帧接收方将无法辨别是旧帧还是新帧。左图0号帧是重传的旧帧，而右图是新的数据不同的0号帧，但是在接收方视角接收方都将按照新帧来接收这明显会造成灾难性的结果。

例题

数据链路层采用了选择重传（SR）协议，发送方发送了0-3号帧，现在已经收到了1号帧的确认，而0,2号帧依次超时，则发送方需要重传的帧数是多少？

需要重传0号和2号两个帧。所以重传帧数是2。

性能分析

选择重传协议可以避免重复传送那些本可以正确到达接收端的数据帧，但是在接收端即需要设置具有相当容量的缓冲区来暂存那些未能按序正确收到的帧。虽然SR相对于GBN减少了帧的重传数量从而减少了资源的浪费，但是相应的他需要额外的接受窗口容量以及更多的单帧计时器。因此SR和GBN两者各有优劣点。

总结

我们在学习完了三种可靠传输的机制后进行一个简单的对比总结。

我们发现实际上SR本质上相当于许多个并行执行的停止-等待协议，从单个帧的角度上来看实际上SR和停止-等待协议很相似。而GBN的重传机制很特别，一定要特别注意GBN重传时只重传那些已经发送过但是还未被确认的帧。