The Researches And Applications On High Performance Packet Classification Technology

With the rapid development of computer hardware architecture and virtual network, the operational mode of packet classification has changed dramatically. First, the physical routing platform of packet classification has been transforming from single-core processors to multi-core processors. Second, a physical router needs to be multiplexed as a large number of virtual routers. In order to solve the problems brought by the changing operational mode of packet classification, this paper focuses on efficient multi-dimensional packet classification algorithms which can support large-scale rule sets, and efficient packet classification technology which can support multiple virtual routers on a multi-core processor routing platform. Moreover, the new proposed algorithms in this paper are applied to traffic identification of new network services.(1) This paper proposes two efficient multi-dimensional packet classification algorithms supporting large-scale rule sets. They are respectively the multi-dimensional packet classification decision trees based on sets compression and the packet classification algorithm based on parallel distributed combination bloom filters.The study of multi-dimensional packet classification decision trees based on sets compression consists of two parts. First, a two-dimensional address prefix matching algorithm based on sets compression EGT-SC (Extended Grid of the Trie with Sets Compression) is firstly proposed. Then according to the characteristics of rule sets in new services, four packet classification decision trees applied to multi-dimensional multi-mode matching are presented. Finally, several experiments are carried out to compare time performance and space performance of the four decision trees and the most suitable packet classification algorithm to new services is found.The packet classification algorithm based on parallel distributed combination bloom filter PDCBF (Parallel Distributed Combination Bloom Filter) is divided into two stages. They are the stage of rules storage and the stage of packet matching. The core components of the two stages are the aggregation nodes. In the stage of rules storage, the algorithm divides all the original rule sets into three matching logical units based on protocol. Compared with the numbers of the original packet matching rules, the scale of rule sets for packet matching is greatly reduced. In the stage of packet matching, there are three matching steps, and they are protocol matching, address single-field matching and aggregation matching. The theoretical analysis and experimental results show that PDCBF algorithm has the features of high-efficient packet matching, reasonable consumption of hardware resources and high-accurate packet classification. And it is an efficient multi-dimensional packet classification algorithm for large-scale rule sets.(2) The packet classification techniques supporting multiple virtual routers on the multi-core processor routing platform include two multi-core dynamic selection algorithms for multiple virtual routers, and they are respectively based on evolutionary game (non-cooperative game) and coalitional game (cooperative game).The multi-core dynamic selection behaviors of multiple virtual routers are analyzed and modeled by multiple independent groups in evolutionary game. The strategy distribution of evolutionary equilibrium is the final solution. This paper proposes three evolutionary algorithms based on evolutionary game model. The three evolutionary algorithms are respectively the population evolution algorithm, the reinforcement learning algorithm and the distributed evolutionary algorithm. The experimental results show that the three algorithms are able to achieve balanced loads among the cores, guarantee fair use of computing resources among virtual routers and maintain stable high-throughput of the system. Distributed evolutionary algorithm based on the balanced iterative equation has faster convergence speed than the other two algorithms.This paper also constructs a coalitional game model to solve the problem of multi-core dynamic selection for multiple virtual routers. Then an efficient multiprocessor selection scheme based on the process of coalition formation is presented. In this algorithm, it is the cores that constitute coalitions in order to increase the throughput performance of the system. A core can belong to different coalitions, and a whole coalition services for virtual routers. The simulation results demonstrate that our algorithm can effectively support load balance and maintain stable high-throughputs of the system.(3) This paper proposes two traffic identification techniques for new network services. They are respectively a H.323-based VoIP traffic identification technique and an efficient P2P traffic identification technique.This paper firstly analyzes the H.323protocol and the session characteristics in the communication process. By extracting tuple information of the communication participant, the whole VoIP traffic can be identified. Then a scheme of storage, search and update for traffic nodes is designed and a H.323-based VoIP traffic identification algorithm is proposed. The simulation results show that our algorithm can identify the H.323-based VoIP voice traffic more accurately, compared with the traditional traffic identification method.For the typical P2P applications in the network, this paper extracts the five-tuple information in the data transmission channel by analyzing the characteristics of communication terminal session. Then a rule set for identifying P2P traffic is built and an efficient packet classification algorithm for identifying P2P traffic is proposed. The simulation and actual link testing results show that compared with the port-based and the host-behavior-based identification methods, the proposed algorithm has higher identification accuracy and faster identification speed. And it can effectively identify P2P application traffic of multiple protocols and is of more practical value.