Range matching, the process of identifying a range that contains a given input number, is vital in various computer systems, like networking, security, and storage. However, the current methods for range matching hit a wall when it comes to handling a larger number of supported ranges without slowing down search performance: they heavily rely on pointer-chasing algorithms, causing issues when their data structures outgrow the CPU core cache. This reliance on data-dependent memory accesses also constrains efficient memory prefetching and limits potential hardware implementations.
We introduce a novel data structure called the Range Query Recursive Model Index (RQRMI) to tackle the complexities associated with range matching (SIGCOMM’20). RQRMI utilizes shallow neural networks that learn the mapping between inputs and the position of the matching range in memory. This transformation turns the memory-intensive lookup processes into swift neural network inferences, essentially trading costly memory accesses for cheap computations. Remarkably, RQRMI achieves an impressive range compression ratio, up to 90X compared to current methods, enabling direct lookup operations while staying within the CPU core cache limits. The RQRMI training algorithm guarantees a strict upper bound on lookup delay, assures result accuracy, and showcases rapid convergence rates when implemented on CPUs.
We present an algorithm for multi-field packet classification that leverages RQRMI models, and integrate it into the critical path of Open vSwitch, a broadly used open-source virtual switch (NSDI’22). The integration of RQRMI yields impressive scalability, empowering Open vSwitch to manage 500 times more routing rules and experiencing a throughput boost of up to 160 times. When implemented in hardware, RQRMI resolves scalability issues seen in current longest-prefix-matching methods (MICRO’23). This allows scaling the number of routing rules and their bit length to meet forthcoming network demands. Its efficient memory usage and low bandwidth needs make it suitable for genomic processing hardware (BCB’23), and address translators in SSD storage drives (under submission).
Alon Rashelbach, is a 6th year PhD candidate at the Technion, supervised by prof. Mark Silberstein and prof. Ori Rottenstreich.