A Green VNF-FG Embedding Algorithm

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 approaches do not scale well with problem size, the proposed algorithm selects a limited number of candidate hosts from the infrastructure to control complexity. The proposed on line ILP based heuristic is shown to outperform a tree based algorithm from the state of the art that relies also on sharing of VNFs to improve resource utilization. Results from extensive simulations report the achieved performance improvements in terms of rejection of service requests, energy consumption, scalability and attained revenues. Limiting the number of candidate hosts is an efficient way to tune the ILP to ensure scalability and to find good VNF-FG placement solutions for large problem sizes.