Classifier Characteristics
- Not many rules (Mean: 50, Max:1734)
- < 0.7% have > 1000 rules
- Most fields specified by range
- 14% have a rules with a non-contiguous mask
- Rules tend to share fields
- 8% are redundant
Rule
A regular expression (with don’t care characters) using AND / OR / > / < / =
Complexity of a Rule:
2-D space (every rule has 2 fields)
3 rules (simple)
Rules of the form
(a≤ field 1 ≤ b) (c ≤ field 2 ≤ d) (*)
Theorem: You can divide space into 2|F| zones using rules of the form (*) with |F| rules
To find a matching rule:
- use data structures
- use computational geometry
- heuristics
- TCAMS (hardware)
IP lookup – based on destination address, decide on outgoing link with CIDR (special case of packet classification) that destination address can be of any length.
Longest Prefix Match
List / Next hop1 / 110* / Link 1
2 / 11* / Link 2
3 / 100* / Link 3
4 / 0* / Link 4
5 / 1* / Link 5
6 / 1101* / Link 6
Property of Data:
Temporal Locality
- Cache
- Move-To-Front list
(Once an element is matched, move to the front of the list for fast lookup)
Trie (re tri eve):
Patricia Trees
Write down which bit to compare
TCAMS – Tertiary Content Addressable Memory
- Compare in parallel
- O(1) time searches
W-bit field (value, mask)
e.g. search for 10***
value = 10000
mask = 11000
Why TCAMS are not sufficient?
1 bit SRAM: 4-6 transistors
1 bit TCAM: 11-15 transistors (less dense)
Energy:
8 MB SRAM @200 Mhz 3W
2 MB TCAM @100 Mhz 7W
TCAMS:
Price:(1) ~ $30
(2) ~ $70
Space needed can be up to ~500 times more than on RAM, in addition to above.