Reliability-Aware Service Function Chain Provisioning in Mobile Edge-Cloud Networks

Mobile Edge Computing (MEC) has been envisioning as a promising technology to address limited computing and storage resources in mobile devices. The virtual services provided by the MEC platform are implemented as instances of Virtual Network Functions (VNFs). However, these VNF instances as pieces of software that run in virtual machines (VMs) are not always reliable. To provide reliable services for their users while meeting user service reliability requirements, the service providers of MEC usually adopt the replica policy that deploy a certain number of service replicas for each VNF instance. In this paper, we study reliable service provisioning in an MEC network through redundant placement of instances of VNFs. We assume that each service request consists of a Service Function Chain (SFC) requirement and a service reliability requirement. We formulate a novel reliability-aware service function chain provisioning problem with the aim to maximize the number of requests admitted, while meeting the specified reliability requirement of each admitted request. We first show that the problem is NP-hard, and formulate an ILP solution for the problem when the problem size is small. We then develop a randomized algorithm with a provable approximation ratio and high probability for the problem when the problem size is large, and the achieved approximation ratio is at the expense of moderate computing capacity and reliability constraint violations. We also devise an efficient heuristic for the problem without any resource and requirement constraint violations. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising.