A Mask Matching Algorithm with Fast Incremental Update Support

This paper proposes a mask match algorithm, TernarySort, supporting fast incremental update. The algorithm uses decision trees to partition mask matching rules. To guarantee the update performance, it restricts that rules residing in different leaf nodes do not overlap with each other. At the same time, TernarySort selects effective bits to reduce the depth of decision trees. And it allows rules to overlap in one leaf node, to decrease the number of partitions and improve the classification performance. The experimental results show that, compared to currently used algorithms, TernarySort can improve packet classification performance by more than 80% while maintaining fast rule updating performance. TernarySort meets the requirements of SDN for mask matching algorithms.