Similar articles

Abstract: The virtual network embedding/mapping problem is a core issue of network virtualization. It is concerned mainly with how to map virtual network requests to the substrate network efficiently. There are two steps in this problem: node mapping and link mapping. Current studies mainly focus on developing heuristic algorithms, since both steps are computationally intractable. In this paper, we propose a new algorithm based on the proximity principle, which considers the distance factor besides the capacity factor in the node mapping step. Thus, the two steps of the embedding problem can be better integrated and the substrate network resource can be used more efficiently. Simulation results show that the new algorithm greatly enhances the performance of the revenue/cost (R/C) ratio, acceptance ratio, and runtime of the embedding problem.

[1]Andersen, D.G., 2002. Theoretical Approaches to Node Assignment. Available from http://www.cs.cmu.edu/~dga/papers/andersen-assign.ps [Accessed on Sept. 20, 2010].

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

[3]Bavier, A., Feamster, N., Huang, M., Peterson, L., Rexford, J., 2006. In VINI Veritas: Realistic and Controlled Network Experimentation. Proc. Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communications, p.3-14.

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

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

[6]Kleinberg, J., 1996. Approximation Algorithms for Disjoint Paths Problems. PhD Thesis, MIT, USA.

[7]Kolliopoulos, S.G., Stein, C., 1997. Improved Approximation Algorithms for Unsplittable Flow Problems. Proc. 38th Annual Symp. on Foundations of Computer Science, p.426-436.

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

[9]Ricci, R., Alfeld, C., Lepreau, J., 2003. A solver for the network testbed mapping problem. ACM SIGCOMM Comput. Commun. Rev., 33(2):65-81.

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

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

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

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