Tabu Search For Service Function Chain Composition In NFV

Abstract

One of the main challenges for service providers when they try to deploy Network Function Virtualization (NFV)- based networks is to efficiently make use of substrate network resources to facilitate the design, delivery and operation of network services in a dynamic and scalable manner. This challenge is known as NFV Resource Allocation (NFV-RA). We consider that NFV-RA can be addressed in two stages called Service Function Chain (SFC) composition and SFC embedding. The main objective of the first stage is to compose an optimized chain of Virtual Network Functions (VNFs) which offers a complete network service. The second stage is responsible for the embedding of such network service onto a physical infrastructure based on NFV. In this paper, we propose a metaheuristic algorithm to face the scalability challenges of exact approaches, when solving the SFC chain composition stage. The performance of our metaheuristic approach shows that large, complex and heterogeneous service requests (VNFRs) can be processed in reasonable running times, finding better results compared with existing heuristics in the state of the art.