TY - JOUR
T1 - Robust Service Provisioning with Service Function Chain Requirements in Mobile Edge Computing
AU - Li, Jing
AU - Liang, Weifa
AU - Ma, Yu
N1 - Publisher Copyright:
© 2004-2012 IEEE.
PY - 2021/6
Y1 - 2021/6
N2 - 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.
AB - 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.
KW - Markov approximation technique
KW - Mobile edge computing networks
KW - QoS-aware request admissions
KW - network function virtualization (NFV)
KW - performance analysis
KW - resource allocation and optimization
KW - service function chain placement
KW - uncertain resource demands and measurement
UR - http://www.scopus.com/inward/record.url?scp=85102253853&partnerID=8YFLogxK
U2 - 10.1109/TNSM.2021.3062650
DO - 10.1109/TNSM.2021.3062650
M3 - Article
SN - 1932-4537
VL - 18
SP - 2138
EP - 2153
JO - IEEE Transactions on Network and Service Management
JF - IEEE Transactions on Network and Service Management
IS - 2
M1 - 9371018
ER -