软件定义网络（SDN）中，流表规则匹配域之间相互重叠，使得流表更新问题变得复杂。一条更新规则往往会触发多条三态内容寻址存储器（TCAM）表项移动，导致更新时间长。另外，现有SDN交换机采用的TCAM多为单端口设计，当TCAM进行流表更新时，数据包查找会被阻塞，导致数据平面的转发性能受到影响。因此，如何实现快速更新并保障数据包查找，是提高网络性能的一个重要研究问题。该文以采用TCAM查找方案的SDN交换机为硬件基础，设计并实现了流表更新系统。多个网络应用的更新经过前端整合并同时下达时，系统对规则之间的依赖关系进行高效检测，赋予延时需求高的规则高优先级，使其能得到快速响应。该更新算法不会阻塞TCAM查找，可以实现查找和更新穿插执行。实验结果表明：通过采用不同的调度策略，系统性能在更新优先策略与查找优先策略之间取得了平衡。
In software-defined networking (SDN), the overlapping among the matching fields of rules complicates flow table updates. One update often triggers the movement of multiple ternary content addressable memory (TCAM) entries, which increases the update times. In addition, the TCAMs in existing SDN switches are mostly designed with a single port. The TCAM update suspends the packet lookup which affects the packet forwarding in the data plane. Therefore, how to achieve fast update while supporting wire-speed packet lookup is an important research topic to improve network performance. This paper presents a TCAM-based SDN switch with a flow table update system. When multiple network application updates are integrated at the front end and simultaneously sent to the switch, the system can efficiently detect the dependencies between rules and prioritize the rules which need to be quickly updated, so that they can respond quickly. The update algorithm does not need to block the TCAM search operation and can provide interleaved execution of the packet lookups and rule updates. Tests show that these scheduling strategies improve the system performance by balancing the lookup first algorithm and the update first algorithm.
[1] CASADO M, FREEDMAN M J, PETTIT J, et al. Rethinking enterprise network control[J]. IEEE/ACM Transactions on Networking, 2009, 17(4):1270-1283.
[2] HONG C Y, CAESAR M, GODFREY P. Finishing flows quickly with preemptive scheduling[C]//ACM Special Interest Group on Data Communication (SIGCOMM) Conference Applications, Technologies, Architectures, and Protocols for Computer Communication. Helsinki, Finland, 2012:127-138.
[3] BENSON T, ASHOK A, ADITYA A, et al. MicroTE:Fine grained traffic engineering for data centers[C]//Proceedings of the Seventh Conference on Emerging Networking Experiments and Technologies (CoNEXT). Tokyo, Japan, 2011:1-12.
[4] JIN X, LI E L, VANBEVER L, REXFORD J. SoftCell:Scalable and flexible cellular core network architecture[C]//Proceedings of the Ninth ACM Conference on Emerging Networking Experiments and Technologies (CoNEXT). Santa Barbara, USA, 2013:163-174.
[5] HE P, ZHANG W Y, GUAN H T, et al. Partial order theory for fast TCAM updates[J]. IEEE/ACM Transactions on Networking (TON), 2018, 26(1):217-230.
[6] WAN Y, SONG H Y, CHE H, et al. FastUp:Fast TCAM update for SDN Switches in datacenter networks[C]//41st International Conference on Distributed Computing Systems (ICDCS). Washington DC, USA, 2021:887-897.
[7] WEN X T, YANG B, CHEN Y, et al. RuleTris:Minimizingrule update latency for TCAM-based SDN switches[C]//36th IEEE International Conference on Distributed Computing Systems (ICDCS). Nara, Japan, 2016:179-188.
[8] QIU K, YUAN J, ZHAO J, et al. FastRule:Efficient flow entry updates for TCAM-based OpenFlow switches[J]. IEE Journal on Selected Areas in Communications, 2019, 37(3):484-498.
[9] WANG Z J, CHE H, KUMAR M, et al. COPTUA:Consistent policy table update algorithm for TCAM without locking[J]. IEEE Transactions on Computers, 2004, 53(12):1602-1614.
[10] MISHRA T, SAHNI S. Duo-dual TCAM architecture for routing tables with incremental update[C]//IEEE Symposium Computers and Communications (ISCC). Riccione, Italy, 2010:503-508.
[11] VAROL Y L, ROTEM D. An algorithm to generate all topological sorting arrangements[J]. The Computer Journal, 1981, 24(1):83-84.
[12] BRIGHTWELL G, WINKLER P. Counting linear extensions[J]. Order, 1991, 8(3):225-242.
[13] Cypress Semiconductor. CYNSE70256 network search engine[EB/OL]. (2003-12)[2021-09-01]. https://www.digchip.com/datasheets/parts/datasheet/115/CYNSE70256-83BHC.php.
[14] TAYLOR D E, TURNER J S. ClassBench:A packet classification benchmark[J]. IEEE/ACM Transactions on Networking (TON), 2007, 15(3):499-511.
