Lesson 50: 可靠数据传输 — 停等协议（Stop-and-Wait）

练习任务

难度：中【标杆题】

在不可靠信道上实现可靠数据传输协议——停等协议（Stop-and-Wait）。真实网络（IP 层）只提供"尽力而为"服务：数据包可能丢失、损坏，ACK 也可能在回程中丢失。停等协议用"发一个包 → 等 ACK → 超时重传"的简单模型，在不可靠信道上保证可靠交付。

你需要完成 6 个核心任务：

log_event(num, tag, seq, data) — 事件日志格式化输出
sender_send() — 发送方发包（调用 log_event 记录 SEND）
sender_ack(ack_seq, arrived) — 发送方处理 ACK 或超时
receiver_recv(pkt_seq, data, ok, send_ack, ack_seq) — 接收方核心逻辑：检查损坏/序号匹配/重传
init() — 初始化随机种子 srand(42) 与全局变量
main() — 停等协议主循环与统计输出

channel()（信道模拟）和 ack_lost()（ACK 回程丢失模拟）已提供。msgs[4] 预置了 4 则消息： {"HELLO", "OpenCamp", "NCCL", "2026"}。

标准输出（srand(42) 固定种子）：

=== RDT Stop-and-Wait ===
Msgs: HELLO OpenCamp NCCL 2026
Loss=25% Corrupt=10% ACKloss=10%

[00] SEND  seq=0 "HELLO"
[01] RECV  seq=0 "HELLO"
[01] ACK   seq=0
[01] SEND  seq=1 "OpenCamp"
[02] RECV  seq=1 "OpenCamp"
[02] ACK   seq=1
[02] SEND  seq=0 "NCCL"
[03] LOST  seq=0
[03] SEND  seq=0 "NCCL"
[04] RECV  seq=0 "NCCL"
[04] ACK   seq=0
[04] SEND  seq=1 "2026"
[05] RECV  seq=1 "2026"
[05] ACK   seq=1

=== Stats ===
Delivered: 4/4
Sends: 5  Retrans: 1

提示：log_event 格式为 "[NN] TAG seq=N \"DATA\"\n"（TAG 占 5 列左对齐，data 为空时不输出双引号部分）。发送方的 sender_ack 中，只有 ack_seq == seq_snd 时才算序号正确（翻 seq）。接收方遇到损坏包不发 ACK，遇到序号不匹配（旧重传包）记录 DUPL 但重发 ACK。主循环中 LOST 后 continue 回到循环开头重传。

核心知识点

不可靠信道模型 — 真实 IP 层不保证送达：丢包、损坏、乱序均可能发生。停等协议用确认 + 重传机制屏蔽信道不可靠性
停等协议（Stop-and-Wait） — 发送方发一个包后停止，等待接收方 ACK 才发下一个。简单可靠，但信道利用率极低（RTT 远大于发送时间时，大部分时间在"等"）
有限状态机（FSM） — 发送方和接收方各自是一对状态的有限状态机。发送方在两个 seq 状态间交替；接收方在两个 seq_exp 状态间交替
1 比特序号空间 — 停等协议同一时刻信道中最多只有 1 个未确认包，0/1 交替足矣区分新包与重传包。GBN 或 SR 协议则需要更大的序号空间
ACK 确认与序列号匹配 — 接收方只交付 seq_exp 匹配的包，ACK 携带该序号。发送方只接受 ack_seq == seq_snd 的 ACK，忽略"迟到"的旧 ACK
超时重传 — 定时器超时（或模拟中 ACK 回程丢失）触发重传，这是可靠性的核心保障。本练习用 MAX_SENDS=30 做重传安全上限
幂等交付 — 接收方用序号保证每条消息只交付一次：重传的旧包（seq != seq_exp）记录 DUPL 但不交付，仅重发 ACK
确定性随机测试 — srand(42) 固定种子确保每次运行输出一致，使 make test 可通过管道 | diff 比对标准输出

代码框架

rdt_stop_wait.c

/* 50_rdt-stop-and-wait.c — 可靠数据传输：停等协议【标杆题】
 *
 * 任务：1. 实现 log_event()   — 日志格式化输出
 *       2. 实现 sender_send() — 发送方发包
 *       3. 实现 sender_ack()  — 发送方处理 ACK / 超时
 *       4. 实现 receiver_recv() — 接收方处理包
 *       5. 实现 init()        — 初始化随机种子和变量
 *       6. 补全 main()         — 停等协议主循环
 *
 * 背景：真实网络中，数据包可能丢失、损坏、乱序。停等协议
 *       (Stop-and-Wait) 是可靠传输的"Hello World" —
 *       发一个包，等一个 ACK，超时重传，序号 0/1 交替。
 *
 * 知识点：序号空间、超时重传、ACK 确认、不可靠信道模拟
 *
 * 验证：srand(42) 固定种子 → make test 比对 expected_output.txt
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MSG_COUNT 4      /* 待发送消息数量 */
#define MAX_MSG_LEN 16   /* 每则消息最大长度 */
#define LOSS_RATE 25     /* 丢包概率 (%) */
#define CORRUPT_RATE 10  /* 损坏概率 (%) */
#define ACK_LOSS_RATE 10 /* ACK 丢失概率 (%) */
#define MAX_SENDS 30     /* 最大发送次数（安全上限）*/

typedef enum { OK, LOST, CORRUPT } Outcome;

char msgs[MSG_COUNT][MAX_MSG_LEN] = {"HELLO", "OpenCamp", "NCCL", "2026"};
int msg_idx = 0;     /* 当前发送第几条消息 */
int seq_snd = 0;     /* 发送方的当前序号 (0 或 1) */
int seq_exp = 0;     /* 接收方期望的序号 (0 或 1) */
int send_count = 0;  /* 总发送次数（含重传）*/
int retrans_cnt = 0; /* 重传次数（丢包+损坏+ACK丢失均计入）*/
int deliv_cnt = 0;   /* 成功交付次数 */

/* ─── 信道模拟：返回包在信道中的命运 ─── */
static Outcome channel(void) {
    int r = rand() % 100;
    if (r < LOSS_RATE) return LOST;
    if (r < LOSS_RATE + CORRUPT_RATE) return CORRUPT;
    return OK;
}

/* ─── ACK 是否在返回途中丢失？ ─── */
static int ack_lost(void) { return (rand() % 100) < ACK_LOSS_RATE; }

/* ─── 日志输出 ─── */
static void log_event(int num, const char *tag, int seq, const char *data) {
    // TODO 1: 格式化输出 "[NN] TAG   seq=N \"DATA\"\n"
    // TAG 占 5 列左对齐 (%-5s)，data 为空时不输出双引号部分
    // 示例: "[03] SEND  seq=0 \"HELLO\"\n"
    //       "[03] LOST  seq=0\n"
}

/* ─── 发送方：发送当前消息 ─── */
static void sender_send(void) {
    // TODO 2: log_event(send_count, "SEND", seq_snd, msgs[msg_idx])
    // send_count++
}

/* ─── 发送方：处理 ACK (arrived=1) 或超时 (arrived=0) ─── */
static int sender_ack(int ack_seq, int arrived) {
    // TODO 3:
    // 若 arrived==0: log_event TOUT, retrans_cnt++, return 0
    // 若 arrived==1:
    //   log_event(send_count, "ACK", ack_seq, NULL)
    //   若 ack_seq == seq_snd: msg_idx++, seq_snd = 1 - seq_snd, return 1
    //   否则 return 0（旧 ACK，忽略）
}

/* ─── 接收方：处理收到的数据包 ─── */
static void receiver_recv(int pkt_seq, const char *data, int ok,
                          int *send_ack, int *ack_seq) {
    // TODO 4:
    // *send_ack = 0
    // 若 ok==0: log_event CORR, retrans_cnt++, return（不发 ACK）
    // 若 pkt_seq == seq_exp: log_event RECV, deliv_cnt++,
    //                         seq_exp = 1 - seq_exp, *send_ack = 1
    // 否则 (pkt_seq != seq_exp): log_event DUPL, *send_ack = 1
    // *ack_seq = pkt_seq
}

/* ─── 初始化 ─── */
static void init(void) {
    // TODO 5: srand(42), 所有全局变量置 0
}

/* ─── 主循环：停等协议 ─── */
int main(void) {
    init();

    // TODO 6:
    // 打印头部:
    //   === RDT Stop-and-Wait ===
    //   Msgs: HELLO OpenCamp NCCL 2026
    //   Loss=25% Corrupt=10% ACKloss=10%
    //   (空一行)
    //
    // while (msg_idx < MSG_COUNT && send_count < MAX_SENDS):
    //   ① sender_send()
    //   ② oc = channel()
    //   ③ if (oc == LOST): log_event LOST, retrans_cnt++, continue
    //   ④ receiver_recv(seq_snd, msgs[msg_idx], oc==OK, &send_ack, &ack_seq)
    //   ⑤ if (send_ack):
    //        ack_arrived = !ack_lost()
    //        if (!ack_arrived): log_event ACK-L, retrans_cnt++, continue
    //        sender_ack(ack_seq, 1)
    //
    // 打印统计:
    //   printf("\n=== Stats ===\n");
    //   printf("Delivered: %d/%d\n", deliv_cnt, MSG_COUNT);
    //   printf("Sends: %d  Retrans: %d\n", send_count, retrans_cnt);

    return 0;
}

TIP

先在纸上用 srand(42) 完整追踪一遍 channel() 的返回值序列。理解每一步是丢包、损坏还是正常到达，再对照预期输出逐行校对。核心要抓住四个判断条件：① 接收方 ok==0 不发 ACK；② 接收方 seq ≠ seq_exp 不交付但回 ACK；③ 发送方 ack_seq ≠ seq_snd 忽略旧 ACK；④ ACK 回程丢失等同于超时。

深度讲解

1. 不可靠信道模型——为什么需要可靠传输？

1.1 真实网络的服务原语

IP 层提供的是**尽力而为（best-effort）**服务——不保证数据包一定到达，不保证按序到达，不保证不重复。应用层需要的数据传输语义（可靠、有序、不重复）必须在传输层（如 TCP）或应用层自己实现。

发送方                                 接收方
  │                                     │
  ├──[Pkt]──→  ✗ 丢失                    │   ← 路由器队列满，Tail Drop
  │                                     │
  ├──[Pkt]──→  ⚡损坏                    │   ← 电磁干扰，比特翻转
  │                                     │
  ├──[Pkt]───────────────────────────────→│   ✓ 正常到达
  │            ←──[ACK]── ✗ 丢失         │   ← ACK 回程同样走不可靠信道
  │                                     │

1.2 本练习的信道模拟参数

参数	值	含义	对应的 `rand()%100` 区间
LOSS_RATE	25%	数据包在信道中丢失的概率	[0, 24]
CORRUPT_RATE	10%	数据包到达但内容损坏的概率	[25, 34]
ACK_LOSS_RATE	10%	ACK 在返回途中丢失的概率	[0, 9]
OK	65%	正常到达的概率 (100% - 25% - 10%)	[35, 99]

channel_model.c

/* 信道模拟：三种命运的判定 */
static Outcome channel(void) {
    int r = rand() % 100;        /* r ∈ [0, 99] */
    if (r < LOSS_RATE)                     /* r ∈ [0, 24]  → LOST   25% */
        return LOST;
    if (r < LOSS_RATE + CORRUPT_RATE)      /* r ∈ [25, 34] → CORRUPT 10% */
        return CORRUPT;
    return OK;                             /* r ∈ [35, 99] → OK     65% */
}

大数定律的依赖：这里用的是简单的均匀分布。在真实场景中，丢包往往是突发性的（burst loss），而非均匀独立。但均匀模型足够演示协议的核心逻辑。

NOTE

srand(42) 是固定种子——保证每次运行 rand() 序列完全相同。这是自动化测试的基础：如果协议逻辑正确，输出必定匹配 expected_output.txt。如果每次运行结果随机，就无法用 diff 验证。

2. 有限状态机——协议的形式化描述

2.1 发送方 FSM

发送方有两个状态，按 seq_snd ∈ {0, 1} 区分：

                      ┌─────────────────────────────────┐
                      │         等待 ACK (seq_snd)       │
                      │                                 │
          ┌───────────┤  ┌─ ACK 到达、序号正确 ──→ seq 翻转, 推进消息
          │           │  ├─ ACK 丢失/超时 ──→ 重传
          │           │  └─ ACK 序号错 ──→ 忽略
          │           │                                 │
          ▼           └─────────────────────────────────┘
    ┌──────────┐                                         │
    │ 从应用层 │                                         │
    │ 取下一则 │                                         │
    └────┬─────┘                                         │
         │ seq_snd = 0                                   │
         ▼                                               │
    ┌──────────┐                                         │
    │  发包    │  seq_snd = 1 ────────────────────────────┘
    │ 启动定时   │
    └───────────┘

关键状态变量：

seq_snd：发送方当前使用的序号（0 或 1），每次成功收到 ACK 后翻转
msg_idx：当前发送的是第几则消息（0..MSG_COUNT-1）
send_count：总发送次数（含重传），也用作事件编号

2.2 接收方 FSM

接收方同样有两个状态，按 seq_exp ∈ {0, 1} 区分：

    ┌───────────────┐            ┌───────────────┐
    │  等待 seq=0   │            │  等待 seq=1   │
    │  seq_exp = 0  │            │  seq_exp = 1  │
    └───────┬───────┘            └───────┬───────┘
            │                            │
            │ pkt 到达                   │ pkt 到达
            ▼                            ▼
    ┌───────────────┐            ┌───────────────┐
    │  检查序号      │            │  检查序号      │
    └───┬───┬───────┘            └───┬───┬───────┘
  匹配  │   │ 不匹配           匹配  │   │ 不匹配
  ┌─────┘   └─────┐          ┌─────┘   └─────┐
  ▼               ▼          ▼               ▼
交付+ACK         重发ACK    交付+ACK         重发ACK
seq_exp ↦ 1            seq_exp ↦ 0

接收方四种输入的完整处理：

`ok`	`pkt_seq == seq_exp`	事件	动作
`false`	—	CORRUPT	记录 CORR，不发 ACK
`true`	`true`	匹配	记录 RECV，`deliv_cnt++`，翻转 `seq_exp`，发 ACK
`true`	`false`	重传	记录 DUPL，重发 ACK（不重复交付）

IMPORTANT

为什么重传的旧包也要回 ACK？因为发送方上次发的 ACK 可能在回程丢失了。如果接收方不给重传包回应，发送方会不断超时重传，直到 MAX_SENDS 上限触发。重发 ACK 确保发送方能尽快推进到下一条消息。

3. 序号空间——1 比特为什么够？

3.1 滑动窗口与序号空间的关系

序号空间的大小取决于正在信道中"飞行"的未确认包数量（窗口大小）：

┌──────────────────────────────────────────────────────────┐
│  协议         │ 窗口大小   │ 所需最小序号空间  │ 序号位数 │
t]───────────────┼────────────┼──────────────────┤──────────│
│  Stop-and-Wait│ 1          │ 2 (0 和 1)       │ 1 bit    │
│  Go-Back-N   │ N (如 8)   │ N+1 (如 9)       │ 4 bits   │
│  Selective Rpt│ N          │ 2N               │ ≥ log₂(2N)│
└──────────────────────────────────────────────────────────┘

停等协议窗口 = 1 的证明：

时间 →
SEND(seq=0) ────→ 等待 ACK=0 ────→ 收到 ACK → SEND(seq=1) ────→ ...
                 │
                 ├ 若超时: 重传 seq=0（同一包）
                 ├ 若收到 ACK=1: 忽略！（旧 ACK）
                 └ 若收到 ACK=0: 正确！翻 seq 为 1

任何时候信道上最多只有一个未确认的包：
  正在飞的是 seq=K → 接收方期望 seq_exp=K
  发送方等待的是 ACK=K
  
  不可能同时有两个包在飞，因为发完第一个后必须等 ACK 才发第二个。

3.2 如果不用序号会怎样？

错误场景：发送方连续发 3 个包，接收方按序交付

发送方: [Pkt A] [Pkt B] [Pkt C]
接收方:    ↓       ↓       ↓
         交付A   交付B   交付C  ✓ 看起来正常...

但网络不可靠：
发送方: [Pkt A] [Pkt B] [Pkt A 重传]
接收方:    ↓       ✗         ↓
         交付A   丢失      交付A  ← 重复交付 A！✗

没有序号，接收方无法区分"新包 A"和"重传的旧包 A"。
序号的作用：让接收方说"我等的是 B，A 我已经收过了"。

WARNING

初学常见误区：以为"序号就是包编号"（即 0, 1, 2, 3...）。递增序号在停等协议中是多余的——因为一次只有一个包在飞，只需要一个比特就能区分"这次是新包"还是"这次的重传"。本练习用 0/1 交替正是最小化的正确设计。

4. 核心函数逐一分析

4.1 `log_event()` — 格式化日志

log_event_format.c

/* 格式说明：
 * "[NN] TAG   seq=N \"DATA\"\n"
 *  ├── 2 位编号，不足补 0
 *  ├── TAG 占 5 列左对齐（%-5s）
 *  ├── seq 固定为 1 位数字
 *  └── data 不为 NULL 时输出 \"DATA\"
 *
 * 示例：
 *   log_event(0,  "SEND", 0, "HELLO")
 *     → "[00] SEND  seq=0 \"HELLO\"\n"
 *   log_event(3,  "LOST", 0, NULL)
 *     → "[03] LOST  seq=0\n"
 *   log_event(1,  "ACK",  0, NULL)
 *     → "[01] ACK   seq=0\n"
 */
static void log_event(int num, const char *tag, int seq, const char *data) {
    printf("[%02d] %-5s seq=%d", num, tag, seq);
    if (data)
        printf(" \"%s\"", data);
    printf("\n");
}

NOTE

%-5s 是 printf 的格式说明——左对齐、最少占 5 列。这保证了 "SEND" 和 "LOST" 等不同长度的 TAG 在输出中对齐。%02d 确保事件编号始终 2 位补 0。

4.2 `sender_send()` — 发包

sender_send_logic.c

static void sender_send(void) {
    log_event(send_count, "SEND", seq_snd, msgs[msg_idx]);
    send_count++;
}

关键观察：log_event 使用当前 send_count 作为事件编号，然后递增。这意味着：

第一次调用：send_count=0 → 输出 [00] SEND ... → send_count=1
后续所有操作（RECV、ACK）使用 send_count=1 → 输出 [01] RECV ... 等
第二次 SEND：send_count=1 → 输出 [01] SEND ... → send_count=2

这就是为什么 [01] 号事件可以有 RECV、ACK、SEND 三条日志——它们发生在同一轮中。

4.3 `sender_ack()` — 处理确认

sender_ack_logic.c

static int sender_ack(int ack_seq, int arrived) {
    if (!arrived) {
        /* 超时：定时器到期，ACK 没来 */
        log_event(send_count, "TOUT", seq_snd, NULL);
        retrans_cnt++;
        return 0;  /* 当前消息未完成，主循环会重传 */
    }

    /* ACK 到达 */
    log_event(send_count, "ACK", ack_seq, NULL);

    if (ack_seq == seq_snd) {
        /* 序号正确 → 确认当前消息，翻序号，推进 */
        msg_idx++;
        seq_snd = 1 - seq_snd;  /* 翻转: 0↔1 */
        return 1;                /* 当前消息完成 */
    }

    /* 序号不匹配 → 旧 ACK 重放，忽略 */
    return 0;
}

1 - seq_snd 的优雅翻转：

seq_snd = 0 → 1 - 0 = 1
seq_snd = 1 → 1 - 1 = 0
比 seq_snd = (seq_snd + 1) % 2 更简洁，无分支。

旧 ACK 重放问题：ACK 可能在网络中延迟太久，等发送方已经发下一个包了才到达。如果不检查 ack_seq == seq_snd，发送方可能错误地确认了当前包，导致 seq 错乱。

4.4 `receiver_recv()` — 接收方核心

receiver_recv_logic.c

static void receiver_recv(int pkt_seq, const char *data, int ok,
                          int *send_ack, int *ack_seq) {
    *send_ack = 0;  /* 默认不坏和 ACK */

    if (!ok) {
        /* 包损坏 → 记录，不发 ACK（无法确认损坏的内容） */
        log_event(send_count, "CORR", pkt_seq, NULL);
        retrans_cnt++;
        return;
    }

    if (pkt_seq == seq_exp) {
        /* 序号匹配 → 是新包！交付 */
        log_event(send_count, "RECV", pkt_seq, data);
        deliv_cnt++;
        seq_exp = 1 - seq_exp;  /* 翻期望序号: 0↔1 */
        *send_ack = 1;
    } else {
        /* 序号不匹配 → 重传的旧包，不交付但重发 ACK */
        log_event(send_count, "DUPL", pkt_seq, data);
        *send_ack = 1;
    }

    *ack_seq = pkt_seq;  /* ACK 携带收到包的序号 */
}

接收方的三种日志事件：

条件	事件	含义
`ok == false`	`CORR`	包损坏，数据不可用，不发 ACK
`ok && pkt_seq == seq_exp`	`RECV`	新包正确到达，交付 + 翻 `seq_exp`
`ok && pkt_seq != seq_exp`	`DUPL`	旧包重传，不交付但重发 ACK

为什么不交付重传包？ 因为该消息在第一次正确接收时已经交付过了。重复交付会破坏上层应用的语义（如同一则短信收到两次）。

4.5 `main()` — 主循环

main_loop_logic.c

int main(void) {
    init();

    /* 打印头部 */
    printf("=== RDT Stop-and-Wait ===\n");
    printf("Msgs: HELLO OpenCamp NCCL 2026\n");
    printf("Loss=%d%% Corrupt=%d%% ACKloss=%d%%\n\n",
           LOSS_RATE, CORRUPT_RATE, ACK_LOSS_RATE);

    int send_ack, ack_seq;

    while (msg_idx < MSG_COUNT && send_count < MAX_SENDS) {
        /* ① 发送方发包 */
        sender_send();

        /* ② 模拟信道 */
        Outcome oc = channel();

        /* ③ 丢包处理 */
        if (oc == LOST) {
            log_event(send_count, "LOST", seq_snd, NULL);
            retrans_cnt++;
            continue;  /* 跳过接收方，回到循环开头重传 */
        }

        /* ④ 接收方处理 */
        receiver_recv(seq_snd, msgs[msg_idx], oc == OK,
                      &send_ack, &ack_seq);

        /* ⑤ ACK 回程模拟 + 发送方处理 */
        if (send_ack) {
            int ack_arrived = !ack_lost();
            if (!ack_arrived) {
                log_event(send_count, "ACK-L", ack_seq, NULL);
                retrans_cnt++;
                continue;  /* ACK 丢失，回到循环开头重传 */
            }
            sender_ack(ack_seq, 1);
        }
    }

    /* 统计输出 */
    printf("\n=== Stats ===\n");
    printf("Delivered: %d/%d\n", deliv_cnt, MSG_COUNT);
    printf("Sends: %d  Retrans: %d\n", send_count, retrans_cnt);

    return 0;
}

主循环的两种 continue 路径：

数据包丢失 → LOST 日志 + retrans_cnt++ + continue → 重传
ACK 回程丢失 → ACK-L 日志 + retrans_cnt++ + continue → 重传

两种路径都回到循环顶部的 sender_send() 重传同一个包。

5. 完整逐轮追踪（srand(42)）

以 srand(42) 固定种子，追踪完整协议运行过程：

═══════════════════════════════════════════════════════════
Round [00] — 发送 HELLO (seq=0)
════════════════════════════════════════════════════════════════
  send_count=0
  sender_send()      → [00] SEND  seq=0 "HELLO"    send_count=1
  channel()          → 判定: OK
  receiver_recv()    → [01] RECV  seq=0 "HELLO"     deliv_cnt=1, seq_exp=1
  ACK 回程判定       → ack_lost()=0 (到达)
  sender_ack(0,1)    → [01] ACK   seq=0             seq_snd=1, msg_idx=1

═══════════════════════════════════════════════════════════
Round [01] — 发送 OpenCamp (seq=1)
═══════════════════════════════════════════════════════════
  sender_send()      → [01] SEND  seq=1 "OpenCamp"   send_count=2
  channel()          → OK
  receiver_recv()    → [02] RECV  seq=1 "OpenCamp"   deliv_cnt=2, seq_exp=0
  ACK 到达
  sender_ack(1,1)    → [02] ACK   seq=1             seq_snd=0, msg_idx=2

═══════════════════════════════════════════════════════════
Round [02] — 发送 NCCL (seq=0)
═══════════════════════════════════════════════════════════
  sender_send()      → [02] SEND  seq=0 "NCCL"       send_count=3
  channel()          → LOST ← 包丢失！
  log_event LOST     → [03] LOST  seq=0              retrans_cnt=1
  continue ──→ 回到循环顶部重传

═══════════════════════════════════════════════════════════
Round [03] — 重传 NCCL (seq=0)
═══════════════════════════════════════════════════════════
  sender_send()      → [03] SEND  seq=0 "NCCL"       send_count=4
  channel()          → OK
  receiver_recv()    → [04] RECV  seq=0 "NCCL"       deliv_cnt=3, seq_exp=1
  ACK 到达
  sender_ack(0,1)    → [04] ACK   seq=0             seq_snd=1, msg_idx=3

═══════════════════════════════════════════════════════════
Round [04] — 发送 2026 (seq=1)
═══════════════════════════════════════════════════════════
  sender_send()      → [04] SEND  seq=1 "2026"       send_count=5
  channel()          → OK
  receiver_recv()    → [05] RECV  seq=1 "2026"       deliv_cnt=4, seq_exp=0
  ACK 到达
  sender_ack(1,1)    → [05] ACK   seq=1

═══════════════════════════════════════════════════════════
  msg_idx=4 = MSG_COUNT → 循环结束
  Stats: Delivered: 4/4  Sends: 5  Retrans: 1
═══════════════════════════════════════════════════════════

IMPORTANT

retrans_cnt 统计了 1 次——来自 LOST 事件。注意 send_count=5（含 1 次重传），deliv_cnt=4（全部成功交付）。srand(42) 使得这次运行恰好出现 1 次丢包，完美展示了协议的重传机制。

6. 常见陷阱与正确做法

错误	症状	根因	正确做法
接收方收到所有包都交付	重复交付	不检查 `pkt_seq == seq_exp`	用 seq_exp 过滤，只交付序号号匹配的包
ACK 不检查序号	seq 错乱，消息被跳过	旧 ACK 可能被当成新 ACK	`if (ack_seq == seq_snd)` 检查
CORRUPT 时还发 ACK	发送方以为成功了	损坏的包不应确认	`ok==0` 时 `*send_ack=0` → return
sender_ack 中忘翻 seq	序号永远是 0，全被当重传	帧里漏了 `seq_snd = 1 - seq_snd`	成功确认后翻 seq
ACK 丢失时误推进 msg_idx	消息被跳过，少了消息	ACK 丢失 ≠ ACK 到达	`arrived==0` 时不推进 msg_idx，不翻 seq
LOST 后不 `continue`	丢包后继续执行接收方逻辑	丢了但代码还去"接收"	`continue` 跳过接收方，回到循环开头重传
`send_count` 作为编号用错	事件编号不连续或重复	混淆了"发送前"和"发送后"的 send_count	`log_event` 用当前值，之后 `send_count++`

参考解答

完整实现：rdt_stop_wait.c（通过 make test）

solution_rdt_stop_wait.c

/* 50_rdt-stop-and-wait.c — 可靠数据传输：停等协议【标杆题】
 *
 * 停等协议：发一个包 → 等 ACK → 超时重传 → 序号 0/1 交替。
 * srand(42) 固定种子，make test 比对 expected_output.txt。
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MSG_COUNT 4
#define MAX_MSG_LEN 16
#define LOSS_RATE 25
#define CORRUPT_RATE 10
#define ACK_LOSS_RATE 10
#define MAX_SENDS 30

typedef enum { OK, LOST, CORRUPT } Outcome;

char msgs[MSG_COUNT][MAX_MSG_LEN] = {"HELLO", "OpenCamp", "NCCL", "2026"};
int msg_idx = 0;
int seq_snd = 0;
int seq_exp = 0;
int send_count = 0;
int retrans_cnt = 0;
int deliv_cnt = 0;

static Outcome channel(void) {
    int r = rand() % 100;
    if (r < LOSS_RATE) return LOST;
    if (r < LOSS_RATE + CORRUPT_RATE) return CORRUPT;
    return OK;
}

static int ack_lost(void) {
    return (rand() % 100) < ACK_LOSS_RATE;
}

/* ─── TODO 1: 日志格式化输出 ─── */
static void log_event(int num, const char *tag, int seq, const char *data) {
    printf("[%02d] %-5s seq=%d", num, tag, seq);
    if (data)
        printf(" \"%s\"", data);
    printf("\n");
}

/* ─── TODO 2: 发送方发包 ─── */
static void sender_send(void) {
    log_event(send_count, "SEND", seq_snd, msgs[msg_idx]);
    send_count++;
}

/* ─── TODO 3: 发送方处理 ACK 或超时 ─── */
static int sender_ack(int ack_seq, int arrived) {
    if (!arrived) {
        log_event(send_count, "TOUT", seq_snd, NULL);
        retrans_cnt++;
        return 0;
    }
    log_event(send_count, "ACK", ack_seq, NULL);
    if (ack_seq == seq_snd) {
        msg_idx++;
        seq_snd = 1 - seq_snd;
        return 1;
    }
    return 0;
}

/* ─── TODO 4: 接收方处理包 ─── */
static void receiver_recv(int pkt_seq, const char *data, int ok,
                          int *send_ack, int *ack_seq) {
    *send_ack = 0;
    if (!ok) {
        log_event(send_count, "CORR", pkt_seq, NULL);
        retrans_cnt++;
        return;
    }
    if (pkt_seq == seq_exp) {
        log_event(send_count, "RECV", pkt_seq, data);
        deliv_cnt++;
        seq_exp = 1 - seq_exp;
        *send_ack = 1;
    } else {
        log_event(send_count, "DUPL", pkt_seq, data);
        *send_ack = 1;
    }
    *ack_seq = pkt_seq;
}

/* ─── TODO 5: 初始化 ─── */
static void init(void) {
    srand(42);
    msg_idx = 0;
    seq_snd = 0;
    seq_exp = 0;
    send_count = 0;
    retrans_cnt = 0;
    deliv_cnt = 0;
}

/* ─── TODO 6: 停等协议主循环 ─── */
int main(void) {
    init();

    printf("=== RDT Stop-and-Wait ===\n");
    printf("Msgs: HELLO OpenCamp NCCL 2026\n");
    printf("Loss=%d%% Corrupt=%d%% ACKloss=%d%%\n\n",
           LOSS_RATE, CORRUPT_RATE, ACK_LOSS_RATE);

    int send_ack, ack_seq;

    while (msg_idx < MSG_COUNT && send_count < MAX_SENDS) {
        sender_send();

        Outcome oc = channel();

        if (oc == LOST) {
            log_event(send_count, "LOST", seq_snd, NULL);
            retrans_cnt++;
            continue;
        }

        receiver_recv(seq_snd, msgs[msg_idx], oc == OK,
                      &send_ack, &ack_seq);

        if (send_ack) {
            int ack_arrived = !ack_lost();
            if (!ack_arrived) {
                log_event(send_count, "ACK-L", ack_seq, NULL);
                retrans_cnt++;
                continue;
            }
            sender_ack(ack_seq, 1);
        }
    }

    printf("\n=== Stats ===\n");
    printf("Delivered: %d/%d\n", deliv_cnt, MSG_COUNT);
    printf("Sends: %d  Retrans: %d\n", send_count, retrans_cnt);

    return 0;
}

核心逻辑回顾：

log_event：%02d 补零编号，%-5s 左对齐 TAG，data 为 NULL 时跳过双引号部分
sender_send：用当前 send_count 记录事件，再递增——保证同轮事件共享编号
sender_ack：arrived==0 记录 TOUT 不推进；ack_seq == seq_snd 才推进消息并翻 seq
receiver_recv：损坏不发 ACK；匹配则交付+翻 seq_exp；不匹配（重传）发 ACK 但不交付
主循环：LOST → continue 重传；ACK 丢失（ACK-L）→ continue 重传；正常走完一条消息的 receive+ack 流程

对照检查：log_event 中 data 为 NULL 时不输出双引号部分了吗？sender_ack 中 ack_seq == seq_snd 的条件写对了吗？receiver_recv 中 ok==0 分支设置了 *send_ack=0 吗？主循环中 LOST 和 ACK-L 分支都写了 continue 吗？

课堂讨论

停等协议的信道利用率有多低？为什么还要学？
如果发送方和接收方的初始 seq 不同会怎样？需要握手吗？
为什么序号不需要更多比特？1 比特真的永远够用吗？
如果 ACK 永远不来，协议会怎样？
真实 TCP 的可靠传输与本模拟的核心差异是什么？
如果信道模拟参数改得极端（如 80% 丢包），协议还能正常工作吗？

讨论答案

Q1: 停等协议的信道利用率有多低？为什么还要学？

设 RTT = 30ms，包大小 = 1KB，带宽 = 1Gbps：

发送 1KB 时间 = 8K bits / 1Gbps = 8μs
等待 ACK 时间 = RTT = 30ms
信道利用率 = 8μs / 30ms ≈ 0.027%

99.97% 的时间信道空闲——都在"等"。

那为什么还要学？

概念基础：停等协议是理解所有可靠传输协议的起点。ACK、序号、超时、重传——这些概念在 TCP、QUIC 中依然核心
极简设计：停等协议的状态机只有 2 个状态，是验证协议正确性的最小模型
短 RTT 场景仍有价值：DDR 内存控制器、芯片内部总线——RTT 极短时停等协议的效率是可接受的
教学载体：理解"窗口大小决定序号空间需求"这一深刻关系——从停等（窗口=1）自然延伸到滑动窗口

Q2: 如果发送方和接收方的初始 seq 不同会怎样？

假设发送方从 seq_snd=0 开始，但接收方从 seq_exp=1 开始（不一致）：

发送方: [00] SEND seq=0 "HELLO"
接收方: seq_exp=1, pkt_seq=0 → 不匹配 → DUPL！→ 不交付！

这是死锁：
  - 接收方永远等 seq=1
  - 发送方永远发 seq=0
  - 消息永远无法交付

解决方案：握手（Handshake）

TCP 用三次握手同步初始序号（ISN）：

Client                           Server
  │── SYN seq=x ──────────────────→│
  │←─ SYN+ACK seq=y, ack=x+1 ────│
  │── ACK seq=x+1, ack=y+1 ───[Pkt]──→│

握手后: Client 的 seq_snd = x+1, Server 的 seq_exp = x+1 → 同步完成

本练习简化了这一步——默认双方初始序号都是 0。在实际实现中，TCP 选择随机 ISN 是为了防止旧连接的数据包干扰新连接。

Q3: 1 比特序号真的永远够用吗？

传包（停等协议的场景下——是的。

证明的边界条件：

停等协议同一时刻只有 1 个包在信道中
用 1 比特序号 → 两个可能值
接收方只需区分"这是新包 (seq ≠ 上一次)"还是"这是重传 (seq = 上一次)"

如果窗口扩大到 N（Go-Back-N），就需要至少 N+1 个序号。因为：

假设窗口=4，序号空间={0,1,2,3}（2 比特）：
  发送方同时发了 seq=0,1,2,3
  接收方全部收到，发 ACK 0,1,2,3
  但 ACK 全部丢失！
  发送方超时重传 seq=0,1,2,3
  接收方看到的 seq=0 是"新批次的第一包"还是"那批次的重传"？
  序号空间=4, 窗口=4 → 无法区分！（这就是著名的问题）
  
解决方法：序号空间 ≥ 窗口+1，即 {0,1,2,3,4} → 3 比特

停等协议中窗口=1，序号空间=2=窗口+1，天然满足。

停等 → GBN → 选择性重传的演进，核心之一就是"序号空间管理"日益复杂。停等协议让你在最简环境下理解这个基本约束。

Q4: 如果 ACK 永远不来，协议会怎样？

协议会不断超时重传，直到 send_count >= MAX_SENDS=30：

[00] SEND  seq=0 "HELLO"
[01] LOST  seq=0        ← 包丢了
[01] SEND  seq=0 "HELLO" ← 重传 1
[02] TOUT  seq=0        ← ACK 丢了
[02] SEND  seq=0 "HELLO" ← 重传 2
...
[29] TOUT  seq=0
[29] SEND  seq=0 "HELLO" ← 重传 29
→ send_count=30 ≥ MAX_SENDS → 循环退出
→ 输出: Delivered: 0/4 ← 全部失败

真实协议的处理：

TCP 有指数退避（exponential backoff）：第一次超时 1s，第二次 2s，第三次 4s...
超过最大重传次数后 TCP 关闭连接（connection reset）
MAX_SENDS=30 是本练习的安全上限，防止死循环

NOTE

本练习用了 send_count 做双重用途：事件编号 + 重传上限。这使得 [00] 到 [29] 恰好 30 次发送。如果 msg_idx < MSG_COUNT 但 send_count >= MAX_SENDS，意味着协议失败——消息未全部交付。

Q5: 真实 TCP 与本模拟的核心差异

维度	本模拟（停等协议）	真实 TCP
窗口大小	1（停等）	动态滑动窗口（如 64KB）
ACK 类型	每包单 ACK	累计 ACK（ack 第 N 个 = 前 N-1 个都收到了）
序号空间	1 bit（0/1）	32 bits（~4GB 范围）
重传触发	单一定时器	超时 + 快速重传（3 个重复 ACK）
流控	无（停等天然限速）	滑动窗口 + 接收方通告窗口（rwnd）
拥塞控制	无	慢启动、拥塞避免、快速恢复（cwnd）
握手	无（默认 seq 同步）	三次握手 + 四次挥手
校验	无（模拟 CORRUPT）	16 位 checksum
面向连接	不显式管理	连接建立/数据传输/连接释放

核心差异的本质：停等协议只解决了正确性（不丢、不错、不乱），TCP 在此基础上解决了效率（流水线、批量确认、自适应窗口）。

Q6: 极端参数下协议还能工作吗？

设 LOSS_RATE=80, CORRUPT_RATE=0, ACK_LOSS_RATE=0，srand(42)：

channel() 判定: r ∈ [0,79] → LOST, r ∈ [80,99] → OK
→ 平均每 5 次尝试才有 1 次到达

协议仍能正常工作——只是慢：
  [00] SEND  seq=0 "HELLO"
  [01] LOST  seq=0
  [01] SEND  seq=0 "HELLO"  (重传)
  [02] LOST  seq=0
  [02] SEND  seq=0 "HELLO"  (重传)
  ...（可能重传 N 次）...
  [NN] RECV  seq=0 "HELLO"  ← 终于到达！

只要满足两个条件，协议就能完成：

MAX_SENDS 足够大（容忍足够多重传）
信道不是"完全断开"（OK 概率 > 0）

停等协议的正确性不依赖信道的可靠性程度——即使 99% 丢包，只要偶尔有一个包能通过，协议最终会成功。这正是"可靠"二字的含义：在不可靠信道上保证可靠。

但极端参数下 send_count 可能很快触及 MAX_SENDS=30——修改 MAX_SENDS 为更大值（如 1000）可以测试协议的"韧性"。

课后练习

波形重传实验。修改 MAX_SENDS 为 200，将 LOSS_RATE 设为 80%，CORRUPT_RATE 和 ACK_LOSS_RATE 设为 0。运行程序，统计重传次数和总发送次数。分析重传次数与理论值 4 × (1/0.2) = 20 次期望的偏差。
知识点提示：在 80% 丢包率下，每次传输成功的概率为 20%。4 则消息的期望发送次数 = 4/0.2 = 20。srand(42) 下实际值可能偏离期望，因为伪随机序列不是真正的独立均匀分布。
参考解答
ex1_request_retry.c
c
```
/* 修改 #define 参数后运行：
 * #define LOSS_RATE 80
 * #define CORRUPT_RATE 0
 * #define ACK_LOSS_RATE 0
 * #define MAX_SENDS 200
 *
 * 输出分析：
 *   Sends 值 ≈ 20（接近理论期望 20）
 *   Retrans 值 = Sends - 4
 *   若 Sends > 20: 随机序列偏"倒霉"
 *   若 Sends < 20: 随机序列偏"幸运"
 */
```
1
2
3
4
5
6
7
8
9
10
11
12

损坏重传实验。修改 LOSS_RATE=0, CORRUPT_RATE=30, ACK_LOSS_RATE=0。观察输出中是否出现 CORR 事件。当接收方收到损坏包时，为何 retrans_cnt 会增加？这个增加发生在 receiver_recv() 中——为什么接收方要修改发送方的统计变量？

知识点提示：retrans_cnt 是全局变量，不是发送方独占的。它统计"需要重传的事件"总数——丢包需要重传、损坏需要重传、ACK 丢失需要重传。接收方在发现损坏包时递增 retrans_cnt，因为发送方在等待 ACK 超时后会重传。

参考解答

ex2_corrupt_test.c

/*
 * 预期输出中会出现 CORR 事件，如:
 *   [NN] CORR  seq=N
 *
 * retrans_cnt 递增位置分布在三个地方:
 *   1. main() 中 LOST 分支     → 丢包导致的重传
 *   2. main() 中 ACK-L 分支    → ACK 丢失导致的重传
 *   3. receiver_recv() 中 CORR → 损坏导致的重传
 *
 * 三个分支共同维护 retrans_cnt 的语义:
 *   "协议经历了多少次需要重传来恢复的事件"
 *
 * 这是全局计数器设计的一个例子:
 *   发送方和接收方共享状态，简化了统计逻辑。
 *   在真实分布式协议中，两端无法共享全局变量,
 *   需要各自维护计数器并通过协议消息同步。
 */

ACK 丢失实验*：修改 LOSS_RATE=0, CORRUPT_RATE=0, ACK_LOSS_RATE=30。观察 ACK-L 事件。发送方在收到 ACK-L 后做了什么？接收方在发送方重传时会收到什么（注意 seq_exp 的状态）？

知识点提示：ACK 丢失时，接收方已经成功交付了消息并翻转了 seq_exp。发送方重传同一个包，接收方发现 pkt_seq != seq_exp，记录 DUPL 事件。这就是"接收方不交付重传包"的典型场景。

参考解答

ex3_ack_loss_test.c

/*
 * ACK 丢失时的协议行为:
 *
 * 正常情况:
 *   sender → pkt(seq=0) → receiver (交付, seq_exp=1)
 *   receiver → ACK(0) → sender (翻 seq_snd=1, msg_idx++)
 *
 * ACK 丢失:
 *   sender → pkt(seq=0) → receiver (交付, seq_exp=1)
 *   receiver → ACK(0) → ✗ 丢失
 *   sender 超时 → 重传 pkt(seq=0)
 *   receiver: seq_exp=1 ≠ pkt_seq=0 → DUPL！
 *   receiver 重发 ACK(0) → sender 收到 → 推进
 *
 * 关键: 即使 ACK 丢失, 消息也只被交付一次 (不是两次)
 * 接收方用 seq_exp 保护了自己, 发送方用重传保证了自己能推进
 */

统计计数器分析。运行程序后，retrans_cnt=1，但实际输出中只有 1 次 LOST 事件。如果出现 CORR 事件，retrans_cnt 是否会额外增加？请修改参数让 CORR 事件出现（如 CORRUPT_RATE=50, LOSS_RATE=0, ACK_LOSS_RATE=0），验证 retrans_cnt 的累积逻辑。

知识点提示：retrans_cnt 是三个递增点的累加和：LOST + CORR + ACK-L。无论哪个条件触发，都意味着至少一次重传。但注意：在 srand(42) 默认参数下，你的随机序列可能永远不会命中 CORRUPT 区间——这是确定性伪随机的正常现象。

参考解答

ex4_counter_analysis.c

/*
 * 验证 retrans_cnt 的累计逻辑:
 *
 * 设置 LOSS_RATE=0, CORRUPT_RATE=50, ACK_LOSS_RATE=0:
 *   retrans_cnt 在 receiver_recv() 的 CORR 分支递增
 *   → 每次 CORR 事件: retrans_cnt++
 *   → 随后发送方超时 (arrived=0) → sender_ack 记录 TOUT
 *   → 主循环回到顶部重传
 *
 * 观察: retrans_cnt 的每次递增都对应一次重传
 *       send_count - MSG_COUNT ≈ retrans_cnt
 *       (重传次数 ≈ 总发送次数 - 消息数)
 *
 * 不精确相等的原因:
 *   - CORR 后发送方要在下一轮才重传 (send_count 已递增)
 *   - 如果最后一则消息没有重传, 差值恰好相等
 */

seq 错乱注入实验。在 receiver_recv 中人为制造一次 seq 错乱：在处理某个正确包时，故意不翻转 seq_exp。观察后续输出——接收方会把下一个正确的包当成 DUPL 吗？这反映了什么问题？

知识点提示：seq_exp 是接收方唯一的状态变量。一旦它出错（没有正确翻转），接收方会把所有后续新包当成"重传"，永不交付。这展示了分布式协议中"状态一致"的关键性——发送方和接收方的序号同步一旦破裂，协议就失效了。

参考解答

ex5_seq_desync.c

/*
 * 实验: 在 receiver_recv() 中注释掉 seq_exp 翻转:
 *
 *   if (pkt_seq == seq_exp) {
 *       log_event(send_count, "RECV", pkt_seq, data);
 *       deliv_cnt++;
 *       // seq_exp = 1 - seq_exp;  ← 故意注释掉！
 *       *send_ack = 1;
 *   }
 *
 * 预期观察:
 *   [00] SEND  seq=0 "HELLO"
 *   [01] RECV  seq=0 "HELLO"    deliv_cnt=1, seq_exp 仍为 0
 *   [01] ACK   seq=0            seq_snd → 1
 *   [01] SEND  seq=1 "OpenCamp"
 *   [02] RECV  seq=1            ← 但 seq_exp=0 ≠ 1
 *   输出变为: [02] DUPL  seq=1 "OpenCamp"  ← 错误！
 *
 * deliv_cnt 正确 (4) 但 RECV 日志全变成 DUPL
 * 因为 seq_exp 卡在 0, 所有 seq=1 的包都被当成重传
 */

参考资料

Kurose & Ross《计算机网络：自顶向下方法》第 3 章 — 可靠数据传输原理（rdt1.0 → rdt2.0 → rdt3.0 逐步构建），从完美信道到有错信道再到丢包信道的协议演进
RFC 793 (Transmission Control Protocol) — 真实世界中可靠传输协议的完整规范，包含滑动窗口、累计 ACK、快速重传、流控与拥塞控制
Tanenbaum《计算机网络》第 6 章 — 数据链路层协议，停等协议与滑动窗口协议的数学分析，信道利用率公式推导
Wikipedia: Stop-and-wait ARQ — 停等协议的百科条目，包含时序图和效率分析
Computer Networking: A Top-Down Approach - RDT — Kurose 配套的 RDT 交互式动画，直观展示停等协议的状态转换过程

"The most profound technologies are those that disappear. They weave themselves into the fabric of everyday life until they are indistinguishable from it." — Mark Weiser

Lesson 50: 可靠数据传输 — 停等协议（Stop-and-Wait） ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 不可靠信道模型——为什么需要可靠传输？ ​

1.1 真实网络的服务原语 ​

1.2 本练习的信道模拟参数 ​

2. 有限状态机——协议的形式化描述 ​

2.1 发送方 FSM ​

2.2 接收方 FSM ​

3. 序号空间——1 比特为什么够？ ​

3.1 滑动窗口与序号空间的关系 ​

3.2 如果不用序号会怎样？ ​

4. 核心函数逐一分析 ​

4.1 log_event() — 格式化日志 ​

4.2 sender_send() — 发包 ​

4.3 sender_ack() — 处理确认 ​

4.4 receiver_recv() — 接收方核心 ​

4.5 main() — 主循环 ​

5. 完整逐轮追踪（srand(42)） ​

6. 常见陷阱与正确做法 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 50: 可靠数据传输 — 停等协议（Stop-and-Wait）

练习任务

核心知识点

代码框架

深度讲解

1. 不可靠信道模型——为什么需要可靠传输？

1.1 真实网络的服务原语

1.2 本练习的信道模拟参数

2. 有限状态机——协议的形式化描述

2.1 发送方 FSM

2.2 接收方 FSM

3. 序号空间——1 比特为什么够？

3.1 滑动窗口与序号空间的关系

3.2 如果不用序号会怎样？

4. 核心函数逐一分析

4.1 `log_event()` — 格式化日志

4.2 `sender_send()` — 发包

4.3 `sender_ack()` — 处理确认

4.4 `receiver_recv()` — 接收方核心

4.5 `main()` — 主循环

5. 完整逐轮追踪（srand(42)）

6. 常见陷阱与正确做法

参考解答

课堂讨论

讨论答案

课后练习

参考资料