Wednesday, 23 July 2014

A Scalable and Modular Architecture for High-Performance Packet Classification


Packet classification is widely used as a core function for various applications in network infrastructure. With increasing demands in throughput, performing wire-speed packet classification has become challenging. Also the performance of today’s packet classification solutions depends on the characteristics of rulesets. In this work, we propose a novel modular Bit-Vector (BV) based architecture to perform high-speed packet classification on Field Programmable Gate Array (FPGA). We introduce an algorithm named StrideBV and modularize the BV architecture to achieve better scalability than traditional BV methods. Further, we incorporate range search in our architecture to eliminate ruleset expansion caused by range to-prefix conversion. The post place-and-route results of our implementation on a state-of-the-art FPGA show that the proposed architecture is able to operate at 100+ Gbps for minimum size packets while supporting large rulesets up to 28 K rules using only the on-chip memory resources. Our solution is ruleset-feature independent, i.e. the above performance can be guaranteed for any ruleset regardless the composition of the ruleset.
PACKET classification is a prominent technique used in networking equipment for various purposes. Its applications are diverse, including network security, access control lists, traffic accounting. To perform packet classification, one or more header fields of an incoming packet is checked against a set of predefined rules, usually referred to as a ruleset or a classifier. Performing packet classification is challenging since it involves inspection of multiple fields against a ruleset possibly containing thousands of rules. Performing such operations at wire-speed is even more challenging with the increasing throughput demands in modern networks. Various hardware platforms have been employed for packet classification in the past.
v Optimizations that target a specific ruleset feature, are not robust to be employed in environments where the ruleset changes dynamically and frequently.
v Various hardware are required to do efficiently.

We present a novel architecture for packet classification, whose performance is independent from ruleset features and is suitable for hardware platforms.We use a Bit-Vector (BV) based approach to represent the ruleset. Each rule is represented as a collection of sub-rules and we propose an algorithm named StrideBV to generate the sub-rules, which is an extension of the Field Split Bit Vector (FSBV) algorithm proposed in [6]. Our solution offers the user the flexibility of deciding the bit width of each sub-rule, which in turn decides the performance trade-off of the architecture. In order to handle the arbitrary ranges,we augment the architecture with explicit range search capability which does not require any range to- prefix conversion. This yields higher memory efficiency which enhances the scalability of our approach. In addition, we propose a rule priority based partitioning scheme which allows us to modularize our solution to eliminate the inherent performance limitations in the traditional BV approaches.
v It delivers high performance due to the custom built nature of the architectures.
v A memory-efficient bit vector-based packet classification algorithm suitable for hardware implementation.



Processor             -       Pentium –IV

Speed                  -       1.1 Ghz
RAM                   -       512 MB(min)
Hard Disk            -       40 GB
Key Board           -       Standard Windows Keyboard
Mouse                 -       Two or Three Button Mouse
Monitor                       -       LCD/LED
Operating system        :       Windows XP.
Coding Language       :       JAVA
Data Base            :       MySQL
Tool                    :       Netbeans.

Thilan Ganegedara, Weirong Jiang, and Viktor K. Prasanna,“ A Scalable and Modular Architecture for High-Performance Packet Classification” IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 5, MAY 2014.

No comments:

Post a Comment