| With the improvement of society informationization, the Internet has been widely applied to various fields of social life. As one of the support technology of the Internet, Packet classification plays a very important role in network measurement, firewall access control list, load balancing, and network intrusion detection. But the sharply increase in the scale of the Internet brings serious challenges to packet classification. In order to satisfy the needs of the increasing network bandwidth and the variety of network business requirements, this paper mainly studies three aspects: improving the throughput rate of the algorithms, reducing the memory usage of the algorithms and optimizing the performance of incremental update of the algorithms. The research content and innovation points of this paper are as follows.1. Traditional decision tree-based packet classification algorithms often generate many redundant rules. To solve this issue, we propose GroupCuts, which employs two novel ideas.(1) Space relationship-based rule clustering: according to the analysis of classifiers, GroupCuts clusters the rules of similar size and then partitions the classifiers into subgroups. Building decision trees in these subgroups achieves fine space performance.(2) Dynamic Point Split: in order to reduce the rule duplication in decision trees, we select multiple rule projection points to accomplish space decomposition. Simulation results show that, compared with other existing algorithms, the proposed algorithm achieves an improvement in search performance without reducing the memory requirement.2. Current packet classification algorithms based on space-decomposition usually use only one heuristic to split the rule space, and they don’t adopt different heuristics according to the characteristics of each dimension. This paper proposes a hybrid intelligent cutting(HIC) scheme for packet classification. HIC firstly partitions the ruleset according to the IP prefix length. Then, in each subruleset, taking into account the characteristics of current cutting dimension, HIC uses bit cuttings and precise projection points cuttings to cut the IP dimension and port dimension, respectively. At last, HIC builds the decision tree of hybrid cutting structures. Simulation results show that, HIC has better scalability with different rulesets. Compared to representative algorithms, its space performance has increased by 74%.3. Previous packet classification algorithms have mainly focused on search speed and memory usage, while overlooking update performance. In this paper, we propose PreCuts, which can drastically improve the update speed. According to the characteristics of IP field, we implement three heuristics to build a 3-layer decision tree. In the first layer, we group the rules with the same highest byte of source and destination IP addresses. For the second layer, we cluster the rules which share the same IP prefix length. Finally, we use the heuristic of information entropy-based bit partition to choose some specific bits of IP prefix to split the ruleset into subsets. The heuristics of PreCuts will not introduce rule duplication and incremental update will not reduce the time and space performance. Using ClassBench, it is shown that compared with BRPS and EffiCuts, the proposed algorithm not only improves the time and space performance, but also greatly increases the update speed.4. When facing a big scale and complex ruleset, previous packet classification systems always have a bad performance. According to the demand of the project Common Security and Control Framework in Tri-Network Convergence, this paper proposes a FPGA based multiple dimensional packet classification system. This system adopts the two dimension pipeline architecture, which allows the system to deal with the complex rulesets. The system can achieve 60 Gbps throughput, it can meet the requirement of the current Tri-Network Convergence. |
PDF Full Text Request