Research On Distributed Packet Classification Algorithms With Scalability And High Performance

With increasing growth of the Internet, the network applications develop rapidly and the traffic grows fast. The network equipments need to provide wider bandwidth and better capability to classify traffic. As an essential technology of firewall, IDS, QoS, VPN, traffic billing and so on, packet classification is confronted with the biggest challenges than ever before. However, high-speed multi-dimension packet classification algorithms still have deficiencies and have become the bottleneck of Internet. The distributed packet classification algorithms have become an important research task becouse of their high processing speed and better dimensional scalability. This thesis summarizes the most studies in packet classification field, and then makes researches on distributed packet classification algorithms with scalability and high performance according to the requirements of 863 new generation of high-trusted network project . The main work and innovations are outlined as follows:By analysing the factors which effect and restrict the performance of distributed packet classification algorithms, this thesis proposes a algorithm called distributed crossproducting of tuple space based on counting Bloom filters (DCTS-CBF) which is easy to implement with hardware. For the purpose of improving the dimensional scalability, this algorithm brings the conception of tuple space into distributed packet classification, and provides a cache-based dendriform multi-stage structure for aggregation network and search methods based on counting Bloom filter variations for aggregation nodes. Then the algorithm proposes a maximum pruning method for the counting Bloom filter variations to avoid the false positive under minimum cost, so that the Sequential Memory Accesses are reduced. The simulation results indicate that DCTS-CBF achieves high storage efficiency and better scalability because of the increasing-trend of memory is lower than rule sets'scale. Furthermore, the processing speed of DCTS-CBF can achieve the standard of OC-192 if choosing appropriate memory.For the purpose of improving the update performance to avoid performance-degrading under the frequent-update environment, this thesis proposes a modified algorithm called multiple label-trees based on field conflict space (MLT-FCS). In order to avoid the problem of that the aggregation network structrue can't change when the algorithm is running, MLT-FCS transforms the multi-stage aggregation to single-stage, and proposes a novel conception which called field conflict space and methods of pre-processing rule sets. Then the algorithm designs a search structure and method based on multiple label-trees for aggregation results, in order to achieve fast, low-cost and exact rule-match. At last, the algorithm provides an update scheme based on the switch between primary cache and standby cache, so the update will not impact the algorithm excution. Analyse and simulation indicate that MLT-FCS achieves higher processing speed, and it can adapt the change of rule sets'property, so we can apply the algorithm to frequent-update entironment.Current methods to evaluate packet classification algorithms have limitation in consistency and hereditability. This thesis designs a packet classification algorithms performance evaluation system which is called CPCA-PES. For the purpose of standardizing and regularizing the performance evaluation of packet classification algorithms, the system utilizes ClassBench to generate different simulated entironments, and inspect algorithms' space and time performance at real time, then use mathematical statistics to determine the evaluation times in order to achieve the evaluation data whitch is close to the real performance. The evaluation system not only provides simulation results for this thesis, but also supplies foundation for the future researches on packet classification algorithms.