Joint Placement and Prewarming for Hybrid Service Function Chains: A Critical-Path-Guided Grey Wolf Optimizer

Abstract

Hybrid service function chains (SFCs) composed of containerized network functions (CNFs) and virtual machine-based network functions (VMNFs) underpin latency-critical services in edge computing environments, yet the order-of-magnitude difference in cold-start latency between the two virtualization types severely undermines end-to-end latency guarantees. Existing studies treat cold-start latency as a black-box constant or reduce prewarming to a type-agnostic binary switch, while prevailing metaheuristic solvers remain blind to the dependency structure of the placement problem. To the best of our knowledge, this paper develops the first unified mixed-integer nonlinear program that jointly optimizes placement and type-differentiated prewarming for hybrid SFCs. The model treats cold-start latency as a placement-dependent staged process and captures the prewarming gap between the two virtualization types through a continuous completion coefficient. To solve this NP-hard problem, we propose a critical-path-guided grey wolf optimizer (CP-GWO). In every generation, it recomputes the critical path of the SFC directed acyclic graph and injects this dynamic structural signal into position updating, constraint repair, and global perturbation. The search thereby shifts from blind numerical sampling to a topology-guided process that is explicitly informed by the end-to-end latency structure. We evaluate CP-GWO on twelve instances spanning two network scales and four SFC lengths, complement them with dedicated sweeps over the CNF-to-VMNF ratio and the standby budget, and corroborate the results with non-parametric statistical tests. CP-GWO attains an average gap of only 0.25% from the best-known solutions and the smallest run-to-run dispersion among the stochastic baselines. Its advantage widens as the problem scale, the SFC length, the VMNF ratio, and the budget tightness increase.