Dissertation
DESIGN AND EVALUATION OF PACKET CLASSIFICATION SYSTEMS ON MULTI-CORE ARCHITECTURE
Doctor of Philosophy (PhD), Washington State University
01/2012
Handle:
https://hdl.handle.net/2376/4263
Abstract
Packet classification (PC) is the core mechanism used by network devices such as edge
routers, firewalls, and intrusion detection systems to classify incoming traffic based on the classification
policy. In decision-tree-based PC, packets are classified by searching in tree data structure.
However, tree search presents significant challenges because it requires a number of unpredictable
and irregular memory accesses. Packet classification is per-packet operation and memory latency
is considerably high (caused by cache and TLB misses). The growing trend of number of rules
in the classifier coupled with the constant increase in link speeds makes wire-speed classification
a challenging task. Hence, satisfactory performance of PC still remains elusive at the wire speed.
Researchers propose to mitigate this problem by exploiting locality in traffic patterns. In this dissertation,
several new algorithms to deal with the different variations of the packet classification
problem. They are: (1) npf, a fast and traffic-adaptive packet classifier which dynamically reorganizes
the internal data structure based on the traffic pattern. Unlike existing approaches requiring a
separate, off-line reorganization phase, npf performs reorganization on-line with little overhead,
resulting in higher throughput without compromising accuracy; (2) Pnpf the design, implementation,
and evaluation of traffic-aware classification system that exploit the strong computational
power and thread-level parallelism capabilities of modern multi-core general purpose processors;(3) An efficient memory layout for the tree data structure which ensures the movement of data
optimally among the different levels of the memory hierarchy on general purpose processors. In
particular, for a given node size, the number of accessed cache lines (and memory pages) is minimized
by our proposed memory layout resulting in less number of cache and TLB misses.
Metrics
3 File views/ downloads
18 Record Views
Details
- Title
- DESIGN AND EVALUATION OF PACKET CLASSIFICATION SYSTEMS ON MULTI-CORE ARCHITECTURE
- Creators
- Shariful Hasan Shaikot
- Contributors
- Min S Kim (Advisor)Carl H Hauser (Committee Member)David E Bakken (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Number of pages
- 112
- Identifiers
- 99900581543701842
- Language
- English
- Resource Type
- Dissertation