A Scalable Algorithm for the Placement of Service Function Chains

Network function virtualization (NFV) decouples software implementations of network functions from their hosts (or hardware). NFV exposes a new set of entities, the virtualized network functions (VNFs). The VNFs can be chained with other VNFs and physical network functions to realize network services. This flexibility introduced by NFV allows service providers to respond in an agile manner to variable service demands and changing business goals. In this context, the efficient establishment of service chains and their placement becomes essential to reduce capital and operational expenses and gain in service agility. This paper addresses the placement aspect of these service chains by finding the best locations and hosts for the VNFs and to steer traffic across these functions while respecting user requirements and maximizing provider revenue. We propose a novel eigendecomposition-based approach for the placement of virtual and physical network function chains in networks and cloud environments. A heuristic based on a custom greedy algorithm is also presented to compare performance and assess the capability of the eigendecomposition approach. The performance of both algorithms is compared to a multi-stage-based method from the state of the art that also addresses the chaining of network services. Performance evaluation results show that our matrix-based method, eigendecomposition of adjacency matrices, has reduced complexity and convergence times that essentially depend only on the physical graph sizes. Our proposal also outperforms the related work in provider’s revenue and acceptance rate.