WAOA 2018 Paper Abstract

TITLE: Algorithms for Dynamic NFV Workload
AUTHORS: Yaron Fairstein, Seffi Naor and Dan Raz

Abstract:
The dynamic NFV placement problem captures one of the main challenges facing the telecom industry following the emergence of the Network Function Virtualization (NFV) networking paradigm, that is, deciding the placement of network functions while taking into consideration the dynamic nature of networks and workloads. We model the problem as a generalization of the classic Uncapacitated Facility Location (UFL) problem, where we consider both multiple types of commodities and dynamic clients whose location changes over time. 

We show that under reasonable assumptions we are able to develop a $7$-approximation algorithm for the Dynamic Facility Location (DFL) problem, improving the logarithmic approximation of Eisenstat et al.. We build upon this result to develop the first virtualized services placement algorithm that accounts for dynamic changes. Our tri-criteria approximation algorithms provide constant approximation factors with respect to the overall performance and size constraints, and logarithmic approximation factors with respect to capacity constraints.