On Scalable In-Network Operator Placement for Edge Computing

The drawbacks encountered in today's cloud computing infrastructures have led to a paradigm shift towards in-network processing, where resources in the core and at the edge of the network are leveraged to perform computations. This can lead to decreased costs and better quality of service for users, e.g., when latency-critical applications are executed close to data sources and users. Deploying applications or parts thereof on these infrastructures requires to place operators (i.e., functional components of applications) on available resources in the network. Solving large instances of this problem in an optimal way is known to be computationally hard and, thus, practically unfeasible. While heuristic approaches exist, they mostly aim at placing functionalities on homogeneous nodes or make unrealistic assumptions for edge computing environments. To address this issue, this paper studies the placement problem in the context of a 3-tier architecture consisting of cloud, fog and edge devices. We provide a comprehensive model and propose a heuristic approach to the problem, in which we introduce constraints on the placement decision to limit the possible solution space, leading to a decrease in the solving time for the problem. These constraints exploit the characteristics of our 3-tier network architecture. To demonstrate the feasibility of the approach, we present a general framework that supports different types of heuristics. We validate the approach by implementing example heuristics for each type. We show that our approach can scale to large instances, i.e., it can significantly reduce the resolution time to find a placement solution while introducing only a small optimality gap.