考研笔记

可靠传输机制

第 3 章计算题的主战场。 停止-等待、GBN、SR 三种协议的原理是一类题，信道利用率和实际数据传输速率是另一类题，帧序号需要几位是第三类——这三类题在 2009、2010、2011、2012、2014、2015、2017、2018、2019、2020、2023、2024 年都出现过，本页有 5 道错题落在这里。

三种协议都建立在同两个机制上：确认和超时重传。它们的差别只在两个窗口开多大（3.4.1），而窗口开多大，决定了一出错要重传多少帧、信道能用上几成。

机制

确认、超时重传与 ARQ

可靠传输是指发送方发送的数据都能被接收方正确地接收，通常采用确认和超时重传两种机制来实现。确认是指接收方每收到发送方发来的数据帧，都要向发送方发回一个确认帧，表示已正确地收到该数据帧。超时重传是指发送方在发送一个数据帧后就启动一个计时器，若在规定时间内没有收到所发送数据帧的确认帧，则重发该数据帧，直到发送成功为止。

使用这两种机制的可靠传输协议称为**自动重传请求（ARQ）**，它意味着重传是自动进行的，接收方不需要对发送方发出重传请求。在 ARQ 协议中，数据帧和确认帧都必须编号，以区分确认帧是对哪个帧的确认，以及哪些帧还未确认。ARQ 协议分为三种：停止-等待（Stop-and-Wait）协议、后退 N 帧（Go-Back-N）协议和选择重传（Selective Repeat）协议。这三种可靠传输协议的基本原理并不仅限于数据链路层，还可应用到其上各层——TCP 就是例子。

在有线网络中，链路的误码率较低，为了降低开销，并不要求数据链路层向其上层提供可靠传输服务，即使出现了误码，可靠传输的问题也由其上层处理。而无线网络的链路易受干扰、误码率较高，因此要求数据链路层必须向其上层提供可靠传输服务（见 3.1.5）。

停止-等待协议（SW）

在停止-等待协议中，发送方每次只能发送一个帧，收到接收方的确认帧之后，才可以发送下一个帧。从滑动窗口的角度看，停止-等待协议的发送窗口和接收窗口大小均为 1。

停止-等待协议可能出现两种差错：

  1. 数据帧出错或丢失。 接收方检测到数据帧出了差错，就简单地将该帧丢弃；若数据帧在传输过程中丢失，接收方当然什么都不知道。为了应付这两种可能，发送方装备了计时器：一个帧发送后等待确认，计时器超时时若仍未收到确认，则重发该数据帧，如此重复，直到该数据帧正确到达为止。
  2. 确认帧出错或丢失。 接收方已收到正确的数据帧，但发送方收不到确认帧，因此发送方会重传已被接收的数据帧。接收方收到相同的数据帧时会丢弃该帧，并重传一个该帧对应的确认帧。

对于停止-等待协议，由于每发送一个数据帧就停止等待，只需保证每次发送的新数据帧的序号与上次发送的数据帧的序号不同，因此用 1 比特来编号就足够了。发送的帧交替地用 0 和 1 来标识，确认帧分别用 ACK0 和 ACK1 表示。若连续出现相同序号的数据帧，表明发送方进行了超时重传；若连续出现相同序号的确认帧，表明接收方收到了重复帧。

此外，为了超时重传和判定重复帧的需要，发送方和接收方都要设置一个帧缓冲区。发送方发送完数据帧时，必须在其发送缓存中保留该数据帧的副本，这样才能在出现差错时进行重传；只有收到对方发来的确认帧 ACK 后，方可清除该副本。

停止-等待协议的信道利用率很低（下文计算）。为了提高传输效率，产生了连续 ARQ 协议（后退 N 帧协议和选择重传协议），发送方可连续发送多个帧，而不是每发完一个帧就停止等待确认。

后退 N 帧协议（GBN）

在后退 N 帧协议中，发送方可在未收到确认帧的情况下，将序号在发送窗口内的多个数据帧全部发送出去（2009 年考过工作原理）。“后退 N 帧”的含义是：发送方发送 个数据帧后，若发现这 个帧的前一个数据帧在计时器超时的时候仍未收到其确认信息，则该帧被判为出错或丢失，此时发送方不得不重传该出错帧及随后的 个帧。这意味着，接收方只允许按顺序接收帧。

因为连续发送了许多帧，所以确认帧必须指明是对哪个帧的确认。为了降低开销，GBN 协议允许接收方进行**累积确认**，即接收方不需要每收到一个正确的数据帧就立即发回一个确认帧，而可在连续收到多个正确的数据帧后，对最后一个数据帧发回确认信息——对某个数据帧的确认就代表该帧和之前所有的数据帧均已正确无误地收到。ACK 表示对 号帧的确认，表示接收方已正确收到 号帧及之前的所有帧，下次期望收到 号帧（也可能是 0 号帧）。确认号的含义与捎带确认 2017 年考过。

sequenceDiagram
    participant S as 发送方
    participant R as 接收方
    S->>R: 0
    R-->>S: ACK0
    S->>R: 1
    R-->>S: ACK1
    S-xR: 2（出错）
    S->>R: 3、4、5、6、7、8
    Note over R: 失序，全部丢弃<br/>可重发最后的确认 ACK1
    Note over S: 2 号帧超时
    S->>R: 重传 2、3、4、5、6、7、8
    R-->>S: ACK2 … ACK7

在上图中，虽然在有差错的 2 号帧之后接着收到了正确的 6 个数据帧，但接收方必须将这些帧丢弃；此外，接收方还可重发已发送的最后一个确认帧 ACK1（以防止 ACK1 丢失）。等 2 号帧超过超时重传时间，发送方重新发送窗口中 2 号帧之后的所有数据帧（超时重传的分析 2017 年考过）。

若采用 比特对帧编号，GBN 的发送窗口应满足 （发送窗口的意义与最大尺寸 2017 年考过）。若 大于 ，会造成接收方无法分辨新数据帧和旧数据帧（证明见下面边界）。GBN 的接收窗口 ，可保证按序接收数据帧。

GBN 一方面因连续发送数据帧而提高了信道利用率；另一方面在重传时又必须重传原来已正确到达的帧（仅因这些帧的前面有一帧出错），这种做法会降低传送效率。当信道误码率较大时，后退 N 帧协议不一定优于停止-等待协议。

选择重传协议（SR）

为了进一步提高信道利用率，可以设法只重传出现差错和计时器超时的数据帧，但此时必须加大接收窗口，以便先收下失序但正确到达且序号仍落在接收窗口内的那些数据帧，等到所缺序号的数据帧收齐后，再一并送交上层。这就是选择重传协议（原理及实现 2011、2024 年考过）。

为了使发送方仅重传出错的帧，接收方不能再采用累积确认，而要对每个正确接收的数据帧逐一进行确认。显然，选择重传协议比后退 N 帧协议更复杂，且接收方需要设置足够的帧缓冲区（帧缓冲区的数量等于接收窗口大小）来暂存那些失序但正确到达且序号落在接收窗口内的数据帧。每个发送缓冲区对应一个计时器，计时器超时时，缓冲区的帧就重传。若接收方收到重复的数据帧（表示确认帧丢失），则丢弃该帧，并重传与该帧对应的确认帧。

选择重传协议还采用了比上述其他协议更有效的差错处理策略：一旦接收方检测到某个数据帧出错，就向发送方发送一个否定帧 NAK，要求发送方立即重传 NAK 指定的数据帧。例如 2 号帧丢失后，接收方仍可正常接收并缓存之后收到的数据帧，待发送方超时重传 2 号帧并被成功接收后，接收窗口就可向前移动；发送方收到 2 号帧的确认后，发送窗口也向前移动。某时刻接收方检测到 10 号帧出错，向发送方发出 NAK10，在此期间仍可正常接收并缓存之后收到的帧，发送方收到 NAK10 后立即重传 10 号帧。

选择重传协议的接收窗口 和发送窗口 都大于 1，一次可以发送或接收多个帧。若采用 比特对帧编号，需满足两个条件：

  1. 。否则，在接收方的接收窗口向前移动后，若有一个或多个确认帧丢失，发送方就会超时重传之前的旧数据帧，接收窗口内的新序号与之前的旧序号出现重叠，接收方无法分辨是新数据帧还是重传的旧数据帧。
  2. 。否则，若接收窗口大于发送窗口，接收窗口永远不可能填满，多出的空间就毫无意义。

由这两个条件不难得出 。一般情况下， 和 的大小是相同的。

信道利用率

信道利用率是指信道的效率。从时间角度看，信道效率是对发送方而言的，是指发送方在一个发送周期（从发送方开始发送分组到收到第一个确认分组所需的时间）内，有效发送数据的时间与整个发送周期之比。这里用”分组”而不用”帧”，是为了更具通用性——同一套公式在 TCP 里照样用。

停止-等待协议（2018、2020 年考过计算）：设发送方发送分组的发送时延为 （等于分组长度除以数据传输速率）；分组正确到达后，接收方处理分组的时间忽略不计，同时立即发回确认；接收方发送确认分组的发送时延为 （通常可以忽略不计）；发送方处理确认分组的时间也忽略不计。那么发送方经过 后就可再发送下一个分组，其中 RTT 是往返时延。因为仅在 内才用来发送数据分组，所以例如 RTT = 20ms，分组长度 1200 比特，数据传输速率 1Mb/s，忽略处理时间和 ：ms，。若把数据传输速率提高到 10Mb/s，则 ms，。当 RTT 大于 时，信道利用率就非常低——速率越高、距离越远，停止-等待越不划算。

连续 ARQ 协议采用流水线传输，发送方可连续发送多个分组，只要发送窗口足够大，就可使信道上有数据持续流动（三种滑动窗口协议信道利用率的比较 2023 年考过）。设发送窗口为 ，即发送方可连续发送 个分组，分两种情况（GBN 信道利用率与发送窗口大小的关系 2012、2015、2017 年考过）：

  1. ：在一个发送周期内可以发送完 个分组，信道利用率为
  1. ：在一个发送周期内发不完（或刚好发完） 个分组。对于这种情况，只要不发生差错，发送方就可不间断地发送分组，信道利用率为 1。

此外（数据传输速率的计算 2009、2010、2014 年考过）：信道平均（实际）数据传输速率信道利用率信道带宽（最大数据传输速率）或者

信道平均（实际）数据传输速率发送周期内发送的数据量发送周期

计算模板

信道利用率与实际速率

  1. 帧长速率；RTT 单向传播时延；确认帧有长度就算 ，题目说”忽略”或”短帧”才略去。
  2. 发送周期 。
  3. ， 是发送窗口（停止-等待取 1）。
  4. 实际速率 带宽，或 帧长（窗口未填满时两者相等）。

由目标利用率反求窗口与序号位数

  1. 由 目标 求出最小窗口 （取整向上）。
  2. GBN：；SR（）：。
  3. 题目只说”滑动窗口协议”、没指明哪种时，按 算（2015 真题的做法）。

错题复盘：一个发送周期要把确认帧的发送时间也算进去

王道 3.4.3 第 17 题：A、B 相邻，速率 20kb/s，数据帧和确认帧都长 2000B，往返传播时延 1400ms，3 比特编号，测得信道利用率大于 80%，则（A. 只能用停止-等待　B. 只能用 GBN　C. 只能用 SR　D. 可以用 GBN 或 SR）。答案 D。

ms，确认帧同样长，ms，一个发送周期 ms。要 ，需 ，即 。3 比特编号时 GBN 的发送窗口最大为 7，SR 最大为 4，都能大于 3；停止-等待只有 。

这道题的坑在 ：确认帧和数据帧一样长，不能忽略。漏掉它会把周期算成 2200ms，窗口门槛变成 2.2，结论虽然碰巧不变，但同类题换个数字就会错。

错题复盘：GBN 的实际速率由"窗口能填满多少周期"决定，而不是带宽

2014 年统考真题（王道 3.4.3 第 25 题）：主机甲、乙用 GBN 传输，甲的发送窗口 1000，帧长 1000B，带宽 100Mb/s，乙每收到一帧立即用短帧确认（忽略其传输时延），单向传播时延 50ms，甲可达到的最大平均数据传输速率约为（A. 10Mb/s　B. 20Mb/s　C. 80Mb/s　D. 100Mb/s）。答案 C。

ms，RTT ms，ms。窗口 1000 帧可发 ms，小于周期，属于”发得完”的情况：，实际速率 Mb/s。也可以直接算：Mb/s。

D 是把带宽当成了实际速率。只有窗口大到能填满整个发送周期时，实际速率才等于带宽。

错题复盘：由目标利用率反推帧序号位数，未指明协议时按 2ⁿ−1

2015 年统考真题（王道 3.4.3 第 26 题）：主机甲通过 128kb/s 卫星链路用滑动窗口协议向乙发数据，单向传播时延 250ms，帧长 1000B，不考虑确认帧开销，为使链路利用率不小于 80%，帧序号的比特数至少是（A. 3　B. 4　C. 7　D. 8）。答案 B。

ms，RTT ms，ms。要 ：，，取 。，。

3 比特时 ，差一点点——这正是出题人设的门槛。窗口数要向上取整后再求位数，用 7.2 直接去比会误判 3 位够用。

错题复盘：同一序号位数下，GBN 的窗口最大、SR 次之、停止-等待最小

2023 年统考真题（王道 3.4.3 第 30 题）：同一信道上，数据链路层分别采用停止-等待、GBN、SR（发送窗口与接收窗口相等），帧长相同，忽略确认帧长，帧序号 3 比特，三者的最大信道利用率 满足（A. 　B. 　C. 　D. ）。答案 B。

3 比特编号：停止-等待 ；GBN ；SR 在 时 。信道利用率随发送窗口增大而增大（到 1 为止），所以 。

直觉上”SR 更先进，利用率应该最高”，但这里比的是无差错时的最大利用率，只由发送窗口决定。SR 的优势在出错时少重传，而不是无差错时窗口更大；为了防止新旧帧混淆，它的窗口反而只有 GBN 的一半多一点。

边界

GBN 的发送窗口为什么是 而不是 。 设用 3 比特编号，可表示 8 个序号，发送窗口似乎可以为 8。但设为 8 会使协议在某些情况下无法工作：发送方发完 0～7 号共 8 个数据帧后暂停，这 8 个帧都正确到达接收方，接收方对每个帧都发回了确认。此时考虑两种情况——

  1. 所有确认帧都正确到达：发送方接着发送 8 个新的数据帧，编号仍是 0～7（序号循环使用，序号相同，但都是新帧）。
  2. 所有确认帧都丢失：经过超时计时器控制的时间后，发送方重传这 8 个旧数据帧，编号仍是 0～7。

接收方第二次收到 0～7 号的 8 个帧时，无法判定这是 8 个新数据帧还是 8 个重传的旧数据帧。窗口为 7 时，第二批第一个帧的序号是 7（新）还是 0（旧）就能区分。这正是 在 时的特例。

SR 的 由两个条件共同推出。 单有 只能说明两者之和有上限；再加上 ，才能得出 。

错题复盘：无序接收的滑动窗口协议，接收窗口最大为 2ⁿ⁻¹

王道 3.4.3 第 16 题：对无序接收的滑动窗口协议，若序号位数为 ，则接收窗口最大尺寸为（A. 　B. 　C. 　D. ）。答案 D。

“无序接收”就是选择重传协议——只有 SR 的接收窗口大于 1，才能收下失序的帧。由 和 得 。

A 是 GBN 发送窗口的上限，B、C 是把 看成了 。先判断题目说的是哪种协议、哪个窗口，再套上限。

停止-等待只需 1 比特序号，但 1 比特不能省。 没有序号，接收方无法区分”新帧”和”因确认丢失而重传的旧帧”，就会把重复帧交给上层（王道 3.4.3 第 4 题：判断重复帧用帧编号）。解决帧丢失导致的死锁用的是超时机制（第 3 题），不是编号。

GBN 不是在任何情况下都优于停止-等待。 误码率高时，GBN 每出一次错就要把后面已正确到达的帧全部重传，效率可能不如停止-等待。停止-等待也不适合往返时间较长的信道（第 1 题 C 错）。

连续 ARQ 里”接收方可以不按序接收”只对 SR 成立。 GBN 同样属于连续 ARQ，但接收窗口为 1，必须按序接收（第 8 题 D 错）。

口径差异：ACK n 在链路层和 TCP 里意思不同

王道链路层口径（GBN）：ACK 表示”已正确收到 号帧及之前的所有帧”，下次期望 。

TCP 口径（第 5 章）：确认号 ack 表示”期望收到的下一个字节序号是 “，即 及之前的字节都已收到。

两者差 1。做链路层题按帧号”已收到”理解，做 TCP 题按”期望下一个”理解；题目若自己定义了 ACK 的含义，以题目为准。工程上 TCP 的 SACK 选项让接收方告诉发送方”哪些失序的块也收到了”，思路与 SR 相同。

对照速查

停止-等待GBNSR
1（常取 ）
11
接收顺序按序按序，失序帧丢弃可失序，缓存后一并上交
确认方式逐个累积确认逐个确认 + NAK
出错后重传该帧该帧及其后所有已发帧只重传该帧
序号位数1 位足够
公式用途
停止-等待利用率
连续 ARQ 利用率
实际速率 带宽 周期内发送的数据量发送周期平均数据传输速率

考点

  • ARQ = 确认 + 超时重传，重传自动进行；三种原理不限于链路层
  • 停止-等待：两种差错（数据帧、确认帧出错或丢失）；1 比特编号；双方都要帧缓冲区
  • GBN：累积确认，接收窗口 1，出错后退重传；（2009、2017）；误码率高时不一定优于 SW
  • SR：逐个确认 + NAK，缓冲区数 = 接收窗口；，，（2011、2024）
  • 利用率 ，发得满则为 1（2012、2015、2017、2018、2020、2023）
  • 实际速率 = 利用率 × 带宽（2009、2010、2014）

链接

反向链接