{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:11:19Z","timestamp":1760134279629,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"23","license":[{"start":{"date-parts":[[2023,11,23]],"date-time":"2023-11-23T00:00:00Z","timestamp":1700697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In software-defined networking (SDN), the traffic forwarding delay highly depends on the latency associated with updating the forwarding rules in flow tables. With the increase in fine-grained flow control requirements, due to the flexible control capabilities of SDN, more rules are being inserted and removed from flow tables. Moreover, the matching fields of these rules might overlap since multiple control domains might generate different rules for similar flows. This overlap implies dependency relationships among the rules, imposing various restrictions on forwarding entries during updates, e.g., by following update orders or storing entries at specified locations, especially in flow tables implemented using ternary content addressable memory (TCAM); otherwise, mismatching or packet dropping will occur. It usually takes a while to resolve and maintain dependencies during updates, which hinders high forwarding efficiency. To reduce the delay associated with updating dependent rules, in this paper, we propose an updating algorithm for TCAM-based flow tables. We formulate the TCAM maintenance process as an NP-hard problem and analyze the inefficiency of existing moving approaches. To solve the problem, we propose an optimal moving chain for single rule updates and provide theoretical proof for its minimum moving steps. For multiple rules arriving at a switch simultaneously, we designed a dynamic approach to update concurrent entries; it is able to update multiple rules heuristically within a restricted TCAM region. As the update efficiency concerns dependencies among rules, we evaluate our flow table by updating algorithms with different dependency complexities. The results show that our approach achieves about 6% fewer moving steps than existing approaches. The advantage is more pronounced when the flow table is heavily utilized and rules have longer dependency chains.<\/jats:p>","DOI":"10.3390\/s23239375","type":"journal-article","created":{"date-parts":[[2023,11,24]],"date-time":"2023-11-24T03:54:35Z","timestamp":1700798075000},"page":"9375","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Reducing Flow Table Update Costs in Software-Defined Networking"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-4788-0475","authenticated-orcid":false,"given":"Wen","family":"Wang","sequence":"first","affiliation":[{"name":"Academy of Military Sciences, Beijing 100141, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lin","family":"Yang","sequence":"additional","affiliation":[{"name":"Academy of Military Sciences, Beijing 100141, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiongjun","family":"Yang","sequence":"additional","affiliation":[{"name":"Academy of Military Sciences, Beijing 100141, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingchao","family":"Wang","sequence":"additional","affiliation":[{"name":"Academy of Military Sciences, Beijing 100141, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,11,23]]},"reference":[{"key":"ref_1","first-page":"437","article-title":"TCAM-efficient flow table mapping scheme for OpenFlow multiple-table pipelines","volume":"54","author":"Liu","year":"2014","journal-title":"J. Tsinghua Univ. Technol."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Curtis, A.R., Mogul, J.C., Tourrilhes, J., Yalagandula, P., Sharma, P., and Banerjee, S. (2011, January 15\u201319). DevoFlow: Scaling Flow Management for High-Performance Networks. Proceedings of the ACM SIGCOMM 2011 Conference, Toronto, ON, Canada.","DOI":"10.1145\/2018436.2018466"},{"key":"ref_3","unstructured":"Mahajan, R., Ming, Z., Kandula, S., Liu, H., and Xin, J. (2014, January 17\u201322). Dynamic scheduling of network updates. Proceedings of the 2014 ACM SIGCOMM Workshop on Capacity Sharing Workshop, Chicago, IL, USA."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1109\/JSSC.2005.864128","article-title":"Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey","volume":"41","author":"Pagiamtzis","year":"2006","journal-title":"IEEE J. Solid-State Circuits"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1109\/JSAC.2019.2894235","article-title":"FastRule: Efficient Flow Entry Updates for TCAM-Based OpenFlow Switches","volume":"37","author":"Qiu","year":"2019","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Wen, X., Diao, C., Zhao, X., Chen, Y., Li, L.E., Yang, B., and Bo, K. (2014, January 22). Compiling minimum incremental update for modular SDN languages. Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, Chicago, IL, USA.","DOI":"10.1145\/2620728.2620733"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Wen, X., Yang, B., Chen, Y., Li, L.E., Bu, K., Zheng, P., Yang, Y., and Hu, C. (2016, January 27\u201330). RuleTris: Minimizing Rule Update Latency for TCAM-based SDN Switches. Proceedings of the 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS), Nara, Japan.","DOI":"10.1109\/ICDCS.2016.41"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1109\/JPROC.2014.2371999","article-title":"Software-Defined Networking: A Comprehensive Survey","volume":"103","author":"Kreutz","year":"2015","journal-title":"Proc. IEEE"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Wang, D., Li, Q., Jiang, Y., Xu, M., and Hu, G. (August, January 31). Balancer: A Traffic-Aware Hybrid Rule Allocation Scheme in Software Defined Networks. Proceedings of the 2017 26th International Conference on Computer Communication and Networks (ICCCN), Vancouver, BC, Canada.","DOI":"10.1109\/ICCCN.2017.8038395"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1109\/40.903060","article-title":"Fast updating algorithms for TCAM","volume":"21","author":"Shah","year":"2001","journal-title":"IEEE Micro"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Wang, W., He, W., Su, J., and Chen, Y. (2016, January 10\u201314). Cupid: Congestion-free consistent data plane update in software defined networks. Proceedings of the 35th Annual IEEE International Conference on Computer Communications, San Francisco, CA, USA.","DOI":"10.1109\/INFOCOM.2016.7524420"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"He, X., Zheng, J., Dai, H., Zhang, C., Rafique, W., Li, G., Dou, W., and Ni, Q. (2020, January 6\u20139). Coeus: Consistent and Continuous Network Update in Software-Defined Networks. Proceedings of the IEEE International Conference on Computer Communications, Virtual Conference.","DOI":"10.1109\/INFOCOM41043.2020.9155392"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2693","DOI":"10.1109\/TNET.2021.3098320","article-title":"T-Cache: Efficient Policy-Based Forwarding Using Small TCAM","volume":"29","author":"Wan","year":"2021","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Vissicchio, S., and Cittadini, L. (2016, January 10\u201314). FLIP the (Flow) table: Fast lightweight policy-preserving SDN updates. Proceedings of the IEEE INFOCOM 2016-the 35th Annual IEEE International Conference on Computer Communications, San Francisco, CA, USA.","DOI":"10.1109\/INFOCOM.2016.7524419"},{"key":"ref_15","unstructured":"Xin, J., Gossels, J., Rexford, J., and Walker, D. (2015, January 4\u20136). CoVisor: A Compositional Hypervisor for Software-Defined Networks. Proceedings of the 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI 15), Oakland, CA, USA."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1109\/TST.2016.7442502","article-title":"HBD: Towards efficient reactive rule dispatching in software-defined networks","volume":"21","author":"Chen","year":"2016","journal-title":"Tsinghua Sci. Technol."},{"key":"ref_17","unstructured":"Bo, Y., Yang, X., Xing, H., Kang, X., and Chao, H.J. (2014, January 22). CAB: A reactive wildcard rule caching system for software-defined networks. Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, Chicago, IL, USA."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Sanabria-Russo, L., Alonso-Zarate, J., and Verikoukis, C. (2018, January 9\u201313). SDN-Based Pro-Active Flow Installation Mechanism for Delay Reduction in IoT. Proceedings of the Global Communications Conference, Abu Dhabi, United Arab Emirates.","DOI":"10.1109\/GLOCOM.2018.8647382"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cai, Y.Z., Wang, Y.T., and Tsai, M.H. (2021). Dynamic adjustment for proactive flow installation mechanism in SDN-based IoT. Comput. Netw., 194.","DOI":"10.1016\/j.comnet.2021.108167"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Xu, J., Wang, L., Song, C., and Xu, Z. (2018, January 25\u201328). Proactive Mitigation to Table-Overflow in Software-Defined Networking. Proceedings of the IEEE Symposium on Computers and Communications, Natal, Brazil.","DOI":"10.1109\/ISCC.2018.8538670"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1547","DOI":"10.1007\/s10922-020-09550-z","article-title":"PARD: Hybrid Proactive and Reactive Method Eliminating Flow Setup Latency in SDN","volume":"28","author":"Rzepka","year":"2020","journal-title":"J. Netw. Syst. Manag."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Li, R., Pang, Y., Zhao, J., and Wang, X. (2019, January 5\u20138). A Tale of Two (Flow) Tables: Demystifying Rule Caching in OpenFlow Switches. Proceedings of the 48th International Conference on Parallel Processing, Kyoto, Japan.","DOI":"10.1145\/3337821.3337896"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Yang, J., Li, T., Yan, J., Li, J., and Wang, B. (2020). PipeCache: High Hit Rate Rule-Caching Scheme Based on Multi-Stage Cache Tables. Electronics, 9.","DOI":"10.3390\/electronics9060999"},{"key":"ref_24","unstructured":"Li, X., and Xie, W. (2017, January 3\u20136). CRAFT: A Cache Reduction Architecture for Flow Tables in Software-Defined Networks. Proceedings of the 2017 IEEE Symposium on Computers and Communications, Heraklion, Greece."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1109\/TNSM.2016.2530687","article-title":"Wildcard Rules Caching and Cache Replacement Algorithms in Software-Defined Networking","volume":"13","author":"Sheu","year":"2016","journal-title":"IEEE Trans. Netw. Serv. Manag."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Katta, N., Alipourfard, O., Rexford, J., and Walker, D. (2016, January 14\u201315). Cacheflow: Dependency-aware rule-caching for software-defined networks. Proceedings of the Symposium on SDN Research, SOSR 2016, Santa Clara, CA, USA.","DOI":"10.1145\/2890955.2890969"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3409109","article-title":"A TCAM-based Caching Architecture Framework for Packet Classification","volume":"20","author":"Srinivasavarma","year":"2020","journal-title":"Acm Trans. Embed. Comput. Syst."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Schneider, T., Birkner, R., and Vanbever, L. (2021, January 23\u201327). Snowcap: Synthesizing Network-Wide Configuration Updates. Proceedings of the 2021 ACM SIGCOMM 2021 Conference, Virtual Event.","DOI":"10.1145\/3452296.3472915"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Schmid, S., Schrenk, B.C., and Torralba, \u00c1. (2022, January 13\u201316). NetStack: A Game Approach to Synthesizing Consistent Network Updates. Proceedings of the IFIP International Conference on Networking, Catania, Italy.","DOI":"10.23919\/IFIPNetworking55013.2022.9829770"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Johansen, N.S., K\u00e6r, L.B., Madsen, A.L., Nielsen, K.\u00d8., Srba,, J., and Tollund, R.G. (2022, January 7\u201310). Kaki: Concurrent Update Synthesis for Regular Policies via Petri Games. Proceedings of the 17th International Conference on Integrated Formal Methods, Lugano, Switzerland.","DOI":"10.1007\/978-3-031-07727-2_14"},{"key":"ref_31","unstructured":"Cormen, T.H. (2009). Introduction to Algorithms, MIT Press."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/23\/9375\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:28:47Z","timestamp":1760131727000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/23\/9375"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,23]]},"references-count":31,"journal-issue":{"issue":"23","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["s23239375"],"URL":"https:\/\/doi.org\/10.3390\/s23239375","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2023,11,23]]}}}