KPath: Dependent and Redundant Task Execution Path Planning in Edge Service Networks

Edge servers cache applications as microservices to provide low-latency services to end-device users. Due to heterogeneous resource constraints, microservices supporting the same application may be distributed across multiple edge servers. When an end-device makes a request, it generates a task execution path comprising interconnected dependent microservices across the edge network. However, task execution time can vary significantly across these servers due to resource heterogeneity, unpredictable workloads, cyberattacks, and software exceptions. The interdependent nature of microservice execution makes single-path models highly vulnerable, as any failure or delay compromises the entire task chain. This paper formulates the Dependent Task Execution Path Planning (DTEP) problem-a novel NP-hard optimization that transforms single-path dependency models into robust multi-path redundancy frameworks. With a redundancy budget, it plans multiple redundant, shortest node-disjoint execution paths to enhance reliability and latency performance. To solve this complex problem efficiently, we propose KPath, a novel two-phase approximation algorithm consisting of base path generation followed by target path acquisition, offering a guaranteed approximation ratio of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(m)$</tex-math></inline-formula>. Experimental results demonstrate that KPath efficiently generates path sets with average path lengths up to 17.87% shorter than modified state-of-the-art methods across various problem scales. Furthermore, when node issues occur, KPath achieves up to 26% reduction in communication latency through redundancy.