As several papers suggested, network processing design has come to a bit of a dilemma over packet classification. The underlying problem is that the action a router should take with a given packet must be inferred from the contents of the packet. In the simplest case, a router must look at the destination address in the header and decide into which output queue to place the packet.

In the more general case, address and data fields are compared against a set of ranges, each range corresponding to a routing rule. Ideally, the ranges are on binary boundaries, so that the comparison can be made by simply matching high-order address bits against a template. For instance, a rule might apply to all packets with destination IP addresses beginning with 192. But sometimes the range is more complicated, and may be disjoint.

As routers attempt to provide more levels of service, the problem grows more complex. If, for instance, a router supports a special category of service for particular clients, then the destination of the packet may depend on its source as well as its destination. If the service is only for particular kinds of packets, then not only the Ethernet MAC addresses and IP address fields, but information from higher layers in the protocol stack and even content of the data packets may be needed.

All of this processing can of course be done in software on a general-purpose CPU. Network processors are intended specifically to do the basic routing operations in software. But with both line speeds and the complexity of the classification task growing, the problem is moving beyond the reach of software.

Two papers examined the nature and location of bottlenecks in a network processor. But beyond that level, a number of papers explored alternative hardware-oriented approaches to classification. Most of these contributions focused on content-addressable memories (CAMs.)

One such paper, presented by Huan Liu of Stanford University, examined a serious issue with using CAMs for classification. Ternary CAMs — CAMs that can mask off some input bits as don't-cares — are nearly ideal for matching ranges on binary boundaries — this case is called prefix matching. But to use a CAM for matching a range that doesn't lie on a binary boundary, the common approach has been to break the range up into subranges that do fit within binary boundaries, and create one entry in the CAM for each subrange. This quickly eats up space.

Liu's paper describes an ingenious way to represent ranges in the TCAM with additional data bits, substantially reducing the number of TCAM entries at a small cost in additional word width.

A second paper, by Panigrahy and Sharma of Cisco Systems, describes a technique for dividing TCAMs into banks and using high-order address bits for bank switching. This approach, the authors said, can considerably reduce the power consumption in large TCAM arrays.

A third paper suggested eliminating the TCAMs by replacing the hardware-matching operation with a binary search. Prakash and Azis of the University of Texas, Austin, then implemented the normally software-based binary decision diagram walk in a series of pipelined SRAMs, achieving both substantial throughput and much lower hardware complexity than might have been used for a TCAM approach. The authors note that binary trees are known for growing exponentially with the number of rules, and show a technique for breaking the rules into groups, building an SRAM-based classification engine for each group and feeding the results into a priority resolver.

In an interesting aside, the authors note that they explored implementing their binary walks in an FPGA, but found that a shortage of long interconnect segments in the FPGA architecture made the implementation impractical. So they stayed with their networks of small SRAMs.

Quite a different view of FPGAs came from Schuehler and Lockwood and the Washington University Applied Research Laboratory. This team has been developing FPGA-based reconfigurable engines for packet processing and implementing them as add-in cards in routing cabinets. In this paper, the authors describe a TCP splitter: a design for classifying TCP/IP packets and splitting the packet stream into two flows. One is an outgoing flow of classified and routed packets and the other a diverted flow of address and/or payload data to be used by a local application, such as a statistics-gathering program or an application working directly with the payloads.

Inside the FPGA, incoming packets are opened, classified, a copy of their relevant content is sent off to the local application and the packet is routed. Classification is done by hashing the source and destination IP addresses and TCP port numbers into a 256-kword external SRAM. The authors also suggest that a tool such as SwitchGen could transform rules directly into reconfigurable logic, eliminating the SRAM. Since the entire function of the TCP splitter is in reconfigurable logic, the user is pretty much free to experiment with implementations. Since the wrapper of TCP/IP packet handling algorithms is an existing design at the lab, this experimentation need not be burdened by packet-handling chores.

All of these papers start with the observation that the packet classification problem is moving beyond the range of either CPUs or NPUs. None of the authors seems optimistic about the ability of sheer ASIC gate counts to come to the rescue. But all the presentations hinged on some pertinent observations about the nature of real packet streams: for instance, that in practice most routers only deal with a limited number of ranges, and that rules sets tend to be set by agreements among humans, and hence change very slowly.