NeTS: Small: Revisiting Network Algorithmics using the CRAM Model

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

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.