Dedicated Protection for Survivable Virtual Network Embedding

被引：58

作者：

Chowdhury, Shihabur Rahman ^{[1
]}

Ahmed, Reaz ^{[1
]}

Khan, Md Mashrur Alam ^{[2
]}

Shahriar, Nashid ^{[1
]}

Boutaba, Raouf ^{[1
]}

Mitra, Jeebak ^{[3
]}

Zeng, Feng ^{[4
]}

机构：

[1] Univ Waterloo, David R Cheriton Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

[2] Cisco Syst, Ottawa, ON K2K 3E8, Canada

[3] Huawei Technol Canada Res Ctr, Ottawa, ON K2K 3J1, Canada

[4] Huawei Technol Co Ltd, Chengdu 611730, Peoples R China

来源：

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT | 2016年 / 13卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Survivable virtual network embedding; network survivability and resilience; optimization techniques; TOPOLOGIES; NODE;

D O I：

10.1109/TNSM.2016.2574239

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Network virtualization is enabling infrastructure providers (InPs) to offer new services to service providers (SPs). InPs are usually bound by service level agreements to ensure various levels of resource availability for different SPs' virtual networks (VNs). They provision redundant backup resources while embedding an SP's VN request to conform to the SLAs during physical failures in the infrastructure. An extreme backup resource provisioning is to reserve a mutually exclusive backup of each element in an SP's VN request. Such dedicated protection scheme can enable an InP to ensure fast VN recovery, thus, providing high uptime guarantee to the SPs. In this paper, we study the 1 + 1-Protected Virtual Network Embedding (1 + 1-ProViNE) problem. We propose Dedicated Protection for Virtual Network Embedding (DRONE), a suite of solutions to the 1 + 1-ProViNE problem. DRONE includes an integer linear programming formulation for optimal solution (OPT-DRONE) and a heuristic (FAST-DRONE) to tackle the computational complexity of the optimal solution. Trace driven simulations show that FAST-DRONE allocates only 14.3% extra backup resources on average compared to the optimal solution, while executing 200-1200 times faster. Simulation results also show that FAST-DRONE can accept four times more VN requests on average compared to the state-of-the-art solution for providing dedicated protection to VNs.

引用

页码：913 / 926

页数：14

共 39 条

[1]

Anagnostopoulos A., 2014, P 25 ANN ACM SIAM S, P26, DOI DOI 10.1137/1.9781611973402.3

[2]

[Anonymous], P IEEE IFIP NOMS IST

[3]

[Anonymous], LNCS

[4]

Bonenfant P. A., 1998, OFC '98. Optical Fiber Communication Conference and Exhibit. Technical Digest. Conference Edition. 1998 OSA Technical Digest Series Vol.2 (IEEE Cat. No.98CH36177), P270, DOI 10.1109/OFC.1998.657389

[5] A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths [J].

Bonsma, Paul ;

Schulz, Jens ;

Wiese, Andreas .

2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, :47-56

[6] A survey of network virtualization [J].

Chowdhury, N. M. Mosharaf Kabir ;

Boutaba, Raouf .

COMPUTER NETWORKS, 2010, 54 (05) :862-876

[7] Virtual Network Embedding with Coordinated Node and Link Mapping [J].

Chowdhury, N. M. Mosharaf Kabir ;

Rahman, Muntasir Raihan ;

Boutaba, Raouf .

IEEE INFOCOM 2009 - IEEE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-5, 2009, :783-791

[8] On the single-source unsplittable flow problem [J].

Dinitz, Y ;

Garg, N ;

Goemans, MX .

COMBINATORICA, 1999, 19 (01) :17-41

[9] Energy Efficient Virtual Network Embedding [J].

Felipe Botero, Juan ;

Hesselbach, Xavier ;

Duelli, Michael ;

Schlosser, Daniel ;

Fischer, Andreas ;

de Meer, Hermann .

IEEE COMMUNICATIONS LETTERS, 2012, 16 (05) :756-759

[10]

Friggstad Z., 2015, LIPICS, V40, P265

← 1 2 3 4 →