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

Yu Hsiang Lin, Wen Chi Shih, Yeim Kuan Chang

研究成果: Article同行評審

2 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)136-147
期刊Journal of Parallel and Distributed Computing
出版狀態Published - 2022 9月

All Science Journal Classification (ASJC) codes

  • 軟體
  • 理論電腦科學
  • 硬體和架構
  • 電腦網路與通信
  • 人工智慧


深入研究「Efficient hierarchical hash tree for OpenFlow packet classification with fast updates on GPUs」主題。共同形成了獨特的指紋。