Application Placement in Edge Computing – Optimization, Game, and Deep Reinforcement Learning

Edge computing is a promising computing paradigm that will meet the service requirements of the latency-sensitive and/or bandwidth-hungry applications brought by the rapidly growing Internet of Things (IoT) and Artificial Intelligence (AI) systems. Different from a traditional cloud computing environment in which all servers are organized in data centers and tightly controlled and managed by a provider, the various service providers in an Edge-Cloud system are independent and located at various distances away from clients. Mobile applications are becoming increasingly more computation intensive, band- width hungry, and delay sensitive, due to the recent rapid development of IoT and AI. An important issue in edge computing is the allocation of resources to the competing demands from different mobile applications. The low latency and low network cost benefits of edge computing are brought by the proximity of edge servers to users. However, it is challenging to optimally place mobile users’ applications on edge computing servers in a Mobile Edge Computing (MEC) system, as users dynamically change their locations from time to time, and the availability of geographically dis- tributed edge servers varies over time. Our goal is to develop a set of effective design approaches, including optimization methods, game theory, and Deep Reinforcement Learning, to solve application placement problems in typical application scenarios of edge computing. In the first part of this dissertation, we explore the design of revenue sharing mechanisms for an Edge-Cloud computing system from a game-theoretic perspective. The system adopts a job distribution mechanism to maximize the total revenue received from clients and employs a revenue sharing mechanism to split the received revenue among service providers. Under these two system-level mechanisms, service providers game with the system in order to maximize their own utilities by strategically allocating their resources. We develop a game-theoretic framework to model the competition among the service providers as a non-cooperative game. Our framework offers an economics approach to the understanding of Edge-Cloud systems and provides fundamental insights into their revenue sharing design. In the second part, we investigate the design of a Mobile Edge Computing (MEC) system in which self-interested users minimize their own costs and a MEC service provider attempts to maximize its revenue. We introduce a platform that works as an intermediary to facilitate the service transaction between the users and the provider. We develop a dynamic programming algorithm for a user to minimize his/her own cost and an efficient heuristic algorithm for the platform to minimize the total cost of all users by optimally scheduling the admission of users’ jobs and still allowing users to make independent optimal decisions. Furthermore we model the interaction between users and an edge provider as a game. We have demonstrated the effectiveness of our algorithms in optimizing and stabilizing the system, and we point to a promising direction to design a MEC system for independent self-optimizing mobile users. Lastly, we investigate the optimal scheduling of a stream of dynamically arriving multi-component application jobs in an edge computing system that consists of geo-distributed edge computing nodes connected through a wide area network. The scheduling and placement of such application jobs in an edge system is challenging due to the interdependence of multiple components of each job, and the communication delays between the geographically distributed data sources and edge nodes and their dynamic availability. To address those challenges, we develop an online scheduling scheme based on Deep Reinforcement Learning (DRL). We have demonstrated that our design outperforms existing traditional algorithms. Our research sheds light on the application of DRL to the design of edge computing systems