TY - GEN
T1 - Layered cutting scheme for packet classification
AU - Chang, Yeim-Kuan
AU - Chen, Han Chen
PY - 2011/6/3
Y1 - 2011/6/3
N2 - Packet classification is an important topic for highspeed routers nowadays. There are many packet classification algorithms based on decision tree like Hicuts, Hypercuts and Hypersplit. Because Hicuts and Hypercuts divides the rule sets by cutting the address space into equal-sized subspaces, their cutting efficiency is not good. Although Hypersplit proposed a good end-point-based cutting scheme, the resulting tree depth is still very high. In this paper, we propose a multi-dimensional cutting algorithm to significantly reduce the decision tree depth and a multi-layered scheme to dramatically reduce the usage of memory. Our experimental results show that the proposed layered scheme needs much less memory than Hypersplit for Firewall and IPC rule tables with a factor of 2 to 106 improvement while the proposed layered scheme needs a little more memory than Hypersplit for some of ACL tables. In addition, in terms of number of memory accesses, the proposed layered scheme and Hypercuts are better than Hicuts and Hypersplit for all tables while the proposed layered scheme is better than Hypercuts for ACL and Firewall tables. In terms of number of memory accesses, our layered cutting scheme and Hypercuts perform equally well for small rule tables. But, in larger rule tables, the proposed layered cutting scheme has better performance.
AB - Packet classification is an important topic for highspeed routers nowadays. There are many packet classification algorithms based on decision tree like Hicuts, Hypercuts and Hypersplit. Because Hicuts and Hypercuts divides the rule sets by cutting the address space into equal-sized subspaces, their cutting efficiency is not good. Although Hypersplit proposed a good end-point-based cutting scheme, the resulting tree depth is still very high. In this paper, we propose a multi-dimensional cutting algorithm to significantly reduce the decision tree depth and a multi-layered scheme to dramatically reduce the usage of memory. Our experimental results show that the proposed layered scheme needs much less memory than Hypersplit for Firewall and IPC rule tables with a factor of 2 to 106 improvement while the proposed layered scheme needs a little more memory than Hypersplit for some of ACL tables. In addition, in terms of number of memory accesses, the proposed layered scheme and Hypercuts are better than Hicuts and Hypersplit for all tables while the proposed layered scheme is better than Hypercuts for ACL and Firewall tables. In terms of number of memory accesses, our layered cutting scheme and Hypercuts perform equally well for small rule tables. But, in larger rule tables, the proposed layered cutting scheme has better performance.
UR - http://www.scopus.com/inward/record.url?scp=79957764082&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79957764082&partnerID=8YFLogxK
U2 - 10.1109/AINA.2011.70
DO - 10.1109/AINA.2011.70
M3 - Conference contribution
AN - SCOPUS:79957764082
SN - 9780769543376
T3 - Proceedings - International Conference on Advanced Information Networking and Applications, AINA
SP - 675
EP - 681
BT - Proceedings - 25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011
T2 - 25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011
Y2 - 22 March 2011 through 25 March 2011
ER -