NeTS: Small: Revisiting Network Algorithmics using the CRAM Model

可以说，由X、Facebook、电子邮件和WhatsApp等平台支持的世界在线社交结构是由互联网核心维系在一起的，除了其他功能外，互联网核心还将信息发送到目的地。此外，我们今天使用的大多数基本服务，如Microsoft 365、Apple Photos、Stock Exchange和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实施只允许最多250,000个前缀，是当前广域数据库的28%。同样，第二种新算法允许Tofino-2扩展到70万个IPv6前缀，是纯CAM解决方案的5.8倍。我们的拨款旨在进一步开发CRAM模型的知识基础，构建从更高级别的CRAM描述到实际实现的编译器，并在IP查找之外进行推广，以找到新的可扩展算法，用于数据包分类、机器学习和安全任务，以帮助维持互联网及其伴随服务的惊人增长。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.