Packet classification plays an important role in next generation networks. Packet classification
is important to fulfill the requirements for many applications including firewalls, multimedia
services, intrusion detection services, and differentiated services to name just a few. Hardware
solutions such as CAM/TCAM do not scale well in space. 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 thesis we propose two novel algorithms, Packet Classification with Incremental Update
(PCIU) and Group Based Search packet classification Algorithm (GBSA), that are scalable and
demonstrate excellent results in terms of preprocessing and classification. The PCIU algorithm is an innovative and efficient packet classification algorithm with a
unique incremental update capability that demonstrates powerful results and is accessible for
many different tasks and clients. The algorithm was further improved and made more available
for a variety of applications through its implementation in hardware. Four such implementations
are detailed and discussed in this thesis. A hardware accelerator based on an ESL approach, using
Handel-C, resulted in a 22x faster classification than a pure software implementation running on
a state of the art Xeon processor. An ASIP implementation achieved on average a 21x quicker
classification. We also 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. In the
worst case scenario, the classification time per packet is 2 μ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. The obtained results 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
approaches using this algorithm are detailed and discussed in this thesis. The first approach was
implemented using an Application Specific Instruction Processor (ASIP), while the others were
pure RTL implementations using two different ESL flows (Impulse-C and Handel-C). The GBSA
ASIP implementation achieved, on average, a 18x faster running speed than a pure software implementation
operating on a Xeon processor. Conversely, the hardware accelerators (based on the
ESL approaches) resulted in 9x faster processing.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OGU.10214/7406 |
| Date | 22 August 2013 |
| Creators | Ahmed, Omar |
| Contributors | Areibi, Shawki |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0018 seconds