A Reinforcement Learning Approach for Online Service Tree Placement in Edge Computing

Abstract

We consider the problem of optimally mapping an edge computing service that is modeled as a tree with multiple processing sub-tasks and data flows onto the underlying physical network. As new computing and data analytics applications require more complicated data processing structures, and different types of data (e.g., images, videos, and numbers) sensed at geographically distributed locations must be collected and processed to obtain a complex and comprehensive result, highly intelligent algorithms are needed to solve this challenging problem. In this paper, we propose a learning-based hierarchical service tree placement strategy that aims to optimize the net utility, defined as achieved utility minus network congestion. The key idea is to decouple a service tree into appropriate sub-trees each containing a single computing sub-task as well as associated data flows and to recursively leverage Q-learning to place each sub-tree while maintaining the dependencies of sub-tasks in the service tree structure. It enables a scalable solution for large networks with unknown arrival statistics and complex service structures. Numerical results show that our solution can significantly outperform baseline heuristics in online service tree placement.