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.

An efficient ternary content addressable memory (TCAM) encoding scheme using a binary reflected Gray code (BRGC) and the concept of elementary intervals is presented for efficiently storing arbitrary ranges in TCAM. The proposed layered BRGC range encoding scheme (L-BRGC) groups ranges into BRGC range sets in which each range can be encoded into a single ternary vector. The results of experiments performed on real-life and synthesized rule tables show that L-BRGC consumes less TCAM than all the existing range encoding schemes for all rule tables, except that the direct conversion scheme (EIGC) using elementary intervals and BRGC codes performs best for a small real-life ACL rule table.

Packet classification has wide applications such as unauthorized access prevention in firewalls and Quality of Service supported in Internet routers. The classifier containing pre-defined rules is processed by the router for finding the best matching rule for each incoming packet and for taking appropriate actions. Although many software-based solutions had been proposed, high search speed required for Internet backbone routers is not easy to achieve. To accelerate the packet classification, the state-of-the-art ternary content-addressable memory (TCAM) is a promising solution. In this paper, we propose an efficient multi-field range encoding scheme to solve the problem of storing ranges in TCAM and to decrease TCAM usage. Existing range encoding schemes are usually single-field schemes that perform range encoding processes in the range fields independently. Our performance experiments on real-life classifiers show that the proposed multi-field range encoding scheme uses less TCAM memory than the existing single field schemes. Compared with existing notable single-field encoding schemes, the proposed scheme uses 12% ~ 33% of TCAM memory needed in DRIPE or SRGE and 56% ~ 86% of TCAM memory needed in PPC for the classifiers of up to 10k rules.

Network Intrusion Detection System (NIDS) is a system which can detect network attacks resulted from worms and viruses on the Internet. An efficient pattern matching algorithm plays an important role in NIDS. There have been many proposed methods for pattern matching algorithms. Traditionally, the multi-character NFA that is capable of matching multiple characters per cycle can be built by duplicating entire circuit of 1-character architecture. In this paper, we propose a pre-processing based architecture to improve the original multi-character architecture. The design of the proposed architecture and its implementation in FPGA are described in details. Our simulation results show that the proposed architecture performs better than all the existing Brute-Force based approaches in terms of the throughput and the slice utilization. Specifically, the proposed architectures of 2-character and 4-character designs can achieve the throughputs of 4.68 and 7.27 Gbps and the slice utilization of 2.86 and 2.10 in terms of char/slice, respectively.

Multi-field Packet classification is the main function in high-performance routers. The current router design goal of achieving a throughput higher than 40 Gbps and supporting large rule sets simultaneously is difficult to be fulfilled by software approaches. In this paper, a set pruning trie based pipelined architecture called Set Pruning Multi-Bit Trie (SPMT) is proposed for multi-field packet classification. However, the problem of rule duplications in SPMT that may cause a memory blowup must be solved in order to implement SPMT with large rule sets in FPGA devices consisting of limited on-chip memory. We will propose two rule grouping schemes to reduce rule duplications in SPMT. The first scheme called Partition by Wildcards (PW) divides the rules into subgroups based on the positions of their wildcard fields. The second scheme called Partition by Length (PL) rules partitions the rules into subgroups according to their prefix lengths. Based on our performance experiments on Xilinx Virtex-5 FPGA device, the proposed pipeline architecture can achieve a throughput of over 100 Gbps with dual port memory. Also, the rule sets of up to 10k rules can be fit into the on-chip memory of Xilinx Virtex-5 FPGA device.

A dynamic multiway segment tree (DMST) is proposed for IP lookups in this paper. DMST is designed for dynamic routing tables that can dynamically insert and delete prefixes. DMST is implemented as a B-tree that has all distinct end points of ranges as its keys. The complexities of search, insertion, deletion, and memory requirement are the same as the existing multiway range tree (MRT) and prefix in B-tree (PIBT) for prefixes. In addition, a pipelined DMST search engine is proposed to further speed up the search operations. The proposed pipelined DMST search engine uses off-chip SRAMs instead of on-chip SRAMs because the capacity of the latter is too small to hold large routing tables and the cost of the latter is too expensive. By utilizing current FPGA and off-chip SRAM technologies, our proposed five-stage pipelined search engine can achieve the worst case throughputs of 33.3 and 41.7 million packets per second (Mpps) with 144-bit and 288-bit wide SRAM blocks, respectively. Furthermore, a straightforward extension of the pipelined search engine with multiple independent off-chip SRAMs can achieve the throughput of 200 Mpps which is equivalent to 102 Gbps for minimal Ethernet packets of size 64 bytes.

With the increasing growth of the Internet, the explosion of attacks and viruses significantly affects the network security. Network intrusion detection system (NIDS) is developed to identify these network attacks by a set of rules. However, searching for multiple patterns is a computationally expensive task in NIDS. Traditional software-based solutions can not meet the high bandwidth demanded in current high-speed networks. In the past, the pre-filtering designed for NIDS is an effective technique that can reduce the processing overhead significantly. A FNP- like TCAM searching engine (FTSE) is an example that uses an 2-stage architecture to detect whether an incoming string contains patterns. In this paper, we propose two techniques to improve the performance of FTSE that utilizes ternary content addressable memory (TCAM) as pre-filter to achieve gigabit performance. The first technique performs the w-byte suffix pattern match instead of using w-byte prefix. The second technique finds the matching results from all groups rather than first group. We finally present the simulation result using Snort pattern set and DEFCON packet traces.

This short report first indicates a design flaw in the contention resolver unit proposed in [Akhbarizadeh et al., 2007] and then proposes an improved design which is simpler and faster.

Packet classification is an enabling function in Internet routers for a variety of Internet applications. In order to classify Internet packets into flows, Internet routers must perform searches over a set of filters using multiple fields of the packet as the search key. Because of its speed and simple filter management the Ternary Content Addressable Memory (TCAM) is currently the dominant hardware solution for IP lookups, i.e., a one-dimensional packet classification. To make TCAM the solution for the multi-dimensional packet classification, efficient methods that store the range fields of the classification tables in TCAM are needed. In this paper, we propose a set of novel range encoding schemes based on Gray code. Many range-encoding techniques are used to improve the existing elementary interval- based range encoding schemes. The present experiment's results show that the proposed Gray code-based schemes consume less TCAM storage space than the existing schemes.