软件定义网络的可扩展规则管理技术研究

  软件定义网络是一种将控制平面和转发平面分离及开放可编程的新型网络创新架构，方便了开发人员管理和维护网络，成为了未来网络发展的趋势。软件定义网络交换机面临可扩展性问题，交换机内用于规则存储的TCAM（三态内容寻址存储器）芯片存储空间十分有限，在通用交换机内只有几千条TCAM表项，难以支持快速增长的网络应用。针对以上问题，本文研究软件定义网络的可扩展规则管理技术，包括在流量分割算法和规则放置算法上开展的研究工作。本文在流量分割算法上研究了如何减少流量分割规则所需的TCAM表项数；在规则放置算法上研究了如何减少规则放置后网络内总的TCAM表项开销。

  流量分割是在多个服务器或路径上进行负载均衡的关键任务。现有的流量分割算法将多个服务的流量划分到多个服务器或路径上时，存在占用大量TCAM表项、不具备可扩展性的问题。本文提出了一种基于规则重叠的流量分割算法，即Tiramisu算法。Tiramisu算法利用TCAM芯片的SRAM宽字技术，实现了将多组服务的流量分割规则重叠压缩放置到一个Tiramisu表内，并设计了在Tiramisu表内快速查找的算法。实验结果表明，在不平衡误差为1%时，与现有的流量分割算法相比，Tiramisu算法减少了1个数量级的TCAM表项数，并实现了更高的流量分割吞吐量和快速的规则更新。

  规则放置是指将网络的边缘交换机内的规则均衡放置到网络中的其他交换机内。现有的规则放置算法存在放置后规则发生膨胀，导致网络内额外的TCAM表项数开销的问题。本文提出了一种基于标签的规则放置算法，即TOP算法。TOP算法划分共享规则和非共享规则并分开放置，以避免共享规则复制到多个路径上；在数据包和交换机内设置标签位，判断数据包匹配规则的优先级，以实现规则放置前后语义不变。实验结果表明，当规则冗余度(a,b,c,d)取值为(1,2,4,6)时，在不同规则集下，与现有的规则放置算法相比，TOP算法减少了1.3倍到6.0倍的规则总数，同时实现了快速的规则放置和更小的流量开销。

  Software-defined network is a novel network architecture that separates the control plane and forwarding plane and provides an open programmable interface. This innovative architecture enables developers to manage and maintain networks more easily and has become a trend in the development of future networks. SDN switches face scalability issues, as the TCAM (ternary content-addressable memory) chips used for rule storage have limited storage space. In commodity switches, there are only a few thousand TCAM entries, making it difficult to support rapidly growing network applications. To address the above problems, this paper proposes the scalable rule management technology of software-defined networks, including research work conducted on traffic splitting algorithms and rule placement algorithms. This paper investigates how to reduce the number of TCAM table entries required for traffic splitting rules in the traffic splitting algorithm, and how to reduce the overall TCAM table entry overhead in the network after rule placement in the rule placement algorithm.
  Traffic splitting is a key task for load balancing over multiple servers or paths.Existing traffic splitting algorithms have problems with occupying a large number of TCAM table entries and lack of scalability when splitting the traffic of multiple services into multiple servers or paths. This paper proposes a traffic splitting algorithm based on rule overlay, called the Tiramisu algorithm. The Tiramisu algorithm exploits the technique of wide SRAM words available in TCAMs to overlay multiple groups of rules for different services within one same Tiramisu table, and designs an algorithm for fast lookup in the Tiramisu table. Experimental results show that, with an imbalance error of 1%, the Tiramisu algorithm reduces the number of TCAM table entries by one order of magnitude compared to other algorithms, and achieves higher traffic splitting throughput and fast rule updates.

 Rule placement is a method of evenly distributing the rules inside the edge switches of a network to other switches in the network. Existing rule placement algorithms suffer from the problem of rule inflation and additional TCAM table entry overhead in the network after placement. This paper proposes a label-based rule placement algorithm, called the TOP algorithm. The TOP algorithm divides shared and non-shared rules and places them separately to avoid replicating shared rules on multiple paths. It also sets label bits in packets and switches to determine the priority of matching rules, thus achieving semantic consistency before and after rule placement. The experimental results show that when the redundancy degree of rules (a, b, c, d) is set to (1, 2, 4, 6), under different rule sets, compared with the existing rule placement algorithms, the TOP algorithm reduces the total number of rules by 1.3 to 6.0 times, while achieving fast rule placement and smaller traffic overhead.

[1] 张丹. 软件定义网络中负载均衡路由算法研究[D]. 重庆邮电大学, 2017.
[2] 张朝昆, 崔勇, 唐翯祎, 等. 软件定义网络 (SDN) 研究进展[J]. 软件学报, 2015: 62-81.
[3] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008: 69-74.
[4] BOSSHART P, DALY D, GIBB G, et al. P4: Programming protocol-independent packet pro- cessors[J]. ACM SIGCOMM Computer Communication Review, 2014: 87-95.
[5] 陈志鹏, 徐明伟, 杨芫. SDN 交换机转发规则 TCAM 存储优化综述[J]. 计算机学报, 2021: 1341-1362.
[6] YU F, KATZ R H, LAKSHMAN T V. Gigabit rate packet pattern-matching using TCAM[C]// Proceedings of IEEE ICNP. 2004: 174-183.
[7] KANNAN K, BANERJEE S. Compact TCAM: Flow entry compaction in TCAM for power aware SDN[C]//Proceedings of ICDCN. 2013: 439-444.
[8] AGRAWAL B, SHERWOOD T. Modeling TCAM power for next generation network devices [C]//Proceedings of IEEE ISPASS. 2006: 120-129.
[9] APPELMAN M, DE BOER M. Performance analysis of OpenFlow hardware[J]. University of Amsterdam, Technical Report, 2012.
[10] HUANG D Y, YOCUM K, SNOEREN A C. High-fidelity switch models for software-defined network emulation[C]//Proceedings of ACM HotSDN. 2013: 43-48.
[11] ROTTENSTREICH O, et al. Lossy compression of packet classifiers[C]//Proceedings of ACM/IEEE ANCS. 2015: 39-50.
[12] KANG N, GHOBADI M, REUMANN J, et al. Efficient traffic splitting on commodity switches [C]//Proceedings of ACM CoNEXT. 2015: 1-13.
[13] HSU K F, TAMMANA P, BECKETT R, et al. Adaptive weighted traffic splitting in pro- grammable data planes[C]//Proceedings of ACM SOSR. 2020: 103-109.
[14] WANG R, BUTNARIU D, REXFORD J, et al. OpenFlow-based server load balancing gone wild.[C]//Proceedings of USENIX Hot-ICE. 2011: 1-12.
[15] ZHOU J, TEWARI M, ZHU M, et al. WCMP: Weighted cost multipathing for improved fairness in data centers[C]//Proceedings of ACM EuroSys. 2014: 1-14.
[16] SADEH Y, ROTTENSTREICH O, BARKAN A, et al. Optimal representations of a traffic distribution in switch memories[J]. IEEE/ACM Transactions on Networking, 2020: 930-943.
[17] SADEH Y, ROTTENSTREICH O, KAPLAN H. Optimal approximations for traffic distribution in bounded switch memories[C]//Proceedings of ACM CoNEXT. 2020: 309-322.
[18] KANIZO Y, HAY D, KESLASSY I. Palette: Distributing tables in software-defined networks [C]//Proceedings of IEEE INFOCOM. 2013: 545-549.
[19] KANG N, LIU Z, REXFORD J, et al. Optimizing the” one big switch” abstraction in software- defined networks[C]//Proceedings of ACM CoNEXT. 2013: 13-24.
[20] CHUPRIKOV P, KOGAN K, NIKOLENKO S. How to implement complex policies on existing network infrastructure[C]//Proceedings of ACM SOSR. 2018: 1-7.
[21] 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: 19-29.
[22] MOSHREF M, YU M, SHARMA A B, et al. Scalable rule management for data centers.[C]// Proceedings of USENIX NSDI. 2013: 157-170.
[23] HUANG H, LI P, GUO S, et al. The joint optimization of rules allocation and traffic engineering in software defined network[C]//Proceedings of IEEE IWQoS. 2014: 141-146.
[24] PATEL P, BANSAL D, YUAN L, et al. Ananta: Cloud scale load balancing[J]. ACM SIG- COMM Computer Communication Review, 2013: 207-218.
[25] GANDHI R, LIU H H, HU Y C, et al. Duet: Cloud scale load balancing with hardware and software[J]. ACM SIGCOMM Computer Communication Review, 2014: 27-38.
[26] EISENBUD D E, YI C, CONTAVALLI C, et al. Maglev: A fast and reliable software network load balancer[C]//Proceedings of USENIX NSDI. 2016: 523-535.
[27] MIAO R, ZENG H, KIM C, et al. Silkroad: Making stateful layer-4 load balancing fast and cheap using switching asics[C]//Proceedings of ACM SIGCOMM. 2017: 15-28.
[28] OLTEANU V, AGACHE A, VOINESCU A, et al. Stateless datacenter load-balancing with beamer[C]//Proceedings of USENIX NSDI. 2018: 125-139.
[29] BARBETTE T, TANG C, YAO H, et al. A High-Speed Load-Balancer Design with Guaranteed Per-Connection-Consistency.[C]//Proceedings of USENIX NSDI. 2020: 667-683.
[30] PAN T, YU N, JIA C, et al. Sailfish: Accelerating cloud-scale multi-tenant multi-service gate- ways with programmable switches[C]//Proceedings of ACM SIGCOMM. 2021: 194-206.
[31] ALIZADEH M, EDSALL T, DHARMAPURIKAR S, et al. CONGA: Distributed congestion- aware load balancing for datacenters[C]//Proceedings of ACM SIGCOMM. 2014: 503-514.
[32] KATTA N, HIRA M, KIM C, et al. Hula: Scalable load balancing using programmable data planes[C]//Proceedings of ACM SOSR. 2016: 1-12.
[33] ROTTENSTREICH O, KANIZO Y, KAPLAN H, et al. Accurate traffic splitting on commodity switches[C]//Proceedings of ACM SPAA. 2018: 311-320.
[34] SADEH Y, ROTTENSTREICH O, BARKAN A, et al. Optimal representations of a traffic distribution in switch memories[J]. IEEE/ACM Transactions on Networking, 2020: 930-943.
[35] SADEH Y, ROTTENSTREICH O, KAPLAN H. How much TCAM do we need for splitting traffic?[C]//Proceedings of ACM SOSR. 2021: 169-175.
[36] PATEL P, BANSAL D, YUAN L, et al. Ananta: Cloud scale load balancing[J]. ACM SIG- COMM Computer Communication Review, 2013: 207-218.
[37] HOPPS C E. Analysis of an Equal-Cost Multi-Path Algorithm[J]. RFC, 2000, 2992: 1-8.
[38] CHIESA M, KINDLER G, SCHAPIRA M. Traffic engineering with equal-cost-multipath: An algorithmic perspective[J]. IEEE/ACM Transactions on Networking, 2016: 779-792.
[39] HUANG J F, CHANG G Y, WANG C F, et al. Heterogeneous flow table distribution in software- defined networks[J]. IEEE Transactions on Emerging Topics in Computing, 2015: 252-261.
[40] GIROIRE F, MOULIERAC J, PHAN T K. Optimizing rule placement in software-defined networks for energy-aware routing[C]//Proceedings of IEEE GLOBECOM. 2014: 2523-2529.
[41] LU W, SAHNI S. Low-power TCAMs for very large forwarding tables[J]. IEEE/ACM Trans- actions on Networking, 2009: 948-959.
[42] BANERJEE T, SAHNI S, SEETHARAMAN G. PC-TRIO: A power efficient TCAM architec- ture for packet classifiers[J]. IEEE Transactions on Computers, 2014: 1104-1118.
[43] BOSSHART P, GIBB G, KIM H S, et al. Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN[J]. ACM SIGCOMM Computer Communication Review, 2013: 99-110.
[44] CASADO M, FREEDMAN M J, PETTIT J, et al. Rethinking enterprise network control[J]. IEEE/ACM Transactions on Networking, 2009: 1270-1283.
[45] AGRAWAL B, SHERWOOD T. Ternary CAM power and delay model: Extensions and uses [J]. IEEE Transactions on Very Large Scale Integration Systems, 2008: 554-564.
[46] NGUYEN X N, SAUCEZ D, BARAKAT C, et al. Rules placement problem in OpenFlow networks: A survey[J]. IEEE Communications Surveys & Tutorials, 2015: 1273-1286.
[47] CALVERT K L, DOAR M B, ZEGURA E W. Modeling internet topology[J]. IEEE Commu- nications Magazine, 1997: 160-163.
[48] TAYLOR D E, TURNER J S. Classbench: A packet classification benchmark[J]. IEEE/ACM Transactions on Networking, 2007: 499-511.