Show simple item record

dc.contributor.advisorKim, Min Sik
dc.creatorShaikot, Shariful Hasan
dc.date.accessioned2013-03-29T17:22:21Z
dc.date.available2013-03-29T17:22:21Z
dc.date.issued2012
dc.identifier.urihttp://hdl.handle.net/2376/4263
dc.descriptionThesis (Ph.D.), School of Electrical Engineering and Computer Science, Washington State Universityen_US
dc.description.abstractPacket 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.en_US
dc.description.sponsorshipDepartment of Computer Science, Washington State Universityen_US
dc.languageEnglish
dc.rightsIn copyright
dc.rightsPublicly accessible
dc.rightsopenAccess
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.rights.urihttp://www.ndltd.org/standards/metadata
dc.rights.urihttp://purl.org/eprint/accessRights/OpenAccess
dc.subjectComputer science
dc.subjectMulti-Core architecture
dc.subjectPacket Classification
dc.subjectTraffic adaptive
dc.titleDESIGN AND EVALUATION OF PACKET CLASSIFICATION SYSTEMS ON MULTI-CORE ARCHITECTURE
dc.typeElectronic Thesis or Dissertation


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record