Fast flow classification method based on keyword decomposition hash algorithm

Abstract

A fast flow classification method based on keyword decomposition hash algorithm relates to network flow measurement technology. The data blocks of multiple keywords of the packet head are connected into an integral binary string, and then the binary string is divided into a series of data blocks, the binary strings of the series of data blocks and prime numbers are performed with exclusion OR to obtain hash key values, the hash key values are processed by the hash function to obtain the matching rule set which is stored in a hush bucket, each matching rule set is simplified to a hash matched value stored in a matched linked list; the hash matched value is used as the index value of the linked list under query, the captured packets from the network receive keyword decomposition and hash value computation, and also perform quick flow matching with the rule sets in the hash bucket. The invention supports multiple keywords, is applicable to various classification modes, has high speed, low collision rate and is applicable to high speed network flow measurement.

Description

technical field [0001] The invention relates to computer network technology, in particular to flow measurement technology of high-speed network. Background technique [0002] In recent years, the speed of physical links has grown rapidly. According to the survey of the research organization Dataquest, in 2004, the link speed between 14% of core routers reached OC768 (40Gbps), and the link speed between 21% of edge routers reached OC192. (10Gbps). The current speed is faster than before, so to adapt to this development situation, the processing speed of the data flow is required to be faster and more efficient than before. [0003] There are mainly four types of traffic classification methods currently used. (1) BPF algorithm adopts CFG mode for packet filtering, which is complicated to compile filtering rules; (2) uses SRL to write matching rule sets [2] similar to a high-level language, which uses conditional statements and transition statements for matching rules The fo...

AI Technical Summary

Problems solved by technology

[0006] (1) Since the number of bits of each rule used for traffic classification is relatively long, it is necessary to map this complete space value to a smaller space, and the collision rate is very high, which seriously affects the speed of traffic classification

[0007] (2) Since a large number of bits of each rule in the classification rule base of convection measurement may be the same, the conventional Hash algorithm is adopted, and the result does not have the characteristics of uniform distribution

[0008] (3) Since the number of bits of each rule is long, and the data width of a general computer is short, the conventional Hash algorithm requires multiple squares or multiple sums when performing Hash operations, and the amount of calculation is very large

[0009] (4) The conventional Hash algorithm cannot be optimized for different rule sets to obtain a lowest conflict rate

The Bob Jenkins algorithm performs multiple XORs on keywords, and the obtained key values ​​are uniform, but the operation speed is low; IPSX performs XOR operations on keywords separately, and the speed is fast, because the XOR used is relatively simple, and the conflict rate is high. It cannot meet the needs of network traffic measurement; the CRC hash algorithm first constructs a hash comparison table, which reduces the collision rate, but because the comparison table needs to be constructed before the operation, the calculation time is reduced, and it cannot meet the requirements of fast calculation and matching

Images