后退N帧协议（GBN）与滑动窗口性能分析

是什么

本篇整合了数据链路层两大高频核心考点：CSMA/CD（载波监听多路访问/碰撞检测协议，用于总线型以太网解决介质争用）与 GBN（后退N帧协议，基于滑动窗口与累积确认实现单向/双向可靠传输），重点突破争用期碰撞极限、MAC帧结构开销、窗口边界判定、超时重传逻辑以及信道利用率与有效传输速率计算。

公式 & 适用条件

1. 物理信号单向传播时延公式

$\tau =\frac{d}{v}$

• 字母含义：

  • $\tau$：信号在物理介质中的单向传播时延（Propagation Delay）

  • $d$：两通信端点间的物理介质长度/拓扑距离（Distance），单位通常为 $\text{m}$ 或 $\text{km}$

  • $v$：电磁波在传输介质中的物理传播速率（Velocity），光纤/双绞线中通常取 $2\times 10^8\text{ m/s}=200000\text{ km/s}$

• 适用条件：

  • 计算 CSMA/CD 争用期（$2\tau$）或往返传播时延（$\text{RTT}=2\tau$）的基础参数。

2. CSMA/CD 碰撞检测时间极限公式

$t_{\min }=\tau ,t_{\max }=2\tau$

• 字母含义：

  • $t_{\min }$：两台相距 $d$ 的主机同时发送数据时，两台主机 均检测到冲突 的最短耗时

  • $t_{\max }$：发生冲突时，两台主机 均检测到冲突 所需经历的最长耗时（即争用期/碰撞窗口时间 $2\tau$）

  • $\tau$：两主机间的单向介质传播时延

• 适用条件：

  • 仅适用于总线型半双工以太网。

  • $t_{\min }=\tau$ 对应两机同时发送，波形在中点（$0.5\tau$）相撞并各自折返（$0.5\tau$）；$t_{\max }=2\tau$ 对应甲信号跑完 $\tau$ 刚到乙端瞬间乙开始发送，破坏波形须重新传回甲端。

3. 以太网 MAC 帧结构与有效载荷计算公式

$L_{\text{data}}=L_{\text{frame}}-18\text{ B}$

• 结构拆解：

  • 以太网 MAC 帧固定格式为：目的MAC(6B) + 源MAC(6B) + 类型(2B) + IP数据报/负载 + FCS(4B)

  • 头部开销：目的MAC(6B) + 源MAC(6B) + 类型(2B) = 14B

  • 尾部开销：帧校验序列 FCS = 4B

  • 首尾固定开销合计：$14\text{ B}+4\text{ B}=$ 18B

• 字母含义：

  • $L_{\text{data}}$：MAC 帧中携带的上层有效数据载荷（Payload / MTU，最大为 $1518-18=1500\text{ B}$）

  • $L_{\text{frame}}$：以太网物理帧总长度（标准最大帧长为 1518B，最小帧长为 64B）

• 适用条件：

  • 题目要求计算“有效数据传输速率”或“有效吞吐量”时，分子必须扣除 18B 物理协议首尾部，仅计算净负荷 $L_{\text{data}}$。

4. GBN 发送窗口尺寸限制公式

$1<W_T\le 2^n-1$

• 字母含义：

  • $W_T$：GBN 发送窗口大小（Sender Window Size）

  • $n$：帧序号编码所占的比特位数（Sequence Number Bits）

• 适用条件：

  • 仅适用于 后退N帧协议（GBN），接收窗口尺寸固定 $W_R=1$。

  • 若 $W_T=2^n$，当一组连续帧的所有 ACK 全丢引发超时重传时，接收方无法通过序号区分新旧两轮相同序号的帧。

5. 帧传输（发送）时延公式

$t_{\text{frame}}=\frac{L}{C}$

• 字母含义：

  • $t_{\text{frame}}$：发送端将整个帧推入物理信道所需的时间（Transmission Delay）

  • $L$：帧长度（Frame Length），单位通常为 bit（$1\text{ B}=8\text{ bit}$）

  • $C$：信道数据传输速率/带宽（Capacity），单位通常为 b/s（$1\text{ Mb/s}=10^6\text{ b/s}$）

• 适用条件：

  • 适用于恒定速率推入物理信道场景。

6. 单周期总耗时（停止-等待与单帧往返）

$T=t_{\text{data}}+{\tau }_{\text{往}}+t_{\text{ack}}+{\tau }_{\text{返}}=t_{\text{data}}+2\tau +t_{\text{ack}}$

• 字母含义：

  • $T$：从发送数据帧起始到收到该帧对应确认的完整往返总时间

  • $t_{\text{data}}$：数据帧发送时延

  • $t_{\text{ack}}$：确认帧（ACK 帧）发送时延

  • $2\tau$：双向往返介质传播时延（即 $\text{RTT}=2\tau$）

• 适用条件：

  • 停止-等待协议或计算连续 ARQ 的单周期基准时间。若采用捎带确认且 ACK 包含等长数据，必须计入 $t_{\text{ack}}$；若为微秒级 ACK 短包且题目说明忽略确认发送时延，则 $t_{\text{ack}}=0$。

7. 最大信道利用率与有效传输速率公式

$U=\min \left(1,\frac{W_T\times t_{\text{frame}}}{T}\right),C_{\text{eff}}=\frac{L_{\text{data}}}{T}$

• 字母含义：

  • $U$：信道利用率（Channel Utilization，物理介质被有效发送占用的时间占比）

  • $C_{\text{eff}}$：链路有效数据传输速率（Effective Data Rate，单位时间传输的应用层净负荷）

  • $W_T\times t_{\text{frame}}$：发送窗口允许发送方在一个周期内持续发送数据的最大占用时间

• 适用条件：

  • 若 $W_T\times t_{\text{frame}}\ge T$，利用率可达到 ==$100\%$==；若小于 $T$，则受窗口限制必须停等，利用率直接由窗口决定。

怎么用（解题步骤）

1. 审清协议类型与拓扑条件：

   • 若考查 CSMA/CD：先算单向传播时延 $\tau =d/v$。抓准问题是“单端最早检出”还是“两台主机均检测到冲突”（均检测到最短耗时为 $\tau$，最长耗时为 $2\tau$）。

   • 若考查 GBN：找到序号位数 $n$，锁定最大发送窗口 ==$W_{T\max }=2^n-1$==；接收窗口固定 $W_R=1$。

2. 精确区分帧格式与有效载荷：

   • 看到标准以太网帧（1518B），直接依据结构式拆解：头部 14B（目的MAC 6B + 源MAC 6B + 类型 2B）+ 尾部 FCS 4B = 18B。

   • 求有效速率时，分子有效载荷必须用 ==$1518-18=1500\text{ B}$==。

3. 读透帧序号与累积确认标记：

   • 标记形如 $S_{x,y}$ 或 $R_{x,y}$ 时：$x$ 是本地发出的数据帧号；$y$ 是 期望接收对方的下一帧序号（表示 $y-1$ 及之前均已正确接收并入队）。

   • 重传判定：发生超时后，后退至该超时帧，重传该帧以及之后已发送的所有帧。

   • 更新确认号：新发出或重传的帧中，确认序号 $y$ 必须刷新为本地最新正确接收到的对方数据帧编号加 1。

4. 统一时间轴与指标求解：

   • 统一换算单位（$\text{km}\to \text{m}$，$\text{Mb/s}\to 10^6\text{ b/s}$，$\text{s}\to \text{ms}/\mu \text{s}$）。

   • 确认帧往返周期分母：$T=t_{\text{data}}+2\tau +t_{\text{ack}}$（检查捎带确认是否带入 $t_{\text{ack}}$）。

   • 计算 $U$ 或 $C_{\text{eff}}$。

例题

例题 1：CSMA/CD 碰撞极限与有效传输速率（2010真题）

• 题目：

  某局域网采用 CSMA/CD 协议实现介质访问控制，数据传输速率为 10Mb/s，主机甲和主机乙之间的距离是 2km，信号传播速率是 200000km/s。

  1. 若主机甲和主机乙发送数据时发生冲突，则从开始发送数据的时刻起，到两台主机均检测到冲突为止，最短需要经过多长时间？最长需要经过多长时间？

  2. 若网络不存在任何冲突与差错，主机甲总以标准的最长以太网数据帧（1518B）向主机乙发送数据，主机乙成功收到一个数据帧后，就立即向主机甲发送一个 64B 的确认帧，主机甲收到确认帧后方可发送下一个数据帧。此时主机甲的有效数据传输速率是多少（不考虑以太网前导码）？

• 解题过程：

  1. 计算单向传播时延：

     $\tau =\frac{2\text{ km}}{200000\text{ km/s}}=10^{-5}\text{ s}=10\mu \text{s}$

     • 最短时间：两机同时发送，中点相撞后波形各自返回两端：

       $t_{\min }=0.5\tau +0.5\tau =\tau =10\mu \text{s}$

     • 最长时间：甲发送的信号即将到达乙的前一瞬间乙开始发送，乙立即检测到冲突，而碰撞信号还需一个单向时延 $\tau$ 才能传回甲端：

       $t_{\max }=\tau +\tau =2\tau =20\mu \text{s}$

  2. 以太网 MAC 帧头部（14B）与尾部 FCS（4B）共 18B，计算有效载荷：

     $L_{\text{data}}=1518\text{ B}-18\text{ B}=1500\text{ B}$

  3. 分别计算发送时延与周期总时间：

     $t_{\text{data}}=\frac{1518\times 8\text{ bit}}{10\times 10^6\text{ bit/s}}=1214.4\mu \text{s}$

     $t_{\text{ack}}=\frac{64\times 8\text{ bit}}{10\times 10^6\text{ bit/s}}=51.2\mu \text{s}$

     单周期往返总耗时（包含双向介质传播 $2\tau$）：

     $T=t_{\text{data}}+2\tau +t_{\text{ack}}=1214.4+20+51.2=1285.6\mu \text{s}$

  4. 计算有效数据传输速率：

     $C_{\text{eff}}=\frac{L_{\text{data}}}{T}=\frac{1500\times 8\text{ bit}}{1285.6\times 10^{-6}\text{ s}}\approx 9.33\text{ Mb/s}$

• 结论：

  均检测到冲突的最短时间为 10μs，最长时间为 20μs；主机甲的有效数据传输速率约为 9.33Mb/s。

例题 2：GBN 窗口分析与最大信道利用率（2017真题）

• 题目：

  甲乙双方均采用后退 $N$ 帧协议（GBN）进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为 1000B。$S_{x,y}$ 和 $R_{x,y}$ 分别表示甲和乙发送的数据帧，其中 $x$ 是发送序号，$y$ 是确认序号（表示期望接收对方的下一帧序号），数据帧的发送序号和确认序号字段均为 3 比特。信道传输速率为 100Mb/s，$\text{RTT}=0.96\text{ ms}$。图 (a) 中甲发送了 $S_{0,0}\sim S_{4,1}$，乙回复了 $R_{0,1}\sim R_{3,3}$；图 (b) 中甲发至 $S_{4,2}$ 时 $S_{2,0}$ 超时。

  1. 对于图 (a)，$t_0$ 到 $t_1$ 期间甲断定乙已正确接收的数据帧数是多少？是哪几个帧？

  2. 对于图 (a)，从 $t_1$ 起甲未收到乙新帧前，最多还可以发多少帧？起止帧分别是什么？

  3. 对于图 (b)，$t_1$ 时刻 $S_{2,0}$ 超时，甲需重发多少帧？重发的第一个帧是什么？

  4. 甲可以达到的最大信道利用率是多少？

• 解题过程：

  1. $t_1$ 前甲收到的最后确认帧为 $R_{3,3}$，确认号为 3，表示乙期望接收 3 号帧，即 0、1、2 号帧均已正确接收。

     已正确接收帧数为 3 个，分别为 $S_{0,0},S_{1,0},S_{2,0}$。

  2. 序号位数 $n=3$，发送窗口上限 $W_T=2^3-1=7$。

     已确认帧为 0、1、2，窗口下界滑动至 3 号帧。已发未确认帧为 3 号（$S_{3,0}$）和 4 号（$S_{4,1}$），共占用 2 个窗口额度。

     剩余可发帧数：

     $7-2=5\text{ 个}$

     甲最新收到的乙帧为 $R_{3,3}$（乙发送序号为 3），甲期望收到乙的下一帧为 4，故新帧确认序号均为 4。

     发送的帧序号依次为 5、6、7、0、1。

     第一个帧为 $S_{5,4}$，最后一个帧为 $S_{1,4}$。

  3. GBN 发生超时须重传该帧及后续所有已发送帧。

     $S_{2,0}$ 超时，需重发 2、3、4 号共 3 个帧。

     甲最后收到乙的帧为 $R_{2,2}$（乙发送序号为 2），故甲期望接收 3 号帧，捎带确认号填 3。

     重传的第一个帧为 $S_{2,3}$。

  4. 计算帧发送时延：

     $t_{\text{frame}}=\frac{1000\times 8\text{ bit}}{100\times 10^6\text{ bit/s}}=0.08\text{ ms}$

     因为双方均采用捎带确认且帧长均为 1000B，确认帧发送时延相同：

     $t_{\text{ack}}=0.08\text{ ms}$

     一个往返周期的基准总耗时：

     $T=t_{\text{frame}}+\text{RTT}+t_{\text{ack}}=0.08+0.96+0.08=1.12\text{ ms}$

     连续发送 7 个帧的耗时：

     $7\times t_{\text{frame}}=7\times 0.08=0.56\text{ ms}<T$

     代入最大信道利用率公式：

     $U=\frac{7\times t_{\text{frame}}}{T}=\frac{0.56\text{ ms}}{1.12\text{ ms}}=50\%$

• 结论：

  图 (a) 正确接收 3 帧；甲最多还可发 5 帧，分别为 $S_{5,4}$ 至 $S_{1,4}$；图 (b) 需重发 3 帧，首帧为 $S_{2,3}$；最大信道利用率为 50%。

⚠️ 易错点

Warning

• “两机均检测到碰撞”的最短时间不是 0：如果问“最快有节点发现碰撞”，时间趋于 0；但只要题目带有“两机均检测到”，两机同时发在中点相撞折返，耗时必定严格为 ==$\tau$==。

• 有效速率误用总帧长：以太网 MAC 帧结构开销固定为 ==目的MAC(6B) + 源MAC(6B) + 类型(2B) + FCS(4B) = 18B==。若题目问“有效数据传输速率”，分子必须扣去 18B（即 $1518-18=1500\text{ B}$）。

• 停等周期分母遗漏回传时延：单周期耗时 $T=t_{\text{data}}+2\tau +t_{\text{ack}}$，分母中的介质传播时延是往返双向的，必须计入 ==$2\tau$==。

• GBN 窗口上限误写为 $2^n$：GBN 的最大发送窗口为 ==$2^n-1$==（SR 才是 $W_T+W_R\le 2^n$ 且 $W_T\le 2^{n-1}$）。

• 捎带确认号混淆：确认号 $y$ 的定义为“期望接收对方的下一帧序号”，即 $y-1$ 及之前的帧已被正确接收；且新发帧的确认号永远取自本地最新收到的对方帧序号加 1。

速记

冲突均测两头算（最短一重$\tau$最长两重$\tau$），载荷扣除十八算（6+6+2+4），GBN窗口少留一（$2^n-1$），确认指明下一期，停等周期双程延。