Abstract:Regional partition packet classification algorithm is one of the most effective algorithms. To solve the unsymmetrical distribution problem of regional partition for packet classification, a heuristic lookup partition algorithm is proposed after analysing the character of rules’ sets. The main research work on the algorithm in this paper includes two parts: the method of lookup partition to ensure the symmetrical distribution of rules, and the construction of decision tree based on the partition found. The time cost of this algorithm is composed by the time for lookup partition and the time for line-search in the partition found. The results of simulation show that the algorithm is not sensitive to the increasement of rules, meanwhile it supports the incremental updating on-line.