TY - GEN
T1 - Provably efficient algorithms for joint placement and allocation of virtual network functions
AU - Sang, Yu
AU - Ji, Bo
AU - Gupta, Gagan R.
AU - Du, Xiaojiang
AU - Ye, Lin
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/10/2
Y1 - 2017/10/2
N2 - Network Function Virtualization (NFV) has the potential to significantly reduce the capital and operating expenses, shorten product release cycle, and improve service agility. In this paper, we focus on minimizing the total number of Virtual Network Function (VNF) instances to provide a specific service (possibly at different locations) to all the flows in a network. Certain network security and analytics applications may allow fractional processing of a flow at different nodes (corresponding to datacenters), giving an opportunity for greater optimization of resources. Through a reduction from the set cover problem, we show that this problem is NP-hard and cannot even be approximated within a factor of (1 - o(1))lnm (where m is the number of flows) unless P=NP. Then, we design two simple greedy algorithms and prove that they achieve an approximation ratio of (1 - o(1))ln m + 2, which is asymptotically optimal. For special cases where each node hosts multiple VNF instances (which is typically true in practice), we also show that our greedy algorithms have a constant approximation ratio. Further, for tree topologies we develop an optimal greedy algorithm by exploiting the inherent topological structure. Finally, we conduct extensive numerical experiments to evaluate the performance of our proposed algorithms in various scenarios.
AB - Network Function Virtualization (NFV) has the potential to significantly reduce the capital and operating expenses, shorten product release cycle, and improve service agility. In this paper, we focus on minimizing the total number of Virtual Network Function (VNF) instances to provide a specific service (possibly at different locations) to all the flows in a network. Certain network security and analytics applications may allow fractional processing of a flow at different nodes (corresponding to datacenters), giving an opportunity for greater optimization of resources. Through a reduction from the set cover problem, we show that this problem is NP-hard and cannot even be approximated within a factor of (1 - o(1))lnm (where m is the number of flows) unless P=NP. Then, we design two simple greedy algorithms and prove that they achieve an approximation ratio of (1 - o(1))ln m + 2, which is asymptotically optimal. For special cases where each node hosts multiple VNF instances (which is typically true in practice), we also show that our greedy algorithms have a constant approximation ratio. Further, for tree topologies we develop an optimal greedy algorithm by exploiting the inherent topological structure. Finally, we conduct extensive numerical experiments to evaluate the performance of our proposed algorithms in various scenarios.
UR - http://www.scopus.com/inward/record.url?scp=85034051717&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85034051717&partnerID=8YFLogxK
U2 - 10.1109/INFOCOM.2017.8057036
DO - 10.1109/INFOCOM.2017.8057036
M3 - Conference contribution
AN - SCOPUS:85034051717
T3 - Proceedings - IEEE INFOCOM
BT - INFOCOM 2017 - IEEE Conference on Computer Communications
T2 - 2017 IEEE Conference on Computer Communications, INFOCOM 2017
Y2 - 1 May 2017 through 4 May 2017
ER -