Delay-Optimal Congestion-Aware Routing and Computation Offloading in Arbitrary Networks

Abstract

Emerging edge computing paradigms enable heterogeneous devices to collaborate on complex computation applications. However, for arbitrary heterogeneous edge networks, delay-optimal forwarding and computation offloading for long-term average performance remains an open problem. In this paper, we jointly optimize data/result routing and computation placement in arbitrary networks with heterogeneous node capabilities and congestion-dependent nonlinear transmission and processing costs. Despite the non-convexity of the formulated problem, by analyzing the KKT conditions, we provide a set of sufficient optimality conditions that solve the problem globally. To provide insight into such global optimality, we show that the proposed non-convex problem is geodesically convex under mild assumptions. We also show that the proposed sufficient optimality condition leads to a lower hemicontinuous solution set, providing stability against user-input perturbations. We then extend the framework to incorporate utility-based congestion control and fairness. We develop a fully distributed algorithm that converges to the global optimum. Numerical results demonstrate significant improvements over multiple baseline algorithms.