Abstract
Virtualization is a promising technology to enhance the scalability and utilization of data centers for managing, developing, and operating network functions. Furthermore, it allows to flexibly place and execute virtual networks and machines on physical hardware. The problem of mapping a virtual network to physical resources, however, is known to be \(\mathcal {NP}\)-hard and is often tackled by optimization techniques, e.g., by (ILP). On the one hand, highly tailored approaches based on heuristics significantly reduce the search space of the problem for specific environments and constraints, which, however, are difficult to transfer to other scenarios. On the other hand, ILP-based solutions are highly customizable and correct by construction with a huge search space. To mitigate search space problems while still guaranteeing correctness, we propose a combination of model transformation and ILP techniques. This combination is highly customizable and extensible in order to support multiple network domains, environments, and constraints allowing for rapid prototyping in different settings of virtualization tasks. Our experimental evaluation, finally, confirms that model transformation reduces the size of the optimization problem significantly and consequently the required runtime while still retaining the quality of mappings.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Amaldi, E., Coniglio, S., Koster, A.M.C.A., Tieves, M.: On the computational complexity of the virtual network embedding problem. Electron. Notes Discrete Math. 52, 213–220 (2016)
Fischer, A., Botero, J.F., Beck, M.T., de Meer, H., Hesselbach, X.: Virtual network embedding: a survey. Commun. Surv. Tutorials 15(4), 1888–1906 (2013)
Ballani, H., Costa, P., Karagiannis, T., Rowstron, A.I.T.: Towards predictable datacenter networks. In: Conference on Applications, pp. 242–253 (2011)
Guo, C., Lu, G., Wang, H.J., Yang, S., Kong, C., Sun, P., Wu, W., Zhang, Y.: SecondNet: a data center network virtualization architecture with bandwidth guarantees. In: Proceedings of the 6th International Conference, pp. 15:1–15:12 (2010)
Zeng, D., Guo, S., Huang, H., Yu, S., Leung, V.C.: Optimal VM placement in data centers with architectural and resource constraints. Int. J. Auton. Adapt. Commun. Syst. 8(4), 392–406 (2015)
Yang, Z., Guo, Y.: An exact virtual network embedding algorithm based on integer linear programming for virtual network request with location constraint. China Commun. 13(8), 177–183 (2016)
Tomaszek, S., Leblebici, E., Wang, L., Schürr, A.: Model-driven development of virtual network embedding algorithms with model transformation and linear optimization techniques. In: Modellierung 2018, pp. 39–54 (2018)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1999)
Sahhaf, S., Tavernier, W., Rost, M., Schmid, S., Colle, D., Pickavet, M., Demeester, P.: Network service chaining with optimized network function embedding supporting service decompositions. Comput. Netw. 93, 492–505 (2015)
Schürr, A.: Specification of graph translators with triple graph grammars. In: Graph-Theoretic Concepts in Computer Science, pp. 151–163 (1994)
Gurobi Optimization, Inc.: Gurobi Optimizer Reference Manual 2015 (2016)
Leblebici, E., Anjorin, A., Schürr, A.: Inter-model consistency checking using triple graph grammars and linear optimization techniques. In: Fundamental Approaches to Software Engineering, pp. 191–207 (2017)
Bari, M.F., Boutaba, R., Esteves, R.P., Granville, L.Z., Podlesny, M., Rabbani, M.G., Zhang, Q., Zhani, M.F.: Data center network virtualization: a survey. Commun. Surv. Tutorials 15(2), 909–928 (2013)
Pohlmann, U., Hüwe, M.: Model-driven allocation engineering (T). In: International Conference on Automated Software Engineering, pp. 374–384 (2015)
Lopes, F.A., Lima, L., Santos, M., Fidalgo, R., Fernandes, S.: High-level modeling and application validation for SDN. In: Network Operations and Management Symposium, pp. 197–205 (2016)
Kluge, R., Stein, M., Varró, G., Schürr, A., Hollick, M., Mühlhäuser, M.: A systematic approach to constructing incremental topology control algorithms using graph transformation. J. Vis. Lang. Comput. 38, 47–83 (2017)
Fleck, M., Troya, J., Wimmer, M.: Marrying search-based optimization and model transformation technology. In: Proceedings of NasBASE (2015)
Kessentini, M., Sahraoui, H., Boukadoum, M.: Model transformation as an optimization problem. In: Czarnecki, K., Ober, I., Bruel, J.-M., Uhl, A., Völter, M. (eds.) MODELS 2008. LNCS, vol. 5301, pp. 159–173. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87875-9_12
Acknowledgement
This work has been funded by the German Federal Ministry of Education and Research within the Software Campus project GraTraM at TU Darmstadt, funding code 01IS12054, and by the German Research Foundation (DFG) as part of project A1 within CRC 1053–MAKI.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Tomaszek, S., Leblebici, E., Wang, L., Schürr, A. (2018). Virtual Network Embedding: Reducing the Search Space by Model Transformation Techniques. In: Rensink, A., Sánchez Cuadrado, J. (eds) Theory and Practice of Model Transformation. ICMT 2018. Lecture Notes in Computer Science(), vol 10888. Springer, Cham. https://doi.org/10.1007/978-3-319-93317-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-93317-7_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-93316-0
Online ISBN: 978-3-319-93317-7
eBook Packages: Computer ScienceComputer Science (R0)