High-speed IP address lookup with fast prefix update is essential for designing wire-speed packet forwarding routers. The developments of optical fiber and 100 Gbps interface technologies have placed IP address lookup as the major bottleneck of high performance networks. In this paper, we propose a novel structure named Compressed Multi-way Prefix Tree (CMPT) based on B+ tree to perform dynamic and scalable high-speed IP address lookup. Our contributions are to design a practical structure for high-speed IP address lookup suitable for both IPv4 and IPv6 addresses, and to develop efficient algorithms for dynamic prefix insertion and deletion. By investigating the relationships among routing prefixes, we arrange independent prefixes as the search indexes on internal nodes of CMPT, and by leveraging a nested prefix compression technique, we encode all the routing prefixes on the leaf nodes. For any IP address, the longest prefix matching can be made at leaf nodes without backtracking. For a forwarding table with u independent prefixes, CMPT requires O(logmu) search time and O(mlogmu) dynamic insert and delete time. Performance evaluations using real life IPv4 forwarding tables show promising gains in lookup and dynamic update speeds compared with the existing B-tree structures.

Several hardware-based pattern matching engines for network intrusion/prevention detection systems (NIDS/NIPSs) can achieve high throughput with less hardware resources. However, their flexibility to update new patterns is limited and still challenging. This paper describes a PAttern Matching Engine with Limited-time updAte (PAMELA) engine using a recently proposed hashing algorithm called Cuckoo Hashing. PAMELA features on-the-fly pattern updates without reconfiguration, more efficient hardware utilization, and higher performance compared with other works. First, we implement the improved parallel exact pattern matching with arbitrary length based on Cuckoo Hashing and linked-list technique. Second, while PAMELA is being updated with new attack patterns, both stack and FIFO are utilized to bound insertion time due to the drawback of Cuckoo Hashing and to avoid interruption of input data stream. Third, we extend the system for multi-character processing to achieve higher throughput. Our engine can accommodate the latest Snort rule-set, an open source NIDS/NIPS, and achieve the throughput up to 8.8 Gigabit per second while consuming the lowest amount of hardware. Compared to other approaches, ours is far more efficient than any other implemented on Xilinx FPGA architectures.