Similar articles

Abstract: network virtualization is recognized as an effective way to overcome the ossification of the Internet. However, the virtual network mapping problem (VNMP) is a critical challenge, focusing on how to map the virtual networks to the substrate network with efficient utilization of infrastructure resources. The problem can be divided into two phases: node mapping phase and link mapping phase. In the node mapping phase, the existing algorithms usually map those virtual nodes with a complete greedy strategy, without considering the topology among these virtual nodes, resulting in too long substrate paths (with multiple hops). Addressing this problem, we propose a topology awareness mapping algorithm, which considers the topology among these virtual nodes. In the link mapping phase, the new algorithm adopts the k-shortest path algorithm. Simulation results show that the new algorithm greatly increases the long-term average revenue, the acceptance ratio, and the long-term revenue-to-cost ratio (R/C).

[1]Anderson, T., Peterson, L., Shenker, S., Turner, J., 2005. Overcoming the Internet impasse through virtualization. Computer, 38(4):34-41.

[2]Bansal, N., Lee, K.W., Nagarajan, V., Zafer, M., 2011. Minimum Congestion Mapping in a Cloud. Proc. 30th Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, p.267-276.

[3]Bavier, A., Feamster, N., Huang, M., Peterson, L., Rexford, J., 2006. In VINI veritas: realistic and controlled network experimentation. ACM SIGCOMM Comput. Commun. Rev., 36(4):3-14.

[4]Cheng, X., Su, S., Zhang, Z.B., 2011. Virtual network embedding through topology-aware node ranking. ACM SIGCOMM Comput. Commun. Rev., 41(2):39-47.

[5]Chowdhury, N.M.M.K., Rahman, M.R., Boutaba, R., 2009a. Network virtualization: state of the art and research challenges. IEEE Commun. Mag., 47(7):20-26.

[6]Chowdhury, N.M.M.K., Rahman, M.R., Boutaba, R., 2009b. Virtual Network Embedding with Coordinated Node and Link Mapping. Proc. 28th IEEE Int. Conf. on Computer Communications, p.783-791.

[7]Eppstein, D., 1994. Finding the k shortest paths. SIAM J. Comput., 28(2):652-673.

[8]Fan, J., Ammar, M.H., 2006. Dynamic Topology Configuration in Service Overlay Networks: a Study of Reconfiguration Policies. Proc. 25th IEEE Int. Conf. on Computer Communications, p.1-12.

[9]Feamster, N., Gao, L., Rexford, J., 2007. How to lease the Internet in your spare time. ACM SIGCOMM Comput. Commun. Rev., 37(1):61-64.

[10]Guo, C., Lu, G., Wang, H.J., Yang, S., Kong, C., Sun, P., Wu, W., Zhang, Y., 2010. SecondNet: a Data Center Network Virtualization Architecture with Bandwidth Guarantees. Proc. 6th Int. Conf. on Emerging Networking Experiments and Technologies, p.15-26.

[11]Lischka, J., Karl, H., 2009. A Virtual Network Mapping Algorithm Based on Subgraph Isomorphism Detection. Proc. 1st ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures, p.81-88.

[12]Lu, J., Turner, J., 2006. Efficient Mapping of Virtual Networks onto a Shared Substrate. Technical Report No. WUCSE-2006-35, Washington University, USA.

[13]Turner, J.S., Taylor, D.E, 2005. Diversifying the Internet. IEEE Global Telecommunications Conf., p.755-760.

[14]Wang, Q.B., Jin, X., He, L., Zhao, Y., 2009. Virtualization and Cloud Computing. Publishing House of Electronic Industry, Beijing, China, p.26-30 (in Chinese).

[15]Yu, M., Yi, Y., Rexford, J., Chiang, M., 2008. Rethinking virtual network embedding: substrate support for path splitting and migration. ACM SIGCOMM Commun. Rev., 38(2):17-29.

[16]Zegura, E.W., Calvert, K.L., Bhattacharjee, S., 1996. How to Model an Internetwork. Proc. 15th IEEE Int. Conf. on Computer Communication, p.594-602.

[17]Zhu, Y., Ammar, M., 2006. Algorithms for Assigning Substrate Network Resources to Virtual Network Components. Proc. 25th IEEE Int. Conf. on Computer Communications, p.1-12.