Packet classification for core routers: is there an alternative to CAMs?

Abstract

A classifier consists of a set of rules for classifying packets based on header fields. Because core routers can have fairly large (e.g., 2000 rule) database and must use limited SRAM to meet OC-768 speeds, the best existing classification algorithms (RFC, HiCuts, ABV) are precluded because of the large amount of memory they need. Thus the general belief is that hardware solutions like CAMs are needed, despite the amount of board area and power they consume. In this paper, we provide an alternative to CAMs via an extended grid-of-tries with path compression (EGT-PC) algorithm whose worst-case speed scales well with database size while using a minimal amount of memory. Our evaluation is based on real databases used by tier 1 ISPs, and synthetic databases. EGT-PC is based on a observation that we found holds for all the tier 1 databases we studied: regardless of database size, any packet matches only a small number of distinct source-destination prefix pairs. The code we wrote for EGT-PC, RFC, HiCuts, and ABV is publicly available (Ref.1), providing the first publicly available code to encourage experimentation with classification algorithms.