1. 从“停等”到“流水线”为什么我们需要选择重传协议如果你写过网络编程或者调试过TCP连接大概率遇到过“丢包”和“重传”这两个词。在数据链路层和传输层可靠传输是基石。最早的“停等协议”Stop-and-Wait简单直接发一帧等一个确认ACK收到后再发下一帧。这就像两个人用对讲机你说一句“完毕”必须等对方回一句“收到”才能说下一句。在网络质量尚可的局域网里这种方式勉强够用。但一旦把场景放到广域网或者带宽稍高、延迟稍大的环境里停等协议的效率问题就暴露无遗。它的信道利用率低得可怜计算公式是U Td / (Td RTT Ta)其中Td是发送数据时间RTT是往返时延Ta是发送确认时间。在高速、高延迟的链路上Td可能很短但RTT很长导致大部分时间信道都在空等带宽被白白浪费。这就像用万吨巨轮一次只运一个集装箱船跑得再快大部分时间也在等装货卸货。于是“滑动窗口协议”登场了。它允许发送方在收到确认前连续发送多个数据帧将信道“管道化”极大地提高了利用率。滑动窗口协议主要有两种回退N帧Go-Back-N, GBN和选择重传Selective Repeat, SR。GBN协议相对简单发送方维护一个发送窗口按序发送接收方只按序接收一旦发现某帧出错或丢失就丢弃该帧及之后所有帧发送方需要从出错帧开始全部重传。这就像流水线上一个零件装错了整条线都得停下来从这个零件开始全部返工。而选择重传协议SR则更加“精明”和“宽容”。它的核心思想是接收方可以缓存乱序到达但正确的帧只要求发送方重传真正丢失或出错的那一帧。这解决了GBN协议中“一个错误株连九族”的弊端在错误率较高的信道中比如早期的无线网络、卫星链路优势明显。今天虽然TCP等高层协议有更复杂的拥塞控制但SR协议的思想——选择性确认与重传——依然是其重要组成部分。理解SR不仅是理解计算机网络课本上的一个算法更是理解现代可靠传输协议设计哲学的一把钥匙。2. SR协议的核心机制发送与接收窗口如何协同工作选择重传协议的精髓在于发送方和接收方窗口的独立与协同。它们不再是GBN中那种强耦合的同步关系而是各自维护状态通过确认机制进行松耦合的交互。2.1 发送方不只是个无情的发送机器发送方维护着三个关键的数据结构发送窗口Send Window, SWND 一个固定大小的、允许已发送但未被确认的帧的序号范围。假设窗口大小为N序号从0开始那么在任何时刻发送方只能发送序号落在[send_base, send_base N - 1]这个区间内的帧。send_base指向最早已发送但未确认的帧。定时器Timer 在GBN中通常只有一个定时器用于最早的未确认帧。而在SR中每个已发送但未确认的帧都需要一个独立的定时器。这是SR能实现“选择性”重传的关键。当某个帧的定时器超时发送方只重传这一帧然后重启该帧的定时器。确认状态缓存 记录哪些帧已被确认ACKed。通常用一个布尔数组或位图来实现。发送方的动作可以分解为以下几个驱动事件上层调用发送数据 检查下一个要发送的序号next_seq_num是否在发送窗口内。如果在则封装数据帧并发送启动该帧的独立定时器然后next_seq_num加一。如果不在则缓存数据或通知上层窗口已满。收到ACK 这是最有趣的部分。SR协议允许接收方发送累计确认但更典型的是使用选择性确认SACK。假设收到对序号n的ACK。如果n在发送窗口内即send_base n send_base N发送方会标记该帧为已确认。如果n恰好等于send_base即确认了窗口最左端的帧那么发送方会将send_base向右移动到当前窗口内最小未确认的序号。这相当于窗口向前“滑动”了。无论n是否等于send_base只要该帧被确认就停止该帧的定时器。定时器超时 当序号为n的帧定时器超时发送方仅重传这一帧并重启该帧的定时器。这是与GBN最本质的区别。这里有一个关键细节窗口大小N和序号空间大小必须满足一定关系否则会造成歧义。我们稍后在“序号空间与窗口大小的约束”一节会详细讨论。2.2 接收方一个有序的缓存管理员接收方的逻辑比发送方更复杂一些因为它要处理乱序到达的帧。接收窗口Receive Window, RWND 同样是一个固定大小为N的窗口期望接收的帧序号范围是[rcv_base, rcv_base N - 1]。任何序号落在这个窗口内的帧都会被接收方处理窗口外的帧会被直接丢弃并可能引发一个ACK用于帮助发送方同步。缓存区Buffer 一个能容纳至少N个帧的缓存区用于存放乱序到达但正确的帧。交付队列 用于向上层按序交付数据。接收方的动作分解收到序号为n的帧情况A帧在接收窗口内且正确rcv_base n rcv_base N发送一个针对该帧的ACKACK n。如果该帧是新的之前没缓存过则将其缓存。如果该帧恰好是期望的帧即n rcv_base接收方会检查缓存从rcv_base开始连续地向上层交付所有已缓存的、按序的帧。每交付一帧rcv_base就加一接收窗口随之向右滑动。这个过程会一直持续直到遇到第一个未缓存的序号为止。情况B帧在接收窗口内但出错 直接丢弃。在SR中接收方通常不会发送否定确认NAK而是等待发送方该帧的定时器超时。当然有些SR变种会使用NAK来加速重传。情况C帧在接收窗口左侧n rcv_base 这说明接收方已经交付了该帧并且窗口已经滑过。此时接收方必须再发送一个ACK n。为什么因为发送方可能丢失了之前对这个帧的ACK这个重复的ACK能帮助发送方知道该帧已被正确接收从而避免不必要的重传。情况D帧在接收窗口右侧n rcv_base N 帧已超出接收方当前能处理的范畴直接丢弃。这通常意味着发送方和接收方窗口出现了不同步。接收方的设计体现了SR的智能它利用缓存容忍乱序通过按序交付保证上层语义并通过ACK机制包括对旧帧的重复ACK来积极协助发送方维护连接状态。3. 关键问题深度剖析序号、窗口与定时器理解了基本流程我们来看几个让SR协议真正稳定工作的关键设计点这些也是面试和实际理解中的高频考点。3.1 序号空间与窗口大小的约束为什么N必须小于等于序号空间的一半这是一个经典的、必须搞清楚的约束条件。我们用一个反例来说明。假设序号空间很小只有0, 1, 2, 3即2比特模4运算而发送/接收窗口大小N 3。考虑如下场景初始状态发送方和接收方窗口都是[0, 1, 2]。发送方发送了帧0, 1, 2接收方都收到了并发送了ACK 0, ACK 1, ACK 2。但ACK 0和ACK 1在网络中丢失了只有ACK 2到达。发送方收到ACK 2窗口滑动。现在发送窗口变为[3, 0, 1]因为模4运算3之后是0。send_base现在是3不对这里有个关键send_base必须移动到最小的未确认帧。由于ACK 0和ACK 1丢失发送方认为帧0和帧1未确认所以send_base仍然是0窗口实际上无法滑动但为了继续通信协议必须允许发送新数据。假设经过一段时间发送方超时重传了帧0旧的帧0。此时接收方的窗口已经因为收到了0,1,2而滑动到了[3, 0, 1]。它现在期待的是帧3, 0, 1。当重传的旧帧0到达时它的序号0正好落在接收方当前窗口[3, 0, 1]内接收方无法区分这个帧0是新的属于下一个轮回还是旧的重传。它会错误地将其作为新帧接收导致数据错误。问题的根源在于当窗口大小N等于或大于序号空间大小时窗口向前滑动后新旧两个轮回的序号范围会产生重叠接收方无法区分。因此必须保证发送窗口大小 接收窗口大小 序号空间大小。在SR中通常双方窗口大小相等即N N 2^kk是序号比特数所以N 2^(k-1)。也就是说窗口最大不能超过序号范围的一半。注意 这是理论上的要求。在实际协议如TCP中序号空间非常大32位窗口大小受其他因素如接收缓冲区限制通常不会触及这个理论上限但这个原理是设计的基础。3.2 独立定时器 vs 单一定时器管理开销与效率的权衡GBN使用单一定时器管理最早未确认的帧简单但粗放。SR为每个未确认帧维护独立定时器精细但复杂。实现开销 独立定时器意味着更多的数据结构如链表或优先级队列来管理超时事件和更频繁的定时器操作启动、停止、检查。在帧数量很多时这是一个不可忽视的开销。重传精度与效率 这是独立定时器带来的最大好处。假设窗口内帧1丢失帧2, 3, 4…都正确到达。在GBN下帧1超时会导致2,3,4…全部被重传浪费带宽。在SR下只有帧1被重传。接收方已经缓存了2,3,4…一旦收到重传的帧1就可以立即向上交付一批数据时延更低。实战心得 在实现SR协议仿真或理解其性能时定时器管理是核心。一种常见的优化是使用一个“主定时器”配合时间戳。为每个发送的帧记录其发送时间戳。主定时器周期性检查所有未确认帧的时间戳将那些当前时间 - 发送时间 RTO的帧加入重传队列。这样避免了大量操作系统定时器资源的使用。3.3 确认机制ACK、NAK与SACK肯定确认ACK SR协议主要依赖ACK。接收方每收到一个在窗口内的新帧就立即发送对该帧的ACK。这个ACK有两个作用一是确认该帧收到二是作为接收方窗口状态的隐式通告告诉发送方“我期待rcv_base的帧”。否定确认NAK 标准SR协议不一定需要NAK。没有NAK丢包完全依靠发送方定时器超时来检测这至少需要一个RTO的时间。加入NAK后接收方一旦检测到序号间隙比如收到了帧0和帧2但没收到帧1可以立即发送一个NAK 1通知发送方“帧1可能丢了快重传”。这可以显著减少丢包恢复时间特别是在错误率高的链路上。许多实际实现包括TCP的SACK选项都包含了类似NAK的机制。选择性确认SACK 这是对基本ACK机制的强大增强。一个SACK报文可以同时确认多个不连续的数据块。例如接收方收到了帧0, 1, 3, 4它可以发送一个ACK其中包含“SACK块”指明已收到[0-1]和[3-4]。发送方据此能精确知道只有帧2丢失了无需等待超时就可以重传帧2同时知道帧3和帧4无需重传。TCP的SACK选项正是SR思想在传输层的直接体现。4. 与回退N帧GBN协议的对比与选型思考理解了SR再回头看GBN就能更深刻地体会其设计取舍。我们可以从几个维度对比特性维度回退N帧 (GBN)选择重传 (SR)接收方缓存不缓存乱序帧直接丢弃。缓存乱序但正确的帧。确认机制累计确认。ACK(n)表示n及之前所有帧已正确接收。独立确认或选择性确认(SACK)。每个帧或数据块可被单独确认。重传策略超时后重传所有已发送但未确认的帧从最早未确认帧开始。超时后仅重传超时的那个帧。定时器一个用于最早的未确认帧。每个已发送未确认的帧都有一个独立定时器或等效机制。接收窗口大小固定为1。通常大于1与发送窗口大小相等。优点实现极其简单接收方逻辑简单定时器管理容易。在低错误率信道中效率尚可。带宽利用率高尤其在高错误率、高带宽延迟积BDP的信道中。只重传错误帧避免不必要的重传。缺点一个错误拖累全局。错误率高时大量正确帧被无辜重传效率急剧下降。不适合卫星、无线等链路。实现复杂。需要维护多个定时器、接收方需要缓存管理、序号空间要求更严格窗口序号空间/2。适用场景错误率极低的可靠有线链路如局域网或对实现复杂度有严格限制的嵌入式环境。错误率较高的链路无线网络、早期卫星通信、带宽延迟积大的长肥管道。是现代可靠传输协议如TCP的基础。选型思考 这本质上是一个“简单性”与“效率”的权衡。在计算机早期处理能力和内存非常宝贵GBN的简单性极具吸引力。但随着硬件发展复杂度不再是首要瓶颈而网络带宽和延迟成为关键SR的效率优势就凸显出来。TCP协议的设计就融合了这两种思想默认使用累计确认类似GBN但通过SACK选项实现了选择重传的能力它使用单个重传定时器但通过快速重传收到3个重复ACK即触发重传机制部分实现了对单个丢包的选择性响应。可以说TCP是一个混合体在实践中根据网络状况动态调整策略。5. 实战推演一个完整的SR协议工作流程与故障模拟让我们通过一个具体的例子把SR协议的所有机制串起来。假设窗口大小N4序号空间80-7模8运算满足N 8/2。初始状态发送方send_base 0,next_seq_num 0, 窗口[0,1,2,3]。接收方rcv_base 0, 窗口[0,1,2,3]缓存空。步骤1正常发送与接收发送方发送帧0,1,2,3并为每个启动独立定时器。接收方按序收到帧0。发送ACK 0缓存帧0。发现rcv_base0已收到交付帧0给上层rcv_base变为1窗口滑动至[1,2,3,4]。接收方收到帧2乱序。发送ACK 2缓存帧2。rcv_base仍是1因为帧1没到无法交付。接收方收到帧1。发送ACK 1缓存帧1。此时缓存中有帧1,2。检查rcv_base1已收到于是连续交付帧1和帧2rcv_base变为3窗口滑动至[3,4,5,6]。接收方收到帧3。发送ACK 3缓存帧3。交付帧3rcv_base变为4窗口滑动至[4,5,6,7]。发送方陆续收到ACK 0,ACK 1,ACK 2,ACK 3。窗口滑动send_base变为4现在可以发送帧4,5,6,7。步骤2模拟帧丢失与选择性重传发送方发送帧4,5,6,7。假设帧5在网络中丢失。帧4,6,7正确到达接收方。接收方收到帧4发送ACK 4交付rcv_base5窗口[5,6,7,0]模8。接收方收到帧6发送ACK 6缓存帧6因为期望的是帧5。接收方收到帧7发送ACK 7缓存帧7。发送方收到ACK 4ACK 6ACK 7。它知道帧4,6,7已收到停止它们的定时器。但帧5的ACK始终没来。帧5的定时器超时。发送方仅重传帧5并重启帧5的定时器。接收方收到重传的帧5。发送ACK 5。此时它发现rcv_base5已收到且缓存中有帧6,7。于是它连续交付帧5,6,7rcv_base变为0模8窗口滑动至[0,1,2,3]。发送方收到ACK 5停止帧5的定时器窗口可以继续滑动。步骤3模拟ACK丢失与重复ACK接续步骤2后发送方发送新的一批帧0,1,2,3注意序号轮回。假设帧0的ACK丢失了。发送方帧0的定时器超时重传帧0。此时接收方的窗口是[0,1,2,3]它收到了这个重传的帧0。它无法判断这是新的帧0还是旧的重传。但根据SR规则它必须检查这是否是重复帧。实现上接收方需要维护一个“已接收并确认”的最高序号信息。它发现帧0序号0小于当前的rcv_base此时rcv_base可能已经大于0因为收到了更新的帧或者它发现自己已经缓存过帧0。于是接收方再次发送一个ACK 0。发送方收到这个重复的ACK 0。它知道接收方已经收到了帧0可能是之前ACK丢了于是它可以安全地忽略这个重传帧带来的影响并确认帧0已收到。这避免了发送方错误地认为接收方没收到帧0而陷入死循环。这个推演展示了SR协议如何处理乱序、丢包、ACK丢失等各种异常情况其核心在于缓存、独立确认和重复ACK的巧妙运用。6. 从理论到实践SR思想在现代网络协议中的体现虽然教科书上的SR是一个数据链路层协议但其思想已经深深嵌入现代网络协议栈尤其是在传输层。TCP协议中的SR元素选择性确认SACK 如前所述这是最直接的体现。通过在TCP选项字段中携带SACK块接收方可以告知发送方多个不连续的数据段已收到使发送方能进行选择性重传。快速重传与快速恢复 当发送方连续收到3个对同一序号的重复ACKDup-ACK时它推断该序号的数据段可能丢失于是不等超时立即重传该数据段。这本质上是利用重复ACK作为一种隐式的、负面的选择信号实现了类似SR的快速重传。随后的“快速恢复”算法调整拥塞窗口也体现了对单个丢包的选择性处理而非GBN式的全面回退。乱序缓存与按序交付 TCP接收端有接收缓冲区可以缓存乱序到达的报文段等待缺失的报文段到达后再按序交付给应用层。这完全继承了SR接收方的核心逻辑。QUIC协议中的强化 谷歌提出的QUIC基于UDP协议将SR思想更进一步。它在传输层原生支持了更细粒度的、基于数据流的可靠传输每个数据包都有独立的包号重传机制天然就是选择性的避免了TCP中因序列号重用可能带来的歧义问题在高速长连接下重传效率更高。实战心得与注意事项窗口大小的动态调整 在实际协议中如TCP窗口大小不是固定的而是动态变化的受限于接收方通告窗口rwnd和拥塞窗口cwnd。理解固定窗口的SR是基础但更要明白在实际中窗口是流动的协议需要同时处理可靠传输和流量控制、拥塞控制。定时器管理的优化 为每个数据包维护一个硬件定时器是不现实的。实际中TCP使用一个重传定时器RTO但其超时时间是通过动态测量RTT来计算的。当需要重传时它可能采用类似“批量重传”或基于SACK信息精确重传的策略。在你自己实现可靠UDP时可以采用一个时间轮或优先队列来管理多个虚拟定时器。应用场景选择 如果你在设计一个内部系统的通信模块网络环境可控低错误率、低延迟那么实现一个简单的GBN变种可能更省心。但如果你面对的是公网、移动网络等不稳定环境那么引入选择性重传哪怕是简化版对提升性能至关重要。很多时候不必完全实现教科书式的SR可以取其精髓例如实现乱序缓存和按序交付但重传策略可以简化或者使用一个主定时器配合SACK信息来实现选择性重传。理解选择重传协议不仅仅是记住它的规则更是理解一种“在不可靠的媒介上实现可靠通信”的设计哲学通过增加接收端的复杂性缓存和智能选择性确认来换取信道利用率的本质提升这是一种典型的以空间缓存和计算复杂度换取时间和效率的工程权衡。下次当你用Wireshark抓包看到TCP报文里的SACK选项时你就会会心一笑知道这正是数据链路层那个古老而精妙的选择重传思想在互联网的血管中继续跳动。