(The talk will be given in English)
Speaker: Alon Rashelbach
Electrical Engineering Faculty, Technion
011 hall, Electrical Engineering-Kitot Building
Monday, February 5th, 2024
15:00 - 16:00
Trading Memory Accesses for Computations in Packet Processing (and Beyond)
Abstract
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 (work in progress).
Alon Rashelbach, is a 5th year PhD student at Technion, supervised by Mark Silberstein and Ori Rottenstreic
השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום שם מלא + מספר ת.ז. בטופס הנוכחות שיועבר באולם במהלך הסמינר
