Abstract
Network function virtualization (NFV) is a newly proposed technique designed to construct and manage network functions dynamically and efficiently. Allocating physical resources to the virtual network function forwarding graph is a critical issue in NFV. We formulate the forwarding graph embedding (FGE) problem as a binary integer programming problem, which aims to increase the revenue and decrease the cost to a service provider (SP) while considering limited network resources and the requirements of virtual functions. We then design a novel regional resource clustering metric to quantify the embedding potential of each substrate node and propose a topology-aware FGE algorithm called ‘regional resource clustering FGE’ (RRC-FGE). After implementing our algorithms in C++, simulation results showed that the total revenue was increased by more than 50 units and the acceptance ratio by more than 15%, and the cost of the service provider was decreased by more than 60 units.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bellavista, P., Callegati, F., Cerroni, W., et al., 2015. Virtual network function embedding in real cloud environments. Comput. Netw., 93(3): 506–517. https://doi.org/10.1016/j.comnet.2015.09.034
Bhatia, S., Motiwala, M., Muhlbauer, W., et al., 2008. Hosting Virtual Networks on Commodity Hardware. Technical Report, No. GT-CS-07-10. Georgia Institute of Tech-nology, PA.
Chen, D., Lu, L., Shang, M., et al., 2012. Identifying influen-tial nodes in complex networks. Phys. A., 391(4): 1777–1787. https://doi.org/10.1016/j.physa.2011.09.017
Cheng, X., Su, S., Zhang, Z., et al., 2011. Virtual network embedding through topology-aware node ranking. ACM SIGCOMM Comput. Commun. Rev., 41(2): 38–47. https://doi.org/10.1145/1971162.1971168
Chowdhury, M., Rahman, M., Boutaba, R., et al., 2009. Vineyard: virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Trans. Netw., 20(1): 206–219. https://doi.org/10.1109/TNET.2011.2159308
Eppstein, D., 1998. Finding the K shortest paths. SIAM J. Comput., 28(2): 652–673. https://doi.org/10.1137/S0097539795290477
ETSI NFVISG (European Telecommunications Standards Institute Network Functions Virtualization Industry Specification Group), 2013. Network Functions Virtual-ization, White Paper. http://www.esti.org/technologiescluster/technologies/nfv [Accessed on Nov. 2, 2016].
Fagiolo, G., 2007. Clustering in complex directed networks. Phys. Rev. E, 76(2): 12–23. https://doi.org/10.1103/PhysRevE.76.026107
Fan, J., Ammar, M., 2006. Dynamic topology configuration in service overlay networks: a study of reconfiguration policies. Proc. 25th IEEE Int. Conf. on Computer Com-munications, p.21–32. https://doi.org/10.1109/INFOCOM.2006.139
Goldberg, D., 2009. Genetic Algorithms in Search, Optimiza-tion and Machine Learning. Addison-Wesley Profes-sional, USA, p.216–236.
Gong, L., Wen, Y., Zhu, Z., et al., 2014. Toward profit-seeking virtual network embedding algorithm via global resource capacity. Proc. IEEE Int. Conf. on Computer Communi-cations, p.1–9. https://doi.org/10.1109/INFOCOM.2014.6847918
Koh, Y., Knauerhase, R., Brett, P., et al., 2007. An analysis of performance interference effects in virtual environments. Proc. IEEE Int. Symp. on Performance Analysis of Sys-tems & Software, p.200–209. https://doi.org/10.1109/ISPASS.2007.363750
Lischka, J., Karl, H., 2009. A virtual network mapping algo-rithm based on subgraph isomorphism detection. Proc. 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, p.81–88. https://doi.org/10.1145/1592648.1592662
Lu, J., Turner, J., 2006. Efficient Mapping of Virtual Networks onto a Shared Substrate. Technical Report No. WUCSE- 2006-35, Washington University in St Louis, Washington.
Mehraghdam, S., Keller, M., Karl, H., et al., 2014. Specifying and placing chains of virtual network functions. Proc. 3rd IEEE Int. Conf. on Cloud Networking, p.7–13. https://doi.org/10.1109/CloudNet.2014.6968961
Mei, Y., Liu, L., Pu, X., et al., 2013. Performance analysis of network I/O workloads in virtualized data centers. IEEE Trans. Serv. Comput., 6(1): 48–63. https://doi.org/10.1109/TSC.2011.36
Pu, X., Liu, L., Mei, Y., et al., 2010. Understanding perfor-mance interference of I/O workload in virtualized cloud environment. Proc. 3rd IEEE Int. Conf. on Cloud Com-puting, p.51–58. https://doi.org/10.1109/CLOUD.2010.65
Razzaq, A., Siraj Rathore, M., 2010. An approach towards resource efficient virtual network embedding. Proc. 2nd Int. Conf. on Evolving Internet, p.68–73. https://doi.org/10.1109/INTERNET.2010.21
Shea, R., Wang, F., Wang, H., et al., 2014. A deep investiga-tion into network performance in virtual machine based cloud environments. Proc. IEEE Int. Conf. on Computer Communications, p.1285–1293. https://doi.org/10.1109/INFOCOM.2014.6848061
Su, S., Zhang, Z., Cheng, X., et al., 2012. Energy-aware virtual network embedding through consolidation. Proc. IEEE Int. Conf. on Computer Communications Workshops, p.127–132. https://doi.org/10.1109/INFCOMW.2012.6193473
Wang, Z., Wu, J., Wang, Y., et al., 2014. Survivable virtual network mapping using optimal backup topology in vir-tualized SDN. China Commun., 11(2): 26–37. https://doi.org/10.1109/CC.2014.6821735
Xia, S., Zhang, Y., Green, H., et al., 2014. Network function placement for NFV chaining in packet/optical data cen-ters. Proc. European Conf. on Optical Communication, p.1–3. https://doi.org/10.1109/ECOC.2014.6963925
Yu, M., Yi, Y., Rexford, J., et al., 2008. Rethinking virtual network embedding: substrate support for path splitting and migration. ACM SIGCOMM Comput. Commun. Rev., 32(2): 17–29. https://doi.org/10.1145/1355734.1355737
Zhang, S., Qian, Z., Wu, J., et al., 2012. An opportunistic resource sharing and topology-aware mapping framework for virtual networks. Proc. IEEE Int. Conf. on Computer Communications, p.2408–2416. https://doi.org/10.1109/INFCOM.2012.6195630
Author information
Authors and Affiliations
Corresponding author
Additional information
Project supported by the National Natural Science Foundation of China (Nos. 61309020 and 61521003)
Rights and permissions
About this article
Cite this article
Hu, Hc., Zhang, F., Mao, Yx. et al. A forwarding graph embedding algorithm exploiting regional topology information. Frontiers Inf Technol Electronic Eng 18, 1854–1866 (2017). https://doi.org/10.1631/FITEE.1601404
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/FITEE.1601404