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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations


  • Yu Ma
  • Wenzheng Xu
  • Zichuan Xu
  • Wanlei Zhou

Related Research Unit(s)


Original languageEnglish
Pages (from-to)4541-4554
Journal / PublicationIEEE Transactions on Mobile Computing
Issue number12
Online published18 May 2021
Publication statusPublished - Dec 2022


Provisioning reliable network services for mobile users in edge computing environments is the top priority of network service providers, as unreliable services will result in tremendous losses of revenues and consumers. In this paper, we study a novel service reliability augmentation problem in a Mobile Edge Computing (MEC) network, where mobile users request network services with 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 the primary VNF instance fails. We aim to augment the service reliability of each admitted request to its specified reliability expectation, subject to computing capacity on each cloudlet. To this end, we first formulate a novel service reliability augmentation problem for each request with a SFC and a reliability expectation requirement, by augmenting its reliability through redundant VNF instance deployment. We then show that the problem is NP-hard, and provide an admission framework of user requests by placing primary VNF instances of network functions in the SFC to different cloudlets. We then deal with the service reliability augmentation problem of an admitted request under the assumption that all secondary VNF instances of each primary VNF instance must be placed into the cloudlets no more than l hops from the cloudlet of its primary VNF instance for a fixed l with 1 ≤ ln − 1, where n is the number of cloudlets in the network, for which we formulate an integer linear program solution, and develop a randomized algorithm with a good approximation ratio and high probability, at the expense of moderate resource constraint violations. We also devise a deterministic heuristic for the problem without any resource violation. We thirdly study the service reliability augmentation problem for a set of admitted requests by extending the proposed algorithm for the service reliability augmentation problem for a single request admission. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and their empirical results are superior to their analytical counterparts.

Research Area(s)

  • approximation algorithms, budgeted minimum cost generalized assignment problems, Cloud computing, Computer network reliability, Heuristic algorithms, l-hop message communication model, Mobile computing, Mobile Edge Computing (MEC), primary and secondary VNF instance placement, randomized algorithms, Reliability, Reliability augmentation of services, Service function chaining, virtualized network function (VNF) placement, VNF instance redundancy