The Taub Faculty of Computer Science Events and Talks

Range matching plays a crucial role in computer systems, including networking, security, and storage. It serves the purpose of locating a range that encompasses a given input number from a vast collection of ranges. Address translators in operating systems and longest-prefix matching in networks heavily rely on range matching. However, existing range matching algorithms are limited in scalability and performance due to their reliance on pointer-chasing techniques.

We introduce a novel data structure called the Range Query Recursive Model Index (RQRMI) to address the challenges associated with range matching. By leveraging shallow neural networks, RQRMI enables the learning of range distributions, transforming expensive lookup operations into efficient neural network inference. By employing the RQRMI model, we achieve an impressive range compression ratio of up to 90X. This compression capability allows for direct lookup operations while fitting within the CPU core cache. Importantly, the RQRMI training algorithm guarantees a strict upper bound on lookup latency, ensures the correctness of results, and exhibits fast convergence rates. We have developed NuevoMatch, an algorithm for multi-field packet classification that leverages RQRMI models (SIGCOMM’20), and successfully integrated it into the critical path of Open vSwitch, a broadly used virtual switch (NSDI’22). Through the utilization of RQRMI, we have achieved remarkable scalability, enabling Open vSwitch to handle 500 times more routing rules while experiencing a throughput speedup of up to 160 times. Furthermore, our work demonstrates the versatility of RQRMI beyond software. Specifically, we observed up to 20X reduction in the memory footprint required for DNA hardware accelerators (BCB’23) and developed hardware for enhancing the scalability of network packet processors (MICRO’23).

Joint work with Igor DePaula, Ori Rottenstreich, and Mark Silberstein

Alon is a PhD student supervised by Prof. Mark Silberstein and Prof. Ori Rottenstreich.