三种可靠传输机制在数据链路层中为了在不可靠的信道上实现可靠传输有三种经典协议一、总览协议英文发送窗口接收窗口核心思想停止-等待Stop-and-Wait11发一个等一个回退N帧Go-Back-N (GBN)N11发多个错一个重传全部选择重传Selective Repeat (SR)N1N1发多个只重传出错的那个三者的关系停止-等待 ⊂ GBN ⊂ SR逐步放宽限制效率逐步提高二、停止-等待协议Stop-and-Wait原理发送方 接收方 │ │ │──── 发送帧 0 ──────────────→ │ │ │ 收到校验 │←──────────── ACK 0 ──────────│ │ │ │──── 发送帧 1 ──────────────→ │ │ │ │←──────────── ACK 1 ──────────│ │ │规则发送方每发一帧就停下来等待直到收到ACK才发下一帧帧编号只需0、1两个1比特设置超时计时器超时未收到ACK → 重传四种情况情况处理帧正确到达 → 收到ACK发下一帧帧丢失超时重传ACK丢失超时重传接收方丢弃重复帧ACK迟到超时后才到已重传收到迟到的ACK后丢弃继续优缺点✅ 简单实现容易❌信道利用率极低大部分时间在等三、回退N帧协议Go-Back-NGBN核心思想发送方可以连续发送多个帧不用等ACK但如果某一帧出错从该帧起全部重传。窗口机制发送窗口大小 Wt N如 N4 接收窗口大小 Wr 1 已确认 │ 已发送未确认窗口内│ 可发送 │ 不可发送 │←────── Wt ──────→│工作过程发送方 接收方 │── 帧0 ──→ │ │── 帧1 ──→ │ 按序接收 │── 帧2 ──→ │ │── 帧3 ──→ │ │ │ │←── ACK0 ── │ │←── ACK1 ── │ │ 帧2丢失或出错 │ │←── ACK1 ──重复ACK │ 只期望帧2收到帧3→丢弃重发ACK1 │ │ │ 超时从帧2开始全部重传 │ │── 帧2 ──→ │ │── 帧3 ──→ │ │←── ACK2 ── │ │←── ACK3 ── │关键规则规则说明接收窗口 1只接受按序到达的帧失序帧一律丢弃累积确认ACK_n 表示n及之前的帧全部正确收到超时重传只设一个计时器最早未确认帧超时后重传窗口内所有帧帧编号至少需要N1个编号防止新旧帧混淆编号要求例N4 → 编号 0,1,2,3,4 → 至少3比特优缺点✅ 信道利用率比停止-等待高❌ 一帧出错 → 重传多帧浪费带宽❌ 接收方必须按序接收失序帧全部丢弃四、选择重传协议Selective RepeatSR核心思想发送方连续发送多个帧接收方逐个确认出错时只重传出错的那一帧。窗口机制发送窗口 Wt N 接收窗口 Wr N通常 Wt Wr N 约束Wt Wr ≤ 2^nn为编号位数 通常取Wt Wr 2^(n-1)工作过程发送方 接收方 │── 帧0 ──→ │ │── 帧1 ──→ │ │── 帧2 ──→ 丢失 │ │── 帧3 ──→ │ 收到帧3缓存失序 │ │ │←── ACK0 ── │ │←── ACK1 ── │ │←── ACK3 ──逐个确认 │ │ │ │ 帧2超时 → 只重传帧2 │ │── 帧2 ──→ │ 收到帧2与缓存的帧3一起上交 │←── ACK2 ── │关键规则规则说明接收窗口 N可以缓存失序帧逐个确认每帧独立ACK非累积选择性重传只重传出错/丢失的帧每帧一个计时器发送窗口内每帧各有独立超时计时器帧编号至少2N个编号编号要求例N4 → 编号 0~7 → 至少3比特优缺点✅ 信道利用率最高不浪费带宽❌ 实现复杂接收方需缓存、排序❌ 每帧一个计时器开销大五、三者对比⭐考研必背对比项停止-等待GBNSR发送窗口1NN接收窗口11N确认方式逐个累积逐个重传策略重传当前帧重传窗口内所有帧只重传出错帧计时器数量1个1个N个接收方缓存不需要不需要需要缓存失序帧信道利用率低中高实现复杂度低中高编号数量≥2≥N1≥2N六、信道利用率公式W发送窗口大小$T_d$发送一帧的时延RTT往返传播时延$T_a$发送ACK的时延通常忽略停止-等待W1 → 利用率最低GBN/SRWN → 利用率提高N倍理想情况七、一张图总结可靠传输三兄弟 停止-等待发1个等1个简单但慢 │ │ 放宽允许连续发 ▼ GBN连续发N个错1个重传N个接收方只收按序的 │ │ 放宽接收方可缓存失序帧 ▼ SR连续发N个错1个只重传1个最高效最复杂三种可靠传输协议的实现原理一、停止-等待协议Stop-and-Wait1. 整体架构┌─────────────────────────────────────────────────┐ │ 发送方 │ │ │ │ ┌─────────┐ ┌──────────┐ ┌───────────┐ │ │ │ 数据缓存 │───→│ 发送逻辑 │───→│ 超时计时器 │ │ │ └─────────┘ └──────────┘ └───────────┘ │ │ ▲ │ │ │ │ ┌──────────┐ │ │ │ └─────────│ ACK判断 │←────────┘ │ │ └──────────┘ │ └─────────────────────────────────────────────────┘ │ 信道不可靠 ▼ ┌─────────────────────────────────────────────────┐ │ 接收方 │ │ │ │ ┌──────────┐ ┌──────────┐ ┌──────────┐ │ │ │ 帧校验 │───→│ 序号检查 │───→│ 发送ACK │ │ │ └──────────┘ └──────────┘ └──────────┘ │ │ │ │ │ ▼ │ │ ┌──────────┐ │ │ │ 上交网络层│ │ │ └──────────┘ │ └─────────────────────────────────────────────────┘2. 发送方状态机┌──────────────┐ │ 等待上层数据 │◄──────────────────┐ └──────┬───────┘ │ │ 收到数据 │ ▼ │ ┌──────────────┐ │ │ 发送帧启动 │ │ │ 超时计时器 │ │ └──────┬───────┘ │ │ │ ▼ │ ┌──────────────┐ 超时 │ │ 等待ACK │──────────┐ │ └──────┬───────┘ │ │ │ ▼ │ │ ┌──────────┐ │ │ │ 重传该帧 │────┘ │ └──────────┘ │ 收到正确ACK ▼ ┌──────────────┐ │ 停止计时器 │ │ 翻转序号(0↔1)│───────────────────┘ └──────────────┘3. 实现伪代码# 发送方 seq 0 # 当前帧序号0或1 buffer None # 当前发送的帧 def send(data): global seq, buffer buffer make_frame(seq, data) # 封装成帧 transmit(buffer) # 发送 start_timer(TIMEOUT) # 启动计时器 def on_ack_received(ack): global seq if ack.seq seq: # ACK序号匹配 stop_timer() # 停止计时器 seq 1 - seq # 翻转0→1 或 1→0 # 等待上层新数据 def on_timeout(): transmit(buffer) # 重传同一帧 start_timer(TIMEOUT) # 重新启动计时器 # 接收方 expected 0 # 期望收到的序号 def on_frame_received(frame): global expected if frame.seq expected and crc_check(frame): # 序号对且无错 deliver_to_network(frame.data) # 上交 send_ack(expected) # 回ACK expected 1 - expected # 翻转期望值 else: send_ack(1 - expected) # 重发上一个ACK # 丢弃该帧重复帧或出错帧4. 关键实现要点要点说明序号只需1比特0和1交替即可区分新旧帧一个计时器因为同时只有1帧在传接收方不缓存每次只处理1帧ACK也需校验ACK出错 → 超时重传安全二、回退N帧协议GBN1. 整体架构┌────────────────────────────────────────────────────────┐ │ 发送方 │ │ │ │ ┌─────────────────────────────────────────────┐ │ │ │ 发送窗口大小N │ │ │ │ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │ │ │已确认│已发送未确认│ 可发送 │不可发送│ │ │ │ │ └───┴───┴───┴───┴───┴───┴───┴───┘ │ │ │ │ ↑base ↑nextseq │ │ │ └─────────────────────────────────────────────┘ │ │ │ │ ┌──────────────┐ │ │ │ 一个超时计时器│针对最早未确认帧 │ │ └──────────────┘ │ └────────────────────────────────────────────────────────┘2. 发送方状态机┌─────────────────────────────────────────────────────────┐ │ │ │ 事件1上层调用 send(data) │ │ if (nextseq base N): ← 窗口未满 │ │ 发送帧 nextseq │ │ if (base nextseq): ← 窗口之前为空 │ │ start_timer() ← 启动计时器 │ │ nextseq │ │ else: │ │ 拒绝/缓存窗口已满 │ │ │ │ 事件2收到 ACK(n)累积确认 │ │ base n 1 ← 窗口前移 │ │ if (base nextseq): ← 所有帧都已确认 │ │ stop_timer() │ │ else: │ │ restart_timer() ← 为新的最早帧重启 │ │ │ │ 事件3超时 │ │ 重传 [base, nextseq-1] 范围内所有帧 │ │ restart_timer() │ │ │ └─────────────────────────────────────────────────────────┘3. 接收方状态机┌─────────────────────────────────────────────────────────┐ │ │ │ 收到帧 frame │ │ │ │ if (frame.seq expected crc正确): │ │ 上交网络层 │ │ 发送 ACK(expected) │ │ expected │ │ │ │ else: 失序帧 或 出错帧 │ │ 丢弃该帧 │ │ 重新发送 ACK(expected - 1) ← 重复ACK │ │ │ └─────────────────────────────────────────────────────────┘4. 实现伪代码# 发送方 N 4 # 窗口大小 base 0 # 最早未确认帧 nextseq 0 # 下一个待发送帧 buffer [None] * N # 发送缓冲区 def send(data): global nextseq if nextseq base N: # 窗口未满 buffer[nextseq % N] make_frame(nextseq, data) transmit(buffer[nextseq % N]) if base nextseq: # 第一帧启动计时器 start_timer(TIMEOUT) nextseq 1 else: reject() # 窗口满拒绝 def on_ack_received(ack): global base if ack.seq base: # 有效ACK累积确认 base ack.seq 1 # 窗口滑动 if base nextseq: stop_timer() else: restart_timer() # 为新的base重启 def on_timeout(): for i in range(base, nextseq): # 重传窗口内所有帧 transmit(buffer[i % N]) restart_timer() # 接收方 expected 0 def on_frame_received(frame): global expected if frame.seq expected and crc_ok(frame): deliver(frame.data) send_ack(expected) expected 1 else: send_ack(expected - 1) # 重复上一个ACK # 丢弃不缓存5. 关键实现要点要点说明累积确认ACK_n 表示n及之前全部收到ACK可丢失后续ACK能补一个计时器只为最早未确认帧设置超时则全部重传接收窗口1只接受 expected 序号的帧其余丢弃编号 ≥ N1防止新帧被误认为旧帧的重传6. 为什么编号需要 N1假设 N4编号只有 0,1,2,34个 发送方发了 0,1,2,3 → 全部ACK丢失 → 超时重传 0,1,2,3 接收方已期待 4(0 mod 4)收到0 → 误以为是新帧❌ 若编号有5个0~4 重传的是 0,1,2,3接收方期待4 → 不会混淆 ✓三、选择重传协议SR1. 整体架构┌────────────────────────────────────────────────────────┐ │ 发送方 │ │ │ │ 发送窗口大小N │ │ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │已确认│已发送未确认│ 可发送 │不可发送│ │ │ └───┴───┴───┴───┴───┴───┴───┴───┘ │ │ │ │ 每帧一个独立计时器 │ │ timer[base], timer[base1], ..., timer[nextseq-1] │ │ │ └────────────────────────────────────────────────────────┘ ┌────────────────────────────────────────────────────────┐ │ 接收方 │ │ │ │ 接收窗口大小N │ │ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │已交付│ 接收缓冲区可缓存失序帧│不可接收│ │ │ └───┴───┴───┴───┴───┴───┴───┴───┘ │ │ ↑rcv_base │ │ │ └────────────────────────────────────────────────────────┘2. 发送方状态机┌─────────────────────────────────────────────────────────┐ │ │ │ 事件1上层调用 send(data) │ │ if (nextseq base N): │ │ 发送帧 nextseq │ │ start_timer(nextseq) ← 每帧独立计时器 │ │ nextseq │ │ │ │ 事件2收到 ACK(n)逐个确认 │ │ 标记帧 n 为已确认 │ │ stop_timer(n) ← 停止该帧计时器 │ │ while (buffer[base] 已确认): │ │ base ← 窗口前移 │ │ │ │ 事件3帧 n 超时 │ │ 只重传帧 n ← 选择性重传 │ │ restart_timer(n) │ │ │ └─────────────────────────────────────────────────────────┘3. 接收方状态机┌─────────────────────────────────────────────────────────┐ │ │ │ 收到帧 frame序号 n │ │ │ │ if (rcv_base ≤ n ≤ rcv_base N - 1): ← 在窗口内 │ │ if (crc正确): │ │ 缓存帧 n │ │ 发送 ACK(n) │ │ if (n rcv_base): ← 是窗口下界 │ │ 将连续已收到的帧全部上交网络层 │ │ rcv_base 前移 │ │ │ │ elif (rcv_base - N ≤ n ≤ rcv_base - 1): ← 旧帧 │ │ 发送 ACK(n) ← 仍需回ACK │ │ 丢弃已交付过 │ │ │ │ else: ← 完全超出窗口 │ │ 丢弃不回应 │ │ │ └─────────────────────────────────────────────────────────┘4. 实现伪代码# 发送方 N 4 base 0 nextseq 0 buffer [None] * (2 * N) confirmed [False] * (2 * N) timers {} # 每帧一个计时器 def send(data): global nextseq if nextseq base N: buffer[nextseq] make_frame(nextseq, data) transmit(buffer[nextseq]) timers[nextseq] start_timer(TIMEOUT) nextseq 1 def on_ack_received(ack): global base n ack.seq if base n base N: confirmed[n] True stop_timer(timers[n]) # 窗口前移连续已确认的都滑过去 while confirmed[base]: base 1 def on_timeout(n): # 帧n超时 transmit(buffer[n]) # 只重传帧n timers[n] start_timer(TIMEOUT) # 接收方 rcv_base 0 recv_buf [None] * (2 * N) received [False] * (2 * N) def on_frame_received(frame): global rcv_base n frame.seq if rcv_base n rcv_base N - 1: # 在接收窗口内 if crc_ok(frame): recv_buf[n] frame.data received[n] True send_ack(n) # 逐个确认 # 如果收到的是窗口下界连续交付 while received[rcv_base]: deliver(recv_buf[rcv_base]) received[rcv_base] False rcv_base 1 elif rcv_base - N n rcv_base - 1: # 旧帧已交付 send_ack(n) # 仍回ACK # 丢弃5. 关键实现要点要点说明逐个确认每帧独立ACK非累积每帧一个计时器超时只重传该帧接收方有缓存缓存失序帧等齐后一起上交编号 ≥ 2N防止窗口滑动后新旧帧混淆6. 为什么编号需要 2N假设 N4编号只有 0~45个 接收方窗口 [0,1,2,3]全部收到并ACK但ACK全丢失 发送方超时重传 0,1,2,3 此时接收方窗口已滑到 [4,5,6,7] 收到0 → 0 不在 [4,7] 内 → 丢弃 ✓没问题 但如果编号只有 0~34个 接收方窗口 [4,5,6,7] mod 4 [0,1,2,3] 重传的0 落在 [0,3] 内 → 误认为新帧❌ 所以编号必须 ≥ 2N 80~7才能保证 发送窗口 [0,3] 和 接收窗口 [4,7] 不重叠 ✓四、三者实现原理对比总结┌─────────────────────────────────────────────────────────────┐ │ │ │ 停止-等待 │ │ 发1帧 → 等ACK → 收到则发下一帧 / 超时则重传 │ │ 实现1个buffer 1个timer 1bit序号 │ │ │ │ GBN │ │ 连续发N帧 → 累积ACK → 窗口滑动 / 超时重传全部 │ │ 实现N个buffer 1个timer (N1)个序号 │ │ 接收方无缓存只收按序帧 │ │ │ │ SR │ │ 连续发N帧 → 逐个ACK → 只重传出错帧 │ │ 实现N个buffer N个timer 2N个序号 │ │ 接收方有缓存收失序帧凑齐后交付 │ │ │ └─────────────────────────────────────────────────────────────┘实现要素停止-等待GBNSR发送缓冲区1个帧N个帧N个帧接收缓冲区无无N个帧缓存失序计时器1个1个N个每帧一个序号位数1 bit⌈log₂(N1)⌉⌈log₂(2N)⌉窗口滑动触发收到ACK收到累积ACK连续确认从base开始重传范围1帧base到nextseq全部仅超时的那1帧SR选择重传完整时序演示场景设定参数值发送窗口 Wt4接收窗口 Wr4帧编号范围0 ~ 7共 2N 8 个超时时间设为 T故障设定帧1丢失信道丢包帧2乱序比帧3晚到ACK2丢失完整时序图时间 │ │ 发送方 接收方 │ ────── ────── │ │ 窗口: [0,1,2,3] │ rcv_base 0 │ │ ┌─ 发送帧0 ─────────────────────────→ 收到帧0 ✓ │ │ 缓存帧0 │ │ 发送 ACK0 ──→ │ │ rcv_base仍0等帧0是下界交付 │ │ 交付帧0rcv_base → 1 │ │ 窗口: [1,2,3,4] │ │ │ │ ←──────────────────────────────── ACK0 收到 │ │ 标记帧0已确认停timer[0] │ │ 窗口前移: base → 1 │ │ 窗口: [1,2,3,4] │ │ │ ├─ 发送帧1 ─────────────────── ✗ ── 帧1丢失 │ │ 什么都没收到 │ │ │ ├─ 发送帧2 ─────────────────────────→ 收到帧2 ✓ │ │ 但 rcv_base1期望帧1 │ │ 帧2在窗口[1,2,3,4]内 → 缓存 │ │ 发送 ACK2 ──→ ✗ACK2丢失 │ │ rcv_base仍1不连续不交付 │ │ │ ├─ 发送帧3 ─────────────────────────→ 收到帧3 ✓ │ │ 帧3在窗口[1,2,3,4]内 → 缓存 │ │ 发送 ACK3 ──→ │ │ rcv_base仍1 │ │ │ │ ←──────────────────────────────── ACK3 收到 │ │ 标记帧3已确认停timer[3] │ │ base仍1帧1未确认窗口不动 │ │ │ │ 此时发送方状态 │ │ 窗口: [1,2,3,4] │ │ 帧1: 已发送未确认timer[1]运行中 │ │ 帧2: 已发送未确认ACK2丢了timer[2]运行中 │ │ 帧3: 已确认 ✓ │ │ │ │ 此时接收方状态 │ │ 窗口: [1,2,3,4] │ │ 缓冲区: 帧2 ✓, 帧3 ✓ │ │ 等待: 帧1 │ │ │ │ ⏰ timer[1] 超时 │ │ │ ├─ 只重传帧1 ──────────────────────→ 收到帧1 ✓ │ │ 不动帧2、帧3 帧1 rcv_base → 触发连续交付 │ │ 交付帧1 → rcv_base2 │ │ 帧2已缓存 → 交付帧2 → rcv_base3 │ │ 帧3已缓存 → 交付帧3 → rcv_base4 │ │ 窗口滑动: [4,5,6,7] │ │ 发送 ACK1 ──→ │ │ │ │ ←──────────────────────────────── ACK1 收到 │ │ 标记帧1已确认停timer[1] │ │ │ │ ⏰ timer[2] 超时ACK2之前丢了 │ │ │ ├─ 只重传帧2 ──────────────────────→ 收到帧2 │ │ 帧2 rcv_base(4) → 旧帧 │ │ 丢弃但仍回 ACK2 ──→ │ │ │ │ ←──────────────────────────────── ACK2 收到 │ │ 标记帧2已确认停timer[2] │ │ 窗口前移: base → 41,2,3都已确认 │ │ 窗口: [4,5,6,7] │ │ │ │ ✅ 全部完成可以发送帧4,5,6,7 │ ▼各时刻状态快照时刻①帧0确认后发送方接收方窗口[1,2,3,4][1,2,3,4]缓冲区帧1,2,3待发空已交付—帧0时刻②帧1丢失帧2、帧3到达接收方发送方接收方窗口[1,2,3,4][1,2,3,4]确认状态帧1✗ 帧2✗ 帧3✓—缓冲区—帧2✓ 帧3✓等帧1已交付—帧0关键接收方不丢弃帧2、帧3而是缓存等待。时刻③帧1超时重传到达接收方发送方接收方动作只重传帧1收到帧1连续交付1,2,3窗口[1,2,3,4] → [4,5,6,7][1,2,3,4] → [4,5,6,7]已交付—帧0,1,2,3关键帧1到达后缓存中的帧2、帧3一起交付窗口瞬间滑动3格。时刻④帧2重传因ACK2丢失发送方接收方动作重传帧2识别为旧帧丢弃回ACK2结果收到ACK2确认帧2无影响关键接收方通过rcv_base4 帧2序号判断这是旧帧安全丢弃。对比如果是 GBN 会怎样同样的故障场景帧1丢失GBN发送方 帧1超时 → 重传帧1、帧2、帧3全部重传 GBN接收方 帧2到达时帧1未到→ 丢弃接收窗口1不收失序帧 帧3到达时 → 丢弃 重传的帧1到达 → 接收 重传的帧2到达 → 接收 重传的帧3到达 → 接收 结果帧2和帧3被传了两次浪费带宽SR发送方 帧1超时 → 只重传帧1 ✓ SR接收方 帧2到达时 → 缓存 ✓ 帧3到达时 → 缓存 ✓ 帧1到达时 → 交付1,2,3一次性 结果帧2和帧3只传了一次节省带宽关键机制总结机制作用体现在哪发送方缓存保存已发未确认帧以备重传帧1超时后能重传每帧独立计时器精确知道哪帧超时只重传帧1不牵连帧2、3接收方缓存暂存失序帧帧2、3先存着等帧1逐个ACK精确告知哪帧收到ACK3到了但ACK2丢了互不影响窗口约束限制发送/接收范围编号0~7窗口大小4旧帧识别防止重传帧被误收帧2重传时接收方已交付丢弃一图总结 SR 的选择体现在哪GBN回退 错1帧 → 重传N帧 → 接收方丢弃所有失序帧 → 全部重来 一错全错推倒重来 SR选择 错1帧 → 只重传1帧 → 接收方缓存失序帧 → 凑齐交付 精准手术互不牵连
三种可靠传输机制在数据链路层中为了在不可靠的信道上实现可靠传输有三种经典协议一、总览协议英文发送窗口接收窗口核心思想停止-等待Stop-and-Wait11发一个等一个回退N帧Go-Back-N (GBN)N11发多个错一个重传全部选择重传Selective Repeat (SR)N1N1发多个只重传出错的那个三者的关系停止-等待 ⊂ GBN ⊂ SR逐步放宽限制效率逐步提高二、停止-等待协议Stop-and-Wait原理发送方 接收方 │ │ │──── 发送帧 0 ──────────────→ │ │ │ 收到校验 │←──────────── ACK 0 ──────────│ │ │ │──── 发送帧 1 ──────────────→ │ │ │ │←──────────── ACK 1 ──────────│ │ │规则发送方每发一帧就停下来等待直到收到ACK才发下一帧帧编号只需0、1两个1比特设置超时计时器超时未收到ACK → 重传四种情况情况处理帧正确到达 → 收到ACK发下一帧帧丢失超时重传ACK丢失超时重传接收方丢弃重复帧ACK迟到超时后才到已重传收到迟到的ACK后丢弃继续优缺点✅ 简单实现容易❌信道利用率极低大部分时间在等三、回退N帧协议Go-Back-NGBN核心思想发送方可以连续发送多个帧不用等ACK但如果某一帧出错从该帧起全部重传。窗口机制发送窗口大小 Wt N如 N4 接收窗口大小 Wr 1 已确认 │ 已发送未确认窗口内│ 可发送 │ 不可发送 │←────── Wt ──────→│工作过程发送方 接收方 │── 帧0 ──→ │ │── 帧1 ──→ │ 按序接收 │── 帧2 ──→ │ │── 帧3 ──→ │ │ │ │←── ACK0 ── │ │←── ACK1 ── │ │ 帧2丢失或出错 │ │←── ACK1 ──重复ACK │ 只期望帧2收到帧3→丢弃重发ACK1 │ │ │ 超时从帧2开始全部重传 │ │── 帧2 ──→ │ │── 帧3 ──→ │ │←── ACK2 ── │ │←── ACK3 ── │关键规则规则说明接收窗口 1只接受按序到达的帧失序帧一律丢弃累积确认ACK_n 表示n及之前的帧全部正确收到超时重传只设一个计时器最早未确认帧超时后重传窗口内所有帧帧编号至少需要N1个编号防止新旧帧混淆编号要求例N4 → 编号 0,1,2,3,4 → 至少3比特优缺点✅ 信道利用率比停止-等待高❌ 一帧出错 → 重传多帧浪费带宽❌ 接收方必须按序接收失序帧全部丢弃四、选择重传协议Selective RepeatSR核心思想发送方连续发送多个帧接收方逐个确认出错时只重传出错的那一帧。窗口机制发送窗口 Wt N 接收窗口 Wr N通常 Wt Wr N 约束Wt Wr ≤ 2^nn为编号位数 通常取Wt Wr 2^(n-1)工作过程发送方 接收方 │── 帧0 ──→ │ │── 帧1 ──→ │ │── 帧2 ──→ 丢失 │ │── 帧3 ──→ │ 收到帧3缓存失序 │ │ │←── ACK0 ── │ │←── ACK1 ── │ │←── ACK3 ──逐个确认 │ │ │ │ 帧2超时 → 只重传帧2 │ │── 帧2 ──→ │ 收到帧2与缓存的帧3一起上交 │←── ACK2 ── │关键规则规则说明接收窗口 N可以缓存失序帧逐个确认每帧独立ACK非累积选择性重传只重传出错/丢失的帧每帧一个计时器发送窗口内每帧各有独立超时计时器帧编号至少2N个编号编号要求例N4 → 编号 0~7 → 至少3比特优缺点✅ 信道利用率最高不浪费带宽❌ 实现复杂接收方需缓存、排序❌ 每帧一个计时器开销大五、三者对比⭐考研必背对比项停止-等待GBNSR发送窗口1NN接收窗口11N确认方式逐个累积逐个重传策略重传当前帧重传窗口内所有帧只重传出错帧计时器数量1个1个N个接收方缓存不需要不需要需要缓存失序帧信道利用率低中高实现复杂度低中高编号数量≥2≥N1≥2N六、信道利用率公式W发送窗口大小$T_d$发送一帧的时延RTT往返传播时延$T_a$发送ACK的时延通常忽略停止-等待W1 → 利用率最低GBN/SRWN → 利用率提高N倍理想情况七、一张图总结可靠传输三兄弟 停止-等待发1个等1个简单但慢 │ │ 放宽允许连续发 ▼ GBN连续发N个错1个重传N个接收方只收按序的 │ │ 放宽接收方可缓存失序帧 ▼ SR连续发N个错1个只重传1个最高效最复杂三种可靠传输协议的实现原理一、停止-等待协议Stop-and-Wait1. 整体架构┌─────────────────────────────────────────────────┐ │ 发送方 │ │ │ │ ┌─────────┐ ┌──────────┐ ┌───────────┐ │ │ │ 数据缓存 │───→│ 发送逻辑 │───→│ 超时计时器 │ │ │ └─────────┘ └──────────┘ └───────────┘ │ │ ▲ │ │ │ │ ┌──────────┐ │ │ │ └─────────│ ACK判断 │←────────┘ │ │ └──────────┘ │ └─────────────────────────────────────────────────┘ │ 信道不可靠 ▼ ┌─────────────────────────────────────────────────┐ │ 接收方 │ │ │ │ ┌──────────┐ ┌──────────┐ ┌──────────┐ │ │ │ 帧校验 │───→│ 序号检查 │───→│ 发送ACK │ │ │ └──────────┘ └──────────┘ └──────────┘ │ │ │ │ │ ▼ │ │ ┌──────────┐ │ │ │ 上交网络层│ │ │ └──────────┘ │ └─────────────────────────────────────────────────┘2. 发送方状态机┌──────────────┐ │ 等待上层数据 │◄──────────────────┐ └──────┬───────┘ │ │ 收到数据 │ ▼ │ ┌──────────────┐ │ │ 发送帧启动 │ │ │ 超时计时器 │ │ └──────┬───────┘ │ │ │ ▼ │ ┌──────────────┐ 超时 │ │ 等待ACK │──────────┐ │ └──────┬───────┘ │ │ │ ▼ │ │ ┌──────────┐ │ │ │ 重传该帧 │────┘ │ └──────────┘ │ 收到正确ACK ▼ ┌──────────────┐ │ 停止计时器 │ │ 翻转序号(0↔1)│───────────────────┘ └──────────────┘3. 实现伪代码# 发送方 seq 0 # 当前帧序号0或1 buffer None # 当前发送的帧 def send(data): global seq, buffer buffer make_frame(seq, data) # 封装成帧 transmit(buffer) # 发送 start_timer(TIMEOUT) # 启动计时器 def on_ack_received(ack): global seq if ack.seq seq: # ACK序号匹配 stop_timer() # 停止计时器 seq 1 - seq # 翻转0→1 或 1→0 # 等待上层新数据 def on_timeout(): transmit(buffer) # 重传同一帧 start_timer(TIMEOUT) # 重新启动计时器 # 接收方 expected 0 # 期望收到的序号 def on_frame_received(frame): global expected if frame.seq expected and crc_check(frame): # 序号对且无错 deliver_to_network(frame.data) # 上交 send_ack(expected) # 回ACK expected 1 - expected # 翻转期望值 else: send_ack(1 - expected) # 重发上一个ACK # 丢弃该帧重复帧或出错帧4. 关键实现要点要点说明序号只需1比特0和1交替即可区分新旧帧一个计时器因为同时只有1帧在传接收方不缓存每次只处理1帧ACK也需校验ACK出错 → 超时重传安全二、回退N帧协议GBN1. 整体架构┌────────────────────────────────────────────────────────┐ │ 发送方 │ │ │ │ ┌─────────────────────────────────────────────┐ │ │ │ 发送窗口大小N │ │ │ │ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │ │ │已确认│已发送未确认│ 可发送 │不可发送│ │ │ │ │ └───┴───┴───┴───┴───┴───┴───┴───┘ │ │ │ │ ↑base ↑nextseq │ │ │ └─────────────────────────────────────────────┘ │ │ │ │ ┌──────────────┐ │ │ │ 一个超时计时器│针对最早未确认帧 │ │ └──────────────┘ │ └────────────────────────────────────────────────────────┘2. 发送方状态机┌─────────────────────────────────────────────────────────┐ │ │ │ 事件1上层调用 send(data) │ │ if (nextseq base N): ← 窗口未满 │ │ 发送帧 nextseq │ │ if (base nextseq): ← 窗口之前为空 │ │ start_timer() ← 启动计时器 │ │ nextseq │ │ else: │ │ 拒绝/缓存窗口已满 │ │ │ │ 事件2收到 ACK(n)累积确认 │ │ base n 1 ← 窗口前移 │ │ if (base nextseq): ← 所有帧都已确认 │ │ stop_timer() │ │ else: │ │ restart_timer() ← 为新的最早帧重启 │ │ │ │ 事件3超时 │ │ 重传 [base, nextseq-1] 范围内所有帧 │ │ restart_timer() │ │ │ └─────────────────────────────────────────────────────────┘3. 接收方状态机┌─────────────────────────────────────────────────────────┐ │ │ │ 收到帧 frame │ │ │ │ if (frame.seq expected crc正确): │ │ 上交网络层 │ │ 发送 ACK(expected) │ │ expected │ │ │ │ else: 失序帧 或 出错帧 │ │ 丢弃该帧 │ │ 重新发送 ACK(expected - 1) ← 重复ACK │ │ │ └─────────────────────────────────────────────────────────┘4. 实现伪代码# 发送方 N 4 # 窗口大小 base 0 # 最早未确认帧 nextseq 0 # 下一个待发送帧 buffer [None] * N # 发送缓冲区 def send(data): global nextseq if nextseq base N: # 窗口未满 buffer[nextseq % N] make_frame(nextseq, data) transmit(buffer[nextseq % N]) if base nextseq: # 第一帧启动计时器 start_timer(TIMEOUT) nextseq 1 else: reject() # 窗口满拒绝 def on_ack_received(ack): global base if ack.seq base: # 有效ACK累积确认 base ack.seq 1 # 窗口滑动 if base nextseq: stop_timer() else: restart_timer() # 为新的base重启 def on_timeout(): for i in range(base, nextseq): # 重传窗口内所有帧 transmit(buffer[i % N]) restart_timer() # 接收方 expected 0 def on_frame_received(frame): global expected if frame.seq expected and crc_ok(frame): deliver(frame.data) send_ack(expected) expected 1 else: send_ack(expected - 1) # 重复上一个ACK # 丢弃不缓存5. 关键实现要点要点说明累积确认ACK_n 表示n及之前全部收到ACK可丢失后续ACK能补一个计时器只为最早未确认帧设置超时则全部重传接收窗口1只接受 expected 序号的帧其余丢弃编号 ≥ N1防止新帧被误认为旧帧的重传6. 为什么编号需要 N1假设 N4编号只有 0,1,2,34个 发送方发了 0,1,2,3 → 全部ACK丢失 → 超时重传 0,1,2,3 接收方已期待 4(0 mod 4)收到0 → 误以为是新帧❌ 若编号有5个0~4 重传的是 0,1,2,3接收方期待4 → 不会混淆 ✓三、选择重传协议SR1. 整体架构┌────────────────────────────────────────────────────────┐ │ 发送方 │ │ │ │ 发送窗口大小N │ │ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │已确认│已发送未确认│ 可发送 │不可发送│ │ │ └───┴───┴───┴───┴───┴───┴───┴───┘ │ │ │ │ 每帧一个独立计时器 │ │ timer[base], timer[base1], ..., timer[nextseq-1] │ │ │ └────────────────────────────────────────────────────────┘ ┌────────────────────────────────────────────────────────┐ │ 接收方 │ │ │ │ 接收窗口大小N │ │ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │已交付│ 接收缓冲区可缓存失序帧│不可接收│ │ │ └───┴───┴───┴───┴───┴───┴───┴───┘ │ │ ↑rcv_base │ │ │ └────────────────────────────────────────────────────────┘2. 发送方状态机┌─────────────────────────────────────────────────────────┐ │ │ │ 事件1上层调用 send(data) │ │ if (nextseq base N): │ │ 发送帧 nextseq │ │ start_timer(nextseq) ← 每帧独立计时器 │ │ nextseq │ │ │ │ 事件2收到 ACK(n)逐个确认 │ │ 标记帧 n 为已确认 │ │ stop_timer(n) ← 停止该帧计时器 │ │ while (buffer[base] 已确认): │ │ base ← 窗口前移 │ │ │ │ 事件3帧 n 超时 │ │ 只重传帧 n ← 选择性重传 │ │ restart_timer(n) │ │ │ └─────────────────────────────────────────────────────────┘3. 接收方状态机┌─────────────────────────────────────────────────────────┐ │ │ │ 收到帧 frame序号 n │ │ │ │ if (rcv_base ≤ n ≤ rcv_base N - 1): ← 在窗口内 │ │ if (crc正确): │ │ 缓存帧 n │ │ 发送 ACK(n) │ │ if (n rcv_base): ← 是窗口下界 │ │ 将连续已收到的帧全部上交网络层 │ │ rcv_base 前移 │ │ │ │ elif (rcv_base - N ≤ n ≤ rcv_base - 1): ← 旧帧 │ │ 发送 ACK(n) ← 仍需回ACK │ │ 丢弃已交付过 │ │ │ │ else: ← 完全超出窗口 │ │ 丢弃不回应 │ │ │ └─────────────────────────────────────────────────────────┘4. 实现伪代码# 发送方 N 4 base 0 nextseq 0 buffer [None] * (2 * N) confirmed [False] * (2 * N) timers {} # 每帧一个计时器 def send(data): global nextseq if nextseq base N: buffer[nextseq] make_frame(nextseq, data) transmit(buffer[nextseq]) timers[nextseq] start_timer(TIMEOUT) nextseq 1 def on_ack_received(ack): global base n ack.seq if base n base N: confirmed[n] True stop_timer(timers[n]) # 窗口前移连续已确认的都滑过去 while confirmed[base]: base 1 def on_timeout(n): # 帧n超时 transmit(buffer[n]) # 只重传帧n timers[n] start_timer(TIMEOUT) # 接收方 rcv_base 0 recv_buf [None] * (2 * N) received [False] * (2 * N) def on_frame_received(frame): global rcv_base n frame.seq if rcv_base n rcv_base N - 1: # 在接收窗口内 if crc_ok(frame): recv_buf[n] frame.data received[n] True send_ack(n) # 逐个确认 # 如果收到的是窗口下界连续交付 while received[rcv_base]: deliver(recv_buf[rcv_base]) received[rcv_base] False rcv_base 1 elif rcv_base - N n rcv_base - 1: # 旧帧已交付 send_ack(n) # 仍回ACK # 丢弃5. 关键实现要点要点说明逐个确认每帧独立ACK非累积每帧一个计时器超时只重传该帧接收方有缓存缓存失序帧等齐后一起上交编号 ≥ 2N防止窗口滑动后新旧帧混淆6. 为什么编号需要 2N假设 N4编号只有 0~45个 接收方窗口 [0,1,2,3]全部收到并ACK但ACK全丢失 发送方超时重传 0,1,2,3 此时接收方窗口已滑到 [4,5,6,7] 收到0 → 0 不在 [4,7] 内 → 丢弃 ✓没问题 但如果编号只有 0~34个 接收方窗口 [4,5,6,7] mod 4 [0,1,2,3] 重传的0 落在 [0,3] 内 → 误认为新帧❌ 所以编号必须 ≥ 2N 80~7才能保证 发送窗口 [0,3] 和 接收窗口 [4,7] 不重叠 ✓四、三者实现原理对比总结┌─────────────────────────────────────────────────────────────┐ │ │ │ 停止-等待 │ │ 发1帧 → 等ACK → 收到则发下一帧 / 超时则重传 │ │ 实现1个buffer 1个timer 1bit序号 │ │ │ │ GBN │ │ 连续发N帧 → 累积ACK → 窗口滑动 / 超时重传全部 │ │ 实现N个buffer 1个timer (N1)个序号 │ │ 接收方无缓存只收按序帧 │ │ │ │ SR │ │ 连续发N帧 → 逐个ACK → 只重传出错帧 │ │ 实现N个buffer N个timer 2N个序号 │ │ 接收方有缓存收失序帧凑齐后交付 │ │ │ └─────────────────────────────────────────────────────────────┘实现要素停止-等待GBNSR发送缓冲区1个帧N个帧N个帧接收缓冲区无无N个帧缓存失序计时器1个1个N个每帧一个序号位数1 bit⌈log₂(N1)⌉⌈log₂(2N)⌉窗口滑动触发收到ACK收到累积ACK连续确认从base开始重传范围1帧base到nextseq全部仅超时的那1帧SR选择重传完整时序演示场景设定参数值发送窗口 Wt4接收窗口 Wr4帧编号范围0 ~ 7共 2N 8 个超时时间设为 T故障设定帧1丢失信道丢包帧2乱序比帧3晚到ACK2丢失完整时序图时间 │ │ 发送方 接收方 │ ────── ────── │ │ 窗口: [0,1,2,3] │ rcv_base 0 │ │ ┌─ 发送帧0 ─────────────────────────→ 收到帧0 ✓ │ │ 缓存帧0 │ │ 发送 ACK0 ──→ │ │ rcv_base仍0等帧0是下界交付 │ │ 交付帧0rcv_base → 1 │ │ 窗口: [1,2,3,4] │ │ │ │ ←──────────────────────────────── ACK0 收到 │ │ 标记帧0已确认停timer[0] │ │ 窗口前移: base → 1 │ │ 窗口: [1,2,3,4] │ │ │ ├─ 发送帧1 ─────────────────── ✗ ── 帧1丢失 │ │ 什么都没收到 │ │ │ ├─ 发送帧2 ─────────────────────────→ 收到帧2 ✓ │ │ 但 rcv_base1期望帧1 │ │ 帧2在窗口[1,2,3,4]内 → 缓存 │ │ 发送 ACK2 ──→ ✗ACK2丢失 │ │ rcv_base仍1不连续不交付 │ │ │ ├─ 发送帧3 ─────────────────────────→ 收到帧3 ✓ │ │ 帧3在窗口[1,2,3,4]内 → 缓存 │ │ 发送 ACK3 ──→ │ │ rcv_base仍1 │ │ │ │ ←──────────────────────────────── ACK3 收到 │ │ 标记帧3已确认停timer[3] │ │ base仍1帧1未确认窗口不动 │ │ │ │ 此时发送方状态 │ │ 窗口: [1,2,3,4] │ │ 帧1: 已发送未确认timer[1]运行中 │ │ 帧2: 已发送未确认ACK2丢了timer[2]运行中 │ │ 帧3: 已确认 ✓ │ │ │ │ 此时接收方状态 │ │ 窗口: [1,2,3,4] │ │ 缓冲区: 帧2 ✓, 帧3 ✓ │ │ 等待: 帧1 │ │ │ │ ⏰ timer[1] 超时 │ │ │ ├─ 只重传帧1 ──────────────────────→ 收到帧1 ✓ │ │ 不动帧2、帧3 帧1 rcv_base → 触发连续交付 │ │ 交付帧1 → rcv_base2 │ │ 帧2已缓存 → 交付帧2 → rcv_base3 │ │ 帧3已缓存 → 交付帧3 → rcv_base4 │ │ 窗口滑动: [4,5,6,7] │ │ 发送 ACK1 ──→ │ │ │ │ ←──────────────────────────────── ACK1 收到 │ │ 标记帧1已确认停timer[1] │ │ │ │ ⏰ timer[2] 超时ACK2之前丢了 │ │ │ ├─ 只重传帧2 ──────────────────────→ 收到帧2 │ │ 帧2 rcv_base(4) → 旧帧 │ │ 丢弃但仍回 ACK2 ──→ │ │ │ │ ←──────────────────────────────── ACK2 收到 │ │ 标记帧2已确认停timer[2] │ │ 窗口前移: base → 41,2,3都已确认 │ │ 窗口: [4,5,6,7] │ │ │ │ ✅ 全部完成可以发送帧4,5,6,7 │ ▼各时刻状态快照时刻①帧0确认后发送方接收方窗口[1,2,3,4][1,2,3,4]缓冲区帧1,2,3待发空已交付—帧0时刻②帧1丢失帧2、帧3到达接收方发送方接收方窗口[1,2,3,4][1,2,3,4]确认状态帧1✗ 帧2✗ 帧3✓—缓冲区—帧2✓ 帧3✓等帧1已交付—帧0关键接收方不丢弃帧2、帧3而是缓存等待。时刻③帧1超时重传到达接收方发送方接收方动作只重传帧1收到帧1连续交付1,2,3窗口[1,2,3,4] → [4,5,6,7][1,2,3,4] → [4,5,6,7]已交付—帧0,1,2,3关键帧1到达后缓存中的帧2、帧3一起交付窗口瞬间滑动3格。时刻④帧2重传因ACK2丢失发送方接收方动作重传帧2识别为旧帧丢弃回ACK2结果收到ACK2确认帧2无影响关键接收方通过rcv_base4 帧2序号判断这是旧帧安全丢弃。对比如果是 GBN 会怎样同样的故障场景帧1丢失GBN发送方 帧1超时 → 重传帧1、帧2、帧3全部重传 GBN接收方 帧2到达时帧1未到→ 丢弃接收窗口1不收失序帧 帧3到达时 → 丢弃 重传的帧1到达 → 接收 重传的帧2到达 → 接收 重传的帧3到达 → 接收 结果帧2和帧3被传了两次浪费带宽SR发送方 帧1超时 → 只重传帧1 ✓ SR接收方 帧2到达时 → 缓存 ✓ 帧3到达时 → 缓存 ✓ 帧1到达时 → 交付1,2,3一次性 结果帧2和帧3只传了一次节省带宽关键机制总结机制作用体现在哪发送方缓存保存已发未确认帧以备重传帧1超时后能重传每帧独立计时器精确知道哪帧超时只重传帧1不牵连帧2、3接收方缓存暂存失序帧帧2、3先存着等帧1逐个ACK精确告知哪帧收到ACK3到了但ACK2丢了互不影响窗口约束限制发送/接收范围编号0~7窗口大小4旧帧识别防止重传帧被误收帧2重传时接收方已交付丢弃一图总结 SR 的选择体现在哪GBN回退 错1帧 → 重传N帧 → 接收方丢弃所有失序帧 → 全部重来 一错全错推倒重来 SR选择 错1帧 → 只重传1帧 → 接收方缓存失序帧 → 凑齐交付 精准手术互不牵连
