CLC number: TP393
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2011-08-26
Cited: 13
Clicked: 8832
Jiang Liu, Tao Huang, Jian-ya Chen, Yun-jie Liu. A new algorithm based on the proximity principle for the virtual network embedding problem[J]. Journal of Zhejiang University Science C, 2011, 12(11): 910-918.
@article{title="A new algorithm based on the proximity principle for the virtual network embedding problem",
author="Jiang Liu, Tao Huang, Jian-ya Chen, Yun-jie Liu",
journal="Journal of Zhejiang University Science C",
volume="12",
number="11",
pages="910-918",
year="2011",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1100003"
}
%0 Journal Article
%T A new algorithm based on the proximity principle for the virtual network embedding problem
%A Jiang Liu
%A Tao Huang
%A Jian-ya Chen
%A Yun-jie Liu
%J Journal of Zhejiang University SCIENCE C
%V 12
%N 11
%P 910-918
%@ 1869-1951
%D 2011
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1100003
TY - JOUR
T1 - A new algorithm based on the proximity principle for the virtual network embedding problem
A1 - Jiang Liu
A1 - Tao Huang
A1 - Jian-ya Chen
A1 - Yun-jie Liu
J0 - Journal of Zhejiang University Science C
VL - 12
IS - 11
SP - 910
EP - 918
%@ 1869-1951
Y1 - 2011
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1100003
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.
Open peer comments: Debate/Discuss/Question/Opinion
<1>