DESIGN AND EVALUATION OF PACKET CLASSIFICATION SYSTEMS ON MULTI-CORE ARCHITECTURE

Thesis (Ph.D.), School of Electrical Engineering and Computer Science, Washington State UniversityPacket classification (PC) is the core mechanism used by network devices such as edgerouters, firewalls, and intrusion detection systems to classify incoming traffic based on the classificationpolicy. 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 unpredictableand irregular memory accesses. Packet classification is per-packet operation and memory latencyis considerably high (caused by cache and TLB misses). The growing trend of number of rulesin the classifier coupled with the constant increase in link speeds makes wire-speed classificationa 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 classificationproblem. They are: (1) npf, a fast and traffic-adaptive packet classifier which dynamically reorganizesthe internal data structure based on the traffic pattern. Unlike existing approaches requiring aseparate, 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 computationalpower 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 dataoptimally among the different levels of the memory hierarchy on general purpose processors. Inparticular, for a given node size, the number of accessed cache lines (and memory pages) is minimizedby our proposed memory layout resulting in less number of cache and TLB misses.Department of Computer Science, Washington State Universit