28-10-2010, 08:46 AM
Packet Classification Algorithms
Presented by
Dains Raj Antony
M1 CSE
College Of Engineering, Trivandrum
[attachment=6884]
What this seminar is about:
Algorithms and techniques that a flow-aware router uses to classify packets into flows (packet classification)
What is a Flow?
All the packets sharing common header characterstics
Eg: All packets flowing between two specific IP addresses
flow = (src-IP-address, dst-IP-address), or a flow = (dst-IP-prefix, protocol) etc
Flow-aware vs Flow-unaware Routers
Flow-aware router: keeps track of flows and perform similar processing on packets in a flow
Flow-unaware router (packet-by-packet router): treats each incoming packet individually
Examples of special processing
Filtering packets for security reasons
Delivering packets according to a pre-agreed delay guarantee
Treating high priority packets preferentially
Maintaining statistics on the number of packets sent by various routers
Special Processing Requires Identification of Flows
All packets of a flow obey a pre-defined rule and are processed similarly by the router
E.g. a flow = (src-IP-address, dst-IP-address), or a flow = (dst-IP-prefix, protocol) etc.
Router needs to identify the flow of every incoming packet and then perform appropriate special processing
Why Flow-aware Router?
ISPs want to provide differentiated services
Routers require additional mechanisms: admission control, resource reservation, per-flow queueing, fair scheduling etc.
capability to distinguish and isolate traffic belonging to different flows based on negotiated service agreements
Need for Differentiated Services
Multi-field Packet Classification
Packet Header Fields for Classification
Flow-aware Router: Basic Architectural Components
Routing, resource reservation, admission control, SLAs
Routing lookup
Packet classification
Special processing
Switching
Scheduling
Datapath:
per-packet
processing
Packet Classification
Metrics for Classification Algorithms
Speed
Storage requirements
Low update time
Ability to handle large classifiers
Flexibility in implementation
Low preprocessing time
Scalability in the number of header fields
Flexibility in rule specification
Example Classifier
Linear Search
Keep prefixes in a linked list
O(N) storage, O(N) lookup time, O(1) update complexity
Improve average time by keeping linked list sorted in order of prefix lengths
Recursive Flow Classification
Observations:
Difficult to achieve both high classification rate and reasonable storage in the worst case
Real classifiers exhibit structure and redundancy
A practical scheme could exploit this structure and redundancy
Recursive Flow Classification
One-step
Multi-step
Source L3 Address
Destination L3 Address
L4 protocol and flags
Source L4 port
Destination L4 port
Type of Service
Ternary Content Adressable Memory
Need for higher processing capacity
Can be used for multi-diamensional classification
Fully associative memory:
compares input string with all the entries in parallel
Ternary CAMs
Advantages
Suitable for multiple fields
Fast: 16-20 ns (50-66 Mpps)
Simple to understand
Disadvantages
Inflexible:
Density: largest available in 2000 is 32K x 128 (but can be cascaded)
Management software, and on-chip logic:
Power: 5-8 W
Incremental updates: slow
DRAM-based CAMs: higher density but soft-error is a problem
Cost: $30-$160 for 1Mb
Conclusion
Linear search is simple but poor at scaling.
Heirarchical trie provides good worst case query time.
Set pruning tries has fast retrieval at the cost of storage.
RFC is suitable for small set of rules.
TCAM is simple but very costly.
References
[1] Pankaj Gupta & Nick Mckeown, "Algorithms for Packet Classification",Computer Systems Laboratory, Stanford University Stanford, CA.
[2]Pankaj Gupta and Nick McKeown , "Packet Classification using Hierarchical Intelligent Cuttings" Computer Systems Laboratory, Stanford.
