Research And Implementation Of Multi-dimensional Packet Classification Algorithm Based On Patricia Trie

Packet classification is a technique to match each incoming packet at a router according to forwarding rules which are defined and stored in a database of classifiers. Because routers need to classify each input packet for forwarding, QoS schedule, multi cast, VPN, policy routing by one-dimentional or multi-dimentional packet classification. The research of fast packet classification is special significance.According to analysis on multi fields of packet head, an algorithm named Picking bits test(PBT) is presented in this thesis. The PBT algorithm is a multi-dimensional packet classification algorithm based on Patricia trie. The number and sorts of field used for classification are selective, and classification by range is performed in the algorithm. Furthermore, the algorithm is convenient to be realized with hardware and is fit for advanced routers. Comparing to other multi-dimensional packet classification algorithm, the PBT algorithm is flexible and scalable, and provides better time and space complexity. Tests indicate the PBT algorithm instance in Network Processor can enable searches at wire speed of up to 50 complicated, intersecting gateway rules, or up to 1000 nonintersecting rules with irregular domains of application.The thesis also proposes the technology to apply PBT algorithm to classifying packet for other protocol, and describes the design and implementation of multi independent application instances of PBT algorithm in the same router.