TY - JOUR
T1 - Boundary cutting for packet classification
AU - Lim, Hyesook
AU - Lee, Nara
AU - Jin, Geumdan
AU - Lee, Jungwon
AU - Choi, Youngju
AU - Yim, Changhoon
PY - 2014/4
Y1 - 2014/4
N2 - Decision-tree-based packet classification algorithms such as HiCuts, HyperCuts, and EffiCuts show excellent search performance by exploiting the geometrical representation of rules in a classifier and searching for a geometric subspace to which each input packet belongs. However, decision tree algorithms involve complicated heuristics for determining the field and number of cuts. Moreover, fixed interval-based cutting not relating to the actual space that each rule covers is ineffective and results in a huge storage requirement. A new efficient packet classification algorithm using boundary cutting is proposed in this paper. The proposed algorithm finds out the space that each rule covers and performs the cutting according to the space boundary. Hence, the cutting in the proposed algorithm is deterministic rather than involving the complicated heuristics, and it is more effective in providing improved search performance and more efficient in memory requirement. For rule sets with 1000-100 000 rules, simulation results show that the proposed boundary cutting algorithm provides a packet classification through 10-23 on-chip memory accesses and 1-4 off-chip memory accesses in average.
AB - Decision-tree-based packet classification algorithms such as HiCuts, HyperCuts, and EffiCuts show excellent search performance by exploiting the geometrical representation of rules in a classifier and searching for a geometric subspace to which each input packet belongs. However, decision tree algorithms involve complicated heuristics for determining the field and number of cuts. Moreover, fixed interval-based cutting not relating to the actual space that each rule covers is ineffective and results in a huge storage requirement. A new efficient packet classification algorithm using boundary cutting is proposed in this paper. The proposed algorithm finds out the space that each rule covers and performs the cutting according to the space boundary. Hence, the cutting in the proposed algorithm is deterministic rather than involving the complicated heuristics, and it is more effective in providing improved search performance and more efficient in memory requirement. For rule sets with 1000-100 000 rules, simulation results show that the proposed boundary cutting algorithm provides a packet classification through 10-23 on-chip memory accesses and 1-4 off-chip memory accesses in average.
KW - Binary search
KW - HiCuts
KW - boundary cutting
KW - decision tree algorithms
KW - packet classification
UR - http://www.scopus.com/inward/record.url?scp=84899501428&partnerID=8YFLogxK
U2 - 10.1109/TNET.2013.2254124
DO - 10.1109/TNET.2013.2254124
M3 - Article
AN - SCOPUS:84899501428
SN - 1063-6692
VL - 22
SP - 443
EP - 456
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 2
M1 - 6496176
ER -