An efficient packet classification algorithm for network processors

The exponential growth in optical link speed has stressed the performance of routers and switches. Consequently, a new breed of microprocessors, called network processors, are designed and fabricated specifically to effectively process packets on switches and routers. Packet classification is a major function in network processors to fit requirements of next-generation Internet. In this paper, we present a hardware-based packet classification algorithm for network processors. The innovative aspect of the proposed algorithm is to use the prior knowledge of rule characteristics to avoid performance fluctuation under different rule characteristics. First, we use divide-and-conquer approach to partition rules into several clusters and perform parallel search in different clusters. Then, we encode each rule into shorter bit string to prune unnecessary search. Finally, we employ level compression scheme to accelerate the lookup time. By running an intensive computer simulation, we show that the performance of the proposed simulation can achieve 8 million packets by 549 KB 10-ns SRAM for 20000 four-dimensional rules. This result demonstrates that the proposed scheme is superior to previous approaches.