Dynamically updateable and memory-efficient search structures for Internet protocol (IP) lookup have lately attracted a great deal of attention from the researchers. In this paper, we focus on the next-generation IPv6 routing protocol comprising large and sparsely distributed routing tables. The existing data structures either suffer from inefficient resource and memory usage (trie-based algorithms), or require complicated construction processes such as converting routing prefixes into their longer representatives and sorting (tree-based algorithms), or both. We propose a novel data structure denoted value-coded trie (VC-trie) for IP lookup. VC-trie provides significant memory saving in comparison with that of the existing solutions in both IPv4 and IPv6 domains. Thereby, our structure can support longer prefix lengths and larger routing tables. We also design an static random access memory (SRAM)-based pipelined architecture to assist the VC-trie structure to improve the throughput. The architecture is implemented utilizing a state-of-the-art field programmable gate array (FPGA) device and sustainable throughput of 448 million lookups per second (with a routing table consisting of 324 K prefixes) is achieved. Furthermore, the architecture can be enhanced with external SRAMs to relax the limitations of the existing FPGA device in on-chip memory.
Most current SRAM-based high-speed Internet Protocol (IP) packet classification implementations use tree traversal and pipelining. However, these approaches result in inefficient memory utilization. Due to the limited amount of on-chip memory of the state-of-the-art Field Programmable Gate Arrays (FPGAs), existing designs cannot support large filter databases arising in backbone routers and intrusion detection systems. Hierarchical search structures for packet classification exhibit good memory performance and support quick rule update. However, pipelined hardware implementation of these algorithms suffer from inefficient resource and memory usage due to variation in the size of the trie nodes and backtracking. We propose a memory efficient organization denoted Clustered Hierarchical Search Structure (CHSS) for packet classification. We present a clustering algorithm that partitions a given filter database to reduce the memory requirement. We show that, using the resulting structure, backtracking is not needed to perform a search. We introduce two parameters (NR trie , NR tree ), which can be chosen based on the given filter database to achieve good memory efficiency. Our algorithm demonstrates substantial reduction in the memory footprint compared with the state-of-the-art. For all publicly available filter databases, the achieved memory efficiency is between 21.54 and 41.25 bytes per rule. We map the proposed data structure onto a linear pipeline architecture to achieve high throughput. Post place and route result using a state-of-the-art FPGA device shows that the design can sustain a throughput of 408 million packets per second, or 130.5 Gbps (for the minimum packet size of 40 Bytes).
1 May 2014 in Computers and Electrical Engineering