This paper describes a new algorithm for packet classification using the concept of independent sets. The algorithm has very small memory requirements. The search speed is neither sensitive to the rule table nor to the percentage of wildcards in the fields. It also scales well from two dimensional classifiers to high dimensional ones. In particular, the algorithm is inherently parallel. Hardware tailored to this algorithm can achieve very fast search speed.

Additional Metadata
Persistent URL dx.doi.org/10.1109/ISCC.2003.1214105
Conference 8th IEEE International Symposium on Computers and Communication, ISCC 2003
Citation
Sun, X. (Xuehong), & Zhao, Y. (2003). Packet classification using independent sets. Presented at the 8th IEEE International Symposium on Computers and Communication, ISCC 2003. doi:10.1109/ISCC.2003.1214105