Efficient Hierarchical Hash Tree for OpenFlow Packet Classification with Fast Updates on GPUs

Abstract

Packet classification is an important functionality of modern routers and it supports packet forwarding Quality of Service (QoS) firewall traffic control virtual private network (VPN) and Load Balancing In order to better utilize routers on the Internet SDN decouples control plane from data plane to fulfill centralized management With the support of OpenFlow standard SDN is designed for multi-field rules which are different from traditional 5-tuple rules Apart from traditional 5-tuple rules additional 7 fields in OpenFlow 1 0 rules are exact-match fields The main purpose of this thesis is to implement a new packet classification algorithm to deal with 12-field rules in OpenFlow 1 0 We propose a hierarchical hash tree (H-HashTree) to partition rules into subsets according to the two IP address fields and the 7 fields added in OpenFlow 1 0 We also implement extended Bloom filter to accelerate search process by skipping groups in the hash tree and maintain an extra hierarchical hash tree for those rules which cannot apply extended Bloom filter The algorithm is implemented on GPU to further improve the performance We tested on 100K OpenFlow rules including synthesized rules containing characteristics of ACL FW and IPC with different wildcard ratio 0 1 0 5 and 0 9 for the exact-match fields and real OpenFlow rules from Open vSwitch Compared with the existing state-of-the-art packet classification algorithms [20] [22] we achieved the best performance on both search speed and rule updates Compared with [20] H-HashTree achieve 1 17 ~ 1 67 times faster in search speed and 2 03 ~ 3 30 times faster in rule updates from synthesized rulesets and 13 9 times faster in search speed and 6 0 times faster in rule updates from real world rulesets Compared with [22] H-HashTree achieve 2 48 ~ 3 54 times faster in search speed and 1 87 ~ 3 06 times faster in rule updates from synthesized rules and 12 7 times faster in search speed and 4 53 times faster in rule updates from real world rulesets On GPU platform H-HashTree can achieve up to 114 MPPS in search speed and more than 0 04 usec/rule in rule updates

Date of Award	2020
Original language	English
Supervisor	Yeim-Kuan Chang (Supervisor)