SIGCOMM ’25: ACM SIGCOMM 2025 Conference
Conference Sponsors: SIGCOMM‘25
https://dl.acm.org/doi/10.1145/3718958.3750531

一、研究背景与动机：名字查找的速度瓶颈
在信息中心网络（ICN）和内容分发网络（CDN）中，基于名字的数据转发是核心机制。与传统的 IP 地址不同，内容名字（如 URL）通常是分层的、变长的且长度无界的。这种特性使得**名字前缀查找（Name Prefix Lookup）**成为限制网络转发速率的关键瓶颈。
现有的解决方案大多基于 Trie 树、哈希或 Bloom Filter，通常运行在 SRAM 或 DRAM 上。虽然 SRAM/DRAM 容量大，但其查找速度往往受限于访存次数（Memory Access），难以追赶日益增长的链路速率（Line Rate）。相比之下，**三态内容寻址存储器（TCAM）** 以其并行查询能力著称，能够在一个时钟周期内完成查找，是实现线速转发的理想选择。然而，TCAM 的容量极小且功耗高，难以直接存储数以千万计的长名字前缀。如何利用小容量的 TCAM 实现大规模、长名字的高速查找，是本论文解决的核心问题。

二、核心挑战：如何在小 TCAM 上装下海量长名字？
将 TCAM 应用于名字查找面临两个主要挑战：
1.  扩展性（Scalability）：名字集合（FIB）规模巨大且名字长度无界，而 TCAM 容量有限（通常仅几十 Mb）。将完整的变长名字直接存入 TCAM 是不可能的。
2.  特定的硬件约束：TCAM 适合固定宽度的匹配，而分层名字结构复杂，需要高效的编码方式才能利用 TCAM 的位并行特性。

三、PtCAM 系统架构：基于 Patricia Trie 的混合查找方案
PtCAM（Patricia-TCAM）提出了一种创新的软硬件协同设计，巧妙结合了 **Binary Patricia Trie** 的结构优势与TCAM的硬件加速能力。
其核心思想采用“分而治之”的策略：
TCAM 作为分类器（Classifier）：不仅存储完整的名字，而是存储从名字中提取的“紧凑摘要”（Compact Name）。这些摘要由 Patricia Trie 上的关键区分位（Discrimination Bits）组成。
RAM 作为验证器（Verifier）：存储完整的名字前缀和转发信息。TCAM 快速定位可能的候选条目，RAM 进行最终的精确匹配验证。

关键技术点：
1. 紧凑名字提取（Compact Name Extraction）：
利用 Binary Patricia Trie 的特性，PtCAM 能够识别出区分不同名字的“关键位位置”（Critical Bit Positions）。对于每一个名字，仅需提取这些位置上的比特值，拼接成一个定长的“紧凑名字”存入 TCAM。这种方法极大地压缩了存储空间，使得 TCAM 能够容纳海量名字。
2.  TCAM 内存布局生成：
PtCAM 将提取的关键位映射为 TCAM 的列。对于不需要匹配的位，利用 TCAM 的“Don’t Care”状态（通配符）进行处理，从而完美适配 TCAM 的硬件特性。

四、实验评估：逼近硬件极限的查找速度
论文原型系统在商用 TCAM 设备上进行了验证，并进行了大规模的仿真实验。
极高的查找吞吐量：实验结果表明，PtCAM 的查找速度接近 TCAM 设备的物理吞吐量极限。相比于传统的基于 Trie 或 Hash 的软件/FPGA 方案，PtCAM 实现了数量级的性能提升。
优异的存储效率：在单片 80Mbits 的 TCAM 芯片上，PtCAM 能够支持超过110 万个现实世界的人类可读名字（如 URL），或160 万个随机字符名字。
良好的扩展性：通过级联多片 TCAM，系统可以轻松扩展以支持更大规模的名字表。、

五、总结与展望：开启工业级 ICN 部署之门
PtCAM的重要意义在于，通过巧妙的算法设计，使得现有的、成熟的商用 TCAM 硬件（通常用于 IP 路由）能够直接用于下一代互联网（ICN/NDN）的名字路由。这意味着我们无需等待昂贵的新型专用硬件，即可在现有基础设施上实现高性能的名字转发。
这项工作不仅为 ICN 的落地扫除了一大性能障碍，也为其他需要高速字符串前缀匹配的领域（如 DPI、防火墙、内容感知路由）提供了一种通用且高效的硬件加速范式。