Scheduling Dependent Functions at the Network Edge

The convergence of computing and networking heralds a promising paradigm for future sixth-generation (6G) systems, enabling low-latency services for end users by deploying modern applications, which typically consist of multiple interdependent functions, at the network edge. However, unstable and short-range Device-to-Device (D2D) links often restrict offloading options, forcing users to either face limited access to nearby devices or rely on distant cloud resources, thereby underutilizing edge resources and diminishing user experience. To address this challenge, we propose utilizing base stations to relay traffic between unconnected edge devices. Additionally, we strategically reuse historical function placements to balance re-deployment costs against dynamic request adaptation. Then, aiming to minimize storage, computation, and transmission resource consumption costs along with function replacement costs, we formulate the Dependent Function Scheduling (DFS) problem as a Mixed Integer Non-Linear Programming (MINLP) problem, which is NP-hard even in single-slot scenarios. We introduce a random rounding-based approach to derive high-quality integer solutions for the single-slot DFS problem. Building on this, we further develop an efficient online algorithm for the general multi-slot DFS problem, which is proved to achieve near-optimal performance with high probability. Extensive real-trace simulations demonstrate that our proposed method significantly outperforms state-of-the-art baselines, achieving up to a 68.22% reduction in total cost.