PATHFINDER: A Pattern-Based Packet Classifier

Mary Bailey, Burra Gopal, M. Pagels and L. Peterson (Arizona)

Summary. They present the design of a packet classifier which can and has been implemented in both hardware and software. The software implementation is twice as fast as the fastest existing classifier (MPF) and the hardware implementation currently supports 622Mb/s (OC12) and the authors expect it to support gigabit speeds in the future.

More Detail

Shares goal of supporting fragmentation, efficient implementation, works for a wide range of protocols, able to process var length headers with MPF. Faster than MPF, however, due to careful DAG optimization, simple cell semantics which can be implemented efficiently, and a unique warm cache: "instead of storing the set of MR matched composites in a separate DAG, a few key (unique/unchanging) fields are identified and used to create a new key-pattern associated with the same path ID.

Using a special language, one can define a cell and then define the following recursively in terms of the cell:

cell: set of predicates designed to match a single field of a protocol header
line: comprised of cells; designed to match a protocol header
pattern: pair
composite pattern: comprised of patterns; classifies packets on a particular path (in this paper, a path is defined as an abstraction that encapsulates the code block and all the resources required to process a packet on that path)

Fragmentation is handled via a dual line (as opposed to the primal line which is an inactive template that contains cells to be loaded the when the first line matches. The idea is that the dual line will store a msg id so that the dual line will match subsequent fragments. Handle non-fragmented and fragmented packets by specifying two patterns.

Out-of-order delivery. Pathfinder handles out-of-order delivery by associating a postpone attribute with each cell. If this attribute is set hten the classification of packets that do not match the cell is postponed until a packet that matches the cell arrives. They give an example, IP might submit a patter that sets the postpone attribute for the cell that checks for the morefrags bits of the IP header (?). Note: MPF also has a postpone feature to handle out-of-order fragment arrival.

Other features. Can peek into other protocol's headers, can match ranges, perform more sophisticated operations that boolean ops.

Implemented in software and hardware. Software implementation uses a carefully constructed DAG to bound the packet to the longest matching composite pattern. Nodes in the graph represent a predicate (as in BPF). DAG edges are AND edges within a line and OR edges to separate lines. When a pattern is added, the DAG is traversed to determine the longest current prefix match. Only the remainder of the cells is added to the DAG by using an OR edge. Without the longest-prefix match, "the DAG would degenerate to a linear list of patterns ... This would result in behavior similar to BPF." Duplicate triples which differ only in the field are detected and implemetned as a hash table that maps value -> edge. Note: MPF had hash tables, also.

The hardware implementation does not support any feature other than fragmentation. For example, the prototype does not support variable sized headers (does this mean it doesn't support IP fully???) or the postpone facility. They foresee two possible implementations:

packets are buffered on the network adapter, packet headers are loaded onto the host and a software implementation classifies the packet using the headers, and the rest of packet processing is done using the correct resources allocation. The NIC must have enough buffering to survive bursts.
a hardware implementation on the network adapter (NIC) which acts as a cache and a software implementation to classify any packets which the hw misses. Because the hw version can keep up with network speeds, this eliminates the need for buffering on the NIC.

Miscellaneous

Call pathfinder a classifier rather than a filter because it classifies all packets rather than filtering out select packets.

"The specification can either be given by a block of imperative code, in which case the classifier can be viewed as in interpretor [...], or the specification can be declarative, that is, given by a pattern to be matched (this is the case for the classifier presented in this paper)."

Note that both MPF and Pathfinder must deal with IP service model (frag and OOO delivery); wonder how fast it would be if they didn't have to support that. This would usually be a silly statement, but in the context of ANs, not so silly. Understandably, these PCs have to be backward compatible AND it might be a mistake to limit the usefulness of your work to the AN arena.

Tradeoff: high DAG setup costs for faster lookup times.

Would be interesting to find/gather a trace of packets for classification tests.