Pyramid:一种基于精化DDLGN的层次化大规模路由查找
《Journal of Systems Architecture》:Pyramid: A hierarchical refined DDLGN-based large-scale routing lookup
【字体:
大
中
小
】
时间:2026年09月24日
来源:Journal of Systems Architecture 5.3
编辑推荐:
**摘要**
IPv6路由表的快速扩展使得核心路由器面临严峻的可扩展性危机,传统的最长前缀匹配(LPM)引擎不堪重负。虽然基于神经网络的方法展现出前景,但它们往往受制于"精度-可扩展性困境",即轻量级模型缺乏拟合复杂IPv6地址空间的能力,导致频繁的降级处理和高额的内存访问
**摘要**
IPv6路由表的快速扩展使得核心路由器面临严峻的可扩展性危机,传统的最长前缀匹配(LPM)引擎不堪重负。虽然基于神经网络的方法展现出前景,但它们往往受制于"精度-可扩展性困境",即轻量级模型缺乏拟合复杂IPv6地址空间的能力,导致频繁的降级处理和高额的内存访问开销。本文提出Pyramid,一种基于深度可微逻辑门网络(DDLGN)的层次化精化LPM架构。Pyramid将LPM问题分解为三阶段流水线,包括粗粒度分区、细粒度选择和DDLGN推理。通过将变长前缀映射为固定长度标签,Pyramid将LPM转化为一个静态分类任务。该设计利用专为FPGA LUT6资源优化的DDLGN,实现极致的参数压缩并消除浮点运算。此外,一种带范围预取的双重SRAM缓存机制有效掩盖了置信区间引导的二分搜索延迟。在基于FACE-VUP-13B FPGA的原型系统上,利用真实数据集进行评估,Pyramid在IPv6上达到95.3%的推理精度,与NeuroLPM相比减少了50%的内存访问。该系统支持多达100万条目的路由表,并可扩展至1000万条,在100 Gbps下实现线速处理,平均端到端查询延迟仅为1.0–1.25μs。
**引言**
物联网(IoT)设备的快速普及和IPv6的全面部署,在核心路由器中引发了前所未有的"路由爆炸"[1]、[2]。全球边界网关协议(BGP)路由表早已超过数十万条目,并持续指数级增长[3]。为了在100 Gbps及以上速度下维持线速转发,核心路由器必须在严格的延迟预算内执行最长前缀匹配(LPM)。然而,传统的LPM引擎正面临可扩展性瓶颈。三态内容可寻址存储器(TCAM)尽管提供O(1)的查询复杂度,但功耗极高且成本昂贵,其容量仅能维持在数万条目的量级[4]。相反,算法方案(如Tree Bitmap、SAIL)通常依赖外部DRAM访问,导致严重的缓存缺失惩罚,使其难以在不牺牲性能的情况下扩展至百万级条目表[5]、[6]。
近期研究探索利用机器学习(ML),特别是神经网络(NN),通过学习路由前缀的分布来解决该挑战[7]。尽管前景可期,这些方法面临着"精度-可扩展性困境"。一方面,通用神经网络如多层感知器(MLP)需要庞大的参数存储,且随规则集规模线性增长,使其在资源受限的转发平面中不可行[8]。另一方面,轻量级模型(如RQRMI)往往缺乏准确拟合复杂IPv6地址空间的能力,导致高误判率[9]。这些错误迫使频繁的降级机制(如二分搜索),重新引入了模型试图消除的内存访问延迟。图1对LPM解决方案进行了调查,并标明了Pyramid在其中的定位。
本研究的核心洞察在于,尽管IPv6地址空间极其庞大,但它表现出强烈的数值局部性和层次化结构[10]。我们不应将LPM视为纯粹的内存检索问题或黑箱分类任务,而是可以将其分解为层次化精化过程。通过将变长前缀映射为固定长度整数标签,并将推理组织为多阶段流水线,我们可以将查询开销与规则集规模解耦。
采用神经网络学习路由模式的合理性在于互联网拓扑的稳定性。在核心路由环境中,IP地址前缀本身变化频率较低[11]。真正频繁变化的是与这些前缀关联的出接口或下一跳,这由动态路由协议或流量工程驱动[12]。这一观察使我们能够将LPM问题建模为学习从IP地址到固定长度标签(表示前缀身份)的稳定映射,该映射不受接口变更影响。通过将标签推理与可变的转发动作解耦,Pyramid将LPM问题转化为一个非常适合神经网络近似的静态分类任务。
本文提出Pyramid,一种面向大规模路由查询的层次化精化DDLGN-LPM架构。Pyramid采用新颖的三阶段流水线:(1)通过并行比较器进行粗粒度区间划分,(2)细粒度子区间选择,以及(3)深度可微逻辑门网络(DDLGN)推理[13]、[14]。与传统输出one-hot向量的神经网络不同,Pyramid采用二进制编码输出层,大幅压缩参数占用。此外,我们引入一种置信区间引导的二分搜索机制,在保证100%正确性的同时,维持平均端到端查询延迟仅为1.0–1.25μs。
本文的主要贡献如下:
- 我们提出Pyramid,结合离散化地址采样与层次化神经网络结构。该设计降低了分类复杂度,使系统能够在单一现场可编程门阵列(FPGA)上处理多达100万条目的规则集。即使在1000万规则集的情况下,也可以利用片外DRAM存储规则集,在单一FPGA内完成推理压缩,并利用SRAM作为缓存实现线速处理。
- 我们使用DDLGN实现推理引擎,并针对FPGA 6输入查找表(LUT6)资源进行了专门优化。通过固定网络拓扑并采用二进制编码,我们消除了存储神经元间连接参数的需求,与BNNs、INT8或FP32模型相比,模型体积缩小了数个数量级。
- 我们设计了带范围预取的双重SRAM缓存机制。该机制掩盖了降级二分搜索的延迟,确保主流水线在200 MHz下达到200 Mpps的吞吐量,且与路由表大小无关。
- 我们在FACE-VUP-13B FPGA上利用真实数据集对Pyramid进行了评估。结果表明,Pyramid在IPv6上达到95.3%的推理精度,精度优于NeuroLPM 30%,并将内存访问减少50%。
**章节片段**
**LPM与路由查询**
假设一条LPM规则由$b$位组成,其中最低有效位被一个或多个通配符替换,例如5位规则$r_1=001**$和$r_2=00***$。非通配符位称为前缀。对于$b$位的二进制串,LPM寻找前缀最长的匹配规则。在该示例中,对于输入00111,匹配规则为$r_1$,因为它匹配了更多的固定位[15]。
当前的路由查询遵循LPM原则。传统方法是搜索路由表……
**系统概述**
Pyramid系统由三个核心组件组成:离线训练、在线推理和二分搜索,如图2所示。离线训练模块部署在控制平面,负责训练和分发神经网络模型参数。在线推理和二分搜索模块部署在数据平面。其主要功能是执行线速计算,为给定IP地址推导出固定长度索引和置信度因子$\alpha$……
**路由表条目标签分配算法**
为提升大规模IPv6路由表的处理效率,本文提出一种基于基数排序的路由表预处理和固定长度标签分配算法。该算法通过对路由条目进行标准化编码、排序和标签映射,为后续的前缀空间采样和高效查询奠定了基础。
**并行逻辑门计算单元**
传统DDLGN在训练过程中将层间神经元连接优化作为其一部分,并存储所得的最优连接状态。然而,在Pyramid架构中,第三阶段的神经网络推理层需要部署大量不同的神经网络。为在FPGA上实现完全流水线化的DDLGN推理,同时增强硬件并行性、最小化参数存储且不损害推理精度,我们将神经网络拓扑固定为全连接网络(FCN)。
**标签构建的理论基础**
在Pyramid框架中,我们采用基数排序基于IP地址空间的数值(即网络地址的整数表示)构建标签。该策略旨在将IP地址的内在结构相关性显式嵌入到标签空间中,从而使DDLGN能够利用数值规律性更高效地学习路由分类模式。该方法的效能源于其与……的高度契合。
**评估**
我们展示了Pyramid原型系统在资源利用、性能和功能方面的实验验证。Pyramid的RTL级设计使用Verilog HDL实现,并在FACE-VUP-13B FPGA开发板上构建了原型系统以支持功能和性能评估[31]。
**结论**
总之,本文提出Pyramid,一种层次化精化LPM架构,有效解决了IPv6扩展背景下的路由查询可扩展性瓶颈。通过将LPM问题分解为三阶段流水线——粗粒度分区、细粒度选择和基于DDLGN的推理——Pyramid成功地将复杂的多百万级分类任务转化为可管理的静态标注问题。其关键创新在于……的协同作用。
**CRediT作者贡献声明**
Zhongpei Liu:写作—审阅与编辑、写作—原稿撰写、验证、方法论、调查、形式化分析、数据整理、概念化。Baosheng Wang:写作—审阅与编辑、形式化分析、概念化。Gaofeng Lv:写作—审阅与编辑、方法论、资金获取、形式化分析、概念化。Jinli Yan:软件、资源。Junnan Li:可视化、调查、数据整理。Changshuai Zhan:方法论、形式化分析、数据整理。
**利益冲突声明**
作者声明不存在已知的竞争性经济利益或个人关系,这些关系可能影响本文所报告的工作。
Zhongpei Liu,博士候选人。其当前主要研究兴趣为计算机网络与网内计算。
Zhongpei Liu | Baosheng Wang | Gaofeng Lv | Jinli Yan | Junnan Li | Changshuai Zhan
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号