Multibit trie-based pipelines for IP lookups have been demonstrated to be able to achieve the throughput of over 100 Gbps. However, it is hard to store the entire multibit trie into the on-chip memory of reconfigurable hardware devices. Thus, their performance is limited by the speed of off-chip memory. In this paper, we propose a new pipeline design called LayeredTrees that overcomes the shortcomings of the multibit trie-based pipelines. LayeredTrees pipelines the multi-layered multiway balanced prefix trees based on the concept of most specific prefixes. LayeredTrees is optimized to fit the entire routing table into the on-chip memory of reconfigurable hardware devices. No prefix duplication is needed and each${\mbi {W}}$-bit prefix is encoded in a (${\mbi {W}} + {\bf 1}$)-bit format to save memory. Assume the minimal packet size is 40 bytes. Our experimental results on Virtex-6 XC6VSX315T FPGA chip show that the throughputs of 33.6 and 120.8 Gbps can be achieved by the proposed single search engine and multiple search engines running in parallel, respectively. Furthermore, the impact of update operations on the search performance is minimal. With the same FPGA device, an IPv6 routing table of 290,503 distinct entries can also be supported.

Ternary content-addressable memory (TCAM) is a simple hardware device for fast IP lookups that can perform a lookup per cycle. However, prefixes may be inserted into or deleted from the TCAM because of changes in Internet topology. Traditional TCAM coprocessors maintain the enclosure relationship among prefixes by using an extended binary trie and perform TCAM movements based on an update algorithm (e.g., CAO_OPT) which runs on a local CPU to maintain the speed and correctness of the TCAM search process. In this paper, we propose a memory-efficient TCAM coprocessor architecture for updates that require only small memory size compared with the extended binary trie. The average number of TCAM movements per update is almost the same as that of CAO_OPT. However, the time to compute how to move TCAM entries in the proposed TCAM coprocessor is less than that in CAO_OPT. Only a small part of total TCAM search cycles is used to complete our update process. The proposed TCAM architecture can also be made smaller and faster because large off-chip memory for the extended binary trie and a local CPU are no longer necessary.

With the evolution of the Internet, current routers need to support a variety of emerging network applications while the high packet processing rate is still guaranteed. As a result, the network processor has become a promising solution for network devices due to its computation capability and programming flexibility. However, developing the network applications on network processors is not easy. How to efficiently program multiple processing elements and utilize various memory modules as well as the hardware resources on network processors are always challenges. In this paper, we investigate several optimization issues and programming techniques that should be considered by the developers to achieve higher packet processing rate on network processors. We use an existing packet classification scheme called hierarchical binary prefix search (HBPS) [1] as the benchmark to test and evaluate these optimization techniques. The experiments conducted on Intel IXP2400 network processor show that the overall performance of HBPS can be improved about 42% while these techniques are adopted.

IP address lookup is one of the most important functionalities in the router design. To meet the requirements in high speed routers consisting of line-cards with 40 Gbps transfer rates, researchers usually take lookup/update speed, storage requirement, and scalability into consideration when designing a high performance forwarding engine. As a result, hardware-based solutions are often used to develop a high speed router nowadays. In this paper, we develop a FPGA-based pipelined forwarding engine which focuses on reducing the update overhead. The proposed scheme partitions the routing table into several disjoint groups. The prefix which resides in the same group is interleaving stored into several memory modules to ensure the parallel comparison at the comparison stage. With the pipeline enabled, the throughput of the design can achieve the speed of OC-768. The update overhead can also be reduced.