Improving the Scalability of Distributed Network Emulations: An Algorithmic Perspective
Authors: 
Huaiyi Zhao, Xinyi Zhang, Yang Wang, Zulong Diao, Yanbiao Li, Gaogang XieAuthors Info & Claims
Pages 4325 - 4339
Abstract
By deploying virtualized network elements (hosts, switches, routers, links, etc.) on clusters of commodity machines, distributed network emulations (DNE) closely mimic the behaviors of network systems and provide real-time interactions and analysis for network service management. However, DNE encounters scalability challenges when faced with large network topologies. These challenges can be boiled down to the assignment problem: to which physical machine each virtualized network element should be assigned so that the largest possible network topology can be emulated? In this paper, we tackle this problem from an algorithmic perspective. We first propose TBR (topology balancing relaxation) as the relaxation of the assignment problem. TBR tries to maintain a balance of the hardware resource consumption, by minimizing the maximum inter-machine bandwidth. We further develop TBS (topology balancing solver), which combines mathematical techniques with multi-level algorithms to solve TBR efficiently. We integrate TBR and TBS into MaxiNet, a famous distributed network emulator. Experimental results show that with the same available physical resources, TBR and TBS can improve emulation scalability by up to <inline-formula> <tex-math notation="LaTeX">$4.7\times $ </tex-math></inline-formula> compared to baselines.
References
[1]
“ns-3.” 2021. [Online]. Available: https://www.nsnam.org
[2]
“OpNet network simulator.” 2021. [Online]. Available: https://opnetprojects.com/opnet-network-simulator/
[3]
“Tetcos: Netsim—Network simulation software, India.” 2021. [Online]. Available: https://www.tetcos.com
[4]
Q. Zhang, K. K. W. Ng, C. Kazer, S. Yan, J. A. Sedoc, and V. Liu, “MimicNet: Fast performance estimates for data center networks with machine learning,” in Proc. ACM SIGCOMM Conf., 2021, pp. 287–304. [Online]. Available: https://doi.org/10.1145/3452296.3472926
[5]
Q. Yanget al., “DeepQueueNet: Towards scalable and generalized network performance estimation with packet-level visibility,” in Proc. ACM SIGCOMM Conf., 2022, pp. 441–457. [Online]. Available: https://doi.org/10.1145/3544216.3544248
[6]
P. Wette, M. Dräxler, and A. Schwabe, “MaxiNet: Distributed emulation of software-defined networks,” in Proc. IFIP Netw. Conf. IFIP Netw., 2014, pp. 1–9.
[7]
M. Zec, “Implementing a clonable network stack in the freebsd kernel,” in Proc. USENIX Annu. Techn. Conf., 2003, pp. 137–150. [Online]. Available: https://www.usenix.org/event/usenix03/tech/freenix03/full_papers/zec/zec_html/
[8]
A. Vahdatet al., “Scalability and accuracy in a large-scale network emulator,” ACM SIGOPS Oper. Syst. Rev., vol. 36, no. S1, pp. 271–284, 2002.
[9]
M. Hibleret al., “Large-scale virtualization in the Emulab network testbed,” in Proc. USENIX Annu. Techn. Conf. USENIX, 2008, pp. 113–128.
[10]
B. Lantz, B. Heller, and N. McKeown, “A network in a laptop: Rapid prototyping for software-defined networks,” in Proc. 9th ACM SIGCOMM Workshop Hot Topics Netw. (Hotnets), Oct. 2010, pp. 1–6. [Online]. Available: https://doi.org/10.1145/1868447.1868466
[11]
M. Scazzariello, L. Ariemma, and T. Caiazzi, “Kathará: A lightweight network emulation system,” in Proc. IEEE/IFIP Netw. Oper. Manag. Symp. (NOMS), 2020, pp. 1–2.
[12]
R. I. Dinita, G. Wilson, A. Winckles, M. Cirstea, and A. Jones, “A cloud-based virtual computing laboratory for teaching computer networks,” in Proc. IEEE 13th Int. Conf. Optim. Elect. Electron. Equip. (OPTIM), 2012, pp. 1314–1318.
[13]
T. Holterbach, T. Bühler, T. Rellstab, and L. Vanbever, “An open platform to teach how the Internet practically works,” ACM SIGCOMM Comput. Commun. Rev., vol. 50, no. 2, pp. 45–52, 2020.
[14]
D. Dobrilović and B. Odadžić, “Virtualization technology as a tool for teaching computer networks,” Int. J. Soc. Sci., vol. 1, no. 2, pp. 138–142, 2006.
[15]
K. Yocum, E. Eade, J. Degesys, D. Becker, J. Chase, and A. Vahdat, “Toward scaling network emulation using topology partitioning,” in Proc. 11th IEEE/ACM Int. Symp. Model. Anal. Simulat. Comput. Telecommun. Syst. (MASCOTS), Oct. 2003, pp. 242–245.
[16]
A. Fischer, J. F. Botero, M. T. Beck, H. de Meer, and X. Hesselbach, “Virtual network embedding: A survey,” IEEE Commun. Surveys Tuts., vol. 15, no. 4, pp. 1888–1906, 4th Quart., 2013.
[17]
H. Cao, S. Wu, Y. Hu, Y. Liu, and L. Yang, “A survey of embedding algorithm for virtual network embedding,” China Commun., vol. 16, no. 12, pp. 1–33, Dec. 2019.
[18]
J. Inführ and G. R. Raidl, “Introducing the virtual network mapping problem with delay, routing and location constraints,” in Proc. 5th Int. Conf. Netw. Optim. (INOC), Hamburg, Germany, Jun. 2011.
[19]
W. Liu, Y. Xiang, S. Ma, and X. Tang, “Completing virtual network embedding all in one mathematical programming,” in Proc. Int. Conf. Electron. Commun. Control (ICECC), Sep. 2011, pp. 183–185.
[20]
N. Shahriaret al., “Virtual network survivability through joint spare capacity allocation and embedding,” IEEE J. Sel. Areas Commun., vol. 36, no. 3, pp. 502–518, Mar. 2018.
[21]
M. Chowdhury, M. R. Rahman, and R. Boutaba, “ViNEYard: Virtual network embedding algorithms with coordinated node and link mapping,” IEEE/ACM Trans. Netw., vol. 20, no. 1, pp. 206–219, Feb. 2012.
[22]
X. Chenget al., “Virtual network embedding through topology-aware node ranking,” ACM SIGCOMM Comput. Commun. Rev., vol. 41, no. 2, pp. 38–47, Apr. 2011.
[23]
O. Soualah, I. Fajjari, N. Aitsaadi, and A. Mellouk, “A reliable virtual network embedding algorithm based on game theory within cloud’s backbone,” in Proc. IEEE Int. Conf. Commun. (ICC), Jun. 2014, pp. 2975–2981.
[24]
Z. Zhang, X. Cheng, S. Su, Y. Wang, K. Shuang, and Y. Luo, “A unified enhanced particle swarm optimization-based virtual network embedding algorithm,” Int. J. Commun. Syst., vol. 26, no. 8, pp. 1054–1073, 2013.
[25]
C. Yu, Q. Lian, D. Zhang, and C. Wu, “PAME: Evolutionary membrane computing for virtual network embedding,” J. Parallel Distrib. Comput., vol. 111, pp. 136–151, Jan. 2018.
[26]
S. Haeri and L. Trajković, “Virtual network embedding via Monte Carlo tree search,” IEEE Trans. Cybern., vol. 48, no. 2, pp. 510–521, Feb. 2018.
[27]
Z. Yan, J. Ge, Y. Wu, L. Li, and T. Li, “Automatic virtual network embedding: A deep reinforcement learning approach with graph convolutional networks,” IEEE J. Sel. Areas Commun., vol. 38, no. 6, pp. 1040–1057, Jun. 2020.
[28]
S. Yang, F. Li, S. Trajanovski, R. Yahyapour, and X. Fu, “Recent advances of resource allocation in network function virtualization,” IEEE Trans. Parallel Distrib. Syst., vol. 32, no. 2, pp. 295–314, Feb. 2021.
[29]
J. G. Herrera and J. F. Botero, “Resource allocation in NFV: A comprehensive survey,” IEEE Trans. Netw. Service Manag., vol. 13, no. 3, pp. 518–532, Sep. 2016.
[30]
I. Afolabi, T. Taleb, K. Samdanis, A. Ksentini, and H. Flinck, “Network slicing and softwarization: A survey on principles, enabling technologies, and solutions,” IEEE Commun. Surveys Tuts., vol. 20, no. 3, pp. 2429–2453, 3rd Quart., 2018.
[31]
M. C. Luizelli, L. R. Bays, L. S. Buriol, M. P. Barcellos, and L. P. Gaspary, “Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions,” in Proc. IFIP/IEEE Int. Symp. Integr. Netw. Manag. (IM), May 2015, pp. 98–106.
[32]
I. Jang, D. Suh, S. Pack, and G. Dán, “Joint optimization of service function placement and flow distribution for service function chaining,” IEEE J. Sel. Areas Commun., vol. 35, no. 11, pp. 2532–2541, Nov. 2017.
[33]
P. K. Thiruvasagam, V. J. Kotagi, and C. S. R. Murthy, “A reliability-aware, delay guaranteed, and resource efficient placement of service function chains in softwarized 5G networks,” IEEE Trans. Cloud Comput., vol. 10, no. 3, pp. 1515–1531, Jul. 2022.
[34]
S. Khebbache, M. Hadji, and D. Zeghlache, “Scalable and cost-efficient algorithms for VNF chaining and placement problem,” in Proc. 20th Conf. Innov. Clouds Internet Netw. (ICIN), Mar. 2017, pp. 92–99.
[35]
M. M. Tajiki, S. Salsano, L. Chiaraviglio, M. Shojafar, and B. Akbari, “Joint energy efficient and QoS-aware path allocation and VNF placement for service function chaining,” IEEE Trans. Netw. Service Manag., vol. 16, no. 1, pp. 374–388, Mar. 2019.
[36]
P. T. A. Quang, Y. Hadjadj-Aoul, and A. Outtagarts, “A deep reinforcement learning approach for VNF forwarding graph embedding,” IEEE Trans. Netw. Service Manag., vol. 16, no. 4, pp. 1318–1331, Dec. 2019.
[37]
Y. Xieet al., “Virtualized network function forwarding graph placing in SDN and NFV-enabled IoT networks: A graph neural network assisted deep reinforcement learning method,” IEEE Trans. Netw. Service Manag., vol. 19, no. 1, pp. 524–537, Mar. 2022.
[38]
B. Pfaffet al., “The design and implementation of open vSwitch,” in Proc. 12th {USENIX} Symp. Netw. Syst. Design Implement. ({NSDI}), 2015, pp. 117–130.
[39]
D. Gupta, K. Yocum, M. McNett, A. C. Snoeren, A. Vahdat, and G. M. Voelker, “To infinity and beyond: Time warped network emulation,” in Proc. 20th ACM Symp. Oper. Syst. Principles (SOSP), Oct. 2005, pp. 1–2. [Online]. Available: https://doi.org/10.1145/1095810.1118605
[40]
H. W. Lee, M. L. Sichitiu, and D. Thuente, “NEAT: Network link emulation with adaptive time dilation,” J. Parallel Distrib. Comput., vol. 104, pp. 88–98, Jun. 2017. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0743731517300199
[41]
Y. Dong, X. Yang, J. Li, G. Liao, K. Tian, and H. Guan, “High performance network virtualization with SR-IoV,” J. Parallel Distrib. Comput., vol. 72, no. 11, pp. 1471–1480, 2012.
[42]
“Open vSwitch hardware offloading.” 2021. [Online]. Available: https://docs.openstack.org/neutron/queens/admin/config-ovs-offload.html
[43]
A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz, Recent Advances in Graph Partitioning [LNCS 9220 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)]. Cham, Switzerland: Springer Int., Nov. 2016, pp. 117–158.
[44]
G. Karypis and V. Kumar, “METIS—Unstructured graph partitioning and sparse matrix ordering system, version 2.0,” Dept. Comput. Sci., Univ. Minnesota, Minneapolis, MN, USA, Rep. DAAH04-95-C-0008, 1995.
[45]
A. Valejo, V. Ferreira, R. Fabbri, M. C. F. D. Oliveira, and A. D. A. Lopes, “A critical survey of the multilevel method in complex networks,” ACM Comput. Surveys, vol. 53, no. 2, pp. 1–35, Jul. 2020. [Online]. Available: https://dl.acm.org/doi/10.1145/3379347
[46]
“Diagonally dominant matrix.” 2021. [Online]. Available: https://en.wikipedia.org/wiki/Diagonally_dominant_matrix
[47]
A. Land and A. Doig, “An automatic method of solving discrete programming problems,” Econometrica, vol. 28, no. 3, pp. 497–520, 1960.
[48]
H. Marchand, A. Martin, R. Weismantel, and L. Wolsey, “Cutting planes in integer and mixed integer programming,” Discr. Appl. Math., vol. 123, no. 1, pp. 397–446, Nov. 2002. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0166218X01003481
[49]
J. E. Mitchell, “Branch-and-cut algorithms for combinatorial optimization problems,” in Handbook of Applied Optimization, vol. 1. Oxford, U.K.: Oxford Univ. Press, 2002, pp. 65–77.
[50]
C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. Savelsbergh, and P. H. Vance, “Branch-and-price: Column generation for solving huge integer programs,” Oper. Res., vol. 46, no. 3, pp. 316–329, 1998.
[51]
“Mixed-integer programming (MIP)—A primer on the basics.” 2019. [Online]. Available: https://www.gurobi.com/resource/mip-basics/
[52]
“MIP gurobi documents.” 2021. [Online]. Available: https://co-at-work.zib.de/berlin2015/files/Gurobi_MIP.pdf
[53]
U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Phys. Rev. E, Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top., vol. 76, no. 3, 2007, Art. no.
[54]
H. Meyerhenke, P. Sanders, and C. Schulz, “Partitioning complex networks via size-constrained clustering,” in Proc. Int. Symp. Exp. Algorithms, 2014, pp. 351–363.
[55]
“Scale-free network.” 2021. [Online]. Available: https://en.wikipedia.org/wiki/Scale-free_network
[56]
A. Elmokashfi, A. Kvalbein, and C. Dovrolis, “On the scalability of BGP: The role of topology growth,” IEEE J. Sel. Areas Commun., vol. 28, no. 8, pp. 1250–1261, Oct. 2010.
[57]
“Network science book.” 2022. [Online]. Available: https://networksciencebook.com/
[58]
M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable, commodity data center network architecture,” ACM SIGCOMM Comput. Commun. Rev., vol. 38, no. 4, pp. 63–74, 2008.
[59]
“Gurobi—The fastest solver.” 2019. [Online]. Available: https://www.gurobi.com
[60]
N. Handigol, B. Heller, V. Jeyakumar, B. Lantz, and N. McKeown, “Reproducible network experiments using container-based emulation,” in Proc. 8th Int. Conf. Emerg. Netw. Exp. Technol. (CoNEXT), Dec. 2012, pp. 253–264. [Online]. Available: https://doi.org/10.1145/2413176.2413206
[61]
M. Zhou, O. Sahni, K. D. Devine, M. S. Shephard, and K. E. Jansen, “Controlling unstructured mesh partitions for massively parallel simulations,” SIAM J. Sci. Comput., vol. 32, no. 6, pp. 3201–3227, 2010.
[62]
A. B. Kahng, J. Lienig, I. L. Markov, and J. Hu, VLSI Physical Design: From Graph Partitioning to Timing Closure. Dordrecht, The Netherlands: Springer, 2011.
[63]
R. H. Möhring, H. Schilling, B. Schütz, D. Wagner, and T. Willhalm, “Partitioning graphs to speedup Dijkstra’s algorithm,” J. Exp. Algorithmics, vol. 11, pp. 2–8, Feb. 2007.
[64]
G. Karypis, “METIS: Unstructured graph partitioning and sparse matrix ordering system,” Dept. Comput. Sci., Univ. Minnesota, Minneapolis, MN, USA, Rep., 1997.
[65]
B. Hendrickson and R. Leland. “Chaco: Software for partitioning graphs.” 2012. [Online]. Available: https://www.cs.sandia.gov/bahendr/chaco.html
[66]
C. Chevalier and F. Pellegrini, “PT-scotch: A tool for efficient parallel graph ordering,” Parallel Comput., vol. 34, nos. 6–8, pp. 318–331, 2008.
[67]
Y. Yuan, Z. Tian, C. Wang, F. Zheng, and Y. Lv, “A Q-learning-based approach for virtual network embedding in data center,” Neural Comput. Appl., vol. 32, no. 7, pp. 1995–2004, Apr. 2020.
[68]
S. Khebbache, M. Hadji, and D. Zeghlache, “A multi-objective non-dominated sorting genetic algorithm for VNF chains placement,” in Proc. 15th IEEE Annu. Consum. Commun. Netw. Conf. (CCNC), Jan. 2018, pp. 1–4.
[69]
J. Cao, Y. Zhang, W. An, X. Chen, J. Sun, and Y. Han, “VNF-FG design and VNF placement for 5G mobile networks,” Sci. China Inf. Sci., vol. 60, no. 4, Mar. 2017, Art. no.
[70]
C. A. Ouedraogo, S. Medjiah, C. Chassot, K. Drira, and J. Aguilar, “A cost-effective approach for end-to-end QoS management in NFV-enabled IoT platforms,” IEEE Internet Things J., vol. 8, no. 5, pp. 3885–3903, Mar. 2021.
Index Terms
- Improving the Scalability of Distributed Network Emulations: An Algorithmic Perspective
Index terms have been assigned to the content through auto-classification.
Recommendations
Improving Scalability of Network Emulation through Parallelism and Abstraction
ANSS '05: Proceedings of the 38th annual Symposium on SimulationOne approach to network emulation involves simulating a virtual network with a real-time network simulator and providing an I/O interface that enables interaction between real hosts and the virtual network. This allows real protocols and applications to ...
A Virtual Time System for OpenVZ-Based Network Emulations
PADS '11: Proceedings of the 2011 IEEE Workshop on Principles of Advanced and Distributed SimulationSimulation and emulation are commonly used to study the behavior of communication networks, owing to the cost and complexity of exploring new ideas on actual networks. Emula-tions executing real code have high functional fidelity, but may not have high ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1932-4537 © 2023 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 16 June 2023
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in