Yaron Fairstein, M.Sc. Thesis Seminar
Wednesday, 29.11.2017, 13:30
Network Function Virtualization (NFV) is an emerging networking paradigm where network functions are located at Commercially-Off-The-Shelf (COTS) servers distributed across a network. This paradigm is a major turning point in the evolution of networking, as it introduces high expectations for both agile and much more economical network services. However, in order to achieve high utilization and low cost, one must deploy resource allocation algorithms that are aware of the dynamicity of workloads and services.
In this paper we introduce the first virtualized services placement algorithmic scheme that accounts for these dynamic changes. We perform a thorough analytical study of this new model and provide approximation algorithms with guaranteed proven performance. The cost is composed of three components: the installation cost of the virtualized network functions on the servers, the service cost that depends on the distance between a client and the location of the virtual function that provides service to it, and the change cost charged for changes in the assignment of clients when the workload changes. Our approximation algorithms provide constant approximation factors with respect to the overall performance and size constraints, and logarithmic approximation factors with respect to capacity constraints. We also evaluate the actual expected performance of the algorithms in realistic scenarios using extensive simulations and show that our scheme performs 25-40% better than current best practice solutions in most relevant settings.