RDT：交替比特协议

如果要列出计网中的十大问题，可靠数据传输（Reliable Data Transfer, RDT）甚至有机会竞争榜首。RDT 能在应用层，传输层，与链路层中实现。

以渐进的方式发展出 RDT 机制。先作一些假设：

• 服务器-用户模型，且只考虑从用户向服务器的单向数据传输（unidirectional data transfer）
• 使用有限状态自动机（finite state machine, FSM）描述

rdt 1.0：完全可靠信道

横线上方：触发转移（transition）的事件；下方：事件发生时采取的行动

rdt 2.0：可能发生位错误的信道

发送方：

• 发送数据
• 在收到确认之前阻塞
  • 若收到确认（acknowledgements, ACKs），解除阻塞
  • 若收到否认（negative acknowledgements, NAKs），重传数据（retransmission）

确认与否认都是一个 1 比特的信号。

接收方：

• 接收数据
• 校验数据
  • 若校验成功，向接收方发送 ACK 信号
  • 若校验失败，向接收方发送 NAK 信号

rdt 2.1：一个修正

一个问题是：确认信号本身也有可能发生位错误！考虑重传（retransmission）修正：收到 garbled 的 ACK 或 NAK 信号时（注意，确认信号也是带校验和的，发送方能够检测其是否 corrupt），发送方直接重传一遍数据。

这又引出一个问题：接收方无法得知新收到的数据包是新数据包还是一次重传（因为它并不知道自己上次发送的确认信号是否在传输过程中 corrupt）。

为此在头中引入一个新字段，让发送方在其中填入序号（sequence number）；接收方只需要检测该序号就能判断收到的数据包是否为重传。

发送方：

在 stop-and-wait 模型中，只需要模二（modulo-2 arithmetic）序号 0/1 用于滚动区分前后两个数据包

接收方：

rdt 2.2：取消 NAK 信号

是 rdt 2.1 的等价模型，但是仅使用 ACK 信号 + 序号。

接收方：

• 总是发送最近一次校验成功数据包的序号：收到第 $n$ 个数据包时，若校验成功，发送 ACK + seq #$n$；否则发送 ACK + seq #$(n-1)$。

发送方：

• 若收到重复的 ACK + seq #$(n-1)$，得知数据包 $n$ 未发送成功，重传
• 否则继续传输第 $n+1$ 个数据包

（以上的序号 $n$ 均为模 2 意义下的）

rdt 3.0：可能发生丢包与位错误的信道

丢包如何处理？

发送方设置一个倒数计时器（countdown timer），每次发送一个包后重置并启动。若在指定的 timeout 后未收到 ACK 信号，触发重传。

• ACK 包丢了怎么办？=> 发送方重传，但由于序号的存在，接收方能够识别 duplication，再次 ACK 即可。

timeout 参数的设置很重要：

• 太短：并未丢包也可能触发重传，引发频繁的 duplication
• 太长：无法迅速处理丢包
• 一个 estimation：将 timeout 设置成发送方与接收方间的往返时延（round trip time, RTT）

Rdt 3.0 是一个完整的 RDT，被称为交替比特协议（alternating-bit protocol）。它的表现很差！主要的瓶颈是 stop-and-wait。