HIGH-SPEED ALGORITHMS OF 2-DEMENSION PACKET CLASSIFICATION BASED ON SHORTER PREFIX LENGTH SPLITTING

Packet classification is a technique to match each incoming packet at a router against a database of classifier and specify forwarding rules for the packets. Classifiers are a powerful and uniform way to implement new network services such as firewalls, network address translation （NAT）. Several algorithms of packet classification have been proposed recently, but none is ideal. In this paper an algorithm of 2-demension packet classification based on the shorter prefix length splitting （SPLS） is proposed. The SPLS is realized by splitting a larger database of classifier into many smaller databases of classifier according to the shorter prefix length between the IP source address and IP destination address. After splitting it, the IP routing lookup algorithm can be used to the smaller database of classifier. Multi-bit tree （or n-ary tree） is the basic data structure for SPLS. The performance when implementing SPLS in quadtree is examined. The algorithm has characteristics of fast average search time, fast update time, small memory space and suiting for large classifiers, and is a better algorithm for Internet routers.