Efficent-cutting packet classification algorithm based on the statistical decision tree

Abstract

Packet classification algorithms based on decision tree are easy to implement and widely employed in high-speed packet classification.The primary objective of constructing a decision tree is minimal storage and searching time complexity.An improved decision-tree algorithm is proposed based on statistics and evaluation on filter sets.HyperEC algorithm is a multiple dimensional packet classification algorithm.The proposed algorithm allows the tradeoff between storage and throughput during constructing decision tree.For it is not sensitive to IP address length,it is suitable for IPv6 packet classification as well as IPv4.The algorithm applies a natural and performance-guided decision-making process.The storage budget is preseted and then the best throughput is achieved.The results show that the HyperEC algorithm outperforms the HiCuts and HyperCuts algorithm,improving the storage and throughput performance and scalable to large filter sets.

Keywords

• decision tree;packet classification;statistic;filters