Network topology emulation and performance evaluation using multiple programmable switches
Li Qifen1, Wang Yangyang2, Li Guanyu2, Wang Ruihao2, Xu Mingwei2
1. School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2. Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing 100084, China
Abstract：[Objective] With the emerging applications of cloud computing and artificial intelligence, traditional network topology structures are no longer suitable for the new traffic pattern. Developing novel network topologies depends on high-fidelity network emulation tools; moreover, traditional network simulators and emulators find it difficult to satisfy the requirements of high-bandwidth and -throughput network scenarios. TurboNet based on programmable switches could achieve high-fidelity network topology emulation, but its application to scenarios where multiple programmable switches are employed for the network topology emulation is difficult due to the physical link bandwidth limitations between different programmable switches. [Methods] To this end, this paper proposes a solution based on a nonlinear integer programming, which can partition the network topology and accommodate the physical link bandwidth constraints, allowing the virtual ports on each subtopology to be mapped using TurboNet on a single programmable switch, thereby enabling the emulation of a large network topology. Herein, a multilevel partitioning algorithm is proposed to further enhance the solver efficiency. The algorithm first utilizes the Metis algorithm to reduce the dimensionality of the input topology, considerably decreasing the size of the topology and enhancing the efficiency of the solver. Additionally, by combining the characteristics of network emulation scenarios, this paper proposes a solution utilizing the match-action table for programmable switches to record the probe forwarding path; as a result, this path is no longer restricted by the restriction of the programmable switch on the packet header length. Specifically, the match-action table would match the current hop number of probes with the corresponding measurement task ID. Subsequently, the existing forwarding port for the corresponding measurement task could be acquired. When sending a new probe, corresponding forwarding table entries need to be added through the control plane based on the probe forwarding path. [Results] The experimental results performed on the Internet Topology Zoo and FatTree reveal that the proposed Metis-based multilevel partition algorithm can effectively improve the solution efficiency of the algorithm. However, due to the limitations of constraint-based methods, for topologies such as FatTree with a small number of switches but a large number of ports, the effect of the multilevel partition algorithm is relatively not evident. The experimental results also demonstrate that the solution for the network telemetry on larger topologies of using the match-action tables on programmable switches to record the probe forwarding paths enables the application of Netview to emulate network topologies on longer forwarding paths. Furthermore, this paper validates the feasibility of the network emulation scheme and performance evaluation with multiple programmable switches on a testbed with two Tofino programmable switches and one server. [Conclusions] By reducing the node dimensionality in the original network topology using the Metis algorithm, the number of constraints in the partitioning problem can be effectively reduced, thereby remarkably enhancing the solution efficiency of the partitioning algorithm. Moreover, the match-action table on programmable switches can be used to record the forwarding paths of the probe, thereby removing the restrictions on the forwarding paths; this solution could be applied to network telemetry on large-scale network topologies.
李其奋, 王旸旸, 李冠宇, 王瑞浩, 徐明伟. 基于多台可编程交换机的网络拓扑仿真与性能评估[J]. 清华大学学报（自然科学版）, 2024, 64(4): 659-667.
Li Qifen, Wang Yangyang, Li Guanyu, Wang Ruihao, Xu Mingwei. Network topology emulation and performance evaluation using multiple programmable switches. Journal of Tsinghua University(Science and Technology), 2024, 64(4): 659-667.
[1] 蒋炜, 钱声攀, 邱奔. 数据中心网络拓扑结构设计策略研究[J]. 中国电信业, 2021(S1): 73-78. JIANG W, QIAN S P, QIU B. Research on design strategies for data center network topology structure[J]. Journal of China Telecommunications Trade, 2021(S1): 73-78. (in Chinese) [2] ISSARIYAKUL T, HOSSAIN E. Introduction to network simulator 2(NS2)[M]//ISSARIYAKUL T, HOSSAIN E. Introduction to Network Simulator NS2. Boston: Springer, 2009. [3] ns-3[EB/OL].[2023-08-01]. https://www.nsnam.org/. [4] BAI J S, BI J, KUANG P, et al. NS4: Enabling programmable data plane simulation[C]//Proceedings of the Symposium on SDN Research. Los Angeles, USA: ACM, 2018: 12. [5] VARGA A, HORNIG R. An overview of the OMNeT++ simulation environment[C]//Proceedings of the 1st international Conference on Simulation Tools and Techniques for Communications, Networks and Systems & Workshops. Marseille France: ICST, 2010. [6] Mininet Team. Mininet: An instant virtual network on your laptop (or other PC)[EB/OL].[2023-08-01]. http://mininet.org. [7] KANNAN P G, SOLTANI A, CHAN M C, et al. BNV: Enabling scalable network experimentation through bare-metal network virtualization[C]//Proceedings of the 11th USENIX Conference on Cyber Security Experimentation and Test. Berkeley, USA: USENIX Association, 2018: 1-8. [8] LIU H H, ZHU Y B, PADHYE J, et al. Crystalnet: Faithfully emulating large production networks[C]//Proceedings of the 26th Symposium on Operating Systems Principles. Shanghai, China: ACM, 2017: 599-613. [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] BERMAN M, CHASE J S, LANDWEBER L, et al. GENI: A federated testbed for innovative network experiments[J]. Computer Networks, 2014, 61: 5-23. [11] 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. [12] 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, 43(4): 99-110. [13] CAO J M, LIU Y, ZHOU Y, et al. TurboNet: Faithfully emulating networks with programmable switches[J]. IEEE/ACM Transactions on Networking, 2022, 30(3): 1395-1409. [14] LIN Y S X, ZHOU Y, LIU Z Z, et al. Netview: Towards on-demand network-wide telemetry in the data center[J]. Computer Networks, 2020, 180: 107386. [15] Menegola B. A study of the k-way graph partitioning problem[D]. Porto Alegre: University of Rio Grande Do Sul, 2012. [16] SUNSHINE C A. Source routing in computer networks[J]. Sunshine, 1977, 7(1): 29-33. [17] Barefoot Networks, Tofino[EB/OL].[2023-08-01]. https://www.barefootnetworks.com/products/brief-tofino/. [18] KARYPIS G, KUMAR V. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices[EB/OL]. (1998-09-20). http://mirror.its.dal.ca/freebsd/distfiles/gmsh/manual.pdf. [19] KNIGHT S, NGUYEN H X, FALKNER N, et al. The internet topology zoo[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(9): 1765-1775. [20] PyMetis[EB/OL].[2023-10-24]. https://pypi.org/project/PyMetis/. [21] SCIP[EB/OL].[2023-10-24]. https://www.scipopt.org/.
2024, Vol. 64 
