Robust Service Provisioning With Service Function Chain Requirements in Mobile Edge Computing

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

24 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)2138-2153
Journal / PublicationIEEE Transactions on Network and Service Management
Issue number2
Online published5 Mar 2021
Publication statusPublished - Jun 2021
Externally publishedYes


With the advent of Network Function Virtualization (NFV) technology, more and more mobile users make use of virtual network services in Mobile Edge Computing (MEC) networks. Each service request not only requests for a service but also a Service Function Chain (SFC) associated with the request. How to effectively allocate resources in MEC to meet the resource demands of user service requests to maximize the expected profit of the network service provider poses a great challenge. Most existing studies considered resource allocation and scheduling in MEC for user request admissions, under the assumption that the amounts of different resources demanded by each request are given a prior and do not change during the execution of the request. In practice, the resource demands during the implementation of a request are dynamically evolving. This uncertainty of resource demands at different execution stages of the request does impact the service quality and the profit of network service providers. Thus, providing robust services to users against their resource demand uncertainties is a critical issue. In this paper, we study the robust service function chain placement (RSFCP) problem under the uncertainty assumption of both computing resource and data rates demanded by request executions, through the placement of SFCs. We first formulate the RSFCP problem as a Quadratic Integer Programming (QIP) and show that the problem is NP-hard. We then develop a near-optimal approximation algorithm for it, by adopting the Markov approximation technique. We also analyze the proposed approximation algorithm with the optimality gap, and the bounds on the convergence time and perturbation caused by resource demand uncertainties. We finally evaluate the performance of the proposed algorithm through analytical and empirical analyses. Experimental results demonstrate that the proposed algorithm is promising, compared with existing baseline algorithms.

Research Area(s)

  • Approximation algorithms, Cloud computing, Heuristic algorithms, Markov approximation technique, Mobile Edge Computing networks, Network function virtualization, Network Function Virtualization (NFV), performance analysis., QoS-aware request admissions, resource allocation and optimization, Resource management, Service Function Chain placement, Task analysis, uncertain resource demands and measurement, Uncertainty