📚 覆盖：第 17–24 讲

第一部分：数据平面、调度与流量监管（第 17 讲，21 分）

题 1（4 分）⭐

转发表如下：

前缀                  接口
1.  10.0.0.0/8         A
2.  10.16.0.0/12       B
3.  10.16.32.0/20      C
4.  10.16.32.0/24      D
5.  0.0.0.0/0          E

判断以下目的地址的输出接口，写出判断过程：

(a) 10.16.32.7 (b) 10.16.40.1 (c) 10.24.0.5 (d) 10.200.1.1 (e) 192.0.2.1

题 2（3 分）

(a) 为什么转发必须在纳秒级完成？以 100 Gbps 链路和 64 字节最小帧为例计算。 (b) TCAM 的优点与缺点各是什么？ (c) 什么是 512K Day？它说明了什么？

题 3（3 分）

(a) 什么是队头阻塞？它在本课程中出现过几次，分别在哪？ (b) 纯输入排队的理论吞吐量上限是多少？ (c) VOQ 如何解决它？这个解法与 HTTP/2 的多路复用有什么共同思想？

题 4（2 分）

(a) 缓冲区应该配 RTT×C 还是 RTT×C/√N？各自的适用条件是什么？ (b) 为什么这两个公式都不是最终答案？

题 5（5 分）⭐

某客户接入链路速率 100 Mbps。运营商用令牌桶对其流量做监管，参数 r = 20 Mbps、b = 50000 bits。

(a) 客户安静很久后突然有数据要发。瞬间最多能放行多少比特？以 100 Mbps 发出这段突发需要多长时间？ (b) 任意 5 ms 的区间内，最多能有多少比特通过监管器？ (c) 若客户持续以 40 Mbps 发送，从开始发送算起多久之后会出现丢包？ (d) 若要让客户能以 100 Mbps 满速突发持续 10 ms 而不被丢弃，b 至少要设成多大？

题 6（4 分）

(a) 用一句话分别说明调度、监管、整形各自回答什么问题，并指出监管与整形的唯一区别。 (b) 一条被令牌桶 (r = 1 Mbps, b = 8000 bits) 监管的流，经过 WFQ 调度器获得保证速率 R = 2 Mbps。求它在该调度器上的最大排队时延。 (c) 若把 b 增大到 32000 bits，时延上限变成多少？由此说明 b 的取值带来什么权衡。

第二部分：IP 编址与 NAT（第 18 讲，22 分）

题 7（6 分）⭐

某公司获得 172.20.0.0/22，需要划分为：

研发部    500 台主机
测试部    200 台主机
运维部     60 台主机
市场部     25 台主机
两条路由器间的点对点链路 × 2

用 VLSM 完成划分，给出每个子网的网络地址、CIDR 前缀、掩码、可用主机范围、广播地址。

题 8（4 分）

一个 6000 字节的 IP 数据报（含 20 字节头部）要通过 MTU = 1400 的链路。

(a) 会分成几片？写出每片的数据长度、片偏移、MF 标志、总长度。 (b) 为什么片偏移以 8 字节为单位？ (c) 若第 3 片丢失，会发生什么？

题 9（4 分）

(a) IP 头部校验和覆盖数据吗？为什么每跳都要重算？ (b) 分片由谁做？重组由谁做？为什么不对称（给出三条理由）？ (c) IPv6 为什么取消了路由器分片？取而代之的是什么？

题 10（4 分）⭐

(a) 用一句话精确定义"子网"，并给出判定方法。 (b) 203.0.113.128/26 有多少可用主机地址？范围是什么？广播地址是什么？ (c) 为什么主机数要"减 2"？ (d) /30 为什么专门用于点对点链路？

题 11（4 分）

(a) DHCP 为什么必须用广播？为什么用 UDP 而不是 TCP？ (b) DHCP 提供哪四样东西？为什么后两样和 IP 地址同等重要？ (c) 主机得到 169.254.x.x 地址说明了什么？

第三部分：NAT 与 IPv6（第 18–19 讲，20 分）

题 12（5 分）⭐

(a) NAT 违反了哪条设计原则？具体是怎么违反的？ (b) 给出支持 NAT 与反对 NAT 的各一条最有力的论证。 (c) 打洞（hole punching）为什么能成功？ (d) 什么类型的 NAT 会让打洞失败？为什么？

题 13（4 分）

(a) IPv6 头部去掉了哪三样东西？各自的理由是什么？ (b) 为什么"更大的地址，反而更简单的头部"？ (c) 压缩地址 2001:0db8:0000:0000:0000:0000:1428:57ab。为什么 :: 只能用一次？

题 14（4 分）

(a) IPv6 为什么取消了广播？用什么替代？ (b) 什么是任播？它在本课程中出现在哪两个场景？ (c) 为什么屏蔽 ICMPv6 会让 IPv6 网络完全不工作？

题 15（3 分）⭐

说出 IPv6 部署缓慢的四条原因，并指出哪一条是最根本的设计失误。

题 16（4 分）

用 OpenFlow 的「匹配 + 动作」写出以下四条规则，并按正确的优先级排列：

① 丢弃所有来自 198.51.100.0/24 的流量
② 把发往 10.0.0.50:443 的流量转发到端口 3
③ 把发往 10.0.2.0/24 的流量转发到端口 5
④ 其余流量交给默认网关（端口 1）

并说明为什么顺序重要。

第四部分：路由算法（第 20–22 讲，36 分）

题 17（6 分）⭐

给定网络（数字为链路开销）：

        3            2
   A ────── B ────── C
   │ ╲      │        │
  1│  ╲5   4│       6│
   │    ╲   │        │
   D ──── E ─────────┘
       2        3

链路：A–B=3, A–D=1, A–E=5, B–C=2, B–E=4, C–E=3, D–E=2, C–E=6 中取 3

（明确列表：A–B=3, A–D=1, A–E=5, B–C=2, B–E=4, C–E=3, D–E=2）

(a) 用 Dijkstra 从 A 出发，写出完整迭代表。 (b) 给出 A 的转发表（目的、最短路径、开销、第一跳）。 (c) 是否存在等价多路径？

题 18（5 分）⭐⭐

三节点网络：

      6              2
  x ─────  y ─────  z
   ╲              ╱
    ╲──── 10 ────╱

(a) 写出三个节点的初始距离向量。 (b) 追踪 DV 的收敛过程，给出每一轮的距离向量表。 (c) 收敛后 x 到 z 的距离与下一跳是什么？

题 19（5 分）⭐⭐

在上题基础上，c(x,y) 从 6 变为 60。

(a) 追踪前 6 轮的 d_y(x) 与 d_z(x)，展示无穷计数。 (b) 收敛需要多少轮？ (c) ⭐ 解释根本原因：为什么 y 会选择一条实际经过自己的路径？ (d) 启用毒性逆转后需要几轮？ (e) ⭐ 毒性逆转能消除所有环路吗？为什么？

题 20（4 分）

(a) LS 与 DV 在健壮性上的根本差异是什么？ (b) 为什么大型网络内部普遍使用 OSPF 而非 RIP？ (c) BGP 是 DV 的变体，它如何避免了无穷计数？

题 21（3 分）

(a) 什么是路由震荡？给出一个具体场景。 (b) 为什么互联网不使用负载敏感的路由开销？ (c) 那么拥塞由谁处理？这体现了什么原则？

题 22（5 分）⭐

AS 拓扑（→ 表示"是……的提供商"）：

      AS10 ──peer── AS20
        │             │
     provider      provider
        ↓             ↓
      AS30 ──peer── AS40
        │
     provider
        ↓
      AS50  （持有前缀 P）

(a) AS50 通告 P 后，按 Gao-Rexford 规则，路由会传播到哪些 AS？逐步说明。 (b) AS20 收到的 AS_PATH 是什么？ (c) 若 AS30 同时从 AS50 和 AS40 收到到 P 的路由，会选哪条？依据是什么？ (d) 若 AS40 通告 P 的一个更具体前缀（/25），会发生什么？RPKI 能挡住吗？ (e) ⭐ 构造一个 RPKI 挡不住的劫持。

题 23（4 分）

(a) 写出 BGP 路由选择的优先级顺序。 (b) 为什么 LOCAL_PREF 排第一？ (c) 什么是热土豆路由？它导致了什么现象？这个现象给排障带来什么困难？

题 24（4 分）

(a) 完整描述 traceroute 的工作原理，包括它如何判断到达终点。 (b) 为什么一律屏蔽 ICMP 是错误的？给出两个具体后果。 (c) ICMP 报文为什么要携带出错数据报的前 8 字节？

第五部分：链路层与数据中心网络（第 23–24 讲，29 分）

题 25（5 分）⭐

D = 1010 1101 10（10 位），G = 11001（5 位）。

(a) 计算 CRC，写出完整的模 2 除法过程。 (b) 写出要发送的比特串。 (c) 接收方如何验证？ (d) 这个 CRC 能保证检出多长的突发错误？

题 26（4 分）⭐

(a) 为什么链路层用 CRC-32 而传输层只用 16 位校验和？给出两条理由。 (b) 举一个 CRC 全部通过但数据仍然损坏的场景。 (c) 这说明了什么原则？

题 27（4 分）⭐

(a) 推导时隙 ALOHA 的最大效率。 (b) 纯 ALOHA 为什么只有它的一半？ (c) CSMA 已经先听后说了，为什么还会碰撞？

题 28（4 分）⭐

(a) 完整推导以太网最小帧长为什么是 64 字节。 (b) 千兆以太网如果沿用 64 字节会有什么问题？实际怎么解决的？ (c) 二进制指数退避的规则是什么？它与 TCP 的哪个机制同构？

题 29（4 分）⭐

主机 A（10.1.1.5，MAC AA）在子网 1；路由器 R 接口 1（10.1.1.1，MAC R1）在子网 1，接口 2（10.2.2.1，MAC R2）在子网 2；主机 B（10.2.2.9，MAC BB）在子网 2。A 要给 B 发数据。

(a) A 会 ARP 查询谁的 MAC？为什么不能查 B 的？ (b) 写出 A 发出的帧的四个地址（源/目的 MAC、源/目的 IP）。 (c) 写出 R 从接口 2 发出的帧的四个地址。 (d) 用这个例子说明一句话原则。

题 30（3 分）

交换机 4 个端口接 A、B、C、D，初始表为空。事件序列：A→C, C→A, B→D, D→B, A→D。

(a) 逐步写出交换机表与转发动作。 (b) 哪些事件发生了泛洪？为什么？ (c) 若换成集线器，事件 5 有什么不同？

题 31（5 分）⭐

(a) k = 24 的 Fat-Tree 拓扑能接入多少台主机？需要多少台核心交换机？ (b) 某数据中心 RTT = 100 µs，而 TCP 最小 RTO = 200 ms。一次超时相当于白白浪费多少个 RTT？ (c) 在 incast 场景下，为什么快速重传帮不上忙，只能等超时？ (d) 写出 DCTCP 的降窗公式。当 α = 0.2 时 cwnd 如何变化？与标准 TCP 遇到丢包时的行为对比。

参考解答

题 1

先把相关字节转成二进制：

10.0.0.0/8      → 10.*
10.16.0.0/12    → 10.0001****  （第二字节高 4 位 = 0001）
10.16.32.0/20   → 10.16.0010**** （第三字节高 4 位 = 0010）
10.16.32.0/24   → 10.16.32.*

(a) 10.16.32.7（第二字节 16=00010000，第三字节 32=00100000）

/8  ✓  /12 ✓（高 4 位 0001）  /20 ✓（第三字节高 4 位 0010）  /24 ✓
⭐ 最长 = /24  →  接口 D

(b) 10.16.40.1（第三字节 40=00101000）

/8 ✓  /12 ✓  /20 ✓（高 4 位 0010）  /24 ✗（40 ≠ 32）
⭐ 最长 = /20  →  接口 C

(c) 10.24.0.5（第二字节 24=00011000，高 4 位 = 0001）

/8 ✓  /12 ✓  /20 ✗（第二字节虽匹配，但 /20 要求第二字节 = 16）
⭐ 最长 = /12  →  接口 B

(d) 10.200.1.1（第二字节 200=11001000，高 4 位 = 1100）

/8 ✓  /12 ✗
⭐ 最长 = /8  →  接口 A

(e) 192.0.2.1

只有默认路由匹配  →  接口 E

题 2

(a)

64 字节 = 512 bit
512 bit / 100×10⁹ bps = 5.12 ns

⭐ 路由器必须在 5.12 ns 内完成一次转发决策，否则跟不上线速，分组会堆积。这个约束迫使转发路径必须完全硬件化。

(b) 优点：⭐ O(1) 查找，一个时钟周期内并行比较所有表项并返回最长匹配，与表项数量无关。缺点：昂贵、功耗高、容量有限（典型上百万条）。

(c) 2014 年 8 月，全球 BGP 路由表条目数突破 512K，而许多在用路由器的 TCAM 默认只为 IPv4 路由分配了 512K 条目。溢出后路由被丢弃或转入软件转发，造成大范围性能崩溃与连通性故障。⭐ 它说明了硬件的物理限制会直接转化为全球性的网络故障，也说明了 CIDR 地址聚合（防止路由表膨胀）为什么重要。

题 3

(a) 队头阻塞指队首元素因某种冲突无法前进时，队列中后面本可以被处理的元素也被迫等待。本课程出现 3 次：① HTTP/1.1 的响应必须按请求顺序返回（第 6 讲）；② TCP 字节流中一个丢包阻塞所有已到达的后续数据（第 6 讲）；③ 交换机输入队列中队首分组因输出端口冲突阻塞后续分组（第 17 讲）。

(b) 约 58.6%（Karol et al., 1987，随机流量假设下）。

(c) VOQ（虚拟输出队列）：每个输入端口为每一个输出端口各维护一个独立队列，队头不再互相牵连，配合调度算法吞吐量可达 100%。⭐ 共同思想是"把一个共享队列拆成 N 个独立队列"——HTTP/2 的多路复用流、QUIC 的独立流用的是完全相同的思路。

题 4

(a) RTT×C 适用于链路上只有一条或少数几条 TCP 流的情形（为在丢包后维持链路满载所需）；RTT×C/√N 适用于有 N 条互不同步的 TCP 流的情形，它们的锯齿相互抵消，所需缓冲大幅减少。

(b) 因为它们都只优化吞吐量而完全不考虑时延——按它们配置的大缓冲区正是 bufferbloat 的成因。⭐ 正确做法是配合 AQM（CoDel） 动态控制分组在队列中的驻留时间，而不是静态设定队列长度。

题 5

(a) 桶攒满时有 b = 50000 个令牌，⭐ 瞬间最多放行 50000 bits。以链路速率 100 Mbps 发出：

50000 bits / 100e6 bps = 0.5 ms

(b) 直接套令牌桶的上限公式：

流量(t) ≤ r · t + b
        = 20e6 × 0.005 + 50000
        = 100000 + 50000
        = 150000 bits

(c) 客户以 40 Mbps 消耗令牌，桶以 20 Mbps 补充，初始存量 50000。设经过 t 秒后令牌耗尽：

消耗 > 供给 + 存量
40e6 · t > 20e6 · t + 50000
20e6 · t > 50000
       t > 2.5 ms

⭐ **约 2.5 ms 后开始丢包。**在此之前客户能以 40 Mbps「超速」发送，靠的是攒下的突发额度——这正是令牌桶允许突发的体现。

(d) 10 ms 内以 100 Mbps 发送需要：

需求 = 100e6 × 0.01 = 1000000 bits
允许 = r · t + b   = 20e6 × 0.01 + b = 200000 + b

要求  200000 + b ≥ 1000000
      ⭐ b ≥ 800000 bits（100 KB）

题 6

(a)

  • 调度：多条流竞争同一条输出链路时，谁先走。
  • 监管：这条流是不是超出了约定速率。
  • 整形：同上，但处理方式不同。

⭐ 监管与整形的唯一区别是【缓存】：监管不缓存，超出的分组当场丢弃或降级，因此不增加时延但会丢包；整形缓存，超出的先排队等令牌，因此不丢包但增加时延并需要缓冲区。

(b)

d_max = b / R = 8000 bits / 2e6 bps = 4 ms

(c)

d_max = 32000 / 2e6 = 16 ms

⭐ 权衡：b 越大，越宽容突发（应用体验更好、丢包更少），但时延上限随 b 线性增大。也就是说——突发容忍度和时延保证是直接对立的，不存在既允许大突发又能给出低时延承诺的配置。这正是为什么 EF（加速转发）这类低时延服务必须配一个很小的桶。

题 7

172.20.0.0/22 = 1024 个地址（172.20.0.0 – 172.20.3.255）。

⭐ VLSM 从大到小分配：

需求 → 前缀
研发 500 台 → 需 502 个 → 2⁹=512 → /23
测试 200 台 → 需 202 个 → 2⁸=256 → /24
运维  60 台 → 需  62 个 → 2⁶=64  → /26
市场  25 台 → 需  27 个 → 2⁵=32  → /27
点对点 ×2   → 各 2 个   → 2²=4   → /30

总需求 = 512 + 256 + 64 + 32 + 4 + 4 = 872 ≤ 1024 ✓

部门 网络地址 前缀 掩码 可用主机范围 广播地址
研发 172.20.0.0 /23 255.255.254.0 172.20.0.1 – 172.20.1.254 172.20.1.255
测试 172.20.2.0 /24 255.255.255.0 172.20.2.1 – 172.20.2.254 172.20.2.255
运维 172.20.3.0 /26 255.255.255.192 172.20.3.1 – 172.20.3.62 172.20.3.63
市场 172.20.3.64 /27 255.255.255.224 172.20.3.65 – 172.20.3.94 172.20.3.95
P2P-1 172.20.3.96 /30 255.255.255.252 172.20.3.97 – 172.20.3.98 172.20.3.99
P2P-2 172.20.3.100 /30 255.255.255.252 172.20.3.101 – 172.20.3.102 172.20.3.103

剩余 172.20.3.104 – 172.20.3.255（152 个地址）留作扩展。

⚠️ 两个易错点：① 必须从大到小分配，否则会产生无法使用的地址碎片；② 500 台主机需要 /23 而不是 /24（254 < 500）。

题 8

(a) 数据部分 = 6000 − 20 = 5980 字节。每片最多携带 1400 − 20 = 1380 字节，⭐ 但必须是 8 的倍数：1380 ÷ 8 = 172.5，向下取整到 172 × 8 = 1376 字节。

片 1: 数据 1376, 偏移 = 0,   MF=1, 总长 = 1396
片 2: 数据 1376, 偏移 = 172, MF=1, 总长 = 1396
片 3: 数据 1376, 偏移 = 344, MF=1, 总长 = 1396
片 4: 数据 1376, 偏移 = 516, MF=1, 总长 = 1396
片 5: 数据  476, 偏移 = 688, MF=0, 总长 =  496
⭐ 共 5 片   （1376×4 + 476 = 5980 ✓）

(b) 因为片偏移字段只有 13 位，而 IP 数据报最大 65535 字节，需要表示的偏移范围是 0–65528。13 位只能表示 0–8191，⭐ 以 8 字节为单位恰好使 8191×8 = 65528 覆盖整个范围。这是一个用"单位换位宽"的经典设计。

(c) ⭐ 整个原始数据报作废。目的主机永远无法完成重组，会在重组定时器超时后丢弃已收到的所有片。上层（TCP）随后会重传整个报文段——这就是为什么分片被认为是坏主意，也是 IPv6 取消它的原因之一。

题 9

(a) ⭐ 不覆盖数据，只覆盖头部（数据完整性交给传输层校验和与链路层 CRC）。每跳必须重算，是因为 TTL 每跳减 1，头部内容改变，原校验和失效。（IPv6 干脆取消了头部校验和，正是因为每跳重算是纯粹的开销。）

(b) ⭐ 分片由路由器做，重组只由目的主机做。三条理由：① 各片可能沿不同路径传输，中间路由器无法保证收齐；② 让路由器维护重组状态会破坏无状态转发、消耗内存并构成 DoS 攻击面；③ 端到端原则——只有终点能正确完成重组。

(c) 因为分片带来三个问题：一片丢失导致整个数据报作废、重组消耗接收方资源且是攻击面、中间设备难以处理非首片（没有端口号）。取而代之的是 ⭐ Path MTU Discovery：源主机主动探测路径上的最小 MTU，自己保证不超过它；路由器遇到过大分组直接回 ICMPv6 “Packet Too Big”。

题 10

(a) ⭐ **子网是一组接口的集合，这些接口彼此之间不经过路由器就能直接通信。**判定方法：把每台路由器的所有接口从图上剪断，剩下的每一个相互连通的孤岛就是一个子网。

(b) /26 → 主机位 6 位 → 64 个地址 → ⭐ 62 个可用主机。

网络地址: 203.0.113.128
可用主机: 203.0.113.129 – 203.0.113.190
广播地址: 203.0.113.191

(c) 因为全 0 的主机部分是网络地址（标识这个子网本身），全 1 的主机部分是广播地址（发给子网内所有主机），二者都不能分配给具体主机。

(d) /30 提供 4 个地址，去掉网络地址和广播地址后恰好剩 ⭐ 2 个可用地址——正好对应点对点链路两端的两个接口，没有任何浪费。（更极端的做法是 /31，RFC 3021 允许在点对点链路上省掉网络与广播地址，得到 2 个可用地址。）

题 11

(a) ⭐ 广播：客户端在获得地址前既没有自己的 IP，也不知道 DHCP 服务器的 IP，无法进行任何单播通信。⭐ UDP：TCP 需要三次握手，而握手本身要求已有可用 IP 地址——同一个循环依赖。

(b) ① IP 地址；② 子网掩码；③ ⭐ 默认网关；④ ⭐ 本地 DNS 服务器。后两样同等重要，是因为：没有网关只能在本子网内通信（无法访问外网），没有 DNS 只能用 IP 地址访问网站（几乎无法使用互联网）。「配好网络」= 这四样都有。

(c) 说明 ⭐ DHCP 获取失败。169.254.0.0/16 是链路本地地址（APIPA），由主机在 DHCP 超时后自动配置。它只能在本链路内通信，无法访问外网。这是网络排障时的第一个诊断信号。

题 12

(a) 违反了⭐ 端到端原则。具体表现：网络中间的设备（路由器）改写了传输层的端口信息，并且越层处理了第 4 层内容——按分层原则路由器只应处理到第 3 层。

(b) 反对最有力：⭐ 它破坏了 IP 的可寻址性，使内网主机无法被主动连接，从而系统性地扼杀了 P2P、IP 电话、个人自建服务等一整类应用，把互联网从对等网络推向了不对称的客户机-服务器结构。支持最有力：⭐ 没有 NAT，IPv4 地址会在 2000 年代初彻底耗尽，而当时 IPv6 远未具备部署条件——NAT 用架构上的妥协为互联网换来了二十年时间。

(c) 因为 NAT 的规则是「阻止未经请求的入站分组」，而不是「阻止所有入站」。当双方同时向对方（的公网地址:端口，通过信令服务器交换得到）发包时，各自的 NAT 都会把对方的回包视为"我方主动发起的会话的响应"而放行，双向映射同时建立。

(d) ⭐ 对称型 NAT（Symmetric NAT）。它为每一个不同的目的地分配一个不同的外部端口，因此通过信令服务器得知的"外部端口"对直连场景不适用——打洞失败，只能退回 TURN 中继。

题 13

(a) ① ⭐ 头部校验和——传输层和链路层都在做差错检测，而 IPv4 因 TTL 变化需要每跳重算，纯属浪费。② ⭐ 分片与重组字段——改由源主机做 PMTUD，避免分片的性能与安全问题。③ 可变长选项——移入扩展首部链，使基本首部固定 40 字节，便于硬件流水线处理。

(b) 因为 ⭐ IPv4 头部里有一半字段是历史包袱（分片、校验和、可变选项、ToS 的历史用法）。IPv6 借地址扩容的机会做了一次彻底清理，字段数从 13 个降到 8 个。地址变长和头部变简单是两件独立的事。

(c) 2001:db8::1428:57ab。:: 只能用一次，是因为它表示"这里有若干组全零"——若出现两次，解析器无法确定每一处各代表几组零，地址产生歧义。

题 14

(a) 因为广播会中断链路上每一台设备的处理（包括完全不关心该报文的设备），在无线网络中还会消耗所有设备的电量并占用共享信道。用 ⭐ 多播替代（ff02::1 = 本链路所有节点，ff02::2 = 本链路所有路由器），只送达显式加入该组的节点。

(b) 任播是让多个物理节点通告同一个 IP 地址，路由协议自然把每个客户端的分组送到拓扑上最近的那个节点。本课程中出现在：① ⭐ 根 DNS 服务器（13 个逻辑标识背后是 1500+ 个任播实例，第 7 讲）；② ⭐ CDN 节点选择（部分 CDN 用任播 IP 吸引流量到最近边缘，第 6 讲）。

(c) 因为 IPv6 的 ⭐ 邻居发现协议（NDP）跑在 ICMPv6 之上——它取代了 IPv4 的 ARP，负责地址解析、路由器发现、重复地址检测。屏蔽 ICMPv6 等于屏蔽了 ARP，主机连本地网关的 MAC 地址都无法获得，网络完全不工作。（很多管理员按 IPv4 的习惯"屏蔽所有 ICMP"，在 IPv6 上这是灾难性的配置错误。）

题 15

① ⭐ 不向后兼容——IPv6 主机不能直接与 IPv4 主机通信；② 网络效应的鸡蛋问题——ISP 与内容商互相等待；③ NAT 缓解了地址短缺的紧迫性，消除了迁移动力；④ 成本与收益错配——迁移成本由网络运营者承担，收益扩散到整个生态。

⭐ 最根本的设计失误是第 ①条：如果 IPv6 被设计成 IPv4 的超集（让 IPv6 节点能直接与 IPv4 节点互通），部署就会是渐进的而非全有全无的。

题 16

优先级 100  匹配: 源IP = 198.51.100.0/24
            动作: DROP

优先级  80  匹配: 目的IP = 10.0.0.50, 协议 = TCP, 目的端口 = 443
            动作: FORWARD(3)

优先级  50  匹配: 目的IP = 10.0.2.0/24
            动作: FORWARD(5)

优先级   0  匹配: *（全通配）
            动作: FORWARD(1)

⭐ 顺序重要的原因：多条规则可能同时匹配同一个分组。一个来自 198.51.100.5、发往 10.0.0.50:443 的分组同时匹配规则 ① 和 ②——若 ② 优先级更高，攻击流量会被正常转发，安全策略完全失效。

📌 **通用原则：安全/丢弃规则的优先级必须高于业务转发规则。**这与防火墙规则表的编写规则一致，也与最长前缀匹配是同一类问题——当多条规则匹配时必须有明确且正确的仲裁规则。

题 17

链路：A–B=3, A–D=1, A–E=5, B–C=2, B–E=4, C–E=3, D–E=2

(a) Dijkstra 从 A 出发

步 N' D(B),p D(C),p D(D),p D(E),p
0 {A} 3,A ∞ 1,A 5,A
1 {A,D} 3,A ∞ 3,D
2 {A,D,B} 5,B 3,D
3 {A,D,B,E} 5,B
4 全部

逐步说明：

步 0: D(B)=3, D(D)=1, D(E)=5。最小是 D(1) → 加入
步 1: 用 D 松弛 E: D(E) = min(5, 1+2) = 3, p(E)=D  ⭐ 更新
      N' 外最小是 B(3) 和 E(3)，任选 B
步 2: 用 B 松弛 C: D(C) = min(∞, 3+2) = 5, p(C)=B
      用 B 松弛 E: D(E) = min(3, 3+4) = 3（不变）
      最小是 E(3)
步 3: 用 E 松弛 C: D(C) = min(5, 3+3) = 5（不变，⭐ 平局）
      最小是 C(5)
步 4: 完成

(b) A 的转发表

目的 最短路径 开销 第一跳
B A→B 3 (A,B)
C A→B→C 5 (A,B)
D A→D 1 (A,D)
E A→D→E 3 (A,D)

(c) ⭐ **是。**到 C 有两条开销均为 5 的路径：A→B→C（3+2）和 A→D→E→C（1+2+3）。⭐ 这是等价多路径（ECMP），OSPF 支持同时使用两条路径做负载均衡。

题 18

(a) 初始距离向量（只知道直连）

D_x = [x:0,  y:6,  z:10]
D_y = [x:6,  y:0,  z:2 ]
D_z = [x:10, y:2,  z:0 ]

(b) 第 1 轮交换后

x: d_x(z) = min{ c(x,y)+d_y(z),  c(x,z)+0 } = min{6+2, 10} = 8  ⭐ 更新，下一跳 y
   d_x(y) = min{ 6+0, 10+2 } = 6                                （不变）

z: d_z(x) = min{ c(z,y)+d_y(x),  c(z,x)+0 } = min{2+6, 10} = 8  ⭐ 更新，下一跳 y
   d_z(y) = min{ 2+0, 10+6 } = 2                                （不变）

y: d_y(x) = min{ 6+0, 2+10 } = 6                                （不变）
   d_y(z) = min{ 2+0, 6+10 } = 2                                （不变）

第 2 轮：x 和 z 通告了新的向量，但 y 重算后无变化；x 和 z 互相重算也无变化 → ⭐ 收敛。

(c)

d_x(z) = 8，下一跳 = y   （路径 x→y→z，开销 6+2=8）

题 19

初始状态（收敛后）：d_y(x) = 6（直连），d_z(x) = 8（经 y）。

(a)

t0: y 检测到 c(y,x) 从 6 变为 60
    d_y(x) = min{ 60+0,  c(y,z)+d_z(x) } = min{60, 2+8} = 10
    ⭐ y 选择经 z ——【但 z 到 x 的路径本来就经过 y】！
    
t1: z 收到 y 报 10
    d_z(x) = min{ 10+0(直连), 2+10 } = min{10, 12} = 10
    ⚠️ 注意 z 有一条直连 x 的链路，开销 10
    ⭐ 因此 z 此时会选择【直连】，d_z(x) = 10

t2: y 收到 z 报 10
    d_y(x) = min{ 60, 2+10 } = 12

t3: z 收到 y 报 12
    d_z(x) = min{ 10, 2+12 } = 10   （不变，仍走直连）

t4: y 收到 z 报 10 → d_y(x) = min{60, 12} = 12   （不变）
⭐ 收敛

⚠️ 本题的特殊性：因为 x–z 之间存在一条开销 10 的直连链路，无穷计数在 z 找到直连路径后很快被截断。

⭐ 要复现完整的无穷计数，需要去掉 x–z 直连链路（即第 20 讲的经典 x-y-z 三角形，其中 z 到 x 只能经 y）。此时：

t0: d_y(x)=min{60, 2+8}=10;   t1: d_z(x)=2+10=12
t2: d_y(x)=2+12=14;           t3: d_z(x)=2+14=16
... 交替 +4，直到 d_y(x) ≥ 60 时才改走直连

(b) 在本题的拓扑下 约 4 轮（因直连链路截断）；在无直连链路的经典拓扑下需 数十轮（第 20 讲的例子为 44 轮）。

(c) ⭐ 根本原因：DV 报文只携带距离数字，不携带路径信息。y 看到 “z 到 x 是 8” 这个数字，不知道这条路径实际上经过 y 自己，因此误以为存在一条绕开坏链路的更短路径。这就是路由环路。

(d) 启用毒性逆转后：z 因为到 x 经过 y，就向 y 报告 d_z(x) = ∞。于是：

t0: d_y(x) = min{60, 2+∞} = 60   ⭐ 立刻正确
t1: y 通知 z，z 更新为 62（或走直连 10）
⭐ 2 轮收敛

(e) ⭐ 不能。毒性逆转只能消除两个节点之间的环路。当环路涉及三个或更多节点（A→B→C→A）时，每一对节点之间的关系都是"我没经过你"，毒性逆转不会触发，无穷计数依然发生。这就是 RIP 必须额外用「16 跳 = 无穷」兜底，并配合水平分割与抑制计时器的原因。

题 20

(a) ⭐ LS：每个节点只广播自己直连链路的状态，所有节点拥有相同的拓扑数据库并各自独立运行 Dijkstra——某个错误信息的影响局限在涉及该链路的路径计算上。⭐ DV：每个节点的距离向量是基于邻居报告的结果计算的，并继续传给下一层邻居——一个错误的距离值会被逐级采纳、累加、传播，在全网扩散并放大。

(b) 因为 OSPF ① 健壮性更好（见上）；② 收敛快且确定（O(E log V)，无无穷计数）；③ 支持认证（防止恶意路由注入）；④ 支持区域分层（限制泛洪范围，适应大规模网络）；⑤ 支持 ECMP。而 RIP 因为跳数上限 15，结构上就只能用于小型网络。

(c) BGP 携带 ⭐ 完整的 AS_PATH。一个 AS 收到路由时，若在 AS_PATH 中看到自己的 ASN，说明这条路由绕回来了，立即丢弃。路径信息使环路一眼可辨，从根本上消除了 DV 因"只传距离、丢失路径"而产生的无穷计数问题。这就是它被称为路径向量协议的原因。

题 21

(a) 路由震荡指流量在多条路径间来回摆动、路由表反复改变。场景：三条流分别经顺时针路径到达目的地，链路开销随负载上升；所有节点同时发现顺时针拥塞而切到逆时针；逆时针随即拥塞、顺时针空闲，所有节点又切回来——无限震荡。

(b) 因为负载敏感开销会形成正反馈，导致上述震荡，造成路由不稳定、分组大量乱序、TCP 性能崩溃。OSPF 的默认开销基于带宽（静态）而非负载。

(c) ⭐ 由端系统的拥塞控制处理（TCP 的 AIMD，第 15–16 讲）。这体现了⭐ 智能在边缘、网络保持简单的端到端原则——网络负责稳定地转发，端系统负责适应可用容量。

题 22

(a)

AS50 → AS30（客户向提供商通告自己的前缀）✓

AS30 收到的是【客户路由】→ ⭐ 通告给所有人：
   AS30 → AS10（提供商）✓
   AS30 → AS40（对等方）✓

AS10 收到的是【客户路由（AS30 是 AS10 的客户）】→ 通告给所有人：
   AS10 → AS20（对等方）✓

AS40 收到的是【对等方路由】→ ⭐ 只通告给客户 → AS40 无客户，不再传播
AS20 收到的是【对等方路由】→ 只通告给客户 → 无客户，不再传播

⭐ P 的路由传播到了 AS10、AS20、AS30、AS40（全部）。

(b) AS_PATH = [AS10, AS30, AS50]

⚠️ AS20 收不到经由 AS40 的路径——AS40 从对等方 AS30 学到的路由只通告给客户，而 AS20 是 AS40 的提供商，不是客户。

(c) ⭐ **选择经 AS50 的路由。**依据是 BGP 选路算法第 ① 条 LOCAL_PREF，按 Gao-Rexford 规则 2：客户路由 > 对等方路由 > 提供商路由。AS50 是 AS30 的客户（付钱给 AS30），AS40 是对等方（免费）。⭐ 即使经 AS40 的 AS_PATH 更短，也选 AS50——因为 LOCAL_PREF 的优先级高于 AS_PATH 长度。理由是商业的，不是技术的。

(d) ⭐ /25 比 /24 更长，由最长前缀匹配，所有收到该路由的 AS 都会把流量送往 AS40 → 劫持成功。

RPKI 能挡住：ROA 声明「AS50 有权通告 P，maxLength = /24」。AS40 通告的 /25 有两处不符——起源 AS 是 AS40（不是 AS50），且前缀长度超出 maxLength。判定为 invalid，路由被丢弃。

(e) ⭐ AS40 伪造 AS_PATH，通告前缀 P（原始 /24 长度）并声称 AS_PATH = [AS40, AS50]——即"我是从 AS50 学到的"。

起源 AS 显示为 AS50  ✓ 与 ROA 匹配
前缀长度 = /24       ✓ 未超 maxLength
⭐ RPKI 检查【通过】

但整条路径是编造的，流量仍被送往 AS40

⭐ **这需要 BGPsec（对整条 AS_PATH 逐跳签名）才能防御，而 BGPsec 基本未部署。**这是第 21 讲最重要的安全结论：RPKI 只验证起源，不验证路径。

题 23

(a) ① LOCAL_PREF 最大者胜；② AS_PATH 最短者胜；③ NEXT_HOP 的 IGP 开销最小者胜（热土豆）；④ 其他 tie-break（如 router ID 最小）。

(b) 因为它编码了本 AS 的商业策略——按 Gao-Rexford 规则 2，客户路由必须优于对等方路由、对等方优于提供商路由。这个偏好必须凌驾于任何性能考量之上，否则 AS 会为不产生收入（甚至要付费）的流量买单。⭐ 策略优先于性能。

(c) 热土豆路由：当多条路由的 LOCAL_PREF 与 AS_PATH 都相同时，选择离自己最近的出口，尽快把流量甩出本 AS（因为分组在自己网络中每多走一段就多消耗自己的资源）。它导致 ⭐ 路径不对称：A→B 与 B→A 走完全不同的路径。排障困难：traceroute 只能显示去程路径，你看到的每一跳时延实际上是"去程到该跳 + 该跳的 ICMP 回程"，而回程路径可能完全不同且更长——因此无法从单向 traceroute 判断问题出在哪个方向。

题 24

(a) 发送方向目的地发送探测分组（传统用 UDP，目的端口设为极不可能被监听的值如 33434+），⭐ TTL 从 1 开始逐次递增，每个 TTL 值发 3 个。TTL 为 n 的分组在第 n 跳被减到 0 而丢弃，该路由器回送 ⭐ ICMP 类型 11（TTL 超时），发送方据此记录第 n 跳的地址与往返时延。当分组终于到达目的主机时，主机发现没有进程监听那个端口，回送 ⭐ ICMP 类型 3 代码 3（端口不可达）——收到"端口不可达"而非"超时"就意味着到达终点，随即停止。

(b) ① ⭐ 屏蔽类型 3 代码 4 会导致 Path MTU Discovery 失效——发送方永远收不到"需要分片"的通知，大分组被静默丢弃。症状是：TCP 握手成功、小请求正常，一传大数据就卡死（PMTUD 黑洞），是最难排查的网络故障之一。② ⭐ 屏蔽 ICMPv6 会让 IPv6 网络完全不工作——NDP 依赖它。正确做法是限速与选择性放行，而不是一律丢弃。

(c) 因为 ⭐ TCP/UDP 头部的前 8 字节恰好包含源端口号和目的端口号。有了它们，收到 ICMP 差错报文的主机才能确定是哪个进程的哪条连接触发了错误，从而把差错正确报告给对应的应用（例如转换成 Connection refused）。这是一个跨层设计：网络层的错误报告需要传输层的信息才能被正确投递。

题 25

D = 1010110110（10 位），G = 11001（5 位）→ r = 4
D 后补 4 个 0：10101101100000（14 位）

(a) 模 2 除法（窗口宽 5 位，首位为 1 就 XOR，为 0 就下移）：

取前 5 位        10101  → XOR 11001 → 余 01100
下移 '1' → 11001 → XOR 11001 → 余 00000
下移 '0' → 00000 → 首位 0     → 余 00000
下移 '1' → 00001 → 首位 0     → 余 00001
下移 '1' → 00011 → 首位 0     → 余 00011
下移 '0' → 00110 → 首位 0     → 余 00110
下移 '0' → 01100 → 首位 0     → 余 01100
下移 '0' → 11000 → XOR 11001 → 余 00001
下移 '0' → 00010 → 首位 0     → 余 00010
下移 '0' → 00100 → 首位 0     → 余 00100

⭐ 余数 R = 0100

(b) 发送的比特串：1010110110 0100（14 位）

(c) 接收方把收到的整个 14 位串模 2 除以 G = 11001，⭐ 余数应为 0000。非 0 则检出差错。

(d) r = 4，因此保证检出 ⭐ 所有长度 ≤ 4 的突发错误。长度大于 4 的突发，漏检概率约 2⁻⁴ = 6.25%（很高——这说明 4 位 CRC 强度不足，以太网用 CRC-32）。

题 26

(a) ① ⭐ 实现成本不同：链路层 CRC 由 NIC 中的专用移位寄存器电路完成，几乎零开销；传输层校验和由 CPU 对每个字节做加法，必须足够简单，否则成为吞吐量瓶颈。② ⭐ 覆盖范围不同：CRC 强但只覆盖一段链路；校验和弱但覆盖端到端全程。

(b) 分组到达路由器，入链路 CRC 校验通过，帧头和 CRC 被剥离，IP 数据报存入路由器内存等待转发。⭐ 在内存中停留期间发生位翻转（宇宙射线软错误、内存故障、软件 bug、NAT 改写出错）。出端口对已损坏的数据重新计算 CRC 并封装成新帧——这个新 CRC 是完全正确的。此后每一跳 CRC 都通过，损坏的数据一路畅通到达目的主机。

(c) ⭐ 端到端原则：逐跳的检查再强，也无法替代端到端的检查。二者不是冗余，是分工。（推论：TCP 校验和的漏检率约 10⁻⁵，在高速链路上意味着每几十 GB 就可能漏一个错，因此对完整性要求高的应用必须在应用层再做一次强校验——这又是同一条原则。）

题 27

(a) 设 N 个节点各以概率 p 在一个时隙发送。

某特定节点成功的概率 = p(1−p)^(N−1)     （它发且其余都不发）
任一节点成功的概率   = N·p(1−p)^(N−1)

对 p 求导取最大：p* = 1/N
代入：N × (1/N) × (1 − 1/N)^(N−1) = (1 − 1/N)^(N−1)
当 N → ∞：→ ⭐ 1/e ≈ 0.37

(b) 因为去掉时隙同步后 ⭐ 碰撞窗口加倍——一个帧不仅会与在同一时隙开始发送的帧碰撞，还会与在它之前一个帧时内开始、尚未发完的帧碰撞。成功概率因而多乘一个 (1−p)^(N−1)，最大效率变为 ⭐ 1/(2e) ≈ 18%。去掉同步这一个约束，效率减半。

(c) 因为 ⭐ 传播时延。节点 B 侦听时，节点 A 已经开始发送但信号还没传到 B，B 判断信道空闲并开始发送，碰撞发生。信道越长（传播时延越大）、帧越短，这个"侦听盲区"的相对影响越严重。

题 28

(a) 为了保证 ⭐ CSMA/CD 能够检测到碰撞。

最坏情况：A 和 B 在网络两端
时刻 0:    A 开始发送
时刻 τ−ε:  B 侦听（A 的信号还没到），开始发送 → 碰撞
时刻 τ:    碰撞信号开始向 A 传回
时刻 2τ:   ⭐ A 才检测到碰撞

⭐ 因此 A 必须至少持续发送 2τ 那么久，
   否则它发完就停止侦听，永远不知道自己的帧被撞坏了

对 10 Mbps 以太网：最大跨距下 2τ ≈ 51.2 μs，10 Mbps × 51.2 μs = 512 bit = 64 字节。减去 14 字节头部与 4 字节 CRC，数据部分最少 46 字节。

(b) ⭐ 网段长度会缩到几十米（因为速率提高 100 倍，同样的 512 比特只需 1/100 的时间，能覆盖的往返距离也缩到 1/100）。实际解决方案是 ⭐ 载波扩展（carrier extension），把最小帧扩到 512 字节。⭐ 但在全双工交换式以太网中碰撞根本不存在，这些机制都成了历史遗迹。

(c) 第 m 次碰撞后，从 {0, 1, ..., 2^m − 1} 中均匀随机选一个 K，等待 K × 512 比特时间后重试；m 上限为 10，连续 16 次后放弃。⭐ 它与 TCP 超时后的指数退避（第 13 讲）同构——两者都是「用观测到的拥挤程度自适应地调整退让力度」：碰撞/超时少说明竞争不激烈，等待短以保证低负载下的低时延；碰撞/超时多说明竞争激烈，指数扩大退让范围。

题 29

(a) ⭐ A 会 ARP 查询路由器接口 1（10.1.1.1）的 MAC。

不能查 B 的 MAC，两个原因：① ⭐ ARP 请求是广播帧，而路由器不转发广播——请求根本到不了 B 所在的子网；② 即使拿到 B 的 MAC 也没用，因为链路层的帧只能在本链路上传递，A 无法把帧直接送到另一个子网。

(b) A 发出的帧

目的 MAC: R1        （⭐ 路由器接口 1，不是 B！）
源   MAC: AA
目的 IP:  10.2.2.9  （⭐ B 的真实地址）
源   IP:  10.1.1.5

(c) R 从接口 2 发出的帧

目的 MAC: BB        （⭐ 变了）
源   MAC: R2        （⭐ 变了）
目的 IP:  10.2.2.9  （⭐ 完全没变）
源   IP:  10.1.1.5  （⭐ 完全没变）

(d) ⭐ IP 地址是端到端的（不变），MAC 地址是逐跳的（每一跳都换）。

题 30

(a)

事件 学习到的表项 查目的 MAC 动作 发往端口
① A→C (A, 1) C 不在表中 泛洪 2, 3, 4
② C→A (A,1)(C,3) A 在表中，端口 1 转发 1
③ B→D (A,1)(C,3)(B,2) D 不在表中 泛洪 1, 3, 4
④ D→B (A,1)(C,3)(B,2)(D,4) B 在表中，端口 2 转发 2
⑤ A→D 表已完整 D 在表中，端口 4 转发 4

(b) 事件 ① 和 ③ 发生泛洪。⭐ 原因：目的 MAC 尚未出现在交换机表中——交换机只能从"帧的源地址"学习，因此在某台主机第一次发送之前，交换机不知道它在哪个端口。

⭐ 关键观察：泛洪是自学习的必然代价，但它是一次性的——C 一旦回复（事件 ②），交换机就学到了 (C, 3)，之后再也不必为 C 泛洪。

(c) 集线器会把帧发到所有其他端口（2、3、4），不做任何过滤。三个后果：① B 和 C 会收到不属于它们的帧 → ⭐ 可以被嗅探；② 所有端口在同一个碰撞域，只能半双工，碰撞随主机数剧增；③ 总带宽被所有主机共享，而交换机的每个端口是独享的。这就是集线器被彻底淘汰的原因。

题 31

(a) k 端口交换机构成的 k-ary Fat-Tree：

主机数     = k³/4 = 24³/4 = 13824/4 = ⭐ 3456 台
核心交换机 = (k/2)² = 12² = ⭐ 144 台

⭐ 全部用同一种 24 口交换机搭成——这正是 Clos 拓扑「用规模换性能」的意义：不依赖任何高端设备。

(b)

200 ms / 100 µs = 200000 µs / 100 µs = ⭐ 2000 个 RTT

⭐ 一次超时白等约 2000 个往返时间，而这段时间链路很可能是空的。RTO 的下限是按广域网设定的，在数据中心里大了整整三个数量级——这是 incast 崩溃的核心。

(c) 因为快速重传依赖三个重复 ACK，而重复 ACK 需要丢包之后仍有后续分组到达接收方才会产生。

⭐ incast 场景下丢的是整个窗口——该流后面没有任何分组能到达接收方，也就产生不了任何 ACK。发送方处于完全静默中，除了等超时别无办法。

📌 对比：普通的单个分组丢失有后续分组继续到达，能凑出重复 ACK，所以走快速重传（第 13、16 讲）；整窗丢失只能等超时，这也是超时相比快速重传被视为「重度拥塞信号」的原因。

(d)

cwnd ← cwnd × (1 − α/2)

α = 被 ECN 标记的 ACK 占比的 EWMA 估计，α ∈ [0, 1]

α = 0.2 时：

cwnd ← cwnd × (1 − 0.1) = ⭐ cwnd × 0.9    只降 10%

对比标准 TCP：只要发生丢包就 cwnd ← cwnd × 0.5，⭐ 一律砍半，因为它只知道「丢了没丢」这一个比特。

⭐ 本质差别：标准 TCP 问「拥塞了吗」，DCTCP 问「拥塞多严重」，然后按比例响应。α → 1（全部被标记）时 DCTCP 退化为砍半，与标准 TCP 一致；轻微拥塞时它只做轻微退让，因而能把队列稳定维持在极低水平——既跑满带宽又几乎不排队。