NeTS:Small:Algorithmic Approaches to Optimizing Hardware-Based Packet Classification Systems via Equivalent Transformation

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。 使用三值内容可寻址存储器（TCAM）来执行高速分组分类已经成为工业界事实上的标准。尽管TCAM具有高速度，但其具有高成本、小容量、大功耗和高发热的局限性。在将范围规则转换为三元规则时，众所周知的范围扩展问题显著加剧了这些TCAM限制。该项目通过开发新的算法来解决TCAM的局限性，将给定的规则集转换为需要更少TCAM条目的等效规则集。这允许使用更小、更快和更节能的TCAM芯片。该项目开发的算法显著优于现有技术，因为这些新算法在列表级别执行等效变换，而现有方法仅在单个规则级别执行压缩。 该项目的预期成果包括有效的等效变换算法和潜在的变革概念。研究成果通过出版物、开源软件版本、免费课程模块和行业互动广泛传播。该项目通过减少现代路由器对大型TCAM的需求，降低路由器价格和能源成本，使低端路由器能够使用小型和廉价的TCAM，并延长路由器寿命，从而造福社会。该项目开发的技术极大地有利于路由器制造商、TCAM芯片提供商和互联网服务提供商的业务。为了促进教育和学习，这项工作积极吸引高中生、本科生和研究生，特别是来自代表性不足的少数民族的学生。

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.