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

NeTS:Small：通过等效变换优化基于硬件的数据包分类系统的算法方法

• 批准号: 0916044
• 负责人: Alex Liu
• 金额: $ 44万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916044&HistoricalAwards=false
• 关键词: NeTS; Small; Algorithmic; Approaches; Optimizing

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.

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