网络算法学
Network Algorithmics 精读笔记

书把反复出现的手法收成大约十五条原则。不必背编号，要能按簇调用：少做无用功、把计算挪出关键路径、放松不必那么严的规格、借已有子系统、为速度保存状态。

系统簇：别在包路径上做能不做的事

实现簇：别被通用性和参考代码绑住

为热路径写特化例程，而不是维护一个能处理所有地址族、所有选项的巨型函数。参考实现的职责是讲清楚协议，线速实现的职责是服务期望情形。协议头和接口调用都可以传「提示」：把已经算过的流标识、下一跳或校验和结果往下传，避免下层再猜。优化期望情形，把罕见情形留在慢路径——这与「先让正确的事发生在快路径」是同一句话的两面。

算法簇：状态、局部性、度量

为速度保存状态：缓存最近的查找结果、记住流所属的队列、把慢路径的结论留给后来的包。该用算法时不要只靠硬件堆容量——压缩 trie、定时轮、亏空轮转，都是用结构换存储器。所有优化都要能度量：加一条巧妙路径却让期望情形变慢，就是负优化。局部性（同一流、同一前缀、同一队列）往往比新发明的最坏情况结构更值钱。

把十五条当成检查单来用，比当成口号有用。设计一个新转发路径时可以逐条问：热路径上有没有重复解析？哪一步可以预计算或批处理？规格是否要求了并不需要的精确？内核或网卡是不是已经做了这件事？参考实现的通用分支有没有漏进线速代码？接口能不能把上一层算过的提示传下去？期望情形有没有自己的特化例程？为了少访存，该缓存哪份状态？上线后用哪几个计数器证明它变快而不是变慢？能答完这些问题，原则就算读进手里了。

读第 2 版时可以把原则当成翻译器： 可编程交换机上的流水线表，是「把计算挪开」和「加硬件」； P4 里把流缓存进精确匹配表，是「为速度保存状态」； 控制面用近似计数做遥测，是「放松规格」。 器件换了，句子还能用。 这正是这本书比某一代芯片手册活得更久的原因。 原则不是加速插件：为速度加的状态会变成一致性负担， 放松规格在计费或安全场景里可能不可接受。 先写清「哪条路径、何种错误可容忍」，再选该用哪一簇。 后面五节都是在给这张检查单提供可以指认的实例， 而不是另一本算法竞赛题集。 指认得出实例，原则才算从目录走进实现。 只记住原则名称、指不出路径，等于没读。 先指路径，再谈器件名词。

主机侧最先被链路速率打穿的，往往不是「协议逻辑」，而是数据从网卡搬到应用、以及内核为此付出的中断与系统调用。端节点算法学的第一课是给这两件事称重。

一次收包可能被拷几次

经典路径里，帧先进入网卡环形缓冲，再拷进内核套接字缓冲，再拷进用户缓冲；校验和若用软件再扫一遍，等于又读了一次。链路速率升高后，存储器带宽会先于 ALU 耗尽。对应原则很直接：能在拷贝的同时算校验和就不要分开走两趟；能把页映射给应用就不要再搬字节；能让网卡直接描述应用缓冲（一类「零拷贝」或内核旁路）就把内核排除在热路径外。

中断是最贵的函数调用

一包一中断在千兆以上会把 CPU 融化在进出内核的过程里。缓解手段按激进程度排列：中断合并（攒一批再叫 CPU）、轮询（NAPI 一类：忙的时候改抽网卡，闲的时候再听中断）、把协议处理从硬中断挪到软中断或专用线程。上下文切换的亲戚是系统调用：每个read /sendmsg 都是一次用户/内核往返。批量收发包、减少调用次数，往往比把单次调用本身再微优化更有效。

控制权转移也是瓶颈

除了数据面拷贝，还有「谁来处理这个包」的调度问题。每来一个包就唤醒一个进程，会把缓存跑冷；永远只在中断上下文里做完所有协议处理，又会让延迟不可控。书里把这类问题看成与拷贝对称的「控制转移」：能在同一条执行流里处理一串包，就不要为每个包重新找人。今天的用户态协议栈、DPDK 轮询线程，仍是同一条原则的当代写法。

网卡侧的卸载是「借用现成部件」的当代清单：校验和卸载、分段卸载、大型接收聚合、甚至把部分连接跟踪沉到器件。原则提醒两件事：卸载省的是主机周期，不是协议语义；卸载路径一旦与软件路径行为不一致（伪校验和、聚合边界、时间戳），排障会从「算法」变成「两条实现谁说了算」。端节点优化必须连测量口一起设计，否则加速和正确性会在同一周里打架。

主机要为海量 TCP 连接维护重传与保活时钟，路由器要为每包做精确匹配或流表查找。两者都要求：启动、停止、到期处理必须摊到接近常数，而不能按连接数线性扫描。

定时轮：用环形数组代替有序堆

若把每个定时器丢进按到期时间排序的堆，启动和取消都要付对数代价，到期再取堆顶。连接数到十万时，光维护时钟就先输了。定时轮（timing wheel）把时间离散成槽，到期时刻对轮长取模后挂进对应槽；时间推进一格，只处理当前槽里的链表。启动是把一项接到槽上，取消是从链表摘下，摊还代价接近常数。时间跨度很大时，用多层轮：低层转完一圈，向高层进位——和机械钟表是同一个主意。

精确匹配：哈希仍是主力

流表、ARP、连接控制块，多数是精确键。哈希在期望情形下是常数查找，但要为碰撞、重哈希和恶意输入留后路。硬件可以用 CAM / TCAM 做「一拍比完」，容量和功耗是它的税。软件侧则靠：好的哈希函数、每桶足够浅的链或开放寻址、以及把热点流钉在缓存里（又是「为速度保存状态」）。

数据结构要匹配访问模式

定时器的访问是「插入、删除、按时间到期」，不是「按连接号随机查」——所以按时间分桶。精确匹配的访问是「这个键在不在」，所以按键分桶。把两种需求塞进同一棵树，会得到处处正确、处处不快的结构。书反复强调：先写清操作集合和期望/最坏代价，再选结构。

精确匹配的最坏情况同样要设计：攻击者若能制造大量碰撞，哈希会退化成链上的线性扫描。盐、种子定期更换、每桶深度上限、超出后改用更稳的结构，都是「期望情形走快路径、恶意情形走慢但有界路径」。硬件 CAM 把最坏情况买成一拍，换来的是容量与功耗；软件不能假装自己也有这种一拍，除非测量证明碰撞已被关进笼子。

TCP 重传、连接保活、邻居发现、流老化， 都会同时产生大量定时器。 实现上往往是「每条连接一个时钟结构」， 但调度器看到的应是按时间分桶的轮，而不是按连接扫描的循环。 把连接表和定时轮拆开， 取消定时器才不会变成「先找到那条连接再从堆里删」。

转发查找不是精确匹配：目的地址可能命中多个前缀，必须取最长的那一条。这是 IP 路由可扩展的代价，也是路由器算法里被写得最透的一章。

问题为什么难

地址空间按前缀划分，短前缀覆盖大块，长前缀覆盖例外。线性扫表在线速下不可接受；普通哈希又不认识「前缀包含」。一比特 trie 从高位往低位走，命中节点可以记下「目前见到的最长前缀」，走到叶子或空枝就出答案。它正确，但对 32 位已嫌深，对 128 位更不可能按一比特走完。

用步宽和压缩换深度

多比特 trie 一次看若干位，深度立刻下降，但每个节点要准备 2 ^k 个指针，存储器膨胀，还要处理「前缀长度不是步宽倍数」的填充。路径压缩跳过只有一个孩子的长链；位图压缩（一类 tree bitmap / Luleå 风格）把稀疏子树收成紧凑数组，让一次缓存行装下更多决策。软件实现常把前 16 或 24 位做成直接索引（DIR-24-8 一类两级表）：期望情形一到两次访存结束，把长前缀留给第二级。

硬件与更新

TCAM 把「所有前缀同时比较、按优先级选出最长」做成一拍操作，更新和功耗是它的账单。软件结构则要同时回答两个问题：查找几拍完成，以及路由更新来时要锁住多少、复制多少。只优化查找不谈更新，会在收敛期把路由器自己打停。第 2 版还会把可编程数据面的表流水线看成「把多级查找拆到级联器件」的当代版本，原则未变。

IPv6 把问题从 32 位拉到 128 位，一比特 trie 的深度立刻不可接受，多比特步宽和直接索引的第一级也不能再按「前 24 位一张表」天真放大。工程上往往对常见长度做特化，把其余长度丢进更通用的慢结构——又是期望情形与罕见情形分家。默认路由、丢弃路由和「查不到」必须在结构里有明确出口，否则压缩节点会把未覆盖的地址悄悄送去错误的下一跳。

防火墙、QoS 分类、流表都在问同一件事：这个包匹配哪一条最高优先级的多域规则。域通常包括源/目的前缀、协议、端口范围。它比最长前缀难一个数量级，因为维度不再是一条数轴。

几何图像与朴素算法

两条前缀加两个端口范围，可以看成高维空间里的矩形；分类就是找到覆盖该点、优先级最高的矩形。线性扫描最清楚，也最慢。分层 trie 按域依次下降，简单但会因规则相关而膨胀；为避免回溯做的集剪枝（set-pruning）用空间换时间，最坏可以爆炸。网格 trie 一类结构专门修补「源、目的两棵前缀树如何交叉」的指针问题。

分解：先各自查找，再组合

交叉乘积把每个域的查找结果当成坐标，再查一张组合表——域一多，组合表就不可接受。递归流分类（RFC 算法，这里的 RFC 是一种分类方法名，不是请求评论）用多级交叉表逐级压缩中间结果，用存储器换确定的访存次数。HiCuts / HyperCuts 则对几何空间做切分，把规则桶切到足够小再用局部搜索。工程选择几乎总是：规则数、域的分布、能否接受更新时重建、以及有没有 TCAM。

TCAM 与软件的分工

TCAM 天然适合「多域同时比较」，范围匹配却要拆成多条前缀，规则一拆就更占容量。软件分类器适合控制面或中等速率；数据面则把热点流记下第一次分类的结果，后续包走精确流表——又是「为速度保存状态」。分类错一次的代价往往是错误的丢弃或错误的优先权，所以慢路径的正确性不能用「近似」随便放松。

规则重叠时，必须先定义「命中」：是第一条匹配、最高优先级，还是最具体的矩形。三种定义会选出不同的规则，实现与配置界面必须用同一种。更新比查找更刺手：插入一条新 ACL 可能迫使交叉表或切分树重建。能接受「更新时短暂走慢路径」的系统，往往比追求无锁热更新却偶尔分错包的系统更安全。分类器的测试集里应包含重叠、缺口、默认丢弃和「只差一个域」的邻近规则，而不是只丢几条互不相关的样例。

多域规则的「维度诅咒」是实在的： 每多一个域，朴素交叉表就按该域取值数膨胀。 所以工程上先问： 有多少条规则、更新有多勤、能否接受重建、 以及是否允许把热点流钉死成精确匹配。 答完这四个问题，再在 trie、切分树、TCAM 之间挑， 比先挑一个论文名字再硬套流量更接近书的读法。

查找决定包该从哪扇门离开；交换结构决定它何时能走进那扇门；调度与整形决定谁先走、走多快。QoS 若没有这三件套，就只是配置文件里的愿望。

交换：队头阻塞与虚拟输出队列

输入排队交换机便宜，但一个出不去的队头会堵住后面要去往空闲出口的包——这就是队头阻塞。虚拟输出队列（VOQ）在每个入口为每个出口各建一队，把「去不同门的包」拆开。接下来要解决的是匹配：每个入口每拍最多选一个出口，每个出口每拍最多收一个入口。iSLIP 一类迭代匹配用几轮请求/许可/接受逼近最大匹配，目标是在可实现的拍数里吃饱和流量，而不是求出图论最优。

调度：公平、时延、可实现性

理想公平排队按「每个流应得的服务量」精细记账，线速下算不起；亏空轮转、加权轮转把公平放松成「每轮能拿走的字节配额」。原则再次出现：放松规格，优化期望情形，把真正要隔离的流才升级到更重的调度器。

整形：令牌桶与漏桶

调度管「出口此刻送给谁」，整形管「这条流长期能多快」。漏桶强调平滑，令牌桶允许突发（桶里存了令牌就能短时超过均速）。它们出现在入口监管、出口整形和切片带宽保证里。和拥塞控制不同，整形是设备主动推迟发送，即使出口空闲——所以它不是工作守恒的。配置时要把「承诺信息速率、峰值、突发尺寸」翻译成桶深和加令牌的速率，而不是只写一个百分比。

输出排队交换机实现简单、没有队头阻塞，但要把所有入口的突发都吞进出口存储器，线速端口一多就先在缓存上破产。组合输入输出排队（CIOQ）用内部加速比缓和两端的压力，加速比做不到理论值时，匹配与缓冲仍然要一起设计。信用或反压则防止上游把下游的 VOQ 灌死。读这一章时不要只记住算法名字：问清排队发生在输入还是输出、匹配几拍一轮、整形是否工作守恒，才能把 QoS 从幻灯片还原成会丢包的机器。

把第六章读回原则总纲： VOQ 是「避免明显浪费」（别让队头挡住去往空闲门的包）； DRR 是「放松规格」换可实现的公平； 令牌桶是「为速度保存状态」（桶里的令牌就是未来发送权）； 内部加速比是「必要时加硬件」。 调度章节看起来像排队论， 其实仍是同一套实现思维在出口上的投影。

合上书可以带三句口令出门： 第一句，先称量拷贝、访存和切换，再谈大 O； 第二句，查找结构必须同时回答查找拍数和更新代价； 第三句，没有可实现的排队与整形，QoS 只是配置愿望。 第 2 版换了一些器件名词，这三句没有过期。

若要把书读成可以动手的地图，建议按这条作业链走： 先给自己的收发包路径数清拷贝次数和中断次数； 再实现一个哈希定时轮，对比有序堆在十万时钟下的开销直觉； 然后用一棵多比特 trie 解释一条默认路由加一条更长例外； 最后把一条五元组 ACL 画成几何矩形，看它和 LPM 差在哪。 不必复现书中每张结构图， 但这四步能把原则从形容词变成你能指出瓶颈的位置。 做完再回头看十五条，会发现它们其实只有几簇： 少做、挪走、放松、借用、特化、留状态。 能用这六簇给自己系统里的热路径贴标签，精华档就算读完。 贴不上的地方，就是下一轮该回原书细看的章节。 原则是地图，原书的结构图才是街道。