RTSS: Robust Tuple Space Search for Packet Classification

Packet classification shows an essential role in net-work functions. Traditional classification algorithms assume that all field values are available and valid. However, such a premise is being challenged as networks become more complex now. Scenarios with field-missing poses great challenges to packet classifiers. Existing approaches can only list all possible situations in such cases, increasing the workload exponentially. RFC algorithm is proved to be helpful for this issue in our previous work, but its spacial performance is much poor. In this paper, we propose a novel classification scheme using Tuple Space Search (TSS) to deal with missing fields. We redesign the hash calculation method and raise a new data structure to recover field-missing packets. The experiment shows that RTSS reduce the memory consumption and construction time by several orders of magnitude. At the same time, RTSS has better classification performance than previous work, while supporting fast updates.