Scaling IP Database Size using Trees of Content Addressable Memories

Due to costs, TCAMs (ternary content addressable memories) were once seen as an impracticalsolution for performing fast IP lookup. Thanks to modern improvements, TCAMs have been reintroduced into the market, notably by Barefoot, as a practical resource to be included on specialized chips. Given that TCAM is a premium, the included amount is limited and supports moderately large datasets but still fails to scale to larger datasets such as backbone routers or datacenters. This thesis proposes that TCAM resource allocation can be reduced, therefore allowing larger datasets to be supported, by using a tree of smaller TCAMs as opposed to a single large TCAM. Furthermore, a method for building the tree and finding an optimal fixed stride are presented. The results show that TCAM usage is reduced at the cost of additional RAM usage and that this tradeoff can be tuned to meet different needs