Multi-dimensional packet classification is a key task in network applications, such as firewalls, intrusion prevention and traffic management systems. With the rapid growth of network bandwidth, wire speed multi-dimensional packet classification has become a major challenge for next-generation network processing devices. In this paper, we present a FPGA-based architecture targeting 100 Gbps packet classification. Our solution is based on HyperSplit, a memory-efficient tree search algorithm. First, we present an efficient pipeline architecture for mapping HyperSplit tree. Special logic is designed to support two packets to be processed every clock cycle. Second, a node-merging algorithm is proposed to reduce the number of pipeline stages without significantly increasing the memory requirement. Third, a leaf-pushing algorithm is designed to control the memory usage and to support on-the-fly rule update. The implementation results show that our architecture can achieve more than 100 Gbps throughput for the 64-byte minimum Ethernet packets. With a single Virtex-6 chip, our approach can handle over 50K rules. Compared with the state-of-the-art multi-core network processor based solutions, our FPGA design offers at least a 10x improvement in throughput performance.

The security gateways today are required not only to block unauthorized accesses by authenticating packet headers, but also by inspecting connection states to defend against malicious intrusions. Hence session creation rate plays a key role in determining the overall performance of stateful intrusion prevention systems. In this paper, we propose a high-speed session creation scheme optimized for network processors. Main contribution includes: a) A high-performance flow classification algorithm on network processors; b) An efficient TCP three-way handshake scheme designed for fast-path processing using a two-stage intelligent hashing. Experimental results show that: a) The presented parallel optimized flow classification algorithm, Parallel Search Cross-Producting, outperforms the original Cross-Producting and Binary Search Cross-Producting algorithms with 300% and 60% increase of classification speed; b) The proposed fast path three-way handshake scheme, IntelliHash, achieves a TCP connection creation rate over 2M connections per second.

There is a growing interest in designing high-performance network devices to perform packet processing at flow level. Applications such as stateful access control, deep inspection and flow-based load balancing all require efficient flow-level packet processing. In this paper, we present a design of high-performance flow-level packet processing system based on multi-core network processors. Main contribution of this paper includes: a) A high performance flow classification algorithm optimized for network processors; b) An efficient flow state management scheme leveraging memory hierarchy to support large number of concurrent flows; c) Two hardware-optimized order-preserving strategies that preserve internal and external per-flow packet order. Experimental results show that: a) The proposed flow classification algorithm, AggreCuts, outperforms the well-known HiCuts algorithm in terms of classification rate and memory usage; b) The presented SigHash scheme can manage over 10M concurrent flow states on the Intel IXP2850 NP with extremely low collision rate; c) The performance of internal packet order-preserving scheme using SRAM queue-array is about 70% of that of external packet order-preserving scheme realized by ordered-thread execution.

In this paper, a novel packet classification scheme optimized for multi-core network processors is proposed. The algorithm, Explicit Cuttings (ExpCuts), adopts a hierarchical space aggregation technique to significantly reduce the memory usage. Consequently, without burst of memory usages, the time-consuming linear search in the conventional decision-tree based packet classification algorithms is eliminated, and an explicit worst-case search time is achieved. To evaluate the performance of ExpCuts, we implement the algorithm, as well as HiCuts and HSM, on the Intel IXP2850 network processor. Experimental results show that ExpCuts outperforms the existing best-known algorithms in terms of memory usage and classification speed.

Next-generation high-end network processors (NP) must address demands from both diversified applications and ever-increasing traffic pressure. One major challenge is to design an extraordinary scalable architecture. In this paper, it is argued that such an objective can only be sufficed by introducing highly paralleled structure, namely the paralleled processing-engine cluster (PPC). We demonstrate this point from the trade-off among aspects such as performance, programmability and flexibility. However, PPC natively suffers from several critical issues on load-balancing, intra-flow packet ordering and memory contention. After investigating several existing approaches, we present novel solutions for each issue according to the balance between performance and coast. Through intensive analysis and comprehensive simulations, it is shown that the shortest queue first scheduling with class-based prediction (SQF-C) performs nearly optimally, while the hardware based per-flow ordering mechanism resolves packet out-of-order independently with the load-balancing issue, inducting little throughput degradation. Implementing the unified solution, it is capable to design a PPC supporting up to OC-768c line rate. Real implementation is also carried out in our THNPU-1 prototype to verify the conclusions.

Packet classification on multiple header fields is one of the basic techniques used in network devices such as routers and firewalls, and usually the most computation intensive task among others. To determine what action needs to be taken to a packet, a network device responsible for packet classification must identify the packet's property, such as associated packet flow, based on multiple fields of its header. Fast packet classification on multiple fields is known to be difficult mathematically and expensive practically. In this paper, we describe and discuss a fast packet classification algorithm using a multiple stage reduction scheme similar to the previously well-known recursive flow classification (RFC) algorithm. The proposed hierarchical space mapping (HSM) algorithm requires much less memory usage than RFC while keeps average search time on the same order. HSM has been proved to be very effective with commercial products in real networks.