D.J. Cornelsen and C.J. Stuart (Canada)
Packet classification, decomposition, Communications, Computer Networks
Packet classification (PC) is the problem of matching incoming packets at a router against a database of rules or filters. The rules specify a directive for incoming packets, and provide a means of implementing new services such as Quality of Service (QoS) guarantees. While many schemes have been proposed, to solve the multi dimensional PC problem, none of them scale well beyond two dimensions in terms of speed and or rule size. In this paper, we present a new scheme that decomposes the multi-dimensional problem into a set of two-dimensional queries. Every two-dimensional query can then be solved in parallel, each returning a set of possible solutions, which are intersected to find the best match. The two dimensional scheme is modeled after a combination of prior research yet exhibits some unique features. Specifically, aggregated bit-vectors (ABV) are introduced into a Fat Inverted Tree (FIS) structure. The aggregated bit-vectors are implemented in the second dimension of a two-dimensional scheme. This returns extremely sparse vectors, which suggests an opportunity for compression. It also means that the ABV scheme may be extended to higher rule sets. This algorithm is also amenable to a hardware implementation.
Important Links:
Go Back
