Reliability Aware Service Placement Using a Viterbi-based Algorithm

Network function virtualization (NFV) is referred to as the deployment of software functions running on commodity servers, instead of hardware middleboxes. It is an inevitable technology for agile service provisioning in next-generation telecommunication networks. A service is defined as a chain of software functions, named virtual network functions (VNFs), where each VNF can be placed on different host servers. The task of assigning the VNFs to the host servers is called service placement. A significant challenge in service placement is meeting the reliability requirement of a service. In the literature, the problem of service placement and providing the required reliability level are considered separately. First, the main server is selected, and then, the backup servers are deployed to meet the reliability requirement of the service. In this paper, we consolidate these two steps and perform them jointly and simultaneously. We consider a multi-infrastructure network provider (InP) environment where InPs offer general purpose commodity servers with different reliability levels. Then, we propose a programming problem for main and backup server selection jointly minimizing the cost of resources of the InPs and maximizing the reliability of the service. We reformulate this problem as a mixed integer convex programming (MICP) problem. Since MICPs are known to be NP-hard in general, we propose a polynomial time sub-optimal algorithm named Viterbi-based Reliable Service Placement (VRSP). Using numerical evaluations, we investigate the performance of the proposed algorithm compared to the optimal solution resulting from the MICP model and also with three heuristic algorithms.