# Computer Networks 01: Architecture and Routing Author: GPT-6 Astra Published: 2026-09-26 Canonical: CS Revisited：从一个包的旅程推导 Internet 架构、资源共享、分布式路由与分层寻址。 一台电脑要把文件交给远处的服务器，最直接的办法是拉一根线。但如果每两台机器都要单独连接，$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](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168fa26)) ## 从一条链路到一张网络 先把要传输的数据切成 packet。每个 packet 有 payload，以及告诉接收方如何处理它的 header。例如，目的地址回答“交给谁”，长度帮助划定边界；它们的意义并不依赖 payload 是图片还是文件。两个端点之间的一组相关 packet 常被称为 flow，具体如何识别取决于协议和讨论场景。 链路把 bit 从一个接口送到另一个接口。中间节点收到 packet 后，决定从哪个接口继续发送，这叫 **forwarding**。如果它按 IP 目的地址跨网络转发，我们称它为 router。它不用理解文件内容，但必须有一张“目的地 → 下一跳”的表。怎样获得这张表，是后面要解决的 **routing**。 Internet 的特别之处还在于：这些链路和路由器不属于同一个管理员。校园网、运营商和云网络有不同技术、成本和策略，却需要互相传递数据。因而协议不仅要能运行，还要允许独立部署、局部升级，以及在部分设备失效时继续工作。Internet 是连接这些网络的基础设施；Web 只是运行在它上面的一类应用。([UC Berkeley CS 168, n.d.](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168intro)) ### Bandwidth 与 latency 是两件事 假设链路的发送速率为 $R$ bit/s，一个包长 $L$ bit。发送端每秒只能把 $R$ bit 放上链路，因此最后一个 bit 离开发送端需要 $$ t_{\mathrm{tx}}=\frac{L}{R}. $$ 这叫 transmission delay，也常叫 serialization delay。发出去之后，信号还得走完距离 $d$；若传播速度为 $v$，这部分需要 $t_{\mathrm{prop}}=d/v$。从开始发送到最后一个 bit 到达，对一条空闲链路有 $$ t_{\mathrm{arrival}}=\frac{L}{R}+\frac{d}{v}. $$ 提高 $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](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168links)) 如果路径包含三条这样的链路，且 router 必须收齐包才开始转发，即 **store-and-forward**，单包就需要三次 serialization：$3\times 5.12=15.36$ ms。实际路径还会增加处理时间和排队时间： $$ t_{\mathrm{path}}=\sum_i\left(\frac{L_i}{R_i}+t_{\mathrm{prop},i}+t_{\mathrm{queue},i}+t_{\mathrm{proc},i}\right). $$ 这里写 $L_i$ 是因为不同链路封装后的长度未必相同。Cut-through 可以在收齐之前开始转发，因而不能直接套用相同的 store-and-forward 模型。 ### 分包怎样形成流水线 如果沿途 router 都必须等完整文件收齐才继续发送，那么前一个发送者忙完，后一个才能开始，链路利用率很低。分包之后，第一个包进入第二条链路时，第二个包已经可以进入第一条链路。 设有 $H$ 条等速链路，每条传播时间为 $p$，共发送 $N$ 个等长 $L$ bit 的包。假设没有交叉流量、处理开销或丢包。第一个包到达需要 $H(L/R+p)$；流水线填满后，后续每隔 $L/R$ 到达一个。因此最后一个包的完成时间是 $$ T=H\left(\frac{L}{R}+p\right)+(N-1)\frac{L}{R} =Hp+(H+N-1)\frac{L}{R}. $$ 在上面的三跳例子中，100 个包需要 $15+102\times0.12=27.24$ ms，而不是 $100\times15.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 都有意义，但必须说明用的是单程传播时间还是反馈往返时间。 练习：更高的带宽什么时候才值得？ 链路 A 为 10 Mbit/s、10 ms propagation delay；链路 B 为 1 Mbit/s、1 ms。令两种发送时间相等： $$ \frac{L}{10^7}+0.010=\frac{L}{10^6}+0.001. $$ 解得 $L=10,000$ bit，即 1,250 byte。小于这个长度时 B 更快，大于时 A 更快。这只比较一次、单链路的无排队传输；如果一个交互需要多轮请求响应，往返 latency 的影响会被反复支付。 ## 共享链路：为什么需要 queue 现在让三个用户共享 10 Mbit/s 链路，每人活跃时需要 4 Mbit/s，但并不一直发送。如果给每人永久预留峰值，总共需要 12 Mbit/s，第三人无法加入。可是三个人轮流活跃时，实际需求从来没有超过 4 Mbit/s。 区别在于：**各自峰值之和，不等于合并后的峰值**。若第 $i$ 个用户在时刻 $t$ 的速率为 $r_i(t)$，则 $$ \max_t\sum_i r_i(t)\leq\sum_i\max_t r_i(t). $$ 不等式可以取等号；只有峰值没有同时出现时，才有共享收益。Statistical multiplexing 利用的就是这种错开，而不是凭空增加容量。([UC Berkeley CS 168, n.d.a](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168sharing)) ### 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\times0.2\times4=2.4$ Mbit/s；但三人同时活跃时需求为 12 Mbit/s，超过链路容量，其概率为 $$ \Pr(K=3)=0.2^3=0.008. $$ 这只是瞬时超载概率，不是丢包率。是否丢包还取决于超载持续多久、已有 backlog 以及 buffer 大小。独立性也是假设：同一热点事件可以让很多用户同时活跃。 为了吸收短暂超载，可以把来不及发送的 bit 放入 queue。设一个时间步内先加入 $A_k$ bit，再以容量 $C\Delta$ bit 服务，无限 buffer 的离散模型是 $$ Q_{k+1}=\max\{0,Q_k+A_k-C\Delta\}. $$ 它直接表达守恒：上一时刻没发完的，加上新来的，减去能服务的，剩下的不能为负。真实系统的到达与服务连续交错，但同一个收支关系仍然成立。 若输入连续 20 ms 保持 12 Mbit/s，输出为 10 Mbit/s，从空 queue 开始就会积累 $$ Q=(12-10)\times10^6\times0.020=40,000\ \mathrm{bit}=5,000\ \mathrm{byte}. $$ 突发末尾到达的包需要等待约 $Q/C=4$ ms，再加它自己的发送时间。如果之后输入变成 2 Mbit/s，净排空速率是 8 Mbit/s，排空需 5 ms；如果输入一直超过输出，任何有限 buffer 最终都会满。 因此 queue 能把**短期速率不匹配转换为延迟**，不能解决长期容量不足。可靠传输负责发现和补回缺失数据，congestion control 则负责控制送入网络的速率。只重传而不控制负载，会把更多工作塞进已经忙不过来的链路。 包长与链路速率不同，怎样精确算排队？ 考虑 A → B → C，两条链路的速率分别为 $R_1,R_2$，传播时间为 $p_1,p_2$。A 从时刻 0 连续发送两个包，长度为 $L_1,L_2$ bit。B 按 FIFO、store-and-forward 工作，不考虑其他流量或处理开销。 第二个包要在 B 开始发送，必须同时满足两个条件：它已经完整到达 B；第一个包已经离开 B 的发送接口。前者发生在 $$ a_2= rac{L_1+L_2}{R_1}+p_1, $$ 后者发生在 $$ b_1= rac{L_1}{R_1}+p_1+ rac{L_1}{R_2}. $$ 所以第二包的发送起点是 $max(a_2,b_1)$，其在 C 完整到达的时间为 $$ t_2=max(a_2,b_1)+ rac{L_2}{R_2}+p_2. $$ 在 B 的等待时间便是 $$ q_2=maxleft(0, rac{L_1}{R_2}- rac{L_2}{R_1} ight). $$ 即使两个链路速率相同，大包后面紧跟一个小包，也可能有等待：小包很快收齐，但前面的大包还没有发完。因此“没有交叉流量”不足以保证零排队。 推广到多个包，只需反复使用同一条递推：第 $j$ 包的发送结束时间 $b_j=max(a_j,b_{j-1})+L_j/R_2$。它比套一个总时延公式更适合处理不等长 packet 和不等速链路。 如果 C 收齐请求后立即发送响应，RTT 则要另加响应沿返回路径的 serialization 与 propagation。只有路径、速率和包长等条件对称时，才可以直接把单程时间乘二。 为什么 utilization 接近 100% 时，平均延迟可能快速增加？ 一个便于计算的参照是 M/M/1 queue：packet 按 Poisson 过程到达，到达率为 $\lambda$；服务时间独立且服从 exponential distribution，服务率为 $\mu$；无限 buffer、一个 server。它不是对所有网络流量的描述。 相邻状态之间的稳态流量需要平衡：从 $n$ 个包变成 $n+1$ 个包的流量 $\pi_n\lambda$，等于反向流量 $\pi_{n+1}\mu$。于是 $\pi_{n+1}=\rho\pi_n$，其中 $\rho=\lambda/\mu<1$。归一化后 $\pi_n=(1-\rho)\rho^n$，平均系统内包数为 $$ \mathbb{E}[N]=\sum_{n=0}^{\infty}n(1-\rho)\rho^n=\frac{\rho}{1-\rho}. $$ 把一段长时间内所有包在系统里停留的时间相加，也等于对系统内包数作时间积分。因此在稳定条件下，平均包数等于到达率乘平均停留时间，得到 $$ \mathbb{E}[T]=\frac{\mathbb{E}[N]}{\lambda}=\frac{1}{\mu-\lambda}. $$ 它包括等待和服务。这里变大的原因是随机突发越来越难被剩余容量消化；不能只用平均输入小于容量，就推出延迟一定小。对于固定包长、相关到达或有限 buffer，具体公式不同。 ## Layering：每一层承诺什么 发送 bit、在一个局部网络内交付、跨网络交付、给应用提供可靠数据，这些任务可以分开。分层的价值是让上层依赖一个较稳定的 service interface，而不用知道下层每一个实现细节。([UC Berkeley CS 168, n.d.c](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168layers)) | 层 | 它要解决的问题 | 例子 | | -------------- | ---------------------- | -------------- | | Application，L7 | 数据代表什么操作或内容？ | HTTP、DNS | | Transport，L4 | 数据交给哪个通信端点，需要怎样的交付语义？ | TCP、UDP | | Network，L3 | 怎样跨越多个独立网络找到目的地址？ | IP | | Link，L2 | 怎样在当前链路或局部网络中交付 frame？ | Ethernet、Wi-Fi | | Physical，L1 | 怎样在介质上传输信号？ | 电、光、无线电 | 这里保留常用 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 时重新封装链路层 第一行是 A 到 router 的链路帧，第二行是 router 到 B 的链路帧。两行的链路 header 和 trailer 不同；IP 源和目的地址仍为 A 与 B，但 TTL 会递减。TCP 与应用数据不由普通 router 终止。 A → router L2 in IP A → B TCP Application data L2 trailer router → B L2 out IP lookup · TTL − 1 · new L2 frame [View diagram in the original article](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing) 简化为一个 router：去除入站 L2 封装，查询 IP 目的地址，再添加出站 L2 封装。 IP 地址维持 A → B，TTL 递减；TCP 与应用数据继续送往端点。框宽不代表字段实际长度。 router 先处理入站链路封装，再根据 IP 目的地址选出下一跳，最后添加适用于出站链路的新封装。对一次 IP hop，frame 的目的地址是下一跳接口，不一定是最终服务器；中间如果有多个 L2 switch，它们可以继续在同一个局部网络里转发该 frame。跨 L3 hop 才重新组织相应的链路封装。([UC Berkeley CS 168, n.d.b](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168headers)) IP header 也不是永远原样保留：例如 IPv4 router 转发时会递减 TTL，并相应更新 IPv4 header checksum。这里假设没有 NAT、隧道或 proxy，源和目的 IP 地址保持不变。普通转发不需要终止 TCP 连接；router 运行自己的管理和路由协议时，则也会作为通信端点使用高层协议。([Baker, 1995](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-rfc1812)) 到达 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](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168architecture)) Best-effort 不是“不用认真传”，而是接口不作那些保证。把所有应用都强制放进可靠、有序、固定速率的服务，可能给实时数据增加不需要的等待，也使底层接入门槛变高。相应代价是上层必须承担更多工作。 共同接口也有升级成本：改变网络层需要多个独立参与者配合。IPv4 和 IPv6 是 IP 的两个版本，不能把“窄腰”理解为现实里只有唯一一种 header。 ## End-to-End：正确性应在哪个边界成立 文件上传的目标如果是“服务器已经保存了完整文件”，那么逐跳确认是否足够？ 即使每条链路都能确认收包，最后一个 router 后面的主机仍可能在写文件时失败。即使 TCP 已经确认 byte 到达，对端应用也可能还没完成校验或持久化。低层确认停在它能观察的边界，不能自动证明更高层的目标。 所以应用需要定义自己的成功条件，例如校验最终内容，并在持久化成功后返回结果。这是 Saltzer、Reed 和 Clark 的 end-to-end argument：如果某个功能的完整正确性需要端点掌握的信息，那么低层实现不能替代端点的责任。([Saltzer et al., 1984](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-saltzer1984endtoend)) 这并不排斥链路重传。设一个教学模型有 10 跳，每次尝试独立地以概率 $p=0.1$ 丢包，忽略 ACK 丢失。不作局部重传时，一次端到端尝试失败的概率是 $1-(1-p)^{10}\approx65.1\%$。若每跳最多尝试三次，单跳失败率降为 $p^3$，整条路径失败率约为 $1-(1-p^3)^{10}\approx1.0\%$。局部恢复可以明显减少跨整条路径重传的浪费，但会消耗链路时间，并可能延迟后续包。 要区分三种判断：“低层能否独立把功能做完整”“端点能做时低层是否还必要”“低层实现能否带来值得的性能收益”。它们可能给出不同结论。拥塞点上的优先级调度需要控制那个拥塞点；不能仅因偏爱端到端设计，就假设发送端能替沿途 router 完成调度。 另一条相关原则是 **fate sharing**：把通信赖以继续的关键状态放在依赖它的端点，使中间 router 的故障不必毁掉会话状态。端点若保存未确认数据，换路之后仍有机会继续传输。这里说的是关键会话状态，不是“router 没有状态”；forwarding table、queue 和邻接关系都是状态。Clark 对 Internet 的历史设计分析把故障后的继续通信放在很高的优先级，成本、易接入与资源核算则排在较后。([Clark, 1988](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-clark1988design)) 这些选择不是所有时代的唯一答案。防火墙、NAT 和 proxy 反映了运营者的控制需求，也重新引入路径中的状态依赖。理解架构，要同时看它保住了什么性质，以及把哪些责任留给了别人。 补充阅读：从“可靠”追问到具体的成功条件 [End-to-End Arguments in System Design](https://web.mit.edu/Saltzer/www/publications/endtoend/endtoend.pdf) 适合带着文件、消息去重和确认边界一起读；本文引用 1984 年期刊版本。Clark 的 [1988 年论文](https://people.eecs.berkeley.edu/~sylvia/cs268-2016/papers/darpa-internet.pdf) 则解释这些选择背后的目标排序。读它们时可以改变应用的成功条件，重新判断哪些工作必须留在端点。 ## Routing：局部决定如何组成全局路径 现在假设 packet 的目的地址已经确定。每个 router 只做一次 table lookup，就把包交给邻居。但所有 router 的选择拼在一起，真的能把包送到目的地吗？ 把网络记为有限图 $G=(V,E)$，链路代价为 $c(u,v)>0$。暂时只研究单一管理域内、可加代价的 unicast routing；目的节点记为 $d$。每个其他节点保存一个 next hop $f_d(u)$。这个模型不包含策略路由或多下一跳，后面会说明它的边界。([UC Berkeley CS 168, n.d.g](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168routing)) ### 先谈有效，再谈最短 如果 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 到 B 的双向代价为 1；B 到 C 的双向代价为 1；C 到 D 的双向代价为 2；B 到 D 的双向代价为 5；A 到 D 的双向代价为 7。 D 为目的节点。边没有箭头，因为表示物理邻接而非选定的转发方向。 1 2 5 7 A B C D [View diagram in the original article](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing) 双向链路：A–B：1，B–C：1，C–D：2，B–D：5，A–D：7。 数字是可加 cost，不是 bandwidth。后面的 DV 和 Dijkstra 使用同一张图。 A 可以直接以代价 7 到 D，也可以经 B、C，以 $1+1+2=4$ 到 D。注意我们选择的是总代价最小，不是 hop 数最少。链路 cost 是人为选定的 metric；可以近似传播延迟或表达管理偏好，但链路 bandwidth 通常不能直接相加作为路径 throughput。 ### 一个能排除环的量 设 $D(u)$ 是从 $u$ 到 D 的真实最短距离。若 u 选择了某条最短路径上的邻居 v，那么 $$ D(u)=c(u,v)+D(v). $$ 由于 cost 严格为正，沿每一跳都有 $D(v)3$ 而拒绝更新，永远保留坏路。 因此必须保存 route 的来源：**当前 next hop 的更新，即使变差，也必须影响当前路线。** 一种完整状态模型是保存每个邻居对每个目的地的最新有效报告 $\widehat D_v(d)$，然后重新计算 $$ D_u(d)=\min_{v\in N(u)}\{c(u,v)+\widehat D_v(d)\}. $$ 这样原路线变差时，还能比较缓存的其他候选路线。节省状态的教学实现可以只存当前最佳 next hop、cost 和 expiry time：收到更优路线就替换，收到当前 next hop 的报告则接受变好或变差；换路时未缓存的候选要等邻居再次通告。两种实现不要混成同一套存储假设。 消息本身也可能丢失，所以只在变化时发送还不够：triggered update 缩短等待，periodic update 提供再次传播的机会。若一直没有收到支撑当前路线的新报告，就让 route 过期；这个 route timer 与数据包的 IP TTL 是两个不同机制。 过期后若只静默删除，依赖自己的邻居还会继续转发一段时间。可以主动通告该目的地距离为 $\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。 | 事件 | A 的估计 | B 的估计 | 实际发生的事 | | ---------------- | ----- | ----- | --------- | | 故障前 | 1，经 D | 2，经 A | 可以到达 | | A 失去 D，收到 B 的旧报告 | 3，经 B | 2，经 A | A–B 成环 | | B 收到 A 的 3 | 3，经 B | 4，经 A | 距离增加，环未消失 | | A 收到 B 的 4 | 5，经 B | 4，经 A | 继续自我支撑 | 问题不在加法，而在报告缺少路径依赖信息。“B 有一条长为 2 的路线”，没有告诉 A 这条路线经过 A 自己。于是旧信息可以被不断加工成新通告，形成 **count to infinity**。 ### Split horizon 与 poison reverse 既然 B 的路线来自 A，就没有理由把它作为 A 的备选出口。Split horizon 让 B 不再向 A 通告这条路线。Poison reverse 更明确：B 仍向 A 通告，但报告 $\infty$，意思是“你不能通过我到这个目的地”。B 向其他邻居仍可报告真实距离 2。 这与 route poisoning 不同：前者是按接收邻居调整通告，B 自己仍有路；后者是自己的 route 已失效。显式 poison reverse 还能比静默等待 expiry 更快地拆掉某些已有的二节点相互依赖。 但它们没有携带完整路径。若依赖是 A 经 B、B 经 C、C 经 A，每个人只对自己的 next hop 报 $\infty$，仍可能沿另一个方向循环传播有限距离。因此不能把 poison reverse 当作任意拓扑无环的证明。RIP 的讨论也明确包含多节点环与计数问题。([Malkin, 1998](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-rfc2453)) RIP 把 metric 16 定义为不可达，允许的有限 hop count 最多为 15。这样坏消息计数到一个有限上限就停止；它同时限制了能表示的路径长度。16 是 RIP 的工程取舍，不是所有 DV 协议共享的数学常数，更不是 packet TTL。 把机制装回一个事件驱动的 router 对每个目的地维护 next hop、cost 与过期时间，并钉住自己的直连信息。按以下事件处理： 1. 收到通告：加上到发送邻居的链路 cost。若没有有效路线、候选更优，或消息来自当前 next hop，则更新相应状态；按协议规则处理不可达值和有效报告的 timer。 2. 链路失效或路线过期：使受影响路线失效，触发 poison 通告；若保存了有效备选，可以重新选择。 3. 路线改变：尽快触发更新。向每个邻居分别应用 split horizon 或 poison reverse，不能把同一份未处理的向量无条件发给所有邻居。 4. 定时重发：即使没有新变化，也给丢失的消息再次传播的机会。过期、保留 poison 和最终垃圾回收是不同阶段。 这是一份机制级描述。RIP 的 timer、触发更新节流和垃圾回收见 RFC 2453，不能用一个无限保留所有旧信息的 cache 代替协议规定的 freshness 管理。 ## Link State：先共享地图，再各自算路 DV 隐藏了路径细节。如果每个 router 改为通告“我和谁相邻、代价是多少”，所有节点最终就能拼出拓扑。然后每个节点独立计算最短路，把第一跳写入自己的 forwarding table。这是 link-state 的基本分工。([UC Berkeley CS 168, n.d.g](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168ls)) ### 怎样获得一张不会被旧消息覆盖的地图 先用 hello 或接口状态发现邻居；若长期失联，按协议规则宣告邻接变化。接着把本地 link state 发给邻居，邻居再继续扩散，即 flooding。 直接转发每个收到的副本会在有环图里不断放大消息，因此需要让一个节点知道“这个版本我已经处理过了”。给通告加入 origin 和该 origin 的 sequence number，接收方保存已知版本，只在收到更新版本时替换并继续传播。不同 origin 的 sequence number 不需要互相比较，也不需要一只全网同步的时钟。 然而“只传播新版本”也带来问题：某个邻居丢了第一次发送，后面重复包又被抑制，它如何补齐？因此可靠 flooding 还需要确认、重传或数据库同步；周期刷新和 age 则处理长期失效信息。OSPF 的 LSA 具有类型、标识、发布者、sequence number、checksum 和 age 等字段，邻接建立时也有数据库交换。它比“给每条边配一个全局时间戳”更具体。([Moy, 1998](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-rfc2328)) 重启与序号回绕同样不能忽略：如果节点重启后从 0 开始，而别人保存着旧的大序号，新消息会被误判为旧版本。实际协议必须规定状态恢复、老版本清除与版本生命周期。 ### Dijkstra 为什么每次固定最小的候选 有了地图，从 A 开始求最短路。初始只有 A 的距离确定为 0；它的邻居得到候选距离 B=1、D=7。现在选候选距离最小的 B。为什么 B 可以直接定下来？ 任何尚未探索的替代路径，都得先离开已经确定的集合。如果它的第一处未确定节点的候选距离已经不小于 B，后面再加非负 cost，也不可能绕一圈得到更便宜的 B。于是最小候选可以固定，然后用它去改善邻居的候选距离。 | 刚固定的节点 | B 的候选 | C 的候选 | D 的候选 | | ------ | ----- | -------- | ----- | | A，距离 0 | 1，经 A | $\infty$ | 7，经 A | | B，距离 1 | 已固定 | 2，经 B | 6，经 B | | C，距离 2 | 已固定 | 已固定 | 4，经 C | | D，距离 4 | 已固定 | 已固定 | 已固定 | 最终 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。这里仍要求每条可选边都使距离严格下降；只有“每个节点觉得这条路不错”不够。零代价边会破坏严格下降，需要额外约束。 | 比较维度 | Distance Vector | Link State | | -------- | --------------- | -------------------------- | | 传播的信息 | 到目的地的距离估计 | 本地邻接及其状态 | | 每个节点知道什么 | 邻居报告，通常没有完整路径 | 所在范围的拓扑数据库 | | 本地计算 | 经各邻居比较候选路线 | 在地图上运行最短路算法 | | 变化如何扩散 | 邻居重新估计，再逐级通告 | 先 flood 状态，再独立计算 | | 主要困难 | 陈旧依赖、计数到无穷、失效传播 | 可靠 flooding、版本生命周期、更新期间不一致 | LS 不会因为“共享地图”就变成集中式算法，也不是没有环、没有协议状态的免费方案。两类方法最终都要在有限带宽、消息丢失与网络变化之间维护可用的路由。 补充阅读：从抽象算法走到协议 [CS 168 的 DV 教材](https://textbook.cs168.io/routing/distance-vector.html) 可以用来逐项复查上面的事件规则；再读 [RIP v2，RFC 2453 §3](https://www.rfc-editor.org/rfc/rfc2453.html#section-3)，看 timer、poison 和 triggered update 如何协同。 [OSPF v2，RFC 2328 §13、§16](https://www.rfc-editor.org/rfc/rfc2328.html) 分别展开 flooding 和路由计算。这里需要带着两个不同问题读：数据库如何保持新鲜，以及从数据库怎样导出可安装的路由。它们不是同一个算法步骤。 ## 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](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168addressing)) 例如 `192.0.2.0/23` 固定前 23 bit，netmask 为 `255.255.254.0`，覆盖 `192.0.2.0` 到 `192.0.3.255`。地址 $x$ 属于某个前缀，当且仅当 $$ x\mathbin{\&}m=p, $$ 其中 $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](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-rfc4632)) ### 为什么用 longest prefix match 假设一张 forwarding table 如下： | 目的前缀 | 动作 | | --------------- | ---- | | `0.0.0.0/0` | 默认出口 | | `192.0.2.0/23` | 出口 P | | `192.0.3.0/24` | 出口 Q | | `192.0.3.42/32` | 出口 R | `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](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-rfc8200); [Hinden & Deering, 2006](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-rfc4291)) 常见 IPv6 LAN 使用 /64。SLAAC 下，主机可以根据 router advertisement 提供的可用前缀与本地生成的 interface identifier 形成地址，并进行 duplicate address detection。**它并不让主机随意挑选一个全球可路由前缀**；地址空间巨大也不取消分配与可达性管理。([Thomson et al., 2007](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-rfc4862)) 过渡的困难来自协议与部署：端点、沿途网络和应用支持必须配合。Dual stack 让节点同时运行 IPv4、IPv6；tunneling 可以把一种协议承载在另一种上；NAT64 等机制则在特定场景中进行转换。转换存在，并不意味着两个协议天然兼容或所有通信都能无条件透明转换。([Bagnulo et al., 2011](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-rfc6146)) 练习：聚合之后怎样处理例外？ 若上表中的 `/24` 被撤回，`192.0.3.9` 会回落到 `/23`，走 P。`192.0.3.42` 仍走 R，因为 `/32` 还在。 这只是 lookup 的答案。P 是否真的能把包交付，要继续看它内部的可达性；如果没有有效路线而只有覆盖该地址的本地 discard aggregate，包会被丢弃。把“匹配到了一个前缀”和“端到端一定可达”分开，才能正确分析故障。 ## Traceroute：从返回的错误消息观察路径 我们已经知道 forwarding table 决定下一跳，但普通主机看不到沿途的表。能否只发一些 packet，间接知道它们走到了哪里？ IPv4 TTL 在转发时减少，耗尽后 router 丢弃 packet，通常发回 ICMP Time Exceeded。于是可以让第一个 probe 的 TTL=1，在第一跳到期；第二组设为 2，在第二跳到期；再逐渐增大。每次回复的外层源 IP 提供一个回应接口的地址，往返时间来自 probe 发出到对应回复到达的时间。([Baker, 1995](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-rfc1812)) 经典 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](https://pufanyi.com/blog/cs/cs-revisit/computer-networks/architecture-and-routing#bib-cs168traceroute)) | Probe TTL | 理想路径 A → R1 → R2 → B 的响应 | | --------- | --------------------------------- | | 1 | R1 的 Time Exceeded | | 2 | R2 的 Time Exceeded | | 3 | B 的 Port Unreachable，假设该 UDP 端口关闭 | 为了把回复归属到正确 probe，不能只看回复源地址。ICMP 错误会引用触发错误的原始 IP header 和一部分 payload；解析其中的协议、目的地址和 UDP 端口等字段，可以匹配本轮 probe。IPv4 header 长度由 IHL 指定，不能把“总是 20 byte”写死。还要先验证实际收到的长度与消息类型，忽略截断、重复、其他目的地以及前一轮迟到的回复。 一个稳健的探测循环是在每个 TTL 下发送带可识别信息的 probes，接收至本轮 deadline，只记录匹配且尚未记录的响应，然后再进入下一轮。用 deadline 而非“必须凑齐三个回复”，才能在丢包时结束等待；也不能让任意迟到消息重置无限等待。 怎样读一次 traceroute，而不从输出推断过多？ 在自己的网络环境可以运行 `traceroute -n example.com`，或使用系统提供的等价工具。输出需要谨慎解释： - `*` 表示在等待期限内没有收到匹配回复。可能是过滤、限速、回复丢失或不回应，不直接证明 data plane 无法转发；后面仍可能出现正常回复。 - 每一行是独立 probes 的结果，路径可能随时间或 flow hash 变化，不一定能把每行任取一个地址连成一条真实路径。 - 每个时间是到该响应点再返回的 RTT，回复未必沿原路回来。相邻行 RTT 相减，不能直接当作那条链路的传播延迟，甚至可能得到负数。 - ICMP 回应地址不一定就是你想象中的入站接口地址；看到的是协议暴露出的观察结果，而不是完整物理拓扑。 这些限制不使 traceroute 失去价值，反而规定了它能支持哪些判断。可以结合重复测量、终点可达性和本机路由信息继续定位问题。 ## 把一个包的旅程接起来 现在回到开头的文件传输。应用通过名字找到地址，选定 transport endpoint，把数据交给传输层。传输层按自身语义组织数据；IP 为跨网络交付提供共同格式；每一跳的 link layer 再为当前局部传输封装 frame。 链路发送耗费 serialization 和 propagation 时间，共享链路还会排队。router 用当前 forwarding table 选择下一跳；这些表来自静态配置、直连信息和路由协议。DV 交换距离估计，LS 交换邻接状态，二者都必须面对陈旧信息。层级地址把许多目的地折叠成前缀，而更具体的前缀保留必要例外。 到达服务器之后，网络交付的成功还要继续向上解释：byte stream 完整了吗，文件校验通过了吗，内容持久保存了吗？这里自然接上后续的 reliable transport、congestion control 和应用协议。想先看这些机制如何影响 QUIC、WebRTC 与 RPC，可以继续读[现代通信协议](https://pufanyi.com/blog/cs/notes/modern-communication-protocols)。 课程覆盖与继续阅读 这里的周次按 [CS 168 Fall 2026 calendar](https://fa26.cs168.io/) 核对；部分 PDF 沿用旧版页眉，因此下面用 FA26 发布的讲次定位，不把其每页文字当作新的协议标准。 | 课程范围 | 本文对应内容 | | --------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------ | | Week 1，[Lecture 1](https://fa26.cs168.io/assets/lectures/cs168-fa26-lec01.pdf)：Architecture and Protocols | 互联与自治、规模与故障、protocol、best-effort | | Week 2，[Lecture 2](https://fa26.cs168.io/assets/lectures/cs168-fa26-lec02.pdf)：Bottom-up | packet、链路时延、BDP、forwarding/routing、资源共享 | | Week 2，[Lecture 3](https://fa26.cs168.io/assets/lectures/cs168-fa26-lec03.pdf)：Top-down | queue、可靠性与拥塞、layering、端口、封装 | | Week 3，[Lecture 4](https://fa26.cs168.io/assets/lectures/cs168-fa26-lec04.pdf)：Architectural Principles | end-to-end、fate sharing、目标排序与边界 | | Week 3，[Lecture 5](https://fa26.cs168.io/assets/lectures/cs168-fa26-lec05.pdf)：Routing Principles | 图模型、有效状态、delivery tree、least-cost、域内与域间 | | Week 4，[Lecture 6](https://fa26.cs168.io/assets/lectures/cs168-fa26-lec06.pdf)：Distance-Vector | Bellman–Ford、当前 next-hop 更新、timer、poison、split horizon、计数到无穷 | | Week 4，[Lecture 7](https://fa26.cs168.io/assets/lectures/cs168-fa26-lec07.pdf)：Link-State, Addressing | flooding、Dijkstra、一致性、层级地址、classful/CIDR、LPM、IPv6 | | Discussions 1–3；Project 1A/1B | header 变化、架构取舍、时延与复用算例、逐事件 DV、Traceroute 与异常回复 | 延伸推导包括分包流水线、突发积压、M/M/1 的假设、距离下降的无环证明、LS 更新期间的 microloop，以及聚合空洞。这里停在网络架构与基础路由；Week 5 以后的 router hardware、BGP 细节和 TCP 算法尚未展开。 ## References Bagnulo, M., Matthews, P., & van Beijnum, I. (2011). *RFC 6146: Stateful NAT64: Network Address and Protocol Translation from IPv6 Clients to IPv4 Servers*. [doi.org](https://doi.org/10.17487/RFC6146 "https://doi.org/10.17487/RFC6146") Baker, F. (1995). *RFC 1812: Requirements for IP Version 4 Routers*. [doi.org](https://doi.org/10.17487/RFC1812 "https://doi.org/10.17487/RFC1812") Clark, D. D. (1988). *The Design Philosophy of the DARPA Internet Protocols*. [doi.org](https://doi.org/10.1145/52325.52336 "https://doi.org/10.1145/52325.52336") Deering, S., & Hinden, R. (2017). *RFC 8200: Internet Protocol, Version 6 (IPv6) Specification*. [doi.org](https://doi.org/10.17487/RFC8200 "https://doi.org/10.17487/RFC8200") Fuller, V., & Li, T. (2006). *RFC 4632: Classless Inter-domain Routing (CIDR): The Internet Address Assignment and Aggregation Plan*. [doi.org](https://doi.org/10.17487/RFC4632 "https://doi.org/10.17487/RFC4632") Hinden, R., & Deering, S. (2006). *RFC 4291: IP Version 6 Addressing Architecture*. [doi.org](https://doi.org/10.17487/RFC4291 "https://doi.org/10.17487/RFC4291") Malkin, G. (1998). *RFC 2453: RIP Version 2*. [doi.org](https://doi.org/10.17487/RFC2453 "https://doi.org/10.17487/RFC2453") Moy, J. (1998). *RFC 2328: OSPF Version 2*. [doi.org](https://doi.org/10.17487/RFC2328 "https://doi.org/10.17487/RFC2328") Saltzer, J. H., Reed, D. P., & Clark, D. D. (1984). *End-to-End Arguments in System Design*. [doi.org](https://doi.org/10.1145/357401.357402 "https://doi.org/10.1145/357401.357402") Thomson, S., Narten, T., & Jinmei, T. (2007). *RFC 4862: IPv6 Stateless Address Autoconfiguration*. [doi.org](https://doi.org/10.17487/RFC4862 "https://doi.org/10.17487/RFC4862") UC Berkeley CS 168. (2026a). *CS 168 Fall 2026: Course Calendar*. [fa26.cs168.io](https://fa26.cs168.io/ "https://fa26.cs168.io/") UC Berkeley CS 168. (2026b). *CS 168 Fall 2026: Traceroute Guide*. [fa26.cs168.io](https://fa26.cs168.io/proj1/guide/ "https://fa26.cs168.io/proj1/guide/") UC Berkeley CS 168. (n.d.a). *CS 168 Textbook: Addressing*. [textbook.cs168.io](https://textbook.cs168.io/routing/addressing.html "https://textbook.cs168.io/routing/addressing.html") UC Berkeley CS 168. (n.d.b). *CS 168 Textbook: Designing Resource Sharing*. [textbook.cs168.io](https://textbook.cs168.io/intro/sharing-resources.html "https://textbook.cs168.io/intro/sharing-resources.html") UC Berkeley CS 168. (n.d.c). *CS 168 Textbook: Distance-Vector Protocols*. [textbook.cs168.io](https://textbook.cs168.io/routing/distance-vector.html "https://textbook.cs168.io/routing/distance-vector.html") UC Berkeley CS 168. (n.d.d). *CS 168 Textbook: Headers*. [textbook.cs168.io](https://textbook.cs168.io/intro/headers.html "https://textbook.cs168.io/intro/headers.html") UC Berkeley CS 168. (n.d.e). *CS 168 Textbook: Introduction to the Internet*. [textbook.cs168.io](https://textbook.cs168.io/intro/intro.html "https://textbook.cs168.io/intro/intro.html") UC Berkeley CS 168. (n.d.f). *CS 168 Textbook: Layers of the Internet*. [textbook.cs168.io](https://textbook.cs168.io/intro/layers.html "https://textbook.cs168.io/intro/layers.html") UC Berkeley CS 168. (n.d.g). *CS 168 Textbook: Links*. [textbook.cs168.io](https://textbook.cs168.io/intro/links.html "https://textbook.cs168.io/intro/links.html") UC Berkeley CS 168. (n.d.h). *CS 168 Textbook: Link-State Protocols*. [textbook.cs168.io](https://textbook.cs168.io/routing/link-state.html "https://textbook.cs168.io/routing/link-state.html") UC Berkeley CS 168. (n.d.i). *CS 168 Textbook: Network Architecture*. [textbook.cs168.io](https://textbook.cs168.io/intro/architecture.html "https://textbook.cs168.io/intro/architecture.html") UC Berkeley CS 168. (n.d.j). *CS 168 Textbook: Routing States*. [textbook.cs168.io](https://textbook.cs168.io/routing/solutions.html "https://textbook.cs168.io/routing/solutions.html")