Single and Multi-Domain Adaptive Allocation Algorithms for VNF Forwarding Graph Embedding

Network function virtualization (NFV) will simplify deployment and management of network and telecommunication services. NFV provides flexibility by virtualizing the network functions and moving them to a virtualization platform. In order to achieve its full potential, NFV is being extended to mobile or wireless networks by considering virtualization of radio functions. A typical network service setup requires the allocation of a virtual network function-forwarding graph (VNF-FG). A VNF-FG is allocated considering the resource constraints of the lower infrastructure. This topic has been well-studied in existing literature, however, the effects of variations of networks over time have not been addressed yet. In this paper, we provide a model of the adaptive and dynamic VNF allocation problem considering also VNF migration. Then we formulate the optimization problem as an integer linear programming (ILP) and provide a heuristic algorithm for allocating multiple VNF-FGs. The idea is that VNF-FGs can be reallocated dynamically to obtain the optimal solution over time. First, a centralized optimization approach is proposed to cope with the ILP-resource allocation problem. Next, a decentralized optimization approach is proposed to deal with cooperative multi-operator scenarios. We adopt AD(3), an alternating direction method of multipliers-based algorithm, to solve this problem in a distributed way. The results confirm that the proposed algorithms are able to optimize the network utilization, while limiting the number of reallocations of VNFs which could interrupt network services.