Efficient Virtualized Network Service Provisioning in Mobile Edge Computing

Abstract

There is a substantial growth in the usage of mobile devices. These devices, including smartphones, sensors, and wearables, are limited by their computational and energy capacities, due to their portable size. Mobile edge computing (MEC), which provides cloud resources at the edge of mobile network in close proximity to mobile users, is a promising technology to reduce response delays, ensure network operation efficiency, and improve user service satisfaction. Mobile edge computing is a promising technology to leverage the capability of mobile devices to offload tasks to nearby edge-clouds (cloudlets) for processing. Furthermore, Network Function Virtualization (NFV) is another promising technique that implements various network functions for many applications as pieces of software in servers or cloudlets in MEC networks. The provisioning of virtualized network services in MEC can improve user service experiences, simplify network service deployment, and ease network resource management.

In this thesis, we will focus on the efficient virtualized network service provisioning in MEC networks by judicious resource allocations and request admissions to maximize network throughput and minimize request admission cost in different application scenarios.

We firstly address dynamic request admissions with service function chain requirements in MEC with the objective to maximize the profit collected by the network service provider, assuming that the cloudlets are located at different geographical locations and electricity prices at different locations are different. We formulate an integer linear programming (ILP) solution to the offline problem, and devise an online algorithm with a provable competitive ratio for the online problem when requests arrive one by one without the knowledge of future request arrivals.

We then study NFV-enabled multicasting that is a fundamental routing problem in an MEC network, subject to resource capacities on both its cloudlets and links. We devise an admission framework for single NFV-enabled multicast request admission with the aim to minimize request admission cost. We then develop an efficient algorithm for the throughput maximization problem for the admissions of a given set of NFV-enabled multicast requests. We also devise an online algorithm with a provable competitive ratio for the online NFV-enabled multicast request admissions.

We thirdly investigate virtualized network function service provisioning for mobile users in MEC that takes into account user mobility and service delay requirements. We formulate two novel optimization problems of user service request admissions with the aims to maximize the accumulative network utility and accumulative network throughput for a given time horizon, respectively, where network utility is a submodular function that can be used to tradeoff between individual user service satisfaction and accumulative network throughput. We then devise a constant approximation algorithm for the utility maximization problem. We also develop an online algorithm for the accumulative throughput maximization problem.

We fourthly explore a non-trivial tradeoff between different types of resources in NFV-enabled request scheduling in MEC with an objective to minimize request admission cost, through introducing a novel concept - load factor. We formulate the cost minimization problem that admits all requests by assuming that there is sufficient computing resource in MEC to accommodate the requested VNF instances of all requests, for which we formulate an ILP solution and two efficient heuristic algorithms. We also deal with the problem under the computing resource constraint, for which we formulate an ILP solution when the problem size is small; otherwise, we devise efficient algorithms for it.

We finally summarize the thesis and explore several potential research topics that are based on the work in this thesis.