CLC number: TP393
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2017-11-24
Cited: 0
Clicked: 7228
Hong-chao Hu, Fan Zhang, Yu-xing Mao, Zhen-peng Wang. A forwarding graph embedding algorithm exploiting regional topology information[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(11): 1854-1866.
@article{title="A forwarding graph embedding algorithm exploiting regional topology information",
author="Hong-chao Hu, Fan Zhang, Yu-xing Mao, Zhen-peng Wang",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="18",
number="11",
pages="1854-1866",
year="2017",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1601404"
}
%0 Journal Article
%T A forwarding graph embedding algorithm exploiting regional topology information
%A Hong-chao Hu
%A Fan Zhang
%A Yu-xing Mao
%A Zhen-peng Wang
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 11
%P 1854-1866
%@ 2095-9184
%D 2017
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1601404
TY - JOUR
T1 - A forwarding graph embedding algorithm exploiting regional topology information
A1 - Hong-chao Hu
A1 - Fan Zhang
A1 - Yu-xing Mao
A1 - Zhen-peng Wang
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 11
SP - 1854
EP - 1866
%@ 2095-9184
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1601404
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.
Open peer comments: Debate/Discuss/Question/Opinion
<1>