Provably efficient algorithms for joint placement and allocation of virtual network functions

Yu Sang, Bo Ji, Gagan R. Gupta, Xiaojiang Du, Lin Ye

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

125 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationINFOCOM 2017 - IEEE Conference on Computer Communications
ISBN (Electronic)9781509053360
DOIs
StatePublished - 2 Oct 2017
Event2017 IEEE Conference on Computer Communications, INFOCOM 2017 - Atlanta, United States
Duration: 1 May 20174 May 2017

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Conference

Conference2017 IEEE Conference on Computer Communications, INFOCOM 2017
Country/TerritoryUnited States
CityAtlanta
Period1/05/174/05/17

Fingerprint

Dive into the research topics of 'Provably efficient algorithms for joint placement and allocation of virtual network functions'. Together they form a unique fingerprint.

Cite this