Computer Networks: RDT：其他机制

流水线式 RDT 协议

stop-and-wait 协议中，每发送一个包发送方就阻塞，等待 ACK 后（瓶颈是 RTT）才能做出行动。流水线式 RDT 协议（pipelined RDT protocol）令发送方每次发送 $n$ 个包，这就能获得 $n$ 倍的利用率（utilization）提升。

流水线式 RDT 协议要求：

回退 N 帧协议（Go-Back-N Protocol, GBN）是一种滑动窗口（sliding window）协议。

滑动窗口大小为 $N$，序号占 $k$ 位，则 $N\leq 2^k$。

发送方维护两个指针 base = 1 与 nextseqsum = 1：

上一层调用 rdt_send()：若窗口未满，使用 nextseqsum 创建新包并发送，令 nextseqsum++；若窗口已满（nextseqsum = base+N），把数据退还给上一层（或其他缓存机制）
收到 ACK n：GBN 中的 ACK 是累计确认（cumulative acknowledgement），意味着接收方成功接收了所有序号不超过 n 的包，令 base = chkmax(n+1)，nextseqsum = chkmax(n+1)
超时：计时器追踪包 base（最早的已发送但并未收到 ACK 的包，因此当 base = nextseqsum 时计时器闲置），若超时，重传 [base, nextseqsum-1] 中的所有包后重启计时器；若收到 ACK 使得 base 移动，重启计时器。

接收方维护一个指针 expectedseqnum = 1：

收到包 n：若 n = expectedseqnum 并且校验成功，那么交付数据，令 expectedseqnum++，向发送方发送 ACK n；否则（无论是 n != expectedseqnum 还是校验失败）丢弃包 n，向发送方发送 ACK expectedseqnum-1（最近一次按序接受的包）

接收方只看单调递增的 expectedseqnum，它会丢弃任何失序（out-of-order）的包。假如说当前 expectedseqnum = n 但收到了包 n+1，即使知道这个包是一定会被接受的，GBN 仍然将其丢弃。这样做的好处是接收方的逻辑简洁，坏处是重传次数多。

选择重传协议（Selective Repeat Protocol, SR）是 GBN 的按需重传版本。即，发送方只重传那些它「认为」需要重传的数据包。

发送方与接收方均维护长度为 $N$ 的滑动窗口与序号的映射，双方根据 ACK 信号的收发进行同步（synchronization）。

发送方：

上一层调用 rdt_send()：同 GBN
收到 ACK n：若 n 在窗口内（[send_base, send_base+N-1]），将 n 标记为 ACKed（已确认）；若 n = send_base，向前移动 send_base 至当前尚未 ACKed 的最小序号处
超时：为减少重传次数，每个包都拥有各自的计时器（可以用一个硬件计时器模拟多个逻辑计时器）；超时后重传并重置计时器，收到 ACK 后停止计时器

接收方：

收到窗口内（[rcv_base, rcv_base+N-1]）的包 n 并成功校验：向发送方发送 ACK n，将其缓存并标记。若从基序号开始有一段连续的标记为已缓存的包（[rcv_base, rcv_base+k]），则按顺序一并交付，并向前移动 rcv_base 至当前尚未被缓存的最小序号处（rcv_base+k+1）
[*] 收到前一个窗口（[rcv_base-N, rcv_base-1]）的包 n 并成功校验：向发送方发送 ACK n
其余情况：忽略收到的包

[*] 的原因：考虑初始状态下发送方与接收方的窗口同步，均是 [k, k+N-1]

SR 中窗口大小 $N$ 与序号空间大小 $M=2^k$ 的关系：序号必须唯一标识窗口内的所有不同包以避免两个包模 $M$ 映射到同一序号。发送方与接收方的窗口完全错开时最多会有 $2N$ 个不同的数据包（见上），因此 $M\geq 2N$。