Efficient hierarchical hash tree for OpenFlow packet classification with fast updates on GPUs

Packet classification is an important functionality of modern routers/switches, needed in packet forwarding, Quality of Service (QoS), firewall etc. In order to better utilize routers on the Internet, Software Defined Network (SDN) decouples control plane from data plane to fulfill centralized management. Based on OpenFlow standards, packet classification in SDN is designed for multi-field rules which are more complex than traditional 5-tuple rules. In the paper, we propose a novel packet classification algorithm, called hierarchical hash tree (H-HashTree), based on the two IP address fields and the 7 exact-match fields to partition rules into groups. An extended Bloom filter is also proposed to accelerate search process by skipping groups in the hash tree. To further improve the performance, H-HashTree is implemented on GPU. We tested on 100K rules including synthesized rules containing characteristics of ACL, FW, and IPC with different wildcard ratios in exact-match fields, and real OpenFlow rules from Open vSwitch. Compared with the existing state-of-the-art algorithms, CutTSS and TabTree [19][18], H-HashTree achieves the best performance on both search and update speeds. H-HashTree achieves 1.17-13.9 and 2.48-12.7 times faster in search speed and 2.03-6.0 and 1.87-4.53 times faster in rule updates from synthesized rulesets than CutTSS and TabTree, respectively. On the GPU platform, H-HashTree can achieve up to 114 MPPS in search speed and less than 0.04 usec/rule in rule updates.