计算机科学
内存占用
强化学习
IPv6
隐藏物
特里亚
并行计算
IPv4
布线(电子设计自动化)
路由表
节点(物理)
数据结构
路由协议
嵌入式系统
人工智能
操作系统
工程类
互联网
结构工程
作者
Hao Chen,Yuan Yang,Mingwei Xu,Yuxuan Zhang,Chenyi Liu
标识
DOI:10.1109/icdcs54860.2022.00093
摘要
IPv6 has shown notable growth in recent years, imposing the need for high-speed IPv6 lookup. As the forwarding rate of virtual switches continues increasing, software-based IPv6 lookup without using special hardware such as TCAM, GPU, and FPGA is of academic interest and industrial importance. Existing studies achieve fast software IPv4 lookup by reducing the operation number, as well as reducing the memory footprint so as to benefit from CPU cache. However, in the situation of 128-bit IPv6 addresses, it is challenging to keep both operation numbers and memory footprints small. To address the issue, we propose the Neurotrie data structure, which supports fast lookup and arbitrary strides. Thus, a good balance can be made between trie depth and memory footprint by computing the proper stride for each Neurotrie node. We model the optimal Neurotrie problem which minimizes the depth with limited memory footprint and develop a pseudo-polynomial time baseline algorithm to construct Neurotrie using dynamic programming. To improve the performance and reduce the computation complexity, we develop a deep reinforcement learning-based approach, which leverages a deep neural network to construct Neurotrie efficiently, based on characteristics captured from real IPv6 prefixes. We further refine the data structure and develop an efficient mechanism for routing updates. Experiments on real routing tables show that Neurotrie achieves a lookup rate 34% higher than that of state-of-the-art approaches.
科研通智能强力驱动
Strongly Powered by AbleSci AI