Abstract: The recent advance in the research of packet classification was surveyed, and a hash table based rule matching algorithm was given. The time complexity of the algorithm was O(1). Through the analyses of the related problem of rule table, the rule table is separated into two sub groups. The unrelated group is constructed into a hash table which improves the matching speed. Experiments show that the throughput is improved about 10%. Another problem, the rule conflict, was proved and a conflict detection algorithm was given.

Key words: packet classification, hash table, rule table, related rules, conflict detection