Full Text:   <2100>

CLC number: TP393

On-line Access: 2012-03-01

Received: 2011-09-26

Revision Accepted: 2011-11-29

Crosschecked: 2012-02-08

Cited: 12

Clicked: 4411

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

Journal of Zhejiang University SCIENCE C 2012 Vol.13 No.3 P.178-186

10.1631/jzus.C1100282


Topology awareness algorithm for virtual network mapping


Author(s):  Xiao-ling Li, Huai-min Wang, Chang-guo Guo, Bo Ding, Xiao-yong Li, Wen-qi Bi, Shuang Tan

Affiliation(s):  National Key Laboratory of Parallel and Distributed Processing, National University of Defense Technology, Changsha 410073, China; more

Corresponding email(s):   nudtlxl@163.com

Key Words:  Network virtualization, Ossification, Virtual network (VN) mapping, Substrate network (SN), Topology awareness, Acceptance ratio


Xiao-ling Li, Huai-min Wang, Chang-guo Guo, Bo Ding, Xiao-yong Li, Wen-qi Bi, Shuang Tan. Topology awareness algorithm for virtual network mapping[J]. Journal of Zhejiang University Science C, 2012, 13(3): 178-186.

@article{title="Topology awareness algorithm for virtual network mapping",
author="Xiao-ling Li, Huai-min Wang, Chang-guo Guo, Bo Ding, Xiao-yong Li, Wen-qi Bi, Shuang Tan",
journal="Journal of Zhejiang University Science C",
volume="13",
number="3",
pages="178-186",
year="2012",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1100282"
}

%0 Journal Article
%T Topology awareness algorithm for virtual network mapping
%A Xiao-ling Li
%A Huai-min Wang
%A Chang-guo Guo
%A Bo Ding
%A Xiao-yong Li
%A Wen-qi Bi
%A Shuang Tan
%J Journal of Zhejiang University SCIENCE C
%V 13
%N 3
%P 178-186
%@ 1869-1951
%D 2012
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1100282

TY - JOUR
T1 - Topology awareness algorithm for virtual network mapping
A1 - Xiao-ling Li
A1 - Huai-min Wang
A1 - Chang-guo Guo
A1 - Bo Ding
A1 - Xiao-yong Li
A1 - Wen-qi Bi
A1 - Shuang Tan
J0 - Journal of Zhejiang University Science C
VL - 13
IS - 3
SP - 178
EP - 186
%@ 1869-1951
Y1 - 2012
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1100282


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).

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

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

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE