This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). Using Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry. Despite their high speed, TCAMs have limitations of high cost, small capacity, large power consumption, and high heat generation. The well-known range expansion problem in converting range rules to ternary rules significantly exacerbates these TCAM limitations. This project addresses TCAM limitations by developing new algorithms to transform a given rule set into an equivalent rule set that requires significantly fewer TCAM entries. This allows the use of smaller, faster, and more energy efficient TCAM chips. The algorithms developed by this project significantly outperform prior art because these new algorithms perform equivalent transformation at the list level whereas prior approaches only perform compression at the individual rule level. Expected results of this project include effective equivalent transformation algorithms and potentially transformative concepts. Research results are broadly disseminated through publications, open source software releases, freely available course modules, and industry interaction. This project benefits society by decreasing the demand of modern routers for large TCAMs, lowering router prices and energy cost, enabling the use of small and cheap TCAMs on low end routers, and extending router life time. The technologies developed in this project greatly benefit the business of router manufacturers, TCAM chip providers, and Internet service providers. To promote education and learning, this effort actively engages high school, undergraduate, and graduate students, especially students from under-represented minorities.
