FATSS: Filter-Assisted Tuple Space Search for Packet Classification

Packet Classification is a key part of supporting lots of network functions. Various algorithms have been proposed over the years to meet the increasing performance requirements of packet classification. Tuple space search (TSS) is one of the most popular algorithms and well-suited to scenarios requiring efficient online updates. However, the huge number of tuples in the algorithm leads to numerous memory accesses during packet classification, which limits the classification performance. This paper proposes a novel model named FATSS, which uses Filters to Assist the Tuple Space Search algorithm and reduces the number of tuple accesses. We first create the ImCuckoo Filter by improving the Cuckoo Filter from its structure, capacity and hash calculation. Then, we embed ImCuckoo Filter into TSS in two ways (online and offline) to adapt to diverse scenarios and requirements. By the experiments, it can be found that the ImCuckoo Filter can reduce more than 80% of tuple accesses. Furthermore, the access time of the filter is no more than 60% compared with that of the hash table. The experimental results show that the classification time of FATSS is 17%–19% faster than that of existing widely used algorithms.