Hardware accelerator for FIB lookup in named data networking

Packets are identified by names in Named Data Networking (NDN). Names in NDN are hierarchically structured, and are consisted of one or more components. Packet forwarding in NDN router involves the matching of name prefixes using the component-based longest prefix match. Unlike fixed-length IP address, names can have variable-length and can be fairly long with over 100 bytes. Moreover, size of the forwarding information base (FIB) in NDN can be much larger than the IP forwarding table. Memory requirements, I/O bottleneck, and incremental updates to the FIB are the major concerns in the design of hardware FIB lookup engine. An offset-based lookup table organization is employed to optimize the memory spaces of the lookup tables. Name components are inputted to the lookup engine on-demand in order to reduce the I/O requirements. The proposed method allows incremental updates to the data structures without interrupting the on-going lookup operations. For proof of concept, our method is implemented on a virtex-7 FPGA, and the lookup engine can achieve 98.6 million searches per second.