High performance architectures for packet forwarding and string pattern matching

The internet has grown explosively to a giant open network. Routers in the backbone should simply move traffic as fast as possible. However, packet forwarding has long been a performance bottleneck of these routers. While the throughput requirements continue to grow, memory efficiency has also been an additional critical concern. Although ternary content addressable memories (TCAMs) have been widely used for packet forwarding, they have high power consumption and are inflexible for adapting to new addressing and routing protocols.;Along with the rapid development of the Internet, network security has arisen as a major concern. Internet attacks require little effort or monetary investment, and are difficult to trace. They can be launched from virtually anywhere in the world. Computer networks are constantly assailed by attacks and scams, ranging from nuisance hacking to more nefarious probes and activities. Therefore, network traffic filtering is a crucial way to protect these networks.;This dissertation studies (1) algorithms that are applicable to the network field of research, and (2) the use of low-power memory, such as static random access memory (SRAM), combined with application-specific integrated circuit (ASIC) and/or field programmable gate array (FPGA) technology. The goals are to develop high-throughput, memory-efficient, and flexible algorithmic solutions for packet forwarding (used in core routers) and string pattern matching (used in network intrusion detection systems).;Specifically, state-of-the-art packet forwarding algorithms mapped onto SRAM-based architectures are proposed. In these architectures, high throughput is achieved by employing pipelining and/or multiprocessing. Challenges and optimizations for such algorithm-to-architecture mapping are addressed. Due to customized architecture design, these algorithms are optimized to achieve high memory efficiency and throughput. · Tree-based IP lookup : Tree-based algorithms and data structures for the IP lookup problem are described. The algorithm partitions a routing table into groups of prefixes to minimize the total memory consumption. A data structure based on a complete binary search tree that achieves superior memory efficiency and a data structure based on 2--3-tree that supports single-cycle incremental update are also introduced. The achieved throughput also surpasses that of the state-of-the-art. · Trie-based IP lookup: Two algorithms to compress the uni-bit-trie representation of a given routing table are presented. These algorithms determine the optimal maximum skip distance at each node of the trie to minimize the total memory requirement. Our algorithms demonstrate substantial reduction in the memory footprint compared with the uni-bit-trie algorithm and with the original path compression algorithm, for both IPv4/IPv6. · IP lookup in virtual routers: A simple merging algorithm whose performance is not sensitive to the number of routing tables considered is offered. The performance solely depends on the total number of prefixes. A novel scalable, high-throughput linear pipeline architecture for IP-lookup that supports large virtual routing tables and quick non-blocking update is also presented. · String pattern matching: The similarities between IP lookup and string matching problems are intensively exploited. We propose an algorithm called leaf-attaching to efficiently disjoint a given dictionary without increasing the number of patterns is given. We also present a scalable, high-throughput, and memory efficient architecture for large-scale string matching based on pipelined binary search tree.;The proposed algorithm and architecture achieve a superior memory efficiency compared with the state-of-the-art. Dictionary update involves only rewriting the memory content, which can be done quickly without reconfiguring the chip. The proposed solutions are evaluated using modern ASIC/ FPGA platforms. The implementation results demonstrate superior performance over the state-of-the-art, with respect to the throughput and memory consumption.