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）——由大型数据中心网络连接的数千台服务器的集合，因此互联网也就不足为奇了。数据库用于路由的前缀表（所谓的前缀表）在广域网和数据中心中都在稳步增长，更糟糕的是，随着互联网协议版本的快速采用，它们也变得越来越宽（从每个数据包 32 位到 128 位）。所有这些都强调了互联网核心路由器和路由器芯片的能力，特别是在额外的功率限制下。这项拨款旨在为创建一种新的网络算法设计方法（有时）迈出第一步。称为网络算法），使用称为 CRAM 模型的新型路由器处理器。在 CRAM 模型中，细粒度内容可寻址存储器 (CAM) 和随机存取存储器 (RAM) 可以动态分配给一组可编程处理器。该模型是较新网络处理器的抽象，例如 Intel 的 Tofino-1 和 2（由 Arista 7170 和 Cisco Nexus 34180YC 使用），并且很明显在市场上的许多其他新处理器（例如 AMD 的 Pensando）中，CRAM 模型是这些处理器的新抽象（类似于 RAM 和并行随机存取机 (PRAM) 模型等著名的早期复杂模型），它允许快速设计。实际上，我们展示了策略性地使用 CAM 和 RAM 可以极大提高路由器可扩展性的早期结果，例如，我们的新观点允许我们创建新的算法来实现。 Tofino-2 可扩展到 500 万个 IPv4 前缀，而纯 CAM 实现最多只允许 250,000 个前缀，即当前广域数据库的 28%。同样，第二个新算法允许 Tofino-2 扩展到 700,000 个 IPv6 前缀，是当前广域数据库的 5.8 倍。我们的资助旨在进一步开发 CRAM 模型的知识基础，从更高级别的 CRAM 构建编译器。描述到实际情况，并超越 IP 查找，找到新的可扩展算法来实现数据包分类、机器学习和安全任务，这有​​助于维持互联网及其附带服务的惊人增长。该奖项反映了 NSF 的法定使命，并被视为值得通过使用基金会的智力优点和更广泛的影响审查标准进行评估来支持。