面向可编程边缘交换机的内存高效NDN转发信息库设计CoFIB

《IEEE Transactions on Nanotechnology》：CoFIB: A Memory-Efficient NDN FIB Design for Programmable Edge Switches

本文针对命名数据网络（NDN）中转发信息库（FIB）规模远超IP路由表、难以在可编程交换机芯片内存中存储百万级前缀的挑战，提出了一种名为CoFIB的压缩FIB数据结构。该研究设计了基于规范名称前缀的压缩算法，优化了流水线中表项放置策略，并实现了在数据平面进行最长名称前缀匹配（LNPM）的算法。实验表明，CoFIB内存压缩比达到16.58倍，吞吐量较线性表放置策略提升23.17%，为NDN在可编程边缘交换机上的Tbps级转发提供了纳秒级延迟的解决方案。

　　

在当今互联网流量爆发式增长的背景下，基于IP地址的传统网络架构逐渐暴露出扩展性不足、内容分发效率低下等问题。命名数据网络（Named Data Networking，NDN）作为一种革命性的未来网络架构，将通信模式从关注"在哪里"转变为关注"是什么"，通过名称直接标识和获取内容，为高效内容分发提供了新思路。然而，这种范式转变也带来了前所未有的技术挑战——其中最为关键的就是如何设计高性能、低内存占用的转发信息库（Forwarding Information Base，FIB）。

与传统IP网络中的路由表相比，NDN的FIB需要存储的是可变长度的名称前缀，其规模可能比IP路由表大几个数量级。更棘手的是，现代可编程交换机的芯片内存资源极其有限，TCAM（Ternary Content-Addressable Memory）昂贵且功耗高，SRAM（Static Random-Access Memory）虽然成本较低但容量有限。现有的解决方案往往需要在性能和内存效率之间做出妥协：软件实现的FIB虽然灵活但处理速度慢，硬件方案虽然快速但难以支持大规模前缀存储。这种矛盾在网络边缘设备上表现得尤为突出，因为边缘交换机需要同时处理高速数据流和海量内容请求。

正是在这样的背景下，研究人员将目光投向了可编程数据平面技术，特别是P4（Programming Protocol-independent Packet Processors）语言的出现为在硬件层面实现定制化数据包处理提供了可能。但是，将NDN FIB成功卸载到可编程交换机ASIC（Application-Specific Integrated Circuit）中仍然面临多重障碍：不仅需要克服P4语言对可变长度名称处理的限制，还要在有限的TCAM/SRAM内存中高效存储数百万个名称前缀，同时保证纳秒级的查找延迟。

为了突破这些技术瓶颈，本研究团队开发了CoFIB（Compressed FIB），一种专为SDN（Software-Defined Networking）环境下可编程边缘交换机设计的内存高效FIB数据结构。CoFIB的创新之处在于它不再试图将整个FIB强制塞入有限的芯片内存，而是通过智能的协同设计方法，在数据平面和控制平面之间合理分配存储和计算任务。

研究团队首先提出了规范名称前缀（Canonical Name Prefix）的概念——即所有组件在所有前缀的相同位置出现的名称前缀。通过专门设计的规范前缀提取算法（Canonical Prefix Extractor，CPE），系统能够自动从路由信息库（Routing Information Base，RIB）中识别出适合在数据平面存储的规范前缀，而将非规范前缀卸载到控制平面处理。这种策略显著减少了数据平面需要存储的前缀数量，同时保持了转发准确性。

在数据平面设计上，CoFIB采用了多表分散存储策略，将名称组件按其长度分布存储在不同的P4表中，而非使用单个大表。这些表被优化放置在交换机的入口和出口流水线中，充分利用了芯片两端的SRAM内存资源。为了简化名称处理，团队还设计了P4名称友好格式（P4 Name Friendly Format，P4NF），将可变长度的NDN名称转换为固定字段的格式，便于P4程序解析和处理。

最长名称前缀匹配（Longest Name Prefix Matching，LNPM）算法是CoFIB的核心创新之一。该算法通过在流水线中精心安排数据包的重循环（recirculation），在单次管道传递中执行多次匹配操作，显著减少了处理延迟。研究人员还开发了表放置优化算法，根据名称组件的分布特征智能安排表项在入口和出口流水线中的位置，进一步减少了重循环次数。

关键技术方法包括：1）基于规范前缀提取算法的控制平面设计，从RIB中智能分离适合硬件存储的前缀子集；2）P4名称友好格式转换，将可变长度NDN名称转换为固定字段格式；3）多表分散存储架构，按组件长度将FIB分布到多个SRAM表中；4）入口-出口流水线协同处理机制，实现高效的最长前缀匹配；5）基于真实和合成名称数据集（包括0.1K、440K、2M、10M等）的性能评估方法。

规范前缀提取性能

研究团队通过CPE算法从不同规模的RIB数据集中提取规范前缀，实验结果表明即使对于包含数百万前缀的大型数据集，算法仍能有效识别出相当比例的规范前缀。当数据集规模增大时，卸载比率（即适合存储在数据平面的前缀比例）有所下降，但对于真实名称数据集（如440K和10M），这种下降较为平缓，证明CPE算法具有良好的扩展性。

内存占用分析

与FCTree、NDN.p4和HBM等现有方案相比，CoFIB在内存压缩方面表现卓越。实验数据显示，CoFIB的内存消耗比NDN.p4减少高达13.64倍，比FCTree减少16.58倍，比HBM减少2.83倍。即使是存储430万前缀的4M数据集，CoFIB也仅需占用25.5MB SRAM（占芯片总SRAM的25.5%）和1.9MB TCAM（占芯片总TCAM的36.8%），完全在现有可编程交换机的内存容量范围内。

吞吐量性能

在吞吐量测试中，CoFIB与HBM的性能差距极小——在排序数据包测试中仅为3.86%，在随机数据包测试中进一步缩小到2.83%。更重要的是，通过表放置优化策略，CoFIB能够将线速处理的数据包比例从20.57%提升到43.74%，使吞吐量更接近线速性能。管道传递次数分析表明，94.77%的Interest数据包（Ipkts）仅需两次或更少的管道传递即可完成LNPM操作。

管道传递效率

CoFIB的管道处理逻辑通过精心设计的入口和出口流水线协作，有效减少了不必要的重循环。实验结果显示，使用表放置优化策略后，经历两次管道传递的数据包比例从82.95%提升至94.77%，经历三次管道传递的比例从96.98%提升至99.65%。这种优化显著提高了整体处理效率，为在真实可编程交换机上实现纳秒级延迟奠定了基础。

研究结论表明，CoFIB成功解决了NDN FIB在可编程边缘交换机上面临的内存可扩展性和处理延迟之间的权衡问题。通过规范前缀提取、流水线优化和智能表放置等创新技术，CoFIB能够在有限的芯片内存中存储数百万名称前缀，同时保持纳秒级的处理延迟。与现有解决方案相比，CoFIB是首个充分利用可编程ASIC中SRAM内存资源的NDN FIB数据结构，不再依赖稀缺且功耗高的TCAM内存。

讨论部分强调了CoFIB设计的实用价值和理论意义。首先，将CoFIB部署仅限於边缘交换机的策略，允许核心网络继续以线速转发数据包，从而优化了端到端性能。其次，通过协同设计方法，CoFIB在保持硬件转发性能的同时，通过控制平面处理复杂案例，实现了灵活性和性能的理想平衡。最后，研究人员指出未来工作的重点包括将CoFIB部署到Tofino等真实可编程交换机硬件上，以及探索推测性匹配操作等进一步优化技术。

这项研究为未来网络架构的实践部署提供了重要技术支撑，标志着NDN从理论研究向实际应用迈出了关键一步。通过解决FIB这一长期困扰NDN发展的核心难题，CoFIB为构建高效、可扩展的命名数据网络奠定了基础，对未来互联网演进具有深远影响。