NeTS: Small: Revisiting Network Algorithmics using the CRAM Model

NeTS：小型：使用 CRAM 模型重新审视网络算法

• 批准号: 2333587
• 负责人: George Varghese
• 金额: $ 60万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-02-15 至 2027-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2333587&HistoricalAwards=false
• 关键词: NeTS; Small; Revisiting; Network; Algorithmics

The online social fabric of the world as supported by platforms such as X, Facebook, email and WhatsApp is arguably held together by the Internet core, which among other functions, routes information to its destination. Further, most essential services we use today, such as Microsoft 365, Apple Photos, Stock Exchanges, and ChatGPT, are ensconced in large data centers that include Microsoft Azure, iCloud, and Google Cloud -- collections of many thousand servers connected by large data center networks. It is no surprise then that Internet databases (so-called prefix tables), used for routing, are growing steadily in both the wide area and data centers. Worse, they are also getting wider (from 32 bits to 128 bits per data packet) with the rapid adoption of Internet Protocol version 6 (IPv6) by mobile carriers. All this has stressed the capability of the Internet core’s routers and router chips, especially with additional power constraints.This grant seeks to take first steps towards creating a new approach to designing Network Algorithms (sometimes called Network Algorithmics) using a new model of router processors called the CRAM model. In the CRAM model, fine-grained Content-Addressable Memory (CAM) and random-access memory (RAM) can be dynamically allocated to a set of programmable processors. This model is an abstraction of newer network processors such as Intel’s Tofino-1 and 2 (used by the Arista 7170 and Cisco Nexus 34180YC) and is apparent in many other new processors in the market such as AMD’s Pensando. Intellectually, the CRAM model is a new abstraction of these processors (like famous earlier models of complexity like the RAM and parallel random-access machine (PRAM) models) that allows quickly designing and evaluating scalable algorithms for all router processing tasks. Practically, we show early results that using CAM and RAM strategically can greatly improve router scalability. For example, our new viewpoint allows us to create new algorithms that enable the Tofino-2 to scale to 5 million IPv4 prefixes while a pure CAM implementation only allows at most 250,000 prefixes, 28% of the current wide area database. Similarly, a second new algorithm allows Tofino-2 to scale to 700,000 IPv6 prefixes, 5.8 times larger than a pure CAM solution. Our grant seeks to further develop the intellectual foundations of the CRAM model, build compilers from higher level CRAM descriptions to actual implementations, and generalize beyond IP lookups to find new scalable algorithms for packet classification, machine learning and security tasks, that can help sustain the amazing growth of the Internet and its accompanying services.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

由X、Facebook、电子邮件和WhatsApp等平台支持的世界在线社交结构可以说是由互联网核心维系的，互联网核心除其他功能外，还将信息路由到目的地。 此外，我们今天使用的大多数基本服务，如Microsoft 365，Apple Photos，Stock Exchanges和ChatGPT，都位于大型数据中心，包括Microsoft Azure，iCloud和Google Cloud-由大型数据中心网络连接的数千台服务器组成的集合。 因此，用于路由的互联网数据库（所谓的前缀表）在广域网和数据中心都在稳步增长也就不足为奇了。 更糟糕的是，随着移动的运营商迅速采用互联网协议版本6（IPv6），它们也变得更宽（从每个数据包32位到128位）。 所有这一切都强调了互联网核心的路由器和路由器芯片的能力，特别是在额外的功率限制下。这项资助旨在迈出第一步，创造一种新的方法来设计网络算法（有时称为网络算法），使用一种新的路由器处理器模型，称为CRAM模型。在CRAM模型中，细粒度的内容可寻址存储器（CAM）和随机存取存储器（RAM）可以动态分配给一组可编程处理器。该模型是对较新网络处理器的抽象，如英特尔的Tofino-1和2（用于Arista 7170和Cisco Nexus 34180YC），并且在市场上的许多其他新处理器中很明显，如AMD的Pensando。 从智力上讲，CRAM模型是这些处理器的一个新抽象（就像RAM和并行随机存取机（PRAM）模型等著名的早期复杂性模型一样），它允许快速设计和评估所有路由器处理任务的可扩展算法。实际上，我们展示了早期的结果，战略上使用CAM和RAM可以大大提高路由器的可扩展性。 例如，我们的新观点允许我们创建新的算法，使Tofino-2能够扩展到500万个IPv4前缀，而纯CAM实现最多只允许25万个前缀，占当前广域数据库的28%。同样，第二个新算法允许Tofino-2扩展到700，000个IPv6前缀，比纯CAM解决方案大5.8倍。 我们的资助旨在进一步开发CRAM模型的知识基础，从更高级别的CRAM描述到实际实现构建编译器，并超越IP查找，为数据包分类，机器学习和安全任务寻找新的可扩展算法，该奖项反映了NSF的法定使命，并被认为值得支持通过使用基金会的知识价值和更广泛的影响审查标准进行评估。