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.

一种基于区域拓扑信息的转发图映射算法

[1]Bellavista, P., Callegati, F., Cerroni, W., et al., 2015. Virtual network function embedding in real cloud environments. Comput. Netw., 93(3):506-517.

[2]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 Technology, PA.

[3]Chen, D., Lu, L., Shang, M., et al., 2012. Identifying influential nodes in complex networks. Phys. A., 391(4):1777-1787.

[4]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.

[5]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.

[6]Eppstein, D., 1998. Finding the K shortest paths. SIAM J. Comput., 28(2):652-673.

[7]ETSI NFVISG (European Telecommunications Standards Institute Network Functions Virtualization Industry Specification Group), 2013. Network Functions Virtualization, White Paper. http://www.esti.org/technologiescluster/technologies/nfv [Accessed on Nov. 2, 2016].

[8]Fagiolo, G., 2007. Clustering in complex directed networks. Phys. Rev. E, 76(2):12-23.

[9]Fan, J., Ammar, M., 2006. Dynamic topology configuration in service overlay networks: a study of reconfiguration policies. Proc. 25th IEEE Int. Conf. on Computer Communications, p.21-32.

[10]Goldberg, D., 2009. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Professional, USA, p.216-236.

[11]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 Communications, p.1-9.

[12]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 Systems & Software, p.200-209.

[13]Lischka, J., Karl, H., 2009. A virtual network mapping algorithm based on subgraph isomorphism detection. Proc. 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, p.81-88.

[14]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.

[15]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.

[16]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.

[17]Pu, X., Liu, L., Mei, Y., et al., 2010. Understanding performance interference of I/O workload in virtualized cloud environment. Proc. 3rd IEEE Int. Conf. on Cloud Computing, p.51-58.

[18]Razzaq, A., Siraj Rathore, M., 2010. An approach towards resource efficient virtual network embedding. Proc. 2nd Int. Conf. on Evolving Internet, p.68-73.

[19]Shea, R., Wang, F., Wang, H., et al., 2014. A deep investigation into network performance in virtual machine based cloud environments. Proc. IEEE Int. Conf. on Computer Communications, p.1285-1293.

[20]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.

[21]Wang, Z., Wu, J., Wang, Y., et al., 2014. Survivable virtual network mapping using optimal backup topology in virtualized SDN. China Commun., 11(2):26-37.

[22]Xia, S., Zhang, Y., Green, H., et al., 2014. Network function placement for NFV chaining in packet/optical data centers. Proc. European Conf. on Optical Communication, p.1-3.

[23]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.

[24]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.