Paper Info
Title
A Middle Ground between CAMs and DAGs for High-Speed Packet Classification
Abstract
Packet classification is a computationally intensive task that routers need to perform at high speed to implement features such as QoS, access control, and VPNs. A classification rule-set consists of a prioritized set of rules, where each rule is a condition-action pair. Current approaches to classification can be categorized as belonging in one of two extreme categories: (1.) an incoming packet is fed to custom hardware which concurrently checks all rules for applicability and returns the action of the highest priority applicable rule; (2.) a graph-like data-structure is stored in memory and traversed based on the bits in the incomingpacket's header. Both these approaches suffer from severe limitations: the former uses a large amount of hardware; the latter requires huge amounts of memory to achieve high performance. Our thesis is that the right approach to packet classification lies in the middle. Specifically, we describe an architecture with a small number of hardware-based rule evaluation units operating in parallel. We show that dividing the rule-set across these units so as to make them fit in the hardware available is NP-hard; our primary contribution is a heuristic for doing this division.
Year
DOI
Venue
2002
10.1109/CONECT.2002.1039262
Hot Interconnects
Keywords
Field
DocType
classification rule-set,incoming packet,custom hardware,access control,computationally intensive task,packet classification,high-speed packet classification,high performance,high speed,applicable rule,middle ground,hardware-based rule evaluation unit,directed acyclic graph,np hard problem,high performance computing,hardware,intrusion detection,directed graphs,dag,boolean functions,qos,data structure,knowledge based systems,computational complexity,cam,packet switching,content addressable memory,data structures
Data structure,Heuristic,Content-addressable memory,Computer science,Network packet,Quality of service,Computer network,Packet switching,Header,Intrusion detection system
Conference
ISBN
Citations 
PageRank 
0-7695-1650-5
0
0.34
References 
Authors
6
2
Name
Order
Citations
PageRank
Amit Prakash1505.97
Adnan Aziz21778149.76