| Packet forwarding has long been a performance bottleneck in Internet infrastructure, including routers and switches. While the throughput requirements continue to grow, power dissipation has emerged as an additional critical concern. Also, as the Internet continues to constantly evolve, packet forwarding engines must be flexible in order to enable future innovations. 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.;This thesis studies the use of low-power memory, such as static random access memory (SRAM) combined with application-specific integrated circuit (ASIC)/fieldprogrammable gate array (FPGA) technology, to develop high-throughput, power-efficient, and flexible algorithmic solutions for various packet forwarding problems, which include IP lookup, packet classification and flexible flow matching (such as OpenFlow).;We propose to map state-of-the-art packet forwarding algorithms onto SRAM-based parallel architectures. High throughput is achieved via pipelining and/or multi-processing. Several challenges for such algorithm-to-architecture mapping are addressed. Meanwhile, enabled by the customized architecture design, the algorithms are optimized to achieve memory and/or power/energy efficiency. (1) For IP lookup, we propose two mapping schemes to balance the memory distribution across the stages in a pipeline. In the case of multi-pipeline architectures, our schemes balance both the memory requirement and the traffic load among multiple pipelines. The intra-flow packet order is also preserved. (2) In addition to the power reduction achieved by replacing TCAMs with SRAMs, we propose data structure and architectural optimizations to further lower the power/energy consumption for SRAM-based pipelined IP lookup engines. (3) For packet classification, we propose a decision-tree-based, two-dimensional dual-pipeline architecture. Several optimization techniques are proposed for the state-of-the-art decision-tree-based algorithm. As a result, the memory requirement is almost linear with the number of rules in the forwarding table. (4) Considering OpenFlow as a representative of flexible flow matching, we develop a framework to partition a given table of flexible flow rules into multiple subsets, of which each is built into a depth-bounded decision tree. The partitioning scheme is carefully designed to reduce the overall memory requirement. We evaluate our solutions implemented on modern ASIC/FPGA and demonstrate their superior performance over the state-of-the-art with respect to throughput, memory requirement and power/energy consumption. |
