High Performance Packet-classification Algorithm Study

Nowadays, more and more PCs link to the Internet and this makes Internet data flow growing much faster than any time before. Consequently, good quality of Internet services much more difficulty to obtain. With the rapid development of fiber and DWDM technology, the networks transmission rate is satisfying basically. As a basic equipment of networks, router becomes a bottle neck of the Internet now and the basic technology of router is packet classification.In this paper, we first do a systemic, detail research on almost all the classical packet classification algorithms and analyze the time and space request of all the algorithms and compare on time/space consumption between them. Our research shows: the most of the classical packet classification algorithms only suit for one or to type of matching. Nowadays, the packet filter becomes to be more and more complexity. One filter usually comprises longest prefix matching, accurate matching, rang matching and so on. That one algorithm fits all the type of matching remains a problem.As to the problem above, we introduce a new algorithm named multidimensional subsection on field algorithm and this algorithm uses strategy of filter-division on matching type. Concretely says, this algorithm deals different matching field in one rule with different strategy. In our new algorithm, we use Tuple Space Search algorithm for the longest prefix matching parts, hashing table for accurate matching parts and develop state transmission tree algorithm for the last parts of the rule. We introduced the parallel algorithm soon. Finally we coded in C language for our algorithm for verifying.It is obvious that our algorithm can fit various filters well. We analyzed the time and space requirement of the algorithm. The result shows that time complexity is O( log n) and space complexity is O(N), the n is the number of the Tuple, the N is the number of rule and n