Decomposition Approaches for Virtual Network Embedding With One-Shot Node and Link Mapping

被引:79
作者
Jarray, Abdallah [1 ]
Karmouch, Ahmed [1 ]
机构
[1] Univ Ottawa, Sch Informat Technol & Engn, Ottawa, ON K1N 6N5, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
Auction; column generation; integer linear programming; network virtualization; one-shot embedding; optimization; physical infrastructure provider; quality of service; virtual network;
D O I
10.1109/TNET.2014.2312928
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Network virtualization is a promising new resource management approach that allows customized virtual networks (VNs) to be multiplexed on a shared physical infrastructure. In this paper, our focus is on the embedding of VN resources onto this infrastructure. Since this problem is known to be NP-hard, embedding proposals in literature are heuristic-based approaches that restrict the problem space in different dimensions. Limitations of these proposals are: 1) as embedding of VN links and nodes is performed in two separate stages, it may ensue in a high blocking of VN requests and a less efficient usage of substrate resources; and 2) as pricing of embedding resources is based on linear functions, it triggers no competition among VN users in order to maximize infrastructure provider profits. These drawbacks motivate us to propose a mathematical model that makes use of large-scale optimization tools and proposes a Column Generation (CG) formulation of the problem, coupled with branch-and-bound technique or rounding-off heuristic. We also propose a periodical planning of embedding process where profitable VN requests are selected through an auction mechanism. In our experiments with different substrate network topologies and many different VN request patterns, we show a clear advantage of auction-based CG models over present benchmarks.
引用
收藏
页码:1012 / 1025
页数:14
相关论文
共 32 条
[1]  
Abdeljaouad I, 2013, 2013 IEEE CONSUMER COMMUNICATIONS AND NETWORKING CONFERENCE (CCNC), P190, DOI 10.1109/CCNC.2013.6488445
[2]  
[Anonymous], THEORETICAL APPROACH
[3]  
[Anonymous], IBM ILOG CPLEX 12 1
[4]  
[Anonymous], WUCSE2006
[5]   Data Center Network Virtualization: A Survey [J].
Bari, Md. Faizul ;
Boutaba, Raouf ;
Esteves, Rafael ;
Granville, Lisandro Zambenedetti ;
Podlesny, Maxim ;
Rabbani, Md Golam ;
Zhang, Qi ;
Zhani, Mohamed Faten .
IEEE COMMUNICATIONS SURVEYS AND TUTORIALS, 2013, 15 (02) :909-928
[6]  
Baucke S., 2009, Virtualization approach: concept, 4WARD project
[7]  
Carapinha J, 2009, VISA 09, P73
[8]   ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping [J].
Chowdhury, Mosharaf ;
Rahman, Muntasir Raihan ;
Boutaba, Raouf .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2012, 20 (01) :206-219
[9]   A survey of network virtualization [J].
Chowdhury, N. M. Mosharaf Kabir ;
Boutaba, Raouf .
COMPUTER NETWORKS, 2010, 54 (05) :862-876
[10]   An auction mechanism for allocating the bandwidth of networks to their users [J].
Dramitinos, Manos ;
Stamoulis, George D. ;
Courcoubetis, Costas .
COMPUTER NETWORKS, 2007, 51 (18) :4979-4996