Chapter 3.2 Transport Layer 2

讲义 chap3-transport layer-2.pdf：PDF p1–36（页脚 1、3-2～3-42）

Chapter 3.1 Transport Layer 1 中的 UDP 只能检测差错，不能恢复；而 IP 提供的是尽力而为的服务，数据可能出错、丢失。本篇讨论怎样在这样不可靠的信道上实现可靠数据传输：先从理想信道开始，每次加入一种新的信道缺陷，再加入对应的机制，最后得到流水线协议 GBN 和 SR。这些机制是后面 TCP 可靠传输的基础。

协议	信道假设	新增机制
rdt1.0	完全可靠	无
rdt2.0	会翻转比特	校验和、ACK/NAK 反馈、重传
rdt2.1	同上，且 ACK/NAK 本身也可能出错	序号（0/1）
rdt2.2	同 rdt2.1	去掉 NAK，用带序号的 ACK 代替
rdt3.0	会出错，也会丢包	定时器、超时重传
GBN、SR	同 rdt3.0	流水线：允许多个未确认分组同时在途

3.4 可靠数据传输原理

可靠数据传输是网络中最重要的问题之一，不只出现在运输层，也出现在链路层和应用层。底层信道有哪些缺陷，决定了可靠数据传输协议（reliable data transfer protocol，rdt）需要多复杂。

3.4.1 问题设定与描述方法

对上层来说，可靠数据传输要提供的服务很简单：数据像通过一条可靠信道传送一样，不出错、不丢失，并按发送顺序交付。实际实现时，rdt 协议的发送端和接收端只能通过不可靠信道交换分组。

图中的四个接口：

接口	调用者	作用
rdt_send()	上层（如应用）	把数据交给 rdt 发送端，要求交付给接收方的上层
udt_send()	rdt	通过不可靠信道把分组发给对方
rdt_rcv()	信道	分组到达接收侧时被调用
deliver_data()	rdt	把数据交付给上层

下面逐步构造 rdt 的发送端和接收端，并作两点简化：

• 只考虑单向数据传输：数据从发送端流向接收端，但控制信息（如确认）双向流动。
• 用有限状态机描述发送端和接收端的行为。

定义：有限状态机（Finite State Machine，FSM）的记法

• 状态（圆圈）：处于某个状态时，下一个状态由下一个事件唯一确定。
• 转移（箭头）：标注写成分数形式，横线上方是引起转移的事件，下方是转移时执行的动作。
• 虚线箭头指向初始状态。
• $\Lambda$ 表示没有事件或不执行任何动作。

3.4.2 rdt1.0：可靠信道上的可靠传输

先假设底层信道完全可靠：不翻转比特，也不丢分组。此时发送端和接收端各只需一个状态：

• 发送端：收到上层数据，打包成分组，送入信道。
• 接收端：从信道取得分组，取出数据，交给上层。

3.4.3 rdt2.0：有比特差错的信道

现在假设信道可能翻转分组中的比特，但不丢分组。可以用校验和检测差错（§3.3.4）；问题是检测到差错后如何恢复。人在电话中听不清时会说“请再说一遍”，听清了会说“好的”，rdt2.0 采用同样的办法：

定义：肯定确认（ACK）与否定确认（NAK）

• ACK（acknowledgement）：接收方明确告诉发送方，分组已正确收到。
• NAK（negative acknowledgement）：接收方明确告诉发送方，分组有差错。

发送方收到 NAK 后重传该分组。

与 rdt1.0 相比，rdt2.0 新增了两种机制：

• 差错检测：分组携带校验和。
• 接收方反馈：从接收方发回发送方的控制消息 ACK、NAK。

发送端有两个状态：

• 在“等待上层调用”状态收到数据后，发送带校验和的分组，转入“等待 ACK 或 NAK”。
• 收到 NAK 就重传，仍然等待；收到 ACK 才回到“等待上层调用”。

接收端只有一个状态：分组正确则交付数据并回 ACK，分组损坏则回 NAK。

发送端发出一个分组后，必须等到接收方的响应才能发送下一个分组，在等待 ACK 或 NAK 时不接受上层的新数据。这种方式称为停等（stop-and-wait）。

rdt2.0 有一个致命缺陷：ACK、NAK 本身也可能在信道中出错。发送方收到损坏的 ACK/NAK 时，不知道接收方是否正确收到了分组：

• 不重传：若接收方收到的分组其实有错，数据就丢了。
• 直接重传：若接收方其实已经正确收到，重传的分组就成了重复分组，而接收方无法分辨它是新数据还是重复数据。

3.4.4 rdt2.1：处理受损的 ACK/NAK

解决办法是：ACK/NAK 受损时，发送方一律重传当前分组；同时给每个分组加上序号（sequence number），让接收方识别并丢弃重复分组（不交付给上层）。

停等协议中，发送方在当前分组被确认之前不会发新分组，所以接收方只需区分“刚才那个分组的重传”和“下一个新分组”。1 bit 的序号（0 和 1）就够了。

发送端的状态数是 rdt2.0 的两倍：状态要记住当前分组的序号是 0 还是 1。收到损坏的响应或 NAK 时重传当前分组；收到完好的 ACK 才转去发送下一个序号的分组。

接收端用状态记住期待的序号是 0 还是 1：

• 收到期待序号的完好分组：交付数据，回 ACK，转去期待另一个序号。
• 收到损坏分组：回 NAK。
• 收到完好但序号不对的分组（例如期待 1 却收到 0）：回 ACK，但不交付。

第三种情况说明，接收方之前已正确收到 0 号分组并回了 ACK，但这个 ACK 在途中损坏，发送方于是重传了 0 号分组。接收方必须再次回 ACK，发送方才能前进；如果回 NAK，发送方会一直重传 0 号分组。不交付是因为这份数据已经交付过。

rdt2.1 中，接收方无法知道自己发出的 ACK/NAK 是否被发送方正确收到。

3.4.5 rdt2.2：只用 ACK 的协议

NAK 可以用 ACK 代替：接收方不回 NAK，而是对最后一个正确收到的分组回 ACK。为此，ACK 必须带上被确认分组的序号。

发送方收到重复的 ACK（确认的仍是上一个分组，而不是当前分组）时，就知道当前分组没有被正确收到，采取与收到 NAK 相同的动作：重传当前分组。

图中只画了 FSM 的片段，与 rdt2.1 不同的部分标为红色：

• 发送端在等待 ACK0 时，收到损坏的分组或 ACK1，就重传当前分组。
• 接收端在等待 0 号分组时，收到损坏的分组或 1 号分组，就重发上一次的 ACK1。

TCP 也只使用 ACK，不使用 NAK。

3.4.6 rdt3.0：会出错也会丢包的信道

新的假设是：底层信道还可能丢失分组，包括数据分组和 ACK。校验和、序号、ACK 和重传都有用，但还不够：分组丢失后，发送方会一直等待一个永远不会到来的 ACK。

rdt3.0 让发送方等待一段“合理”的时间：

• 若在这段时间内没有收到 ACK，就重传当前分组。
• 若分组或 ACK 只是延迟了而没有丢失，重传会产生重复分组，但序号已经能处理重复。
• 接收方必须在 ACK 中注明被确认分组的序号，因为迟到的 ACK 可能确认的是更早的分组。

发送方无法区分分组丢失和延迟，只能用时间来判断，所以需要倒计时定时器（countdown timer）：每发出一个分组就启动定时器，收到正确的 ACK 时停止，超时则重传并重新启动。

与 rdt2.2 的发送端相比有两处不同：

• 等待 ACK 时收到损坏分组或错误序号的 ACK，不立即重传，而是什么也不做，等定时器超时后再重传。
• 在“等待上层调用”状态收到的分组（迟到或重复的 ACK）直接忽略。

接收端与 rdt2.2 相同。序号在 0、1 之间交替，所以 rdt3.0 也称交替位协议（alternating-bit protocol）。

下面三种情形中，发送方都能正常推进，接收方也不会重复交付：

• (a) 无丢失：每个分组发出后收到对应的 ACK，序号 0、1 交替。
• (b) 分组丢失：pkt1 丢失，接收方没有反应；发送方超时后重传 pkt1。
• (c) ACK 丢失：ack1 丢失，发送方超时重传 pkt1；接收方发现这是重复分组，丢弃它，但再次发送 ack1。

例子：定时器过早超时

若定时器设得太短，pkt1 和 ack1 都没有丢失，只是 ack1 还在路上，发送方就已超时重传了 pkt1：

1. 接收方收到重复的 pkt1，不交付，再回一个 ack1。
2. 发送方收到第一个 ack1，转而发送 pkt0，并在等待 ACK0 的状态下收到第二个 ack1。
3. 这个 ack1 的序号不对，发送方忽略它，继续等待 ACK0。

过早超时会造成不必要的重传，但借助序号，协议仍然正确。

3.4.7 rdt3.0 的性能

rdt3.0 能正确工作，但性能很差，原因在于停等：发送方每发完一个分组，都要空等一个 RTT。

定义：发送方利用率（Sender Utilization）

发送方实际忙于发送比特的时间占总时间的比例，记为 $U_{\text{sender}}$。设分组长度为 $L$（bit），链路速率为 $R$（bit/s），则发送一个分组的传输时延为 $L/R$。停等协议中，从开始发送一个分组到可以发送下一个分组，经过 $RTT+L/R$，因此

$$U_{\text{sender}}=\frac{L/R}{RTT+L/R}.$$

以 1 Gbps 链路、端到端传播时延 15 ms（RTT 为 30 ms）、1 KB 分组（$L=8000$ bit）为例：

$$\frac{L}{R}=\frac{8000\text{bit}}{10^9\text{bit/s}}=8\mu \text{s}=0.008\text{ms},U_{\text{sender}}=\frac{0.008}{30+0.008}\approx \mathrm{0.00027.}$$

每 30 ms 左右只能发出 1 KB，吞吐量约为 33 kB/s，而链路速率是 1 Gbps。协议本身限制了物理资源的利用。

3.4.8 流水线协议

既然瓶颈是空等，就让发送方在等待确认期间继续发送。

定义：流水线（Pipelining）

发送方允许多个已发送但尚未确认的分组同时“在途”（in-flight），而不是每发一个分组就等待其确认。

流水线带来两个要求：

• 序号范围必须增大：在途的多个分组需要各自不同的序号。
• 发送方和/或接收方需要缓存分组：发送方要保留未确认的分组以备重传，接收方可能要暂存失序到达的分组。

在一个 RTT 内连续发送 3 个分组，利用率提高到 3 倍：

$$U_{\text{sender}}=\frac{3L/R}{RTT+L/R}=\frac{0.024}{30.008}\approx \mathrm{0.0008.}$$

补充例题：要连续发送多少个分组，链路才不空闲？

沿用上面的参数。若发送方在一个 $RTT+L/R$ 的周期内连续发送 $N$ 个分组，则

$$U_{\text{sender}}=\frac{N\cdot L/R}{RTT+L/R}.$$

令 $U_{\text{sender}}=1$，得 $N=\frac{30.008}{0.008}\approx 3751$。也就是说，大约要有 3751 个分组同时在途，第一个分组的 ACK 返回时，发送方才刚好发完最后一个分组。

流水线协议出错时如何恢复有两种基本做法：回退 N 步（Go-Back-N，GBN）和选择重传（Selective Repeat，SR）。

3.4.9 回退 N 步（GBN）

GBN 让发送方最多有 $N$ 个未确认分组在途，接收方保持最简单：只接受按序到达的分组。出错时，发送方把从出错分组开始的所有在途分组全部重发。

定义：GBN 发送方

• 分组首部有 $k$ bit 的序号，序号范围为 $0\sim 2^k-1$，按模 $2^k$ 循环使用。
• 窗口：最多允许 $N$ 个连续的、已发送但未确认的分组。base 是最早的未确认分组的序号，nextseqnum 是下一个待发送分组的序号。
• 累积确认（cumulative ACK）：$\mathrm{ACK}(n)$ 确认序号不超过 $n$ 的所有分组。发送方可能收到重复的 ACK。
• 只为最早的已发送未确认分组设一个定时器。
• $\mathrm{timeout}(n)$：重传分组 $n$ 以及窗口中所有序号更大的已发送分组。

发送方眼中的序号空间分为四段：

序号范围	状态
$[0,\text{base}-1]$	已发送并已确认
$[\text{base},\text{nextseqnum}-1]$	已发送，尚未确认
$[\text{nextseqnum},\text{base}+N-1]$	可用，尚未发送
$\ge \text{base}+N$	不可用

窗口随确认到来向序号增大的方向滑动，因此 GBN 也称为滑动窗口协议（sliding-window protocol）。

定义：GBN 接收方

• 只发 ACK：对正确收到的分组，总是回复当前已按序收到的最大序号的 ACK。这可能产生重复 ACK。接收方只需记住下一个期待的序号 rcv_base（FSM 中的 expectedseqnum）。
• 收到失序分组时：可以丢弃（不缓存），也可以缓存，这由实现决定；同时重新确认已按序收到的最大序号。

下面的扩展 FSM 在 FSM 中加入了变量和类 C 的语句。发送端：

• 上层调用：窗口未满（nextseqnum < base+N）就发送新分组；若它是窗口中唯一的在途分组，启动定时器。窗口已满则拒绝数据（refuse_data），实际实现中可以缓存数据或用同步机制让上层稍后再交。
• 收到完好的 ACK：令 base = getacknum(rcvpkt)+1，窗口前移。若已没有在途分组则停止定时器，否则为新的最早未确认分组重启定时器。
• 超时：重启定时器，重传 base 到 nextseqnum-1 的全部分组。
• 收到损坏的 ACK：不动作。

接收端（采用丢弃失序分组的实现）：

• 收到序号等于 expectedseqnum 的完好分组：交付数据，发送该序号的 ACK，expectedseqnum 加 1。
• 其他情况（default）：重发上一次的 ACK，即已按序收到的最大序号。序号从 1 开始，所以初始的 sndpkt 是 ACK0。

丢弃失序分组看似浪费，但接收方只需维护 expectedseqnum 一个变量；反正发送方超时后会把这些分组重发一遍。

图中 $N=4$：

1. 发送方连续发出 pkt0～pkt3，pkt2 丢失。
2. 接收方收到 pkt0、pkt1 后分别回复 ack0、ack1；收到 pkt3 时它是失序分组，丢弃，并重发 ack1。
3. 发送方每收到一个 ACK，窗口前移一格，发送 pkt4、pkt5。接收方同样丢弃它们，重发 ack1；发送方忽略这些重复的 ACK。
4. pkt2 超时，发送方重传 pkt2～pkt5，接收方依次交付并确认。

一个分组丢失，就导致其后已经到达的 3 个分组也被重传。窗口大、时延长时，大量分组可能因此被不必要地重传。

3.4.10 选择重传（SR）

SR 针对 GBN 的问题，只重传那些真正出错或丢失的分组：

• 接收方逐个确认每个正确收到的分组，必要时缓存失序分组，等缺失的分组到齐后再按序交付给上层。
• 发送方只重传没有收到 ACK 的分组，每个未确认分组都有自己的定时器。
• 发送方窗口仍是 $N$ 个连续序号，限制已发送未确认分组的序号范围。

与 GBN 不同，SR 的发送窗口中，已确认的分组可以夹在未确认分组之间；接收方也有一个大小为 $N$ 的窗口，其中可能有已缓存并确认、但尚未交付的失序分组。

定义：SR 发送方与接收方的动作

发送方：

• 上层交来数据：若下一个可用序号在窗口内，就发送分组。
• $\mathrm{timeout}(n)$：重传分组 $n$，重启它的定时器。
• 收到 $\mathrm{ACK}(n)$，且 $n\in [\text{sendbase},\text{sendbase}+N-1]$：将分组 $n$ 标记为已收到。若 $n$ 是最小的未确认序号，窗口基序号前移到下一个未确认的序号。

接收方：

• 收到分组 $n\in [\text{rcvbase},\text{rcvbase}+N-1]$：发送 $\mathrm{ACK}(n)$。若是失序分组，缓存它；若是按序分组，交付它以及之后已缓存的连续分组，窗口前移到下一个尚未收到的序号。
• 收到分组 $n\in [\text{rcvbase}-N,\text{rcvbase}-1]$：仍然发送 $\mathrm{ACK}(n)$。
• 其他情况：忽略该分组。

接收方对已经交付过的分组仍要回 ACK，原因与 rdt2.1 中“回 ACK 但不交付”相同：之前的 ACK 可能丢了，发送方的窗口还停在那里，收不到这个 ACK 就会一直重传。

图中 $N=4$，红框是发送窗口，绿框是接收窗口：

1. 发送方发出 pkt0～pkt3，pkt2 丢失。
2. 接收方按序收到 pkt0、pkt1，交付并确认，接收窗口前移到 2～5；pkt3 到达后被缓存并确认。
3. 发送方收到 ack0、ack1，窗口前移，发出 pkt4、pkt5；接收方把它们也缓存起来并确认（图中省略了 ack3～ack5）。
4. pkt2 的定时器超时，发送方只重传 pkt2。接收方收到后，把 pkt2～pkt5 一起按序交付，接收窗口前移到 6～9。

比较项	GBN	SR
确认方式	累积确认	逐个确认
接收方对失序分组	通常丢弃	缓存
定时器	只为最早的未确认分组设一个	每个未确认分组一个
出错时重传	该分组及其后所有在途分组	只重传该分组
实现复杂度	接收方简单	双方都要维护窗口和缓存

补充例题：SR 的窗口不能太大

设序号只有 2 bit（0～3），窗口 $N=3$。发送方发出 pkt0、pkt1、pkt2，接收方全部正确收到并确认，接收窗口移到 $\{3,0,1\}$。

• 情形一：三个 ACK 全部丢失。发送方超时，重传旧的 pkt0。
• 情形二：三个 ACK 都到达，发送方发出 pkt3 和新的 pkt0，pkt3 丢失。

两种情形下，接收方看到的都是“序号 0 的分组到达”，而 0 正在它的窗口内。它无法分辨这是旧分组的重传，还是新的数据。情形一中，它会把旧数据当作新数据接收。

发送窗口和接收窗口加起来不能超过序号空间的大小，接收方才不会混淆新旧分组。SR 两个窗口都为 $N$，需要 $2N\le 2^k$，即

$$N\le 2^{k-1}.$$

GBN 的接收窗口为 1，只需 $N\le 2^k-1$。

3.4.11 机制小结

机制	解决的问题	引入于
校验和	检测比特差错	rdt2.0
ACK/NAK 反馈	让发送方知道分组是否正确收到	rdt2.0
重传	从差错和丢失中恢复	rdt2.0
序号	识别重复分组；确认指明对应哪个分组	rdt2.1、rdt2.2
定时器	发现分组或 ACK 丢失	rdt3.0
窗口与流水线	提高停等协议的利用率	GBN、SR
累积确认／逐个确认	流水线中如何确认、出错时重传多少	GBN／SR