Online and batch algorithms for VNFs placement and chaining

This paper proposes an Integer Linear Program (ILP) to address the Virtualized Network Function Forwarding Graph (VNF-FG) placement and chaining problem when VNFs are shared across tenants to optimize resource usage and increase provider revenue. Since ILP based approaches do not scale well with problem size, the proposed algorithm (R-ILP for reduced exploration) selects a limited number of candidate hosts from the infrastructure to control complexity. Since the online R-ILP treats the requests sequentially, a batch strategy that operates on a set of requests is also proposed to improve performance. The online algorithm processes the VNF-FG requests on a sequential basis as they arrive while the batch mode treats several requests jointly over a batch window. This work focuses on energy consumption optimization as a general objective. The proposed solutions are shown to outperform competitor algorithms from the state of the art that rely also on VNFs sharing. Results from extensive simulations, based on realistic and large scale topologies, report the performance in terms of rejection of service requests, energy consumption, scalability and achieved revenues. The performance benefits of operating our R-ILP in batch mode are highlighted.