软件定义网络下的规则缓存算法研究

 软件定义网络（SDN）是网络领域中一种革命性的网络架构，其核心思想在于将控制平面与数据平面分离，实现灵活的网络管理控制，并具备开放可编程性，为网络控制提供了新的基础。三态内容寻址存储器（TCAM）是SDN交换机中重要组成部分，它用于快速匹配规则以确定数据包的处理路径。由于TCAM资源的稀缺性，它通常作为规则表的缓存出现。规则之间存在着问题是规则依赖问题。当需要缓存某一条规则时，往往需要缓存众多的依赖规则才可以保证规则匹配的语义正确性。因此合适的规则缓存算法对于交换机来说十分重要。
  本文针对上述问题提出了CacheBand缓存算法和RuleEmbedding缓存算法，旨在为不同场景下的交换机提供合理的缓存方案。
 CacheBand算法聚焦于产生新规则的方法隔断规则依赖链。通过对原有规则以及当前流量的分布，该算法提供智能化的方法产生绷带规则，用以覆盖住在规则自己搜索空间内的依赖规则。同时解决自身搜索空间内部的依赖规则及外部的间接依赖规则。实验结果表明与同类算法相比，在不同数据包速率的情况下，CacheBand减少了约68\%的缓存条目，显著降低了流表的压力，减缓了不同数据包速率下流表溢出的可能，为网络领域基础的数据转发提供了更可靠的缓存方案。

RuleEmbedding算法则旨在通过分割规则的手段产生合理的新规则以减轻规则间存在的长依赖链问题。通过更加合理的分割方案，将划分后的区域信息融入到原始规则后，形成新规则。新规则的依赖情况在调整后可以实现更为简单的规则缓存方案。该方案在企业网络分布式流架构 （DIFANE）架构中进行实验表明，在整体规则集略微增长后，RuleEmbedding与同类算法相比，减少了约42\%的缓存条目。

[1] DONG M, LI H, OTA K, et al. Rule caching in SDN-enabled mobile access networks[J]. IEEE Network, 2015, 29(4): 40-45.
[2] CHETTRI L, BERA R. A comprehensive survey on Internet of Things (IoT) toward 5G wireless systems[J]. IEEE Internet of Things Journal, 2019, 7(1): 16-32.
[3] SUNYAEV A, SUNYAEV A. Cloud computing[J]. Internet Computing: Principles of Distributed Systems and Emerging Internet-Based Technologies, 2020: 195-236.
[4] THIRUPATHI V, SANDEEP C, KUMAR N, et al. A comprehensive review on SDN architecture, applications and major benefits of SDN[J]. International Journal of Advanced Science and Technology, 2019, 28(20): 607-614.
[5] 张顺淼, 邹复民. 软件定义网络研究综述[J]. 计算机应用研究, 2013, 30(8): 2246-2251.
[6] ACHLEITNER S, LA PORTA T F, MCDANIEL P, et al. Deceiving network reconnaissance using SDN-based virtual topologies[J]. IEEE Transactions on Network and Service Management, 2017, 14(4): 1098-1112.
[7] LANTZ B, O’CONNOR B. A Mininet-based virtual testbed for distributed SDN development[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(4): 365-366.
[8] MUÑOZ R, VILALTA R, CASELLAS R, et al. Integrated SDN/NFV management and orchestration architecture for dynamic deployment of virtual SDN control instances for virtual tenant networks[J]. Journal of Optical Communications and Networking, 2015, 7(11): B62-B70.
[9] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks[J]. ACM SIGCOMM computer communication review, 2008, 38(2): 69-74.
[10] GUDE N, KOPONEN T, PETTIT J, et al. NOX: towards an operating system for networks[J]. ACM SIGCOMM computer communication review, 2008, 38(3): 105-110.
[11] HAN B, GOPALAKRISHNAN V, JI L, et al. Network function virtualization: Challenges and opportunities for innovations[J]. IEEE communications magazine, 2015, 53(2): 90-97.
[12] BERDE P, GEROLA M, HART J, et al. ONOS: towards an open, distributed SDN OS[C]// Proceedings of the third workshop on Hot topics in software defined networking. 2014: 1-6.
[13] ASADOLLAHI S, GOSWAMI B, SAMEER M. Ryu controller’s scalability experiment on software defined networks[C]//2018 IEEE international conference on current trends in advanced computing (ICCTAC). IEEE, 2018: 1-5.
[14] SHEU J P, CHUO Y C. Wildcard rules caching and cache replacement algorithms in software-defined networking[J]. IEEE Transactions on Network and Service Management, 2016, 13(1): 19-29.
[15] WAN Y, SONG H, CHE H, et al. Fastup: Fast TCAM update for SDN switches in datacenter networks[C]//IEEE 41st International Conference on Distributed Computing Systems (ICDCS). IEEE, 2021: 887-897.
[16] WEN X, YANG B, CHEN Y, et al. RuleTris: Minimizing rule update latency for TCAM-based SDN switches[C]//IEEE 36th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2016: 179-188.
[17] XU S, WANG X, YANG G, et al. Routing optimization for cloud services in SDN-based Internet of Things with TCAM capacity constraint[J]. Journal of Communications and Networks, 2020, 22(2): 145-158.
[18] ZHANG S Q, ZHANG Q, TIZGHADAM A, et al. TCAM space-efficient routing in a software defined network[J]. Computer Networks, 2017, 125: 26-40.
[19] QIU K, YUAN J, ZHAO J, et al. Fastrule: Efficient flow entry updates for TCAM-based OpenFlow switches[J]. IEEE Journal on Selected Areas in Communications, 2019, 37(3): 484-498.
[20] YAN B, XU Y, XING H, et al. Cab: A reactive wildcard rule caching system for software-defined networks[C]//Proceedings of the third workshop on Hot topics in software defined networking. 2014: 163-168.
[21] 朱智华, 王思宇, 宋军辉, 等. 基于 TCAM 的包分类算法研究综述[J]. 中国集成电路, 2023, 32(9): 66-73+85.
[22] SRINIVASAN V, VARGHESE G, SURI S, et al. Fast and scalable layer four switching[C]//Proceedings of the ACM SIGCOMM’98 conference on Applications, technologies, architectures, and protocols for computer communication. 1998: 191-202.
[23] SINGH S, BABOESCU F, VARGHESE G, et al. Packet classification using multidimensional cutting[C]//Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications. 2003: 213-224.
[24] GUPTA P, MCKEOWN N. Packet classification using hierarchical intelligent cuttings[C]//Hot Interconnects VII: Vol. 40. 1999.
[25] LAKSHMAN T, STILIADIS D. High-speed policy-based packet forwarding using efficient multi-dimensional range matching[J]. ACM SIGCOMM Computer Communication Review, 1998, 28(4): 203-214.
[26] SRINIVASAN V, SURI S, VARGHESE G. Packet classification using tuple space search[C]//Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication. 1999: 135-146.
[27] LIANG E, ZHU H, JIN X, et al. Neural packet classification[M]//Proceedings of the ACM Special Interest Group on Data Communication. 2019: 256-269.
[28] GRIGORYAN G, LIU Y. PFCA: A programmable FIB caching architecture[C]//Proceedings of the Symposium on Architectures for Networking and Communications Systems. 2018: 97-103.
[29] KATTA N, ALIPOURFARD O, REXFORD J, et al. Cacheflow: Dependency-aware rule caching for software-defined networks[C]//Proceedings of the Symposium on SDN Research. 2016: 1-12.
[30] CURTIS A R, MOGUL J C, TOURRILHES J, et al. DevoFlow: Scaling flow management for high-performance networks[C]//Proceedings of the ACM SIGCOMM 2011 Conference. 2011: 254-265.
[31] MARSICO A, DORIGUZZI-CORIN R, SIRACUSA D. An effective swapping mechanism to overcome the memory limitation of SDN devices[C]//IFIP/IEEE Symposium on Integrated Network and Service Management (IM). IEEE, 2017: 247-254.
[32] WAN Y, SONG H, XU Y, et al. T-cache: Dependency-free Ternary Rule Cache for Policy-based Forwarding[C]//IEEE INFOCOM Conference on Computer Communications. IEEE, 2020: 536-545.
[33] LI X, XIE W. CRAFT: A cache reduction architecture for flow tables in software-defined networks[C]//IEEE Symposium on Computers and Communications (ISCC). IEEE, 2017: 967-972.
[34] YU M, REXFORD J, FREEDMAN M J, et al. Scalable flow-based networking with DIFANE[J]. ACM SIGCOMM Computer Communication Review, 2010, 40(4): 351-362.
[35] LUAN Z, LI Q, WANG Y, et al. H-Cache: Traffic-Aware Hybrid Rule-Caching in Software-Defined Networks[C]//IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2023: 69-78.
[36] KANNAN K, BANERJEE S. Compact TCAM: Flow entry compaction in TCAM for power aware SDN[C]//International conference on distributed computing and networking. Springer, 2013: 439-444.
[37] AGRAWAL B, SHERWOOD T. Modeling TCAM power for next generation network devices[C]//IEEE International Symposium on Performance Analysis of Systems and Software. IEEE, 2006: 120-129.
[38] PFAFF B, PETTIT J, KOPONEN T, et al. The design and implementation of open {vSwitch}[C]//12th USENIX symposium on networked systems design and implementation (NSDI 15). 2015: 117-130.
[39] TU W, WEI Y H, ANTICHI G, et al. Revisiting the open vSwitch dataplane ten years later[C]//Proceedings of the 2021 ACM SIGCOMM 2021 Conference. 2021: 245-257.
[40] HAMADI S, SNAIKI I, CHERKAOUI O. Fast path acceleration for open vSwitch in overlay networks[C]//Global Information Infrastructure and Networking Symposium (GIIS). IEEE, 2014: 1-5.
[41] WANG L M, MISKELL T, FU P, et al. OVS-DPDK port mirroring via NIC offloading[C]//NOMS IEEE/IFIP Network Operations and Management Symposium. IEEE, 2020: 1-2.
[42] XU C, ZHANG R, XIE M, et al. Network intrusion detection system as a service in OpenStack cloud[C]//International conference on computing, networking and communications (ICNC). IEEE, 2020: 450-455.
[43] SHELLY N, JACKSON E J, KOPONEN T, et al. Flow caching for high entropy packet fields[C]//Proceedings of the third workshop on Hot topics in software defined networking. 2014: 151-156.
[44] TRAVERSO S, AHMED M, GARETTO M, et al. Temporal locality in today’s content caching: Why it matters and how to model it[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(5): 5-12.
[45] MENG X, PAPPAS V, ZHANG L. Improving the scalability of data center networks with traffic-aware virtual machine placement[C]//Proceedings IEEE INFOCOM. IEEE, 2010: 1-9.
[46] GLASSNER A S. An introduction to ray tracing[M]. Morgan Kaufmann, 1989.
[47] AKENINE-MO T, HAINES E, HOFFMAN N, et al. Real-time rendering[M]. AK Peters/CRC Press, 2018.
[48] ZHOU K, HOU Q, WANG R, et al. Real-time kd-tree construction on graphics hardware[J]. ACM Transactions on Graphics (TOG), 2008, 27(5): 1-11.
[49] WALD I. On fast construction of SAH-based bounding volume hierarchies[C]//IEEE Symposium on Interactive Ray Tracing. IEEE, 2007: 33-40.
[50] MEISTER D, OGAKI S, BENTHIN C, et al. A survey on bounding volume hierarchies for ray tracing[C]//Computer Graphics Forum: Vol. 40. Wiley Online Library, 2021: 683-712.
[51] TAYLOR D E, TURNER J S. Classbench: A packet classification benchmark[J]. IEEE/ACM transactions on networking, 2007, 15(3): 499-511.
[52] BOSSHART P, DALY D, GIBB G, et al. P4: Programming protocol-independent packet processors[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 87-95.
[53] MA Z, BI J, ZHANG C, et al. Cachep4: A behavior-level caching mechanism for P4[M]//Proceedings of the SIGCOMM Posters and Demos. 2017: 108-110.
[54] 唐鑫新, 曾学文, 凌致远, 等. 可编程数据平面技术综述[J]. 电信科学, 2023, 39(4): 1-16.
[55] 夏计强, 崔鹏帅, 李子勇, 等. 基于 P4 的 SDN 控制-数据平面流规则一致性校验.[J]. Application Research of Computers/Jisuanji Yingyong Yanjiu, 2022, 39(8).
[56] 張燕光, 等. 基於 OpenFlow 及 P4 語言之高效能快速更新之可編程交換機的設計和實現[Z]. 2020.
[57] HOU S, HU Y, TIAN L, et al. NFD. P4: NDN in-networking cache implementation scheme with P4[J]. IEICE TRANSACTIONS on Information and Systems, 2022, 105(4): 820-823.
[58] KFOURY E F, CRICHIGNO J, BOU-HARB E. An exhaustive survey on P4 programmable data plane switches: Taxonomy, applications, challenges, and future trends[J]. IEEE access, 2021, 9: 87094-87155.
[59] GAO P, XU Y, CHAO H J. OVS-CAB: Efficient rule-caching for Open vSwitch hardware offloading[J]. Computer Networks, 2021, 188: 107844.
[60] YAN B, XU Y, CHAO H J. Adaptive wildcard rule cache management for software-defined networks[J]. IEEE/ACM Transactions on Networking, 2018, 26(2): 962-975.
[61] YAN B, XU Y, CHAO H J. BigMaC: Reactive network-wide policy caching for SDN policy enforcement[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(12): 2675-2687.