Slađana Jošilo

Ph.D. student

Division of Network and Systems Engineering
School of Electrical Engineering and Computer Science
KTH Royal Institute of Technology

Title of the doctoral thesis

Task Placement and Resource Allocation in Edge Computing Systems [pdf] [slides_pdf]

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.

Included publications

Paper A: Slađana Jošilo, György Dán, ''Decentralized Algorithm for Randomized Task Allocation in Fog Computing Systems,''
in IEEE/ACM Transactions on Networking, vol. 27., no. 1., pp. 85-97, Feb. 2019. [pdf]

Paper B: Slađana Jošilo, György Dán, ''Selfish Decentralized Computation Offloading for Mobile Cloud Computing in Dense Wireless Networks,''
in Transactions on Mobile Computing, vol. 18., no. 1., pp. 207-220, Apr. 2018. [pdf]

Paper C: Slađana Jošilo, György Dán, ''Computation Offloading Scheduling for Periodic Tasks in Mobile Edge Computing,''
in IEEE/ACM Transactions on Networking, accepted for publication [pdf]

Paper D: Slađana Jošilo, György Dán, ''Joint Management of Wireless and Computing Resources for Computation Offloading in Mobile Edge Clouds,''
in IEEE Transactions on Cloud Computing, pp. 1-1, Jun 2019. [pdf]

Paper E: Slađana Jošilo, György Dán, ''Joint Wireless and Edge Computing Resource Management with Dynamic Network Slice Selection,''
submitted to IEEE/ACM Transactions on Networking. [pdf]

Publications not included in the doctoral thesis

Slađana Jošilo, György Dán, ''Wireless and Computing Resource Allocation for Selfish Computation Offloading in Edge Computing,''
in Proc. of IEEE Infocom, April 2019 [pdf] [slides_pdf]

Slađana Jošilo, György Dán, ''Joint Allocation of Computing and Wireless Resources to Autonomous Devices in Mobile Edge Computing,''
in Proc. of ACM SIGCOMM Mecomm'18 Workshop, Aug. 2018 [pdf] [slides_pdf]

Slađana Jošilo, György Dán, ''Decentralized Scheduling for Offloading of Periodic Tasks in Mobile Edge Computing,''
in Proc. of IFIP Networking, Short Presentations Session, May 2018 [pdf] [slides_pdf]

Slađana Jošilo, György Dán, ''Decentralized Fog Computing Resource Management for Offloading of Periodic Tasks,''
in Proc. of IEEE Infocom, Poster abstract, Apr. 2018 [pdf]

Slađana Jošilo, György Dán, ''A Game Theoretic Analysis of Selfish Mobile Computation Offloading,''
in Proc. of IEEE Infocom, May 2017 [pdf] [slides_pdf]

Slađana Jošilo, Valentino Pacifici, György Dán, ''Distributed Algorithms for Content Placement in Hierarchical Cache Networks,''
Computer Networks Journal, Oct. 2017 [pdf]

Valentino Pacifici, Slađana Jošilo, György Dán, ''Distributed Algorithms for Content Caching in Mobile Backhaul Networks,''
in Proc. of International Teletraffic Congress (ITC), Sep. 2016 [pdf]

Slađana Jošilo, Miloš Pejović, Branko Đorđević, Milan Narandžić, Slobodan Nedić, ''Multicarrier waveforms with I/Q staggering: uniform and nonuniform FBMC formats,''
EURASIP Journal on Advances in Signal Processing, Nov. 2014 [pdf]

Slađana Jošilo, Milan Narandžić, Stefan Tomić, Slobodan Nedić, ''Widely linear filtering based kindred co-channel interference suppression in FBMC waveforms,''
in Proc. of International Symposium on Wireless Communications Systems (ISWCS), Aug. 2014 [pdf]

Slađana Jošilo, Miloš Pejović, Slobodan Nedić, ''Non-uniform FBMC-a pragmatic approach,''
in Proc. of International Symposium on Wireless Communications Systems (ISWCS), Aug. 2013 [pdf]