Towards Efficient Packet Classification Algorithms and Architectures
By Omar Ahmed, PhD, 2008 - 2014
Abstract:
Packet classification is the process of categorizing packets into classes in any network device. In other words, it tends to
perform matching of an incoming packet to rules in the classifier, and accordingly identifying the
type of action to be performed on the packet. Current software-based packet classification algorithms exhibit relatively poor performance,
prompting many researchers to concentrate on novel frameworks and architectures that employ both hardware and software components.
In this these , we propose two novel algorithm namely:
- Packet Classification with Incremental Update (PCIU).
- Group Based Search packet classification (GBSA).
The PCIU algorithm is a novel and efficient packet classification algorithm with a unique incremental
update capability that demonstrated powerful results and was shown to be scalable for many different tasks and clients.
While a pure software implementation can generate powerful results on a server machine, an embedded solution may be more desirable for some
applications and clients. Embedded, specialized hardware accelerator based solutions are typically much more efficient in speed, cost, and
size than solutions that are implemented on general-purpose processor systems.
The algorithm, furthermore, was improved and made more accessible for a variety of applications through implementation
in hardware. Four such implementations are detailed and discussed in this thesis. The results indicate that a
hardware/software co-design (using Xilinx EDK/SDK and Spartan 3E) approach results in a slower, but easier to optimize
and improve within time constraints,
PCIU solution. A hardware accelerator based on an ESL approach using Handel-C on the other hand resulted in a 22x speed up over a pure
software implementation running on a state of the art Xeon processor. An ASIP implementation achieves on average 21x speed-up in terms of
classification.
In this these, we propose another novel algorithm GBSA for packet classification that is scalable, fast and efficient. On average the algorithm
consumes 0.4 MB of memory for a 10k rule set. The classification time per packet in worst case is 2 $\mu s$, and the pre-processing speed is 3M
Rule/sec based on a CPU operating at 3.4 GHz. The proposed algorithm was evaluated and compared to state-of-the-art techniques such as RFC,
HiCut, Tuple, and PCIU using several standard benchmarks. Results obtained indicate that GBSA outperforms these algorithms in terms of speed,
memory usage and pre-processing time. The algorithm, furthermore, was improved and made more accessible for a variety of applications through
implementation in hardware. Three such implementations are detailed and discussed in this paper. The first
approach was implemented using an Application Specific Instruction Processor (ASIP), while the others are pure RTL
implementations using two different ESL flows (Impulse-C and Handel-C). The GBSA ASIP implementation achieved, on average, 18x speedup
over a pure software implementation running on a Xeon processor. Conversely, the hardware
accelerators (based on the ESL approaches) resulted in a 9x speedup.
