Packet Classification for Core Routers: Is there an alternative to CAMs?
Florin Baboescu, Sumeet Singh, and George Varghese
In Proceedings of Infocom 2003
Summary:
The authors refined an earlier obervation by P. Cupta and N. McKeown and showed that every packet matches less than 20 rules when projecting the rule set to only the source-destination prefix pair. This observation made it practical to perform a 2D classification on source-destination prefix pair first and then search linearly on all corresponding rules.
The algorithm they presented is based on the basic Grid-of-Tries which they extended to work for more than 2 fields. Furture optimization is done using path compression and multibit compression techniques.
Performance comparison of RFC, HiCuts, BV, ABV, EGT, and EGT-PC shows that EGT-PC is a reasonably fast algorithm with minimal storage requirements that can fit into on-chip SRAM.
Critique:
- Comments on their main contributions:
- New characteristic:
With the obervation of Pankaj Gupta and Nick McKeown, they counted the number of matched rules projected on distinct souce-destination prefix pairs. They concluded that less than 20 matched rules based on 4 Tier 1 classifiers.
- New Algorithm:
Extended Grid-of-Trie is based on the basic Grid-of-Trie algorithm. The so called "significant extension" is the use of jump pointers instead of switch pointers. Different from 2D problem which assumes all other fields are wildcards, scheme of set the jump pointers is of some difference, but NOT significant.
Path compression and multibit compression techniques are not original.
- Standardized comparision:
Nice.
- Incompleteness and inconsistency:
- In section 7 (methodology), they said they would describe how the EGT algorithm can be implemented. Where? Can EGT-PC be efficiently implemented in hardware?
- In section 6 (extending 2D schemes), they provided two approaches to deciding the list of rules. They said discussion would be provided when analyzing the scheme behavior on ral classifiers. Where?
- Except for the path compression, Fig. 7 and Fig. 8 are inconsistent.
- The paper showed that RFC requires 24 Mb memory on a classifier of 2800 rules. However, RFC paper showed that using 793 packet classifiers from 101 different ISPs and enterprise networks, AdjGrps enabled RFC consumes less than 6.5 Mb for a concatenated classifier of 4000 rules. Is the comparision really fair? How will EGT-PC perform on databased used in RFC paper? The performance of classification algorithms mainly depends on the characteristics of the classifiers.
- All algorithmic classification approaches have a common problem, which is fast update when adding or removing rules are performed frequently. EGT-PC is advantageous in handling this issue compared to RFC, because complete recomputation is not needed and memory updates are expected to be limited.
Jing Lu