PhD defense: Task Placement and Resource Allocation in Edge Computing Systems

Candidate: Sladana Josilo, KTH/EECS/NSE

Chairperson: Prof. Carlo Fischione, KTH/EECS/NSE

Faculty opponent: Prof. Ben Liang, Univ. of Toronto, Canada

Date: 14:00 on Wednesday, 27 May 2020

Register here: https://kth-se.zoom.us/webinar/register/WN_EQCltecySbSMoEQiRztIZg

Grading committee members:
Prof. Albert Banchs, IMDEA and UC3M, Spain
Assoc. Prof. Valeria Cardellini, Univ. Rome Tor Vergata, Italy
Adj. Prof. Johan Eker, Lund University and Ericsson Research, Sweden

Grading committee stand-by members:
Prof. Mats Bengtsson, KTH, Sweden
Prof. James Gross, KTH, Sweden

Advisors: Prof. György Dán (KTH/EECS/NSE), Prof. Viktoria Fodor
(KTH/EECS/NSE)

Abstract:

The evolution of wireless and hardware technology has led to the rapid development of a variety of mobile applications. Common to these applications is that they have low latency and high computational requirements that often cannot be fulfilled by individual devices due to their insufficient computational power, memory and battery capacity. An emerging approach to meet increasing user demand for delay sensitive and computationally intensive applications is mobile edge computing. The core paradigm of mobile edge computing is to bring computing and storage resources close to the end users and by doing so to relieve devices from computationally heavy workloads while meeting delay requirements of applications. However, the overall performance of edge computing systems is determined by the efficiency of the joint allocation of wireless and computing resources. The work in this thesis proposes decentralized algorithms for allocating these two resources in edge computing infrastructures.

In the first part of the thesis, we consider the resource allocation and computational task scheduling problem in an edge computing system in which wireless devices can use cloud resources and the resources of each other with the objective to minimize their own perceived response times. We develop a game theoretical model of the problem, prove the existence of equilibrium task allocations and propose an efficient decentralized algorithm that computes an equilibrium based on average system parameters.

In the second part of the thesis, we consider the resource allocation and computational task assignment problem in an edge computing system that consists of an edge cloud that can be accessed by devices through multiple wireless links. We model the problem as a strategic game, in which each device aims at minimizing a combination of its response time and energy consumption. We prove the existence of equilibrium task allocations, and use game theoretical tools for designing polynomial time decentralized algorithms with a bounded approximation ratio. We then extend the analysis to a system with periodic tasks, and show that equilibrium task allocations still exist. Furthermore, we propose a polynomial complexity decentralized algorithm and characterize the structure of equilibria computed by the algorithm.

In the third part of the thesis, we consider the resource allocation and computational task assignment problem in an edge computing system that consists of multiple wireless links and multiple edge clouds managed by a single network operator. We model the interaction between the operator and devices that aim at minimizing their response times as a Stackelberg game. We express the optimal resource allocation policies in closed form, prove the existence of Stackelberg equilibria and propose an efficient decentralized algorithm with a bounded approximation ratio. Finally, we consider the same edge computing system under network slicing, and based on a game theoretic treatment of the problem we develop an approximation algorithm for assigning tasks to slices and managing the resources across and within slices.

By providing constructive equilibrium existence proofs, the results in this thesis provide low complexity decentralized algorithms for allocating edge computing resources in a variety of edge computing infrastructures.

SmartGridComm 2020: sgc2020.ieee-smartgridcomm.org/