TY - JOUR
T1 - Efficient hierarchical hash tree for OpenFlow packet classification with fast updates on GPUs
AU - Lin, Yu Hsiang
AU - Shih, Wen Chi
AU - Chang, Yeim Kuan
N1 - Publisher Copyright:
© 2022 Elsevier Inc.
PY - 2022/9
Y1 - 2022/9
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85130159006&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85130159006&partnerID=8YFLogxK
U2 - 10.1016/j.jpdc.2022.04.018
DO - 10.1016/j.jpdc.2022.04.018
M3 - Article
AN - SCOPUS:85130159006
SN - 0743-7315
VL - 167
SP - 136
EP - 147
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
ER -