TY - GEN
T1 - Layer partitioned search tree for packet classification
AU - Chang, Yeim-Kuan
AU - Chien, Chao Yen
PY - 2012/5/14
Y1 - 2012/5/14
N2 - Packet classification is an important building block of the Internet routers for many network applications. In this paper, we propose a scheme called Layer Partitioned Search Tree (LPST) to solve multi-field packet classification problem. LPST improves the traditional decision tree based schemes (e.g. Hyper Cuts and EffiCuts) by reconstructing the leaf nodes of the decision tree as an approximately balanced search tree. The rules may be stored not only in the buckets of leaf nodes but also in the internal nodes of LPST. Thus, searches on LPST may be completed immediately without searching all the buckets on the path to some leaf node if the packet already matches an internal node. The experimental results show that LPST requires less memory storage even if LPST categorizes the rules by two fields to reduce rule duplication rather than five fields in EffiCuts. Besides, in terms of number of memory accesses, LPST is better than Hyper Cuts and EffiCuts.
AB - Packet classification is an important building block of the Internet routers for many network applications. In this paper, we propose a scheme called Layer Partitioned Search Tree (LPST) to solve multi-field packet classification problem. LPST improves the traditional decision tree based schemes (e.g. Hyper Cuts and EffiCuts) by reconstructing the leaf nodes of the decision tree as an approximately balanced search tree. The rules may be stored not only in the buckets of leaf nodes but also in the internal nodes of LPST. Thus, searches on LPST may be completed immediately without searching all the buckets on the path to some leaf node if the packet already matches an internal node. The experimental results show that LPST requires less memory storage even if LPST categorizes the rules by two fields to reduce rule duplication rather than five fields in EffiCuts. Besides, in terms of number of memory accesses, LPST is better than Hyper Cuts and EffiCuts.
UR - http://www.scopus.com/inward/record.url?scp=84860723475&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860723475&partnerID=8YFLogxK
U2 - 10.1109/AINA.2012.122
DO - 10.1109/AINA.2012.122
M3 - Conference contribution
AN - SCOPUS:84860723475
SN - 9780769546513
T3 - Proceedings - International Conference on Advanced Information Networking and Applications, AINA
SP - 276
EP - 282
BT - Proceedings - 26th IEEE International Conference on Advanced Information Networking and Applications, AINA 2012
T2 - 26th IEEE International Conference on Advanced Information Networking and Applications, AINA 2012
Y2 - 26 March 2012 through 29 March 2012
ER -