TupleRadar: Accelerating Tuple Space Search in Packet Classification by Learned Index

Tuple space search(TSS)-based packet classification is the keystone of network system. Previous studies accelerate TSS by partitioning tuples, combining trees and tuples, and merging tuples. However, they do not scale with the number of rules, resulting in a high memory footprint or update time. In this paper, we propose TupleRadar, a framework for accelerating TSS while ensuring low memory footprint and fast rule updates. Our key idea is to construct learned indexes for tuples, which inherently improve the lookup speed but ensure the advantages of TSS. Specifically, TupleRadar builds orderly hash table-based tuples and then constructs the updatable learned index. It provides a bounded memory footprint of the index structure as well. We have evaluated TupleRadar on multiple scales rule-sets. Experimental results show that TupleRadar outperforms previous solutions, reducing 46.66% lookup time and 61.53% memory footprint on average, by up to 86.70% and 88.95%. It also performs a competitive rule update speed.

I. INTRODUCTION

Open vSwitch (OVS) [1] is one of the most popular software switches used by cloud providers to implement software-defined networks [2]–[4]. The premier OVS performs forwarding policy with OpenFlow [5] table lookups, which uses tuple space search (TSS) to match rules. Here, rules are partitioned into tuples based on their prefix lengths. At runtime, we traverse all tuples to find the best-matched rule. So as the rule size increases greatly, the exploding tuple number slows down the lookup speed.