Storage compression algorithm for multiprotocol flow tables in software-defined satellite networks
WANG Shuai1, LIU Kai2, YAN Jian2, KUANG Linling2
1. School of Aerospace Engineering, Tsinghua University, Beijing 100084, China; 2. Beijing National Research Center for Information Science and Technology, Beijing 100084, China
Abstract：Multiprotocol packet forwarding in software-defined satellite networks involves large flow tables and expensive storage in onboard devices. A multiprotocol flow table architecture was developed to reduce information storage using a 2-dimensional expanded-field search (2D-EFS) algorithm for the limited resources of satellite networks. The 2D-EFS algorithm generates multiple flow tables by progressively merge fields to compress storage for flow table initialization and flow entry updates. Simulations show that the storage compression efficiency for flow table initialization can reach 86%, which is close to the global optimal and which outperforms existing single-protocol algorithms. The algorithm achieves an average storage compression of 76% for flow entry updates and has the shortest run time and better overall performance than existing single- protocol algorithms.
[1] DU P Y, NAZARI S, MENA J, et al. Multipath TCP in SDN-enabled LEO satellite networks[C]//MILCOM 2016:2016 IEEE Military Communications Conference. Baltimore, USA, 2016:354-359. [2] DU J, GELENBE E, JIANG C X, et al. Contract design for traffic offloading and resource allocation in heterogeneous ultra-dense networks[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(11):2457-2467. [3] DU J, JIANG C X, ZHANG H J, et al. Auction design and analysis for SDN-based traffic offloading in hybrid satellite-terrestrial networks[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(10):2202-2217. [4] XU S, WANG X W, HUANG M. Software-defined next-generation satellite networks:Architecture, challenges, and solutions[J]. IEEE Access, 2018, 6:4027-4041. [5] JIANG C X, GE N, KUANG L L. AI-enabled next-generation communication networks:Intelligent agent and AI router[J]. IEEE Wireless Communications, 2020, 27(6):129-133. [6] 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. [7] GE J G, CHEN Z, WU Y L, et al. H-SOFT:A heuristic storage space optimisation algorithm for flow table of OpenFlow[J]. Concurrency and Computation:Practice and Experience, 2015, 27(13):3497-3509. [8] 鄂跃鹏, 陈智, 葛敬国, 等. 一种高效的OpenFlow流表存储与查找实现方法[J]. 中国科学:信息科学, 2015, 45(10):1280-1288. E Y P, CHEN Z, GE J G, et al. An efficient implementation of storage and lookup for flow tables in OpenFlow[J]. Scientia Sinica Informationis, 2015, 45(10):1280-1288. (in Chinese) [9] 姜腊林, 张亚南, 熊兵. 一种高效的OpenFlow流表拆分压缩算法[J]. 小型微型计算机系统, 2018, 39(2):310-314. JIANG L L, ZHANG Y N, XIONG B. Efficient OpenFlow flow table splitting and compressing algorithm[J]. Journal of Chinese Computer Systems, 2018, 39(2):310-314. (in Chinese) [10] 孙鹏浩, 兰巨龙, 陆肖元, 等. 一种基于匹配域裁剪的包分类规则集压缩方法[J]. 电子与信息学报, 2017, 39(5):1185-1192. SUN P H, LAN J L, LU X Y, et al. Field-trimming compression model for rule set of packet classification[J]. Journal of Electronics & Information Technology, 2017, 39(5):1185-1192. (in Chinese) [11] 王孝龙, 刘勤让, 林森杰, 等. 基于独立规则集位提取的包分类压缩方法[J]. 计算机应用, 2018, 38(8):2375-2380. WANG X L, LIU Q R, LIN S J, et al. Compression method based on bit extraction of independent rule sets for packet classification[J]. Journal of Computer Applications, 2018, 38(8):2375-2380. (in Chinese) [12] ZHANG C Q, SUN P H, HU G W, et al. RETCAM:An efficient TCAM compression model for flow table of OpenFlow[J]. Journal of Communications and Networks, 2020, 22(6):484-492. [13] 刘中金, 李勇, 苏厉, 等. TCAM存储高效的OpenFlow多级流表映射机制[J]. 清华大学学报(自然科学版), 2014, 54(4):437-442. LIU Z J, LI Y, SU L, et al. TCAM-efficient flow table mapping scheme for OpenFlow multiple-table pipelines[J]. Journal of Tsinghua University (Science and Technology), 2014, 54(4):437-442. (in Chinese) [14] 史少平, 庄雷, 马丁, 等. 平衡时空的自适应多级流表构建方法[J]. 计算机工程与设计, 2017, 38(3):830-836. SHI S P, ZHUANG L, MA D, et al. Adaptive method balancing time and space for multiple-table construction[J]. Computer Engineering and Design, 2017, 38(3):830-836. (in Chinese) [15] 郑凌, 邱智亮, 孙士勇, 等. 软件定义网络中一种两步式多级流表构建算法[J]. 西安电子科技大学学报(自然科学版), 2018, 45(5):25-31. ZHENG L, QIU Z L, SUN S Y, et al. Two-step multiple flow table construction algorithm in the software-defined network[J]. Journal of Xidian University (Natural Science), 2018, 45(5):25-31. (in Chinese) [16] BOSSHART P, GIBB G, KIM H S, et al. Forwarding metamorphosis:Fast programmable match-action processing in hardware for SDN[C]//Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM. Hong Kong, China, 2013:99-110. [17] 晏坚, 王帅, 靳瑾, 等. 软件定义网络多协议区分流表构建方法和系统:CN202010270401.4[P]. 2020-11-13. YAN J, WANG S, JIN J, et al. Method and system for constructing software-defined network multi-protocol division table:CN202010270401.4[P]. 2020-11-13. (in Chinese) [18] 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. Vancouver, Canada, 1998:191-202. [19] LI J, LIU H Y, SOLLINS K. AFBV:A scalable packet classification algorithm[J]. ACM SIGCOMM Computer Communication Review, 2002, 32(3):24. [20] MATOUŠEK J, ANTICHI G, LU AČG ANSKÝ A, et al. ClassBench-ng:Recasting ClassBench after a decade of network evolution[C]//2017 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS). Beijing, China, 2017:204-216. [21] JIANG W R. Scalable ternary content addressable memory implementation using FPGAs[C]//Architectures for Networking and Communications Systems. San Jose, USA, 2013:71-82.
2022, Vol. 62 
