基于SDN的高性能网络包分类算法研究

网络包分类算法是软件定义网络（Software Defined Network，SDN）数据平面 的核心算法之一，直接关系到网络设备的转发性能。随着网络服务与网络应用不 断发展，对包分类算法的查询能力提出了更高的要求，还要求包分类算法支持流 表的频繁更新。本文将基于SDN 环境，重点研究软硬件包分类算法，主要贡献如 下：

首先，本文介绍了包分类算法的研究现状及演化过程，分析了各类包分类算法 的优缺点与性能瓶颈，并提出了使用强化学习辅助的递归元组空间搜索算法HybridTSS 。HybridTSS 算法通过元组划分和元组内哈希两项策略，迅速将粗粒度节 点划分成细粒度节点，并在强化学习的辅助下，实现了全局优化，避免了传统算法 中经验化参数选取的问题。相比传统算法，HybridTSS 可以充分挖掘各个规则集的 特征并实现自适应构建，基于ClassBench 的实验测评中表明，HybridTSS 算法在多 数规则集上的查询性能和更新性能同时达到了最优，相比于Open vSwitch（OVS） 虚拟交换机中使用的PSTSS 算法，HybridTSS 算法在查询吞吐率方面平均获得了 8.8 倍的提升，并且在更新性能上与PSTSS 算法持平。

接着本文提出了专为FPGA 设计的硬件包分类算法KickTree。KickTree 算法 结合软硬协同思想，设计了多叉决策树森林结构，充分利用FPGA 的并行能力，同 时完成多棵决策树树并行查找，避免了规则复制问题与FPGA 实现不友好的结构， 通过的启发式划分操作与深度受限机制，保证了算法查询性能的的下限。实验结 果表明KickTree 在查询操作时的内存访问次数明显优于TabTree，同时提供了与 TabTree 相当的规则更新性能，且更易于FPGA 实现。

[1] ROUGHAN M, SEN S, SPATSCHECK O, et al. Class-of-service mapping for QoS: a statistical signature-based approach to IP traffic classification[C]//proceedings of Special Interest Group on Data Communication. 2004: 135-148.
[2] FREED N. Behavior of and requirements for Internet firewalls[R]. 2000.
[3] KUŹNIAR M, PEREŠÍNI P, KOSTIĆ D. What you need to know about SDN flow tables[C]// Proceedings of Passive and Active Measurement. 2015: 347-359.
[4] CHAO H J, LIU B. High performance switches and routers[M]. 2007.
[5] 张朝昆, 崔勇, 唐翯祎, 等. 软件定义网络(SDN) 研究进展[J]. 软件学报, 2015: 62-81.
[6] 黄韬, 刘江, 霍如, 等. 未来网络体系架构研究综述[J]. 通信学报, 2014.
[7] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks[J]. ACM SIGCOMM computer communication review, 2008: 69-74.
[8] JIN X, REXFORD J, WALKER D. Incremental update for a compositional SDN hypervisor [C]//Proceedings of Hot topics in software defined networking. 2014: 187-192.
[9] JIN X, LIU H H, GANDHI R, et al. Dynamic scheduling of network updates[J]. ACM SIGCOMM Computer Communication Review, 2014: 539-550.
[10] YANG T, LIU A X, SHEN Y, et al. Fast OpenFlow table lookup with fast update[C]// Proceedings of International Conference on Computer Communications. 2018: 2636-2644.
[11] LI H, CHEN K, PAN T, et al. Cora: Conflict razor for policies in sdn[C]//Proceedings of International Conference on Computer Communications. 2018: 423-431.
[12] SRINIVASAN V, VARGHESE G, SURI S, et al. Fast and scalable layer four switching[C]// Proceedings of Applications, technologies, architectures, and protocols for computer communication. 1998: 191-202.
[13] TAYLOR D E. Survey and taxonomy of packet classification techniques[J]. ACM Computing Surveys (CSUR), 2005: 238-275.
[14] SONG H, TURNER J, DHARMAPURIKAR S. Packet classification using coarse-grained tuple spaces[C]//Proceedings ofsymposium on Architecture for networking and communications systems. 2006: 41-50.
[15] LIM H, KIM S Y. Tuple pruning using bloom filters for packet classification[J]. IEEE Micro, 2010: 48-59.
[16] SHEN T, XIE G, WANG X, et al. RVH: Range-vector hash for fast online packet classification [A]. 2019.
[17] SRINIVASAN V, SURI S, VARGHESE G. Packet classication using tuple space search[C]// Proceedings of Applications, technologies, architectures, and protocols for computer communication. 1999: 135-146.
[18] PFAFF B, PETTIT J, KOPONEN T, et al. The design and implementation of open vswitch [C]//Proceeding of {USENIX} Symposium on Networked Systems Design and Implementation. 2015: 117-130.
[19] DALY J, TORNG E. Tuplemerge: Building online packet classifiers by omitting bits[C]// Proceedings of Symposium on Architectures for Networking and Communications Systems. IEEE, 2017: 1-10.
[20] HE P, XIE G, SALAMATIAN K, et al. Meta-algorithms for software-based packet classification [C]//Proceedings of International Conference on Network Protocols. IEEE, 2014: 308-319.
[21] CHANG Y K. Efficient multidimensional packet classification with fast updates[J]. IEEE Transactions on Computers, 2008: 463-479.
[22] DALY J, TORNG E. Bytecuts: Fast packet classification by interior bit extraction[C]// Proceedings of International Conference on Computer Communications. 2018: 2654-2662.
[23] GUPTA P, MCKEOWN N. Classifying packets with hierarchical intelligent cuttings[J]. Ieee Micro, 2000: 34-41.
[24] SINGH S, BABOESCU F, VARGHESE G, et al. Packet classification using multidimensional cutting[C]//Proceedings of Applications, technologies, architectures, and protocols for computer communications. 2003: 213-224.
[25] QI Y, XU L, YANG B, et al. Packet classification algorithms: From theory to practice[C]// Proceedings of International Conference on Computer Communications. 2009: 648-656.
[26] VAMANAN B, VOSKUILEN G, VIJAYKUMAR T. EffiCuts: Optimizing packet classification for memory and throughput[J]. ACM SIGCOMM Computer Communication Review, 2010: 207-218.
[27] LI W, LI X. HybridCuts: A scheme combining decomposition and cutting for packet classification[ C]//Proceedings of Symposium on High-Performance Interconnets. IEEE, 2013: 41-48.
[28] LI W, LI X, LI H, et al. Cutsplit: A decision-tree combining cutting and splitting for scalable packet classification[C]//Proceedings of International Conference on Computer Communications. 2018: 2645-2653.
[29] PRAKASH I, BANSAL A, VERMA R, et al. SmartSplit: Latency-energy-memory optimisation for CNN splitting on smartphone environment[C]//Proceedings of International Conference on COMunication Systems & NETworkS. 2022: 549-557.
[30] YINGCHAREONTHAWORNCHAI S, DALY J, LIU A X, et al. A sorted partitioning approach to high-speed and fast-update OpenFlow classification[C]//2016 IEEE 24th International Conference on Network Protocols (ICNP). 2016: 1-10.
[31] LI W, YANG T, ROTTENSTREICH O, et al. Tuple space assisted packet classification with high performance on both search and update[J]. IEEE Journal on Selected Areas in Communications, 2020: 1555-1569.
[32] ZHANG X, XIE G, WANG X, et al. Fast online packet classification with convolutional neural network[J]. IEEE/ACM Transactions on Networking, 2021: 2765-2778.
[33] LIANG E, ZHU H, JIN X, et al. Neural packet classification[M]//Proceedings of Special Interest Group on Data Communication. 2019: 256-269.
[34] RASHELBACH A, ROTTENSTREICH O, SILBERSTEIN M. A computational approach to packet classification[C]//Proceedings of Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication. 2020: 542-556.
[35] SPITZNAGEL E, TAYLOR D, TURNER J. Packet classification using extended TCAMs[C]// Proceedings of International Conference on Network Protocols. 2003: 120-131.
[36] YAO R, LUO C, LIU X, et al. MagicTCAM: A multiple-TCAM scheme for fast TCAM update [C]//Proceedings of International Conference on Computer Communications. 2021: 1-11.
[37] CHE H, WANG Z, ZHENG K, et al. DRES: Dynamic range encoding scheme for TCAM coprocessors[J]. IEEE Transactions on Computers, 2008: 902-915.
[38] VAMANAN B, VIJAYKUMAR T. TreeCAM: decoupling updates and lookups in packet classification[ C]//Proceedings of emerging Networking EXperiments and Technologies. 2011: 1-12.
[39] LIU A X, MEINERS C R, TORNG E. TCAM Razor: A systematic approach towards minimizing packet classifiers in TCAMs[J]. IEEE/ACM Transactions on Networking, 2009: 490-500.
[40] BREBNER G. Packets everywhere: The great opportunity for field programmable technology [C]//Proceedings of International Conference on Field-Programmable Technology. 2009: 1-10.
[41] IBANEZ S, BREBNER G, MCKEOWN N, et al. The p4-> netfpga workflow for line-rate packet processing[C]//Proceedings of International Symposium on Field-Programmable Gate Arrays. 2019: 1-9.
[42] CHANG Y K, HSUEH C S. Range-enhanced packet classification design on FPGA[J]. IEEE Transactions on Emerging Topics in Computing, 2015: 214-224.
[43] FIESSLER A, HAGER S, SCHEUERMANN B, et al. HyPaFilter: A versatile hybrid FPGA packet filter[C]//Proceedings of Architectures for Networking and Communications Systems. 2016: 25-36.
[44] LI W, YANG T, CHANG Y K, et al. TabTree: A TSS-assisted bit-selecting tree scheme for packet classification with balanced rule mapping[C]//Proceedings of Symposium on Architectures for Networking and Communications Systems. 2019: 1-8.
[45] TAYLOR D E, TURNER J S. Classbench: A packet classification benchmark[J]. IEEE/ACM transactions on networking, 2022: 2760-2775.
[46] MATOUŠEK J, ANTICHI G, LUČANSKỲ A, et al. Classbench-ng: Recasting classbench after a decade of network evolution[C]//Proceedings of Symposium of Architectures for Networking and Communications Systems. IEEE, 2017: 204-216.
[47] HERRERA J G, BOTERO J F. Resource allocation in NFV: A comprehensive survey[J]. IEEE Transactions on Network and Service Management, 2016: 518-532.
[48] OVERMARS M H, VAN DER STAPPEN F A. Range searching and point location among fat objects[J]. Journal of Algorithms, 1996: 629-656.
[49] LAKSHMAN T, STILIADIS D. High-speed policy-based packet forwarding using efficient multi-dimensional range matching[J]. ACM SIGCOMM Computer Communication Review, 1998: 203-214.
[50] QU Y R, PRASANNA V K. High-performance and dynamically updatable packet classification engine on FPGA[J]. IEEE Transactions on Parallel and Distributed Systems, 2015: 197-209.
[51] GANEGEDARA T, JIANG W, PRASANNA V K. A scalable and modular architecture for highperformance packet classification[J]. IEEE Transactions on Parallel and Distributed Systems, 2013: 1135-1144.
[52] SHI Z, YANG H, LI J, et al. MsBV: A memory compression scheme for bit-vector-based classification lookup tables[J]. IEEE Access, 2020: 38673-38681.
[53] SUTTON R S, BARTO A G. Reinforcement learning: An introduction[M]. 2018.
[54] LI Y. Deep reinforcement learning: An overview[A]. 2017.
[55] KAELBLING L P, LITTMAN M L, MOORE A W. Reinforcement learning: A survey[J]. Journal of artificial intelligence research, 1996: 237-285.
[56] WATKINS C J, DAYAN P. Q-learning[J]. Machine learning, 1992: 279-292.