臺灣博碩士論文加值系統

封包分類是現代路由器的一項重要功能，它支持封包轉發，連線品質管理（QoS），防火牆，流量控制，虛擬私人網路（VPN）和負載平衡。為了更好地利用網路上的路由器，SDN將控制平面與資料平面分離，以實現路由器的集中管理。在OpenFlow標準的支持下，SDN設計出不同於傳統5維規則的多維規則。除了傳統5維規則外，OpenFlow 1.0規則中的其他7個欄位都是精確匹配欄位(exact-match field)。本文的主要目的是實現一種新的封包分類演算法，以處理OpenFlow 1.0中的12維規則。
我們提出了一個分層雜湊樹（H-HashTree），根據兩個IP位址和OpenFlow 1.0中添加的7個欄位將規則集劃分為多個子集。我們還實現了擴展的布隆過濾器(extended Bloom filter)，通過省略檢查雜湊樹中的雜湊表來加速搜尋過程，並維護一個額外的分層雜湊樹處理無法採用布隆過濾器的特殊規則。該算法在GPU上實現以進一步提高性能。
我們測試了100K OpenFlow規則，其中包括具有精確匹配欄位的萬用字元比例(wildcard ratio)分別為0.1、0.5和0.9的ACL，FW和IPC特性的合成規則，以及來自Open vSwitch的實際OpenFlow規則。與現有的最新封包分類演算法[20] [22]相比，我們在搜尋速度和規則更新方面均達到了最佳性能。與[20]相比，H-HashTree在合成規則集的搜尋速度為其1.17〜1.67倍，規則更新速度為2.03〜3.30倍，現實世界規則集搜尋速度為其13.9倍，規則更新的速度為6.0倍。與[22]相比，H-HashTree在合成規則集的搜尋速度為其2.48〜3.54倍，規則更新為1.87〜3.06倍，現實規則集搜尋速度為其12.7倍，規則更新的速度為4.53倍。在GPU平台上，H-HashTree可以實現高達114 MPPS (Million Packet Per Second)的搜尋速度和超過0.04 usec/rule的規則更新速度。

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.

Abstract...i
摘要...iii
誌謝...iv
TABLE OF CONTENTS...v
LIST OF TABLES...vii
LIST OF FIGURES...viii
Chapter 1 Introduction...1
1.1 Introduction...1
1.2 Organization of the Thesis...2
Chapter 2 Related work...3
2.1 OpenFlow...3
2.1.1 Flow Table...4
2.1.2 OpenFlow vSwitch...5
2.1.3 Classbench-ng Rule Generator...6
2.2 Graphics Processing Unit (GPU)...9
2.2.1 GPU Architecture...10
2.2.2 Wavefront...13
2.2.3 Programming model (HIP)...14
2.3 Hash Tree...14
2.4 Tuple Space Search...18
2.4.1 TabTree...19
2.4.2 CutTSS...22
Chapter 3 Proposed scheme...26
3.1 Overview and Motivation...26
3.2 Main Hierarchical Hash Tree...30
3.2.1 Layer 1...30
3.2.2 Layer 2...34
3.2.3 Layer 3...38
3.2.4 Layer 4...40
3.3 Extended Bloom Filter phase...43
3.4 Extra Hierarchical Hash Tree...49
3.4.1 extra-Layer 1...49
3.4.2 extra-Layer 2...49
3.5 Stream Reduction for update...51
3.6 Extended Counting Bloom filter for update...54
Chapter 4 Experimental Results...56
4.1 Experiment Appendix...65
Chapter 5 Conclusion...71
References...72

[1] Xah Lee, “Internet Speed Growth Rate, from 2006 to date, sited at http://xahlee.info/comp/bandwidth.html
[2] P. Gupta, and N. McKeown, “Algorithms for packet classification, IEEE Network: The Magazine of Global Internetworking archive, Volume 15 Issue 2, Pages 24-32, March 2001
[3] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling Innovation in Campus Networks, ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, 2008, pp. 69-74.
[4] Giorgos Vasiliadis, Lazaros Koromilas, Michalis Polychronakis, Sotiris Ioannidis, “GASPP: A GPU-Accelerated Stateful Packet Processing Framework, 2014 USENIX Annual Technical Conference
[5] Shijie Zhou, Viktor K. Prasanna, “Scalable GPU-Accelerated IPv6 Lookup Using Hierarchical Perfect Hashing, 2015 IEEE Global Communications Conference (GLOBECOM)
[6] Cheng-Liang Hsieh, Ning Weng, Wei Wei, “Scalable Many-Field Packet Classification for Traffic Steering in SDN Switches, IEEE Transactions on Network and Service Management (Volume:16, Issue:1, March 2019)
[7] Younghwan Go, Muhammad Asim Jamshed, YoungGyoun Moon, Changho Hwang, KyoungSoo Park, “APUNet: Revitalizing GPU as Packet Processing Accelerator, USENIX Symposium on Networked Systems Design and Implementation (NSDI ’17)
[8] “OpenFlow Switch Specification Version 1.5.1, March 26, 2015
[9] “OpenFlow Switch Specification Version 1.0.0, December 31, 2009
[10] Dominik Samociuk, “Secure Communication Between OpenFlow Switches and Controllers, AFIN 2015: The Seventh International Conference on Advances in Future Internet
[11] “Open vSwitch Manual Version 2.11.90, ovs−fields − protocol header fields in OpenFlow and Open vSwitch, http://docs.openvswitch.org/en/latest/ref/
[12] Yeim-Kuan Chang and Tung-Yin Chi, “Hash-based OpenFlow Packet Classification on Heterogeneous System Architecture, 2019 Eleventh International Conference on Ubiquitous and Future Networks (ICUFN)
[13] V. Srinivasan, S. Suri, G. Vargheset, “Packet classification using tuple space search, ACM SIGCOMM Computer Communication Review August 1999
[14] Jiří Matoušek, Gianni Antichi, Adam Lučanský, Andrew W. Moore, Jan Kořenek, “ClassBench-ng: Recasting ClassBench After a Decade of Network Evolution, 2017 ACM/IEEE Symposium on Architectures for Networking and Communications
[15] Advanced Micro Devices, Inc. “AMD_GCN1_Instruction_Set_Architecture_rev1.1, December 2012
[16] Advanced Micro Devices, Inc. “AMD_GCN3_Instruction_Set_Architecture_rev1.1, August 2016
[17] Advanced Micro Devices, Inc. “White Paper | AMD GRAPHICS CORES NEXT (GCN) ARCHITECTURE, June 2012
[18] Advanced Micro Devices, Inc. “ROCm Core Technology, site: https://github.com/RadeonOpenCompute
[19] Advanced Micro Devices, Inc. “ROCm Developer Tools, site: https://github.com/ROCm-Developer-Tools
[20] Wenjun Li, Tong Yang, Ori Rottenstreich, Xianfeng Li, Gaogang Xie, Hui Li, Balajee Vamanan, Dagang Li, and Huiping Lin, “Tuple Space Assisted Packet Classification with High Performance on Both Search and Update, CutTss, IEEE Journal on Selected Areas in Communications, April 2020
[21] James Daly, Valerio Bruschi, Leonardo Linguaglossa, Salvatore Pontarelli, Dario Rossi, Jerome Tollet, Eric Torng, and Andrew Yourtchenko, “TupleMerge: Fast Software Packet Processing for Online Packet Classification, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 27, NO. 4, AUGUST 2019
[22] Wenjun Li, Tong Yang, Yeim-Kuan Chang, Tao Li, and Hui Li, “TabTree: A TSS-assisted Bit-selecting Tree Scheme for Packet Classification with Balanced Rule Mapping, 2019 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS)
[23] Wenjun Li, Xianfeng Li, Hui Li and Gaogang Xie, “CutSplit: A Decision-Tree Combining Cutting and Splitting for Scalable Packet Classification, IEEE INFOCOM 2018 - IEEE Conference on Computer Communications
[24] Sorrachai Yingchareonthawornchai, James Daly, Alex X. Liu, and Eric Torng, “A Sorted-Partitioning Approach to Fast and Scalable Dynamic Packet Classification, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 4, AUGUST 2018
[25] Ben Pfaff, Justin Pettit, Teemu Koponen, Keith Amidon, Martin Casado, Scott Shenker, “Extending networking into the virtualization layer, 8th ACM Workshop on Hot Topics inNetworks (HotNets-VIII). October 2009
[26] Ben Pfaff, Justin Pettit, Teemu Koponen, Ethan Jackson, Andy Zhou, Jarno Rajahalme, Jesse Gross, Alex Wang, Joe Stringer, Pravin Shelar, Keith Amidon, Martín Casado, “The Design and Implementation of Open vSwitch, USENIX NSDI, 2015
[27] M. Harris, S. Sengupta, and J. D. Owens, “Parallel prefix sum (scan) with CUDA, in GPU Gems 3, H. Nguyen, Ed. Addison Wesley, Aug. 2007, pp. 851–876.
[28] Burton H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM, 1970
[29] Li Fan, Member, IEEE, Pei Cao, Jussara Almeida, and Andrei Z. Broder, “Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 8, NO. 3, JUNE 2000
[30] MurmurHash family of hash functions along with the SMHasher test suite, sited at: code.google.com/p/smhasher (or https://github.com/aappleby/smhasher)