{'fraction_non_alphanumeric': 0.03420669577874818, 'fraction_numerical': 0.013100436681222707, 'mean_word_length': 4.681818181818182, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
High-Performance Pipelined Architecture for Tree-Based IP Lookup Engine on FPGA

IP lookup problem involves searching the input IP address for a matching IP prefix in the routing table. Hardware-accelerated IP lookup engines based on various data structures such as balanced tree structures have been proposed over the years. In tree-based approaches, as the size of the tree increases, large off-chip memory has to be used. In addition, the linear growth of wire length with respect to the number of nodes at a level adversely affects the throughput. We present a tree-based IP lookup engine on FPGA which optimizes the pipeline with respect to scalability and throughput. Our solution has the following novel features: (1) We present a 2-dimensional fine-grained layout for the Processing Elements (PEs) using distributed RAM to reduce the maximum wire length. (2) We employ "split-tree" architecture for BRAM-based PEs at each tree level to improve the clock rate. (3) We use a realistic model of off-chip memory access and guarantee high throughput for the lookup process. Post place-and-route results show that, our tree-based IP lookup engine can achieve a throughput of 400MLPS (million lookups per second) for any routing table containing 256~512K IPv6 prefixes, while using 59% of the logic resources and 19% of the BRAM available on a state-of-the-art FPGA device.