Computer Networks 01: Architecture and Routing

一台电脑要把文件交给远处的服务器，最直接的办法是拉一根线。但如果每两台机器都要单独连接，$n$ 台机器就需要 $n(n-1)/2$ 条链路；如果所有机器共用一根线，它们又只能争抢同一份容量。我们需要一些中间节点，让许多通信复用同一张网络，同时还能在链路故障后换条路走。

这就引出了计算机网络的几个核心问题：数据怎样被拆开和转发？共享资源不足时怎么办？每个节点只知道局部信息，怎样共同找到一条正确的路径？当网络规模继续增长，又怎样避免每台路由器都记住每台机器？

这是 CS Revisited / Computer Networks 的第一篇。Computer Networks 会按主题持续分篇，本篇先建立架构与路由的基础。假设读者熟悉基本的数据结构、图和概率；协议术语会在用到时引入。本文覆盖 Berkeley CS 168 Fall 2026 第 1–4 周的七讲，按问题之间的依赖组织，也补充一些推导和协议细节。课程范围截至 2026-09-26 核对。(UC Berkeley CS 168, 2026)

从一条链路到一张网络

先把要传输的数据切成 packet。每个 packet 有 payload，以及告诉接收方如何处理它的 header。例如，目的地址回答“交给谁”，长度帮助划定边界；它们的意义并不依赖 payload 是图片还是文件。两个端点之间的一组相关 packet 常被称为 flow，具体如何识别取决于协议和讨论场景。

链路把 bit 从一个接口送到另一个接口。中间节点收到 packet 后，决定从哪个接口继续发送，这叫 forwarding。如果它按 IP 目的地址跨网络转发，我们称它为 router。它不用理解文件内容，但必须有一张“目的地 → 下一跳”的表。怎样获得这张表，是后面要解决的 routing。

Internet 的特别之处还在于：这些链路和路由器不属于同一个管理员。校园网、运营商和云网络有不同技术、成本和策略，却需要互相传递数据。因而协议不仅要能运行，还要允许独立部署、局部升级，以及在部分设备失效时继续工作。Internet 是连接这些网络的基础设施；Web 只是运行在它上面的一类应用。(UC Berkeley CS 168, n.d.)

Bandwidth 与 latency 是两件事

假设链路的发送速率为 $R$ bit/s，一个包长 $L$ bit。发送端每秒只能把 $R$ bit 放上链路，因此最后一个 bit 离开发送端需要

这叫 transmission delay，也常叫 serialization delay。发出去之后，信号还得走完距离 $d$；若传播速度为 $v$，这部分需要 $t_{\mathrm{prop}}=d/v$。从开始发送到最后一个 bit 到达，对一条空闲链路有

提高 $R$ 缩短的是把包放上线的时间，并不会让已经在线上的 bit 传播得更快。一个 1,500 byte 的包在 100 Mbit/s 链路上需要 $0.12$ ms 才能全部发出；若 propagation delay 为 5 ms，最后一个 bit 在 $5.12$ ms 到达。把带宽提高十倍，结果是 $5.012$ ms，而不是 $0.512$ ms。这里使用十进制 Mbit/s，并暂时忽略额外帧开销。(UC Berkeley CS 168, n.d.b)

如果路径包含三条这样的链路，且 router 必须收齐包才开始转发，即 store-and-forward，单包就需要三次 serialization：$3\times 5.12=15.36$ ms。实际路径还会增加处理时间和排队时间：

这里写 $L_i$ 是因为不同链路封装后的长度未必相同。Cut-through 可以在收齐之前开始转发，因而不能直接套用相同的 store-and-forward 模型。

分包怎样形成流水线

如果沿途 router 都必须等完整文件收齐才继续发送，那么前一个发送者忙完，后一个才能开始，链路利用率很低。分包之后，第一个包进入第二条链路时，第二个包已经可以进入第一条链路。

设有 $H$ 条等速链路，每条传播时间为 $p$，共发送 $N$ 个等长 $L$ bit 的包。假设没有交叉流量、处理开销或丢包。第一个包到达需要 $H(L/R+p)$；流水线填满后，后续每隔 $L/R$ 到达一个。因此最后一个包的完成时间是

在上面的三跳例子中，100 个包需要 $15+102\times 0.12=27.24$ ms，而不是 $100\times 15.36$ ms。第一包的 latency 和一长串包的 throughput 必须分别计算。分得更小可以更早启动下一跳，但也会增加 header 比例和每包处理次数，不能无限切小。

链路上同时能容纳多少 bit？发送端在一个传播时间内可以送入 $Rp$ bit，而它们还没到另一端；这就是单链路的 bandwidth-delay product。若 $R=100$ Mbit/s、$p=5$ ms，就是 500,000 bit，即 62.5 kB。

讨论发送窗口时，经常改用 带宽 × RTT。这是另一段时间：发送端要持续发送直到最早的数据得到反馈。若反馈时间约为 40 ms，要维持 100 Mbit/s，未确认数据量就得达到约 500 kB。两种 BDP 都有意义，但必须说明用的是单程传播时间还是反馈往返时间。

共享链路：为什么需要 queue

现在让三个用户共享 10 Mbit/s 链路，每人活跃时需要 4 Mbit/s，但并不一直发送。如果给每人永久预留峰值，总共需要 12 Mbit/s，第三人无法加入。可是三个人轮流活跃时，实际需求从来没有超过 4 Mbit/s。

区别在于：各自峰值之和，不等于合并后的峰值。若第 $i$ 个用户在时刻 $t$ 的速率为 $r_i(t)$，则

不等式可以取等号；只有峰值没有同时出现时，才有共享收益。Statistical multiplexing 利用的就是这种错开，而不是凭空增加容量。(UC Berkeley CS 168, n.d.a)

Circuit switching 与 packet switching

一种做法是在通信开始时申请资源，沿途建立 circuit，结束后释放。Circuit 可以用时隙、频段等资源承载，并不意味着一定要给每个用户铺一根物理线。准入成功后容量更可预测，但保留的份额可能在用户沉默时闲置，而且建立、拆除和故障恢复需要管理对应状态。

另一种做法是有包就发，链路一次为一个 packet 服务，即 packet switching。它在更细的粒度上共享容量，适合突发流量；代价是没有预留时，用户可能同时争用资源，需要排队甚至丢包。每包 header 和调度也有开销。

Circuit switching 也可以在“哪些会话此刻活跃”的层面复用资源；packet switching 则进一步利用一个会话内部的空闲间隔。这里比较的是两种典型设计，reservation 与 packet 的格式并非逻辑上互斥，分组网络也能实现资源预留。

故障恢复同样不同。普通 IP forwarding 可以在路由收敛后让后续包走新路径，不必为每个 flow 重新建立沿途 reservation。它并不保证恢复期间不丢包，也不保证应用不会因超时而终止。

平均负载低，仍然可能丢包

继续用三个用户的例子。假设在某个观察时刻，每个人以概率 $0.2$ 活跃，且三人独立。活跃人数 $K$ 服从 binomial distribution，平均需求只有 $3\times 0.2\times 4=2.4$ Mbit/s；但三人同时活跃时需求为 12 Mbit/s，超过链路容量，其概率为

这只是瞬时超载概率，不是丢包率。是否丢包还取决于超载持续多久、已有 backlog 以及 buffer 大小。独立性也是假设：同一热点事件可以让很多用户同时活跃。

为了吸收短暂超载，可以把来不及发送的 bit 放入 queue。设一个时间步内先加入 $A_k$ bit，再以容量 $C\mathrm{\Delta }$ bit 服务，无限 buffer 的离散模型是

它直接表达守恒：上一时刻没发完的，加上新来的，减去能服务的，剩下的不能为负。真实系统的到达与服务连续交错，但同一个收支关系仍然成立。

若输入连续 20 ms 保持 12 Mbit/s，输出为 10 Mbit/s，从空 queue 开始就会积累

突发末尾到达的包需要等待约 $Q/C=4$ ms，再加它自己的发送时间。如果之后输入变成 2 Mbit/s，净排空速率是 8 Mbit/s，排空需 5 ms；如果输入一直超过输出，任何有限 buffer 最终都会满。

因此 queue 能把短期速率不匹配转换为延迟，不能解决长期容量不足。可靠传输负责发现和补回缺失数据，congestion control 则负责控制送入网络的速率。只重传而不控制负载，会把更多工作塞进已经忙不过来的链路。

Layering：每一层承诺什么

发送 bit、在一个局部网络内交付、跨网络交付、给应用提供可靠数据，这些任务可以分开。分层的价值是让上层依赖一个较稳定的 service interface，而不用知道下层每一个实现细节。(UC Berkeley CS 168, n.d.c)

这里保留常用 OSI 层号，所以 L4 后面直接是 L7；session 和 presentation 的功能并非消失了，而是未必由单独的协议层实现。

Protocol 和 interface 也不同。 Interface 是同一台机器上相邻层之间的服务约定；protocol 是不同节点上的同层实体怎样交换消息的约定。后者不仅规定 byte 格式，还规定状态与动作：收到请求、重复包、错误消息或超时，下一步分别做什么。只定义一个 header struct，还没有定义完整协议。

一个包经过 router 时，什么会变化

假设主机 A 通过 Ethernet 把一个 TCP segment 交给 router，再通过另一条链路送往主机 B。应用数据在发送端向下封装：TCP 加入端口与序号等信息，IP 加入地址，Ethernet 再加入当前局部交付需要的 header 和 trailer。

router 先处理入站链路封装，再根据 IP 目的地址选出下一跳，最后添加适用于出站链路的新封装。对一次 IP hop，frame 的目的地址是下一跳接口，不一定是最终服务器；中间如果有多个 L2 switch，它们可以继续在同一个局部网络里转发该 frame。跨 L3 hop 才重新组织相应的链路封装。(UC Berkeley CS 168, n.d.b)

IP header 也不是永远原样保留：例如 IPv4 router 转发时会递减 TTL，并相应更新 IPv4 header checksum。这里假设没有 NAT、隧道或 proxy，源和目的 IP 地址保持不变。普通转发不需要终止 TCP 连接；router 运行自己的管理和路由协议时，则也会作为通信端点使用高层协议。(Baker, 1995)

到达 B 之后，OS 需要把数据分给正确的 socket。Transport port 是逻辑编号，不是 router 上插网线的物理 port。多个 TCP 连接可以共用服务器的 443 端口，连接还要结合两端地址与端口区分；不能把“端口号”简单等同于某个全局唯一进程。

为什么中间只约定 IP

如果每一种应用都得认识每一种底层链路，两侧的组合会迅速膨胀。让所有参与者共同支持 IP 的交付接口，就可以把问题拆开：新应用建在 IP 之上，新链路提供承载 IP 的方式。

这就是 narrow waist。它用一个共同服务把多种上层和多种下层接起来，而这个共同服务是 best-effort datagram delivery：允许丢失、重排和重复，不承诺固定带宽或交付期限。TCP 可以在这个基础上提供可靠有序 byte stream；UDP 保留 datagram 接口，不替应用实现可靠交付。(UC Berkeley CS 168, n.d.f)

Best-effort 不是“不用认真传”，而是接口不作那些保证。把所有应用都强制放进可靠、有序、固定速率的服务，可能给实时数据增加不需要的等待，也使底层接入门槛变高。相应代价是上层必须承担更多工作。

共同接口也有升级成本：改变网络层需要多个独立参与者配合。IPv4 和 IPv6 是 IP 的两个版本，不能把“窄腰”理解为现实里只有唯一一种 header。

End-to-End：正确性应在哪个边界成立

文件上传的目标如果是“服务器已经保存了完整文件”，那么逐跳确认是否足够？

即使每条链路都能确认收包，最后一个 router 后面的主机仍可能在写文件时失败。即使 TCP 已经确认 byte 到达，对端应用也可能还没完成校验或持久化。低层确认停在它能观察的边界，不能自动证明更高层的目标。

所以应用需要定义自己的成功条件，例如校验最终内容，并在持久化成功后返回结果。这是 Saltzer、Reed 和 Clark 的 end-to-end argument：如果某个功能的完整正确性需要端点掌握的信息，那么低层实现不能替代端点的责任。(Saltzer et al., 1984)

这并不排斥链路重传。设一个教学模型有 10 跳，每次尝试独立地以概率 $p=0.1$ 丢包，忽略 ACK 丢失。不作局部重传时，一次端到端尝试失败的概率是 $1-(1-p{)}^{10}\approx 65.1\mathrm{\%}$。若每跳最多尝试三次，单跳失败率降为 $p^3$，整条路径失败率约为 $1-(1-p^3{)}^{10}\approx 1.0\mathrm{\%}$。局部恢复可以明显减少跨整条路径重传的浪费，但会消耗链路时间，并可能延迟后续包。

要区分三种判断：“低层能否独立把功能做完整”“端点能做时低层是否还必要”“低层实现能否带来值得的性能收益”。它们可能给出不同结论。拥塞点上的优先级调度需要控制那个拥塞点；不能仅因偏爱端到端设计，就假设发送端能替沿途 router 完成调度。

另一条相关原则是 fate sharing：把通信赖以继续的关键状态放在依赖它的端点，使中间 router 的故障不必毁掉会话状态。端点若保存未确认数据，换路之后仍有机会继续传输。这里说的是关键会话状态，不是“router 没有状态”；forwarding table、queue 和邻接关系都是状态。Clark 对 Internet 的历史设计分析把故障后的继续通信放在很高的优先级，成本、易接入与资源核算则排在较后。(Clark, 1988)

这些选择不是所有时代的唯一答案。防火墙、NAT 和 proxy 反映了运营者的控制需求，也重新引入路径中的状态依赖。理解架构，要同时看它保住了什么性质，以及把哪些责任留给了别人。

Routing：局部决定如何组成全局路径

现在假设 packet 的目的地址已经确定。每个 router 只做一次 table lookup，就把包交给邻居。但所有 router 的选择拼在一起，真的能把包送到目的地吗？

把网络记为有限图 $G=(V,E)$，链路代价为 。暂时只研究单一管理域内、可加代价的 unicast routing；目的节点记为 $d$。每个其他节点保存一个 next hop $f_d(u)$。这个模型不包含策略路由或多下一跳，后面会说明它的边界。(UC Berkeley CS 168, n.d.g)

先谈有效，再谈最短

如果 A 认为 B 知道路，而 B 认为 A 知道路，两个局部表项看起来都合法，合起来却产生 loop。如果某个节点没有下一跳，就形成 dead end。到达目的节点后正常停止不算 dead end。

在固定拓扑、固定单下一跳表、无传输丢失的模型中，对能到达 $d$ 的节点，路由有效当且仅当没有 loop，也没有目的地以外的 dead end。充分性很简单：既不能停，也不能重复访问节点，有限个节点最终只能在 $d$ 结束。它说明的是 forwarding state 的性质，不承诺现实中的每个 packet 都不丢。

把每个节点指向自己的 next hop，得到一棵指向 $d$ 的 delivery tree。一旦两条路径相遇，后续路径就相同，因为节点只按目的地作出同一个决定。每个目的地可以有不同的树；不是整张 Internet 只有一棵 spanning tree。

有效路径不一定代价最小。假设下面所有边双向、代价对称，D 是目的节点。

A 可以直接以代价 7 到 D，也可以经 B、C，以 $1+1+2=4$ 到 D。注意我们选择的是总代价最小，不是 hop 数最少。链路 cost 是人为选定的 metric；可以近似传播延迟或表达管理偏好，但链路 bandwidth 通常不能直接相加作为路径 throughput。

一个能排除环的量

设 $D(u)$ 是从 $u$ 到 D 的真实最短距离。若 u 选择了某条最短路径上的邻居 v，那么

由于 cost 严格为正，沿每一跳都有 。距离不断下降，就不可能绕一圈回到原点。这是后面两类 routing algorithm 共同依赖的性质。

但这个证明用的是同一张图上的真实距离。故障期间，不同 router 保存的可能是不同时间的估计；不能看到每台机器都执行“最短路算法”，就认定整个系统此刻无环。

Control plane 与 data plane

Data plane 负责把当前 packet 按表转发，工作发生在每次收包时。Control plane 负责发现邻居、交换可达性、计算路由并更新表，时间尺度由事件与定时器驱动。静态路由由管理员配置，directly connected route 可以从接口配置获得，动态路由再传播其他可达性。

这里主要讨论 intra-domain routing，一个管理者可以约定共同 metric。跨管理域的 inter-domain routing 还涉及商业关系和出口策略，不能简单化成全球统一最短路。BGP 属于后一类问题的主要协议，也能用于域内场景；它的 path-vector 思想与下面的 distance-vector 有联系，但选择目标不同。

Distance Vector：只告诉邻居“我离目的地多远”

如果 A 不知道整张图，能不能仍然作出正确决定？假设每个邻居愿意报告它到 D 的距离。A 要经 B 去 D，必须先支付 A–B 的代价，再承担 B 后面的路程。对所有邻居比较，便得到 Bellman equation：

这不是要求 A 拿到完整路径；A 只需要邻居的距离，以及自己到邻居的 cost。每个目的地重复一次，就是一个 distance vector。Distributed Bellman–Ford 让 router 不断交换估计并更新它们。(UC Berkeley CS 168, n.d.b)

在同一张图上算一遍

先用同步轮次方便观察：初始化时只有 D 知道自己的距离为 0，其他节点为 $\mathrm{\infty }$；第 $k$ 轮只读取上一轮邻居的结果。

例如第二轮 A 比较 $1+5$ 与 $7+0$，得到 6；它此时还不知道 B 已经能用代价 3 到 D。下一轮 B 的新消息到达，A 才得到 4。可达性消息从目的地方向往外传播，而 data packet 沿 next hop 往回走。

为什么这种迭代能得到最短路？初始化只知道零条边的路径。做一次邻居扩展，就能考虑多一条边的路径。因此第 $k$ 轮得到的是至多经过 $k$ 条边的最短距离。正权图的最短路不需要重复节点，最多 $|V|-1$ 条边，故这个同步模型在这么多轮内完成。

真实网络没有全局轮次。消息可能延迟、乱序或丢失，router 收到更新就可以计算。静态拓扑下，从上述初始化出发，若邻居更新最终持续得到传递、节点持续处理，信息仍会逐步传开；但“$|V|-1$ 轮”不是现实中的毫秒级收敛上界。

为什么不能只接受更短的路

现在让 C–D 断开。B 原来选择 C，距离为 3。如果只接受更小的值，C 报告自己已不可达时，B 会因为 而拒绝更新，永远保留坏路。

因此必须保存 route 的来源：当前 next hop 的更新，即使变差，也必须影响当前路线。 一种完整状态模型是保存每个邻居对每个目的地的最新有效报告 ${\hat{D}}_v(d)$，然后重新计算

这样原路线变差时，还能比较缓存的其他候选路线。节省状态的教学实现可以只存当前最佳 next hop、cost 和 expiry time：收到更优路线就替换，收到当前 next hop 的报告则接受变好或变差；换路时未缓存的候选要等邻居再次通告。两种实现不要混成同一套存储假设。

消息本身也可能丢失，所以只在变化时发送还不够：triggered update 缩短等待，periodic update 提供再次传播的机会。若一直没有收到支撑当前路线的新报告，就让 route 过期；这个 route timer 与数据包的 IP TTL 是两个不同机制。

过期后若只静默删除，依赖自己的邻居还会继续转发一段时间。可以主动通告该目的地距离为 $\mathrm{\infty }$，即 route poisoning，加快坏消息传播。这里的含义是“我已经没有有效路线”，而不是网络全局一定不可达。

坏消息为什么会兜圈子

另看一个更小的网络：D–A–B，两条边 cost 都是 1，没有其他出口。收敛后 A 到 D 为 1，B 经 A 到 D 为 2。

假设没有 split horizon，且断链消息尚未送达 B。D–A 断开后，A 收到 B 先前发出的“我到 D 的距离是 2”，于是把 B 当作备用出口，更新为 3。但 B 的那条路本来就依赖 A。

问题不在加法，而在报告缺少路径依赖信息。“B 有一条长为 2 的路线”，没有告诉 A 这条路线经过 A 自己。于是旧信息可以被不断加工成新通告，形成 count to infinity。

Split horizon 与 poison reverse

既然 B 的路线来自 A，就没有理由把它作为 A 的备选出口。Split horizon 让 B 不再向 A 通告这条路线。Poison reverse 更明确：B 仍向 A 通告，但报告 $\mathrm{\infty }$，意思是“你不能通过我到这个目的地”。B 向其他邻居仍可报告真实距离 2。

这与 route poisoning 不同：前者是按接收邻居调整通告，B 自己仍有路；后者是自己的 route 已失效。显式 poison reverse 还能比静默等待 expiry 更快地拆掉某些已有的二节点相互依赖。

但它们没有携带完整路径。若依赖是 A 经 B、B 经 C、C 经 A，每个人只对自己的 next hop 报 $\mathrm{\infty }$，仍可能沿另一个方向循环传播有限距离。因此不能把 poison reverse 当作任意拓扑无环的证明。RIP 的讨论也明确包含多节点环与计数问题。(Malkin, 1998)

RIP 把 metric 16 定义为不可达，允许的有限 hop count 最多为 15。这样坏消息计数到一个有限上限就停止；它同时限制了能表示的路径长度。16 是 RIP 的工程取舍，不是所有 DV 协议共享的数学常数，更不是 packet TTL。

Link State：先共享地图，再各自算路

DV 隐藏了路径细节。如果每个 router 改为通告“我和谁相邻、代价是多少”，所有节点最终就能拼出拓扑。然后每个节点独立计算最短路，把第一跳写入自己的 forwarding table。这是 link-state 的基本分工。(UC Berkeley CS 168, n.d.g)

怎样获得一张不会被旧消息覆盖的地图

先用 hello 或接口状态发现邻居；若长期失联，按协议规则宣告邻接变化。接着把本地 link state 发给邻居，邻居再继续扩散，即 flooding。

直接转发每个收到的副本会在有环图里不断放大消息，因此需要让一个节点知道“这个版本我已经处理过了”。给通告加入 origin 和该 origin 的 sequence number，接收方保存已知版本，只在收到更新版本时替换并继续传播。不同 origin 的 sequence number 不需要互相比较，也不需要一只全网同步的时钟。

然而“只传播新版本”也带来问题：某个邻居丢了第一次发送，后面重复包又被抑制，它如何补齐？因此可靠 flooding 还需要确认、重传或数据库同步；周期刷新和 age 则处理长期失效信息。OSPF 的 LSA 具有类型、标识、发布者、sequence number、checksum 和 age 等字段，邻接建立时也有数据库交换。它比“给每条边配一个全局时间戳”更具体。(Moy, 1998)

重启与序号回绕同样不能忽略：如果节点重启后从 0 开始，而别人保存着旧的大序号，新消息会被误判为旧版本。实际协议必须规定状态恢复、老版本清除与版本生命周期。

Dijkstra 为什么每次固定最小的候选

有了地图，从 A 开始求最短路。初始只有 A 的距离确定为 0；它的邻居得到候选距离 B=1、D=7。现在选候选距离最小的 B。为什么 B 可以直接定下来？

任何尚未探索的替代路径，都得先离开已经确定的集合。如果它的第一处未确定节点的候选距离已经不小于 B，后面再加非负 cost，也不可能绕一圈得到更便宜的 B。于是最小候选可以固定，然后用它去改善邻居的候选距离。

最终 A 到 D 的路径仍是 A–B–C–D，第一跳为 B。前驱用于还原路径；forwarding table 不必保存整条路径。

用邻接表和 binary heap，一次单源计算的常见复杂度为 $O((|V|+|E|)\log |V|)$；简单数组实现则可达 $O(|V{|}^2)$。这只是本地计算代价，未包含探测、flooding 与安装 forwarding state 的时间。

地图一致，不代表更新同时完成

假设 A–B cost 为 1，B–D 为 1，A–D 为 5。故障前 A 经 B 到 D；B–D 断开后，B 先获知故障，选择经 A 到 D。但 A 还在用旧表，把 D 的包交给 B，于是暂时出现 A–B loop。

B 在新图上、A 在旧图上，各自都算对了最短路，但它们拼起来不对。即使控制数据库已经收敛，不同时间安装新 forwarding table 也可能产生类似的 microloop。收敛至少经历故障检测、信息传播、本地计算和表项安装，不能只计 Dijkstra 的运行时间。

在统一拓扑、共同 metric 和正 cost 下，每个合法最短路 next hop 都使真实剩余距离下降，因此不会有环。相同 tie-breaking 有利于得到可复现的单路径选择；但对这个正权条件下的无环证明，并不要求所有节点以同一方式打破平局。

若支持 equal-cost multipath（ECMP），一个目的地可以对应多个合法 next hop，delivery tree 相应推广成 DAG。这里仍要求每条可选边都使距离严格下降；只有“每个节点觉得这条路不错”不够。零代价边会破坏严格下降，需要额外约束。

LS 不会因为“共享地图”就变成集中式算法，也不是没有环、没有协议状态的免费方案。两类方法最终都要在有限带宽、消息丢失与网络变化之间维护可用的路由。

Addressing：不要让每台 router 记住每台主机

到目前为止，A、B、C、D 都是短标签。如果把每个真实接口都当作独立目的地，forwarding table 会随所有目的地增长，每次加入或离开也可能带来远处更新。一个自然的压缩办法是：去往同一个区域、具有相同转发动作的目的地，共用一条记录。

因此地址最好带有可聚合的结构。名字回答“我想找谁”，地址提供网络交付所需的定位信息；DNS 负责名字到地址等记录的解析。IP 地址通常绑定接口，一个设备可以有多个地址；服务也能通过多个地址提供，不应把地址当成永不变化的个人身份。

从固定边界到 CIDR

IPv4 地址有 32 bit。如果固定用前 8 bit 表示网络，剩下 24 bit 表示网络内部位置，最多只能划出 256 种前缀，每个块又很大。Classful addressing 曾用不同类别提供不同尺寸：Class A、B、C 的传统边界分别是 /8、/16、/24，其开头的类别 bit 决定解释方式。

但一个需要约 450 个接口地址的网络，/24 太小，/16 又浪费很多。CIDR 直接在地址旁标明 prefix length，允许边界落在任意 bit，而不是只在预设类别之间选择。一个 /23 有 $2^{32-23}=512$ 个地址，比 /16 的 65,536 个更合适。总地址数不等于所有场景下可分配的 host 数；传统 IPv4 broadcast subnet 通常还保留 network 和 broadcast 地址。(UC Berkeley CS 168, n.d.a)

例如 192.0.2.0/23 固定前 23 bit，netmask 为 255.255.254.0，覆盖 192.0.2.0 到 192.0.3.255。地址 $x$ 属于某个前缀，当且仅当

其中 $m$ 是高位连续为 1 的 mask，$p$ 是主机位清零后的 network prefix， 表示按 bit AND。本文地址与分配仅用于演算，不表示真实可用的公网配置。

聚合需要地址对齐，也需要转发语义一致

192.0.2.0/24 和 192.0.3.0/24 的前 23 bit 相同，刚好是同一个 /23 的两个子块；在相同转发动作下，可以用一条 /23 代替。192.0.3.0/24 与 192.0.4.0/24 虽然数字相邻，却不是同一个 /23 的两个子块，不能按同样方法合并。

地址分配因此常呈层级：较大地址块向下分配给运营者和站点，站点再分配给 subnet。外部只需知道聚合前缀，内部的每次主机变化便不必传播到外部。不过，前缀、物理地点和 Autonomous System 不是一一对应的；多出口和策略会产生例外。CIDR 的作用同时包括减少地址浪费和支持路由聚合。(Fuller & Li, 2006)

为什么用 longest prefix match

假设一张 forwarding table 如下：

192.0.2.8 走 P；192.0.3.9 走 Q；192.0.3.42 走 R。它们都匹配默认路由，但更具体的范围表达了对较大聚合的修正，故采用 longest prefix match（LPM），即固定 bit 最多的匹配项。

这允许一个站点在大聚合之外，因 multihoming 再发布更具体的路线。代价是更具体前缀增多，聚合压缩效果下降。LPM 是 data-plane lookup 规则；同一前缀的多个候选 route 怎样按策略、metric 选择，是 control-plane 问题。前缀更长也不等于路径更短。

聚合还需要处理“洞”。如果 P 宣告整个 /23，但其中某个 /24 已没有有效内部路线，不能盲目把这些包再按默认路由送回提供该聚合路线的上游，否则可能循环。发布聚合的 router 需要相应的 discard/reject 行为，让没有更具体有效路线覆盖的聚合内部地址停止转发；不能把宣告大块范围当成对其中每个地址都可达的证明。

IPv6 改变了容量，没有取消层次

IPv6 把地址扩展到 128 bit，以十六进制组表示。例如 2001:db8:0:1::42，其中 :: 压缩一段连续的全零组，同一地址中只能这样压缩一次。前缀仍然用 /n 表示，最长前缀匹配和层次聚合仍有意义。它也有自己的 packet header 和 Hop Limit；不能只把 IPv4 地址字段直接拉长。(Deering & Hinden, 2017; Hinden & Deering, 2006)

常见 IPv6 LAN 使用 /64。SLAAC 下，主机可以根据 router advertisement 提供的可用前缀与本地生成的 interface identifier 形成地址，并进行 duplicate address detection。它并不让主机随意挑选一个全球可路由前缀；地址空间巨大也不取消分配与可达性管理。(Thomson et al., 2007)

过渡的困难来自协议与部署：端点、沿途网络和应用支持必须配合。Dual stack 让节点同时运行 IPv4、IPv6；tunneling 可以把一种协议承载在另一种上；NAT64 等机制则在特定场景中进行转换。转换存在，并不意味着两个协议天然兼容或所有通信都能无条件透明转换。(Bagnulo et al., 2011)

Traceroute：从返回的错误消息观察路径

我们已经知道 forwarding table 决定下一跳，但普通主机看不到沿途的表。能否只发一些 packet，间接知道它们走到了哪里？

IPv4 TTL 在转发时减少，耗尽后 router 丢弃 packet，通常发回 ICMP Time Exceeded。于是可以让第一个 probe 的 TTL=1，在第一跳到期；第二组设为 2，在第二跳到期；再逐渐增大。每次回复的外层源 IP 提供一个回应接口的地址，往返时间来自 probe 发出到对应回复到达的时间。(Baker, 1995)

经典 UDP traceroute 向目的端一个预计未开放的端口发送 probe。若抵达目的端并得到 ICMP Destination Unreachable / Port Unreachable（IPv4 type 3、code 3），就可以识别终点。其他 unreachable code 可能表示沿途失败，不能一概视为成功抵达。TCP 或 ICMP probe 的结束条件不同。CS 168 前四周的 Traceroute 项目还要求处理延迟、重复和无关回复。(UC Berkeley CS 168, 2026b)

为了把回复归属到正确 probe，不能只看回复源地址。ICMP 错误会引用触发错误的原始 IP header 和一部分 payload；解析其中的协议、目的地址和 UDP 端口等字段，可以匹配本轮 probe。IPv4 header 长度由 IHL 指定，不能把“总是 20 byte”写死。还要先验证实际收到的长度与消息类型，忽略截断、重复、其他目的地以及前一轮迟到的回复。

一个稳健的探测循环是在每个 TTL 下发送带可识别信息的 probes，接收至本轮 deadline，只记录匹配且尚未记录的响应，然后再进入下一轮。用 deadline 而非“必须凑齐三个回复”，才能在丢包时结束等待；也不能让任意迟到消息重置无限等待。

把一个包的旅程接起来

现在回到开头的文件传输。应用通过名字找到地址，选定 transport endpoint，把数据交给传输层。传输层按自身语义组织数据；IP 为跨网络交付提供共同格式；每一跳的 link layer 再为当前局部传输封装 frame。

链路发送耗费 serialization 和 propagation 时间，共享链路还会排队。router 用当前 forwarding table 选择下一跳；这些表来自静态配置、直连信息和路由协议。DV 交换距离估计，LS 交换邻接状态，二者都必须面对陈旧信息。层级地址把许多目的地折叠成前缀，而更具体的前缀保留必要例外。

到达服务器之后，网络交付的成功还要继续向上解释：byte stream 完整了吗，文件校验通过了吗，内容持久保存了吗？这里自然接上后续的 reliable transport、congestion control 和应用协议。想先看这些机制如何影响 QUIC、WebRTC 与 RPC，可以继续读现代通信协议。

References