Request Reliability Augmentation with Service Function Chain Requirements in Mobile Edge Computing

In this paper, we study a novel service reliability augmentation problem in an Edge Computing network, where mobile users request network services with a service function chain (SFC) and reliability expectation requirements. To enhance the service reliability of user requests, it is a common practice to make use of redundant network function (VNF) instance placement in case their primary VNF instances fail. To this end, we first formulate a novel service reliability augmentation problem for each admitted request and show the NP-hardness of the problem. We then provide an admission framework of user requests by placing primary VNF instances of network functions in the SFC to different cloudlets, and then develop a randomized algorithm with a good approximation ratio and high probability for the service reliability augmentation problem, at the expense of moderate resource constraint violations. We also devise a deterministic heuristic for the problem without any resource violation. We thirdly extend the proposed algorithm for a single request to the service reliability augmentation problem for a set of requests. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising and superior to their analytical counterparts.