前言

参考王道书。
后续会进一步整理，包括添加笔记内容，标明参考资料。

更新中。。。

跳过目录

一、流量控制、可靠传输与滑动窗口机制

流量控制与可靠传输机制

较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要工作。

数据链路层和传输层流量控制的比较

数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。

• 数据链路层流量控制手段：接收方收不下就不回复确认。
• 传输层流量控制手段：接收端给发送端一个窗口公告。

流量控制的方法

• 停止等待协议
• 滑动窗口协议
  • 后退N帧协议（GBN）
  • 选择重传协议（SR）

停止-等待协议基本原理

每发送完一个帧就停止发送，等待对方的确认，在收到确认后再发送下一个帧。

• 停止-等待协议也是一种特殊的滑动窗口协议。

滑动窗口协议基本原理

• 后退N帧协议（GBN）
• 选择重传协议（SR）

对比

• 停止-等待协议：发送窗口大小 = 1，接收窗口大小 = 1;

• 后退N帧协议（GBN）：发送窗口大小 > 1，接收窗口大小 = 1

• 选择重传协议（SR）：发送窗口大小 > 1，接收窗口大小 > 1

可靠传输、滑动窗口、流量控制

可靠传输：发送端发啥，接收端收啥。

流量控制：控制发送速率，使接收方有足够的缓冲空间来接收每一个帧。

数据链路层中流量控制机制和可靠传输机制是交织在一起的。

滑动窗口解决：

• 流量控制（收不下就不回复确认，想发也发不了）
• 可靠传输（发送方自动重传）

可靠传输机制

随着技术发展，可靠传输基本不再由数据链路层负责，而是由传输层负责，在《计算机网络》（第七版）中就将可靠传输放在了传输层中。

数据链路层的可靠传输通常使用确认和超时重传两种机制来完成。

确认是一种无数据的控制帧，这种控制帧使得接收方可以让发送方知道哪些内容被正确接收。有些情况下为了提高传输效率，将确认捎带在一个回复帧中，称为捎带确认。

超时重传是指发送方在发送某个数据帧后就开启一个计时器，在一定时间内如果没有得到发送的数据帧的确认帧，那么就重新发送该数据帧,直到发送成功为止。

自动重传请求（Auto Repeat reQuest，ARQ）通过接收方请求发送方重传出错的数据帧来恢复出错的帧，是通信中用于处理信道所带来差错的方法之一。

传统自动重传请求分为三种，即停止-等待（Stop-and-Wait）ARQ、后退N帧（Go-Back-N）ARQ和选择性重传（Selective Repeat）ARQ。

后两种协议是滑动窗口技术与请求重发技术的结合，由于窗口尺寸开到足够大时，帧在线路上可以连续地流动，因此又称其为连续 ARQ协议。

二、停止-等待协议

停止-等待协议究竟是哪一层的？

• 《计算机网络》（第七版）将停止-等待协议放在了传输层。

• 王道书放在了数据链路层。

为什么要有停止-等待协议?

除了比特出差错，底层信道还会出现丢包问题。

丢包：物理线路故障、设备故障、病毒攻击、路由信息错误等原因，会导致数据包的丢失。

研究停等协议的前提?

• 虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据，一方接收数据。

• 因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传送的。

“停止-等待”就是每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。

停等协议有几种应用情况?

• 无差错情况
• 有差错情况

停等协议-无差错情况

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

每发送1个数据帧就停止并等待，因此用1bit来编号就够。

停等协议-有差错情况

1.数据帧丢失或检测到帧出错

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

注意：

• 发完一个帧后，必须保留它的副本。
• 数据帧和确认帧必须编号。

2.AСК丢失

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

3.ACK迟到

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

停等协议性能分析

• 简单
• 信道利用率太低

信道利用率

发送方在一个发送周期内，有效地发送数据所需要的时间占整个发送周期的比率。

信道利用率 = ( L / C ) / T

• T：发送周期（从开始发送数据，到收到第一个确认帧为止的时间）
• L：T内发送L比特数据
• C：发送方数据传输率

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

例：

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

答案：

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

L = 960 bit

拓展：流水线技术

拓展：流水线技术

注意：

• 必须增加序号范围。
• 发送方需要缓存多个分组。

三、后退N帧协议（GBN）

后退N帧协议是为了克服停止等待协议信道利用率低的缺点而产生的。

后退N帧协议中的滑动窗口

发送窗口：发送方维持一组连续的允许发送的帧的序号。

接收窗口：接收方维持一组连续的允许接收帧的序号。

GBN滑动窗口长度

发送窗口：
若采用 n 个比特对帧编号，那么发送窗口的尺寸W_T应满足：1 ≤ W_T ≤ 2ⁿ - 1。因为发送窗口尺寸过大，就会使得接收方无法区别新帧和旧帧。

接收窗口：
1帧

发送与接收步骤

这里设置发送窗口大小为5

1. 拷贝0号帧和1号帧
   
2. 接收方接收0号帧，回复确认帧ACK 0

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

3. 接收窗口往前滑动一格

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

4. 发送端接收到确认帧ACK 0，发送窗口往前移动一格

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

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

上层的调用

上层要发送数据时，发送方先检查发送窗口是否已满。
如果未满，则产生一个帧并将其发送；
如果窗口已满，发送方只需将数据返回给上层，暗示上层窗口已满，上层等一会再发送。(实际实现中，发送方可以缓存这些数据，窗口不满时再发送帧）。

收到了一个ACK

GBN协议中，对n号帧的确认采用累积确认的方式，说明接收方已经收到n号帧和它之前的全部帧。

超时事件

协议的名字为后退N帧，来源于出现丢失和时延过长帧时发送方的行为。就像在停等协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有己发送但未被确认的帧。

GBN接收方要做的事

正确按顺序收到n号帧

那么接收方为n帧发送一个ACK，并将该帧中的数据部分交付给上层。

其余情况

丢弃帧，并为最近按序接收的帧重新发送ACK。接收方无需缓存任何失序帧，只需要维护一个信息: expectedseqnum（下一个按序接收的帧序号）。

运行中的GBN

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

GBN协议重点总结

• 累积确认（偶尔捎带确认）
• 接收方只按顺序接收帧，不按序则无情丢弃
• 确认***最大的、按序到达的帧
• 发送窗口最大为 2ⁿ - 1，接收窗口大小为1

例：

数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为0~7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（  ）。

  A. 2  B. 3  C. 4  D. 5

解析：
累计确认，只需要看收到的确认帧中编号最大的，即3号确认帧，重发时3号和3号前的帧都不用重发，3号帧后面的帧都需要重发，即需要重发4、5、6、7帧，共4帧。

答案：C

GBN协议性能分析

优点：

• 因连续发送数据帧而提高了信道利用率

缺点：

• 在重传时必须把原来已经正确传送的数据帧重传，使得传送效率降低。

四、选择重传协议（SR）

选择重传协议是为了解决后退N帧协议累计确认导致的批量重传问题。

解决方法：设置单个确认，同时加大接收窗口，设置接收缓存，缓存乱序到达的帧。

选择重传协议中的滑动窗口

这里设置：帧的编号：0-8，用3个bit；发送窗口和接收窗口都是4个

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

上层的调用

从上层收到数据后， SR发送方检查下一个可用于该帧的序号：

• 如果序号位于发送窗口内，则发送数据帧；
• 否则就像GBN一样，要么将数据缓存，要么返回给上层，之后再传输。

收到了一个ACK

• 如果收到ACK，且该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收。
• 如果该帧序号是窗口的下界（最左边第一个窗口对应的序号），则窗口向前移动到具有最小序号的未确认帧处。
• 如果窗口移动了并且有序号在窗口内的未发送帧，则发送这些帧。

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

超时事件

每个帧都有自己的定时器，一个超时事件发生后只重传一个帧。

SR接收方要做的事

来者不拒(窗口内的帧)

SR接收方将确认一个正确接收的帧而不管其是否按序。失序的帧将被缓存，并返回给发送方一个该帧的确认帧（收谁确认谁） ，直到所有帧（即序号更小的帧）皆被收到为止，这时才可以将一批帧按序交付给上层，然后向前移动滑动窗口。

• 期望收到5号帧，但收到了6号帧，则缓存6号帧
  
• 收到了5号帧和7号帧，则接收窗口向前移动
  
  

如果收到了窗口序号外（小于窗口下界）的帧，就返回一个ACK

运行中的SR

注：图中ACK N 应该为ACK N+1，表示确认收到N帧，期望收到N+1帧（王道书和计网书中对ACK的使用并不一样）

滑动窗口长度

窗口长度可以无限吗？不可以。

情况一

情况二

• 发送窗口最好等于接收窗口。(大了会溢出，小了没意义)
• W_Tmax = W_Rmax = 2^n-1（避免二义性）
  • T：发送窗口
  • R：接收窗口
  • n：标序号的bit个数

SR协议重点总结

1. 对数据帧逐一确认，收一个确认一个
2. 只重传出错帧
3. 接收方有缓存
4. W_Tmax = W_Rmax = 2^n-1

例：

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

  A.2  B.3  C.4  D.5

答案：A
解析：
这里不看确认，只关注哪些帧超时，重传超时的帧。