Theory Seminar: Approximation Algorithms for Dynamic NFV Workload

Yaron Fairstein (CS, Technion)
Wednesday, 30.5.2018, 12:30
Taub 201

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.

In this talk I will start from the Dynamic Facility Location problem as a basis, and present an approximation algorithm based on LP rounding. At each step I will generalizes the problem, and show how to update the solution and bound the approximation factor of the algorithm. In the end I will present a tri-criteria approximation algorithm for the Dynamic NFV placement problem; constant approximation factors with respect to the overall performance and size constraints, and logarithmic approximation factors with respect to capacity constraints.

Back to the index of events