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.

doi.org/10.1109/ISCC.2003.1214105
8th IEEE International Symposium on Computers and Communication, ISCC 2003
School of Mathematics and Statistics

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