Neurotrie: Deep Reinforcement Learning-based Fast Software IPv6 Lookup
Authors:
- 1 July 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 917-927
Abstract
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.Keywords
Funding Information
- National Science Foundation
This publication has 30 references indexed in Scilit:
- Helix: IP lookup scheme based on helicoidal properties of binary treesComputer Networks, 2015
- Poptrie2015
- New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based AlgorithmsIEEE Transactions on Computers, 2015
- DXRACM SIGCOMM Computer Communication Review, 2012
- Tree bitmapACM SIGCOMM Computer Communication Review, 2004
- Coolcams: power-efficient TCAMs for forwarding engines2004
- Longest prefix matching using bloom filters2003
- Routing lookups in hardware at memory access speeds2002
- Fast address lookups using controlled prefix expansionACM Transactions on Computer Systems, 1999
- Small forwarding tables for fast routing lookups1997