【网络】网络芯片对IP地址最长前缀匹配算法的实现

在网络芯片中IPv4 地址的最长前缀匹配LPM是转发流水线的核心功能要求每时钟周期完成一次甚至多次查找同时兼顾功耗、芯片面积和表项更新速度。硬件上主要有三大类实现方式TCAM 全并行匹配基于 SRAM 的流水线树/多分支 Trie多级哈希混合方案目录1. TCAM三态内容寻址存储器全并行匹配2. 基于 SRAM 的多比特 Trie 流水线结构3. 哈希与分段直接查找的混合方案4. 实际芯片中的混合架构5. 方案对比与总结6. 未来趋势1. TCAM三态内容寻址存储器全并行匹配1.1 工作原理TCAM 是专门为 LPM 设计的硬件结构它在一个时钟周期内把输入 Key 与所有存储的表项同时比较。每个 TCAM 单元存储 3 种值0、1、X无关位。一条路由前缀 Prefix/Len 在 TCAM 中的存储形式为· Data {Prefix, 0...0}32 位补齐· Mask {Len 个 1, (32-Len) 个 0}掩码位为 1 时要求精确匹配为 0 时与 X 等效。比较逻辑match[i] (Key Mask[i]) (Data[i] Mask[i])当 Key 与某条表项的 Mask 无关位无关仅比较前缀部分。1.2 优先级编码器实现“最长”如果多条表项同时匹配必须返回最长的前缀。实现方式不是计算掩码长度而是通过表项物理顺序保证优先级将路由前缀按掩码长度降序排列在 TCAM 中即 /32 在最顶端/0 在最底端。所有匹配线接入一个优先级编码器它输出匹配线中地址最小索引最靠前的那个。因为长前缀排在低地址所以自然选出了最长匹配。这一过程纯组合逻辑完成延迟极低。1.3 硬件成本与局限性· 比较单元巨大每个 TCAM 位需要 16 个晶体管普通 SRAM 位仅需 6 个功耗极高。· 容量受限大容量 TCAM 占据大量芯片面积典型高端芯片也就存放几十万条 IPv4 路由难以承担 100 万 全网路由表。· 更新复杂插入/删除必须维持掩码长度降序可能引起大量表项搬移导致更新速率受限通常需硬件重排序管理器。· 并行度虽完美支持单周期查找但要支持多端口查找需复制多套 TCAM面积直接翻倍。2. 基于 SRAM 的多比特 Trie 流水线结构为了摆脱 TCAM 的限制业界主流做法是用普通 SRAM 存储经过巧妙编码的多比特 TrieMulti-bit Trie并将树的层级映射到硬件流水线。2.1 多比特 Trie 原理将 32 位 IP 地址按 k 比特一组如 k4、8切割成多个步长Stride。一个前缀在标准二叉树中的每个节点被扩展成包含 2^k 个分支的子树节点。硬件查找过程· 第 1 级用 IP[31:32-k] 索引 SRAM取出节点信息· 节点信息包含子树指针下一级 SRAM 的基地址和前缀匹配结果若当前节点本身代表一条路由前缀则记录下一跳· 再用 IP 的下 k 位作为偏移加上基地址读出第 2 级节点依此类推。关键是无论前缀如何分布每步都只读一次 SRAM且路径固定为 32/k 级延迟确定。2.2 经典硬件实现Tree Bitmap树位图Tree Bitmap 是一种高效的节点编码方式将子节点指针和前缀结果压缩存储于一个固定宽度的 SRAM 字中便于硬件流水线直接使用。节点结构一个 Tree Bitmap 节点包含· Internal Bitmap记录当前节点以下sub‑trie 内部哪些深度位置存在前缀。· Extending Paths Bitmap记录哪些分支有子节点需要继续查下一级。· Result Array Pointer指向一个存放下一跳结果的数组结合 Internal Bitmap 可计算命中结果的偏移。· Child Node Pointer子节点块的基地址。硬件查找过程以 k432 位分 8 级为例流水线第 stage 级执行1. 输入级数 stage当前节点基地址 ptrIP 分段 seg4 位。2. 读取 SRAMnode SRAM[ptr seg]实际上 ptr 是对齐的块基地址加上 seg 偏移立即索引子树分支。3. 前缀匹配检查利用 node.InternalBitmap 检查从根到该分支的路径上是否有前缀命中。通常有一个优先级查找逻辑如找路径上 mask 最长的命中 bit如果存在更新临时下一跳 best_nhp。4. 判断是否继续若 node.ExtendingBitmap 中对应 seg 位为 1说明该分支有更深子树计算下一级地址child_ptr node.ChildPtr popcount(ExtendingBitmap ((1seg)-1)) * NodeStrideSizepopcount 硬件实现为一个很小的组合逻辑用于跳过不存在的分支。若为 0则提前终止流水线将该包标记为完成保留 best_nhp。5. 流水线传递 child_ptr 和更新后的 best_nhp 给下一级。最终经过最多 8 级流水线输出包携带的 best_nhp 即是最长匹配结果。2.3 优势与代价· 容量/功耗仅使用标准 SRAM功耗远低于同容量 TCAM可轻松放 1M 条目。· 吞吐率流水线每周期接受一个新包实现每时钟周期 1 次查找甚至可并行多核。· 更新插入/删除只需修改受影响的子树节点重算 Bitmap支持高速批量更新。· 延迟流水线深度带来固定 8~10 周期延迟对于管线化转发可接受。3. 哈希与分段直接查找的混合方案3.1 DIR‑24‑8 经典架构将 IPv4 地址分成高 24 位和低 8 位两部分利用前缀分布的长尾特性绝大多数前缀长度 ≤ 24。· 第一级TBL24一张 2^24 入口的直接寻址表实际用哈希表压缩因为 16M 入口太大但早期 FPGA 实现会分配完整大块或用两层 16‑8 分割。每个 TBL24 条目存储· best_nhp前缀长度 ≤ 24 时到这个 24 位前缀为止的最长匹配下一跳。· long_ptr如果存在长度 24 的更具体前缀指向第二级表。· 第二级TBLlong对于前缀长度 24 的路由将这些前缀的低 8 位组织成一个小型多比特 Trie 或直接哈希表最多 256 个分支。查找时如果第一级指示有 long_ptr就根据 IP 低 8 位索引第二级表命中则覆盖 best_nhp。硬件流水线实现· Stage 1用 IP[31:8] 作为地址读 TBL24 SRAM获得 best1 和 ptr2。· Stage 2并行检查 ptr2 有效性若有效则用 {ptr2, IP[7:0]} 读 TBLlong SRAM得 best2。· Stage 3final_nhp ptr2 ? best2 : best1直接 MUX 选择。该方法电路简洁只用两块 SRAM 和简单控制逻辑功耗极低。缺点是对奇长前缀分布敏感若大量前缀集中在 /25/32 且 disjoint则 TBLlong 可能膨胀但可通过进一步哈希压缩。3.2 分层哈希 Bloom FilterSAIL 等某些架构按前缀长度分层将 /0/32 分成若干组每组单独开哈希表并利用片上 Bloom Filter 过滤掉绝大多数不存在的查询随后才去访问片外或深流水 SRAM。查找时同一 IP 对各层并行计算哈希经 Bloom Filter 筛选后仅命中层参与比较选取掩码最长层的结果。这类似于 TCAM 的并行长度匹配但用哈希实现适合大规模 IPv6同样可应用于 IPv4。---4. 实际芯片中的混合架构现代交换机/路由器 ASIC如 Broadcom XGS/DNX 系列、Barefoot Tofino、Cisco NLB普遍融合上述技术分配策略大体为· TCAM 用于小容量、高灵活性表如 ACL、PBR、少数高优先级路由。· SRAM 算法查找引擎 承担大规模路由表· Tofino 的 MAU可编程匹配‑动作单元可在每个 Stage 中使用 SRAM 实现任意 Trie 算法用户用 P4 编写或内置 Tree Bitmap 引擎。· Broadcom 的 L3_DefIP 表底层就是多比特 Trie 或 DIR‑24‑8 变形通过 SDK 向用户透明。· 硬件支持快速更新算法部分芯片用后台硬件线程重算 Trie 节点位图做到毫秒级 BGP 更新收敛。5. 方案对比与总结特性 TCAM SRAM 多比特 Trie (Tree Bitmap) DIR‑24‑8 混合查找延迟 1 周期极低 流水线深度 × 周期固定如8周期 2-3 周期吞吐率 每周期1次可并行多份 流水线化每周期1次易扩展多引擎 极高SRAM 带宽大容量 受功耗面积限制几十万条 数百万条 支持大规模依赖高效哈希压缩功耗 极高 低 低更新效率 复杂需排序搬移 局部更新可在线重算位图 仅影响分块更新快灵活性 支持任意掩码、范围匹配 仅精确前缀其他匹配需额外 TCAM 仅精确前缀典型应用 ACL、QoS、小容量路由 主干路由器 FIB 数据中心/企业交换机 LPM6. 未来趋势· 算法与可编程性结合P4 允许用户自定义查找算法芯片提供可配置的 SRAM/TCAM 策略。· 更深的流水线与 Chiplet 集成用 2.5D/3D 封装将大容量 SRAM 堆叠在逻辑 Die 上进一步扩大 Trie 规模。· AI‑guided 前缀压缩在线学习路由分布动态调整步长和压缩参数减少 SRAM 占用。· 统一 LPM/LPM6 引擎新一代芯片对 IPv4 和 IPv6 采用相同树位图/哈希引擎仅调整步长。综上硬件 LPM 实现已从单一 TCAM 全面演进到以流水化多比特 Trie 为核心、哈希和 TCAM 作为补充的异构架构用精巧的数据结构编码换取 SRAM 的巨大容量和低功耗支撑现代网络线速转发。