Task Placement and Resource Allocation in Edge Computing Systems
Time: Wed 2020-05-27 14.00
Subject area: Electrical Engineering
Doctoral student: Sladana Josilo , Nätverk och systemteknik, Royal Inst Technol, KTH, Sch Elect Engn & Comp Sci, Dept Network & Syst Engn, Stockholm, Sweden.
Opponent: Professor Ben Liang,
Supervisor: György Dán, Nätverk och systemteknik
The evolution of wireless and hardware technology has led to the rapiddevelopment of a variety of mobile applications. Common to these applicationsis that they have low latency and high computational requirementsthat often cannot be fulfilled by individual devices due to their insufficientcomputational power, memory and battery capacity. An emerging approachto meet increasing user demand for delay sensitive and computationally intensiveapplications is mobile edge computing. The core paradigm of mobileedge computing is to bring computing and storage resources close to the endusers and by doing so to relieve devices from computationally heavy workloadswhile meeting delay requirements of applications. However, the overallperformance of edge computing systems is determined by the efficiency of thejoint allocation of wireless and computing resources. The work in this thesisproposes decentralized algorithms for allocating these two resources in edgecomputing infrastructures.In the first part of the thesis, we consider the resource allocation andcomputational task scheduling problem in an edge computing system in whichwireless devices can use cloud resources and the resources of each other withthe objective to minimize their own perceived response times. We develop agame theoretical model of the problem, prove the existence of equilibrium taskallocations and propose an efficient decentralized algorithm that computes anequilibrium based on average system parameters.In the second part of the thesis, we consider the joint resource allocationand computational task assignment problem in an edge computing systemthat consists of an edge cloud that can be accessed by devices through multiplewireless links. We model the problem as a strategic game, in which eachdevice aims at minimizing a combination of its response time and energyconsumption. We prove the existence of equilibrium task allocations, and usegame theoretical tools for designing polynomial time decentralized algorithmswith a bounded approximation ratio. We then extend the analysis to a systemwith periodic tasks, and show that equilibrium task allocations still exist.Furthermore, we propose a polynomial complexity decentralized algorithmand characterize the structure of equilibria computed by the algorithm.In the third part of the thesis, we consider the joint resource allocation andcomputational task assignment problem in an edge computing system thatconsists of multiple edge clouds and wireless links managed by a single networkoperator. We model the interaction between the operator and devices thataim at minimizing their response times as a Stackelberg game. We expressthe optimal resource allocation policies in closed form, prove the existence ofStackelberg equilibria and propose an efficient decentralized algorithm with abounded approximation ratio. Finally, we consider the same edge computingsystem under network slicing, and based on a game theoretic treatment of theproblem we develop an approximation algorithm for assigning tasks to slicesand managing the resources across and within slices.By providing constructive equilibrium existence proofs, the results in thisthesis provide low complexity decentralized algorithms for allocating edgecomputing resources in a variety of edge computing infrastructures.