Scaling IP Lookup to Large Databases using the CRAM Lens
Robert Chang, Pradeep Dogga, Andy Fingerhut, Victor Rios, George Varghese · 2025
Read Scaling IP Lookup to Large Databases using the CRAM Lens by Robert Chang, Pradeep Dogga, Andy Fingerhut, Victor Rios, George Varghese (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-03003.txt.
Introduction
Robert Chang and co-authors write a 2025 paper on Internet address lookup. Routers must match each packet's address against huge route tables at line speed. New network chips pack two memory types that could hold far larger tables, but testing designs against chip limits is hard.
The team offers a lens called CRAM that models how algorithms run on such chips, plus a set of tuning idioms. Three new lookup schemes built with the lens are then measured. One scheme fits more than two million IPv4 routes on a current chip, about nine times a pure fast-memory design. The IPv6 scheme also triples the reach of the plain approach. Both beat leading prior methods on the same chip.
Catalog record
| CREATOR | Robert Chang, Pradeep Dogga, Andy Fingerhut, Victor Rios, George Varghese |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-03003
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scaling IP Lookup to Large Databases using the CRAM Lens Robert Chang, Pradeep Dogga, Andy Fingerhut, Victor Rios, George Varghese Abstract Wide-area scaling trends require new approaches to Internet Protocol (IP) lookup, enabled by modern networking chips such as Intel Tofino [ 35 ] , AMD Pensando [ 2 ] , and Nvidia BlueField [ 55 ] , which provide substantial ternary content-addressable memory (TCAM) and static random-access memory (SRAM). However, designing and evaluating scalable algorithms for these chips is challenging due to hardware-level constraints. To address this, we introduce the CRAM (CAM+RAM) lens, a framework that combines a formal model for evaluating algorithms on modern network processors with a set of optimization idioms. We demonstrate the effectiveness of CRAM by designing and evaluating three new IP lookup schemes: RESAIL , BSIC , and MashUp . RESAIL enables Tofino-2 to scale to 2.25 million IPv4 prefixes—likely sufficient for the next decade—while a pure TCAM approach supports only 250k prefixes, just 27% of the current global IPv4 routing table. Similarly, BSIC scales to 390k IPv6 prefixes on Tofino-2, supporting 3.2 times as many prefixes as a pure TCAM implementation. In contrast, existing state-of-the-art algorithms, SAIL [ 83 ] for IPv4 and Hi-BST [ 65 ] for IPv6, scale to considerably smaller sizes on Tofino-2. 1 Introduction For many, Internet Protocol (IP) lookup is considered a challenge of the past. With over 40 years of research and hundreds of papers (e.g., [ 29 , 19 , 45 , 89 , 22 , 21 , 7 , 65 , 83 ] ) focused on supporting IP lookup at scale, numerous schemes have been developed—some of which have been in practical use for two decades. However, these classical approaches are single-resource solutions, designed for conventional switch chip architectures that provided either specialized hardware like ternary content-addressable memory (TCAM) or commodity random-access memory (RAM), such as on-chip static RAM (SRAM) coupled with off-chip dynamic RAM (DRAM), but not both. TCAM enables parallel searches across wildcarded entries in a single clock cycle but requires three times more transistors per bit than SRAM and consumes hundreds of watts [ 5 ] . RAM-based approaches are cheaper but require additional complexity and memory compared to pure TCAM solutions. Thus far, commercial switch chip vendors have scaled these single-resource solutions by increasing hardware resources. In this paper, we contend that it is important to reconsider IP lookup due to the continued growth of lookup tables and a recent inflection point in network hardware. A slew of new application-specific integrated circuits (ASICs), such as Intel Tofino [ 35 ] , AMD Pensando [ 2 ] , and Nvidia BlueField [ 55 ] , have transformed the networking chip market [ 58 ] . These chips are built on two modern packet processing architectures—Reconfigurable Match-Action Tables (RMT) [ 9 ] and disaggregated RMT (dRMT) [ 15 ] —which consist of match-action processors with access to large amounts of both TCAM and SRAM. We review these architectures at the start of § 2 . This leads us to our central question: How can we leverage modern networking chips, utilizing both TCAM and SRAM, to develop new IP lookup algorithms that scale to larger databases than classical single-resource solutions? Two main challenges make designing scalable algorithms for RMT and dRMT chips difficult: (1) Lack of an abstract model for evaluating and comparing algorithms. Chip-specific arcana such as memory allocation, metadata storage, and action bits must be carefully considered. (2) Large but finite resources. While TCAM, SRAM, and pipeline stages are available in substantial amounts, they require careful algorithm design to scale effectively. Solution : We introduce the CRAM (CAM+RAM) lens, an abstract model of modern packet processing architectures, such as RMT and dRMT, paired with a set of optimization idioms. The CRAM model enables us to estimate algorithm scalability using higher-order space and time metrics, without requiring simulation of ASIC-specific details such as TCAM block sizes, SRAM page sizes, and per-stage memory. The CRAM model goes beyond classical models such as random-access machine (RAM) [ 23 ] and parallel RAM (PRAM) [ 41 ] by adding TCAM operations and using match-action dependencies to measure time complexity. The optimization idioms provide eight strategies for designing scalable algorithms. CRAM can be generalized to other hardware architectures, such as smart network interface cards (SmartNICs) [ 32 , 2 , 55 ] and field-programmable gate arrays (FPGAs) [ 34 , 3 ] , and applied to broader network applications like packet classification [ 30 , 74 , 44 ] and in-network machine learning (ML) [ 73 , 93 , 91 ] . However, this is not the focus of our paper. For completeness, we briefly discuss these extensions in § 2.4 and § 2.5 . Instead, we concentrate on applying CRAM to IP lookup because of the following observations: 0 3 0 5 0 7 0 9 11 13 15 17 19 21 23 1 2 3 4 5 6 7 8 9 10 Year (2003-2023) Active IPv4 Entries (1x 10^{5} ) AS65000 (IPv4) AS131072 (IPv6) 0 2 4 6 8 10 12 14 16 18 20 Active IPv6 Entries (1x 10^{4} ) Figure 1 : BGP routing table size over the past two decades O1. Continued IPv4 growth: Over the past two decades, the global IPv4 routing table has grown linearly [ 27 , 26 ] , doubling in size every decade ( Figure 1 ). If this trend continues, the IPv4 table could reach two million entries by 2033. O2. Rapid IPv6 deployment: In the same period, the global IPv6 routing table has grown exponentially [ 28 , 25 ] , doubling every three years ( Figure 1 ). Even if growth slows to a linear rate, the IPv6 table could still reach half a million entries by 2033. IPv6 prefixes are also four times wider, though typically, only the first 64 bits are used for global routing. O3. Virtual private networks (VPNs): Some routers maintain hundreds of VPN routing tables. On such devices, publicly available routing tables account for only a fraction of the total capacity required. O4. Other tasks: Routers need table memory for additional tasks such as network address translation (NAT) and firewalls. Minimizing the memory used for forwarding allows more features to fit on a chip. CRAM enables us to rethink pre-existing IP lookup schemes, such as SAIL [ 83 ] , DXR [ 89 ] , and multibit tries, to develop new algorithms that scale to larger databases. We start with the best-of-breed algorithms from three classic IP lookup approaches—search on prefix lengths , search on prefix ranges , and trie-based search. We derive new algorithms using the optimization idioms ( § 2.2 ) and predict their scalability with the CRAM model ( § 2.1 ). Each new algorithm—rethinking SAIL ( RESAIL ), Binary Search with Initial CAM ( BSIC ), and MashUp —offers unique strengths for different settings. We chose Intel Tofino-2, an RMT switch chip, for our experiments because we had access to its development environment. While Intel recently announced it will not develop new Tofino models, it remains committed to supporting Tofino and Tofino-2 [ 53 ] . We expect our results to hold for dRMT, as