Design of On-chip FIB for 10G NDN Router Based on FPGA

Abstract:
The Forwarding Information Base (FIB) of the Named Data Network (NDN) is a routing table that forwards according to the name prefix of each Interest packet, which forwards according to the longest name prefix match (LPM) principle. The use of the FPGA on-chip memory can meet the table lookup speed requirement required by the 10 Gigabit transmission rate, but limited by the on-chip storage capacity of the FPGA, there are few FIB entries that can be stored. To this end, a Bit-aparted Trie based on on-chip memory is proposed. This data structure can maintain the query conflict rate at a low level while significantly improving the search speed and reducing storage space requirements. Experiments show that, in Xilinx Zynq 7000 FPGA, Bit-aparted Trie consumes only 9.81Mbit on-chip BRAM, can store 30k routes, and complete all searches in 153.6ns, and the search speed is 2.52 times faster that of the existing algorithm.