High performance architectures for large-scale 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.互联网已爆发式增长为巨型开放网络。骨干网中的路由器应当以尽可能快的速度转发流量。然而，分组转发长期以来一直是这类路由器的性能瓶颈。随着吞吐量需求持续增长，内存效率也成为了另一项关键考量因素。尽管三元内容可寻址存储器（ternary content addressable memories, TCAMs）已被广泛应用于分组转发场景，但其功耗较高，且难以灵活适配新型寻址与路由协议。 伴随互联网的快速发展，网络安全已成为一项重大关切。网络攻击所需投入的人力与资金成本极低，且难以溯源，攻击者几乎可从全球任意地点发起攻击。计算机网络始终面临各类攻击与诈骗的侵扰，从烦人的黑客行为到更为恶劣的探测与活动。因此，网络流量过滤是保护此类网络的关键手段。 本学位论文研究两方面内容：(1) 适用于网络领域的算法；(2) 结合专用集成电路（application-specific integrated circuit, ASIC）和/或现场可编程门阵列（field programmable gate array, FPGA）技术的低功耗存储器（如静态随机存取存储器（static random access memory, SRAM））的应用。研究目标是为核心路由器所用的分组转发以及网络入侵检测系统所用的字符串模式匹配，开发高吞吐量、内存高效且灵活的算法解决方案。 具体而言，本文提出了映射至基于SRAM的架构中的前沿分组转发算法。此类架构通过采用流水线与/或多处理技术实现高吞吐量。本文探讨了此类算法到架构映射过程中的挑战与优化方案。得益于定制化的架构设计，这些算法经过优化，可实现高内存效率与吞吐量。 * 基于树的IP查找：本文描述了用于IP查找问题的基于树的算法与数据结构。该算法将路由表划分为前缀组，以最小化总内存消耗。本文还介绍了一种基于完全二叉搜索树的数据结构（可实现更优的内存效率），以及一种基于2-3树的数据结构（支持单周期增量更新）。所实现的吞吐量也超越了现有前沿技术。 * 基于前缀树（Trie）的IP查找：本文提出了两种用于压缩给定路由表的单位比特前缀树（uni-bit-trie）表示的算法。这些算法会在前缀树的每个节点上确定最优最大跳过距离，以最小化总内存需求。相较于单位比特前缀树算法与原始路径压缩算法，本文算法在IPv4/IPv6场景下均能显著降低内存占用。 * 虚拟路由器中的IP查找：本文提出了一种简单的合并算法，其性能不受所考虑的路由表数量影响，仅取决于前缀的总数量。本文还提出了一种新型可扩展、高吞吐量的线性流水线架构，用于IP查找，该架构可支持大型虚拟路由表以及快速无阻塞更新。 * 字符串模式匹配：本文深入挖掘了IP查找与字符串匹配问题之间的相似性。我们提出了一种名为“叶子附着（leaf-attaching）”的算法，可在不增加模式数量的前提下，高效地拆分给定字典。我们还提出了一种基于流水线二叉搜索树的、适用于大规模字符串匹配的可扩展、高吞吐量且内存高效的架构。相较于现有前沿技术，本文提出的算法与架构可实现更优的内存效率。字典更新仅需重写内存内容，无需重新配置芯片即可快速完成。 本文所提出的解决方案通过现代ASIC/FPGA平台进行了评估。实现结果表明，在吞吐量与内存消耗方面，本文方案的性能均超越了现有前沿技术。