Optimized Kuhn–Munkres with Dynamic Strategy Selection for Virtual Network Function Hot Backup Migration

Abstract

In Follow-Me Mobile Edge Cloud (FMEC) environments, Virtual Network Function (VNF) instances dynamically move in tandem with user mobility. For latency-sensitive applications, hot backups aim to reduce service downtimes during primary VNF instance failures. However, as the distance between VNF instances and their hot backups shifts due to user mobility, recovery latency can sometimes exceed user expectations, leading to certain backups being perceived as unavailable. To maintain VNF reliability, it becomes essential to either deploy additional hot backups closer to the VNF instances or migrate the deemed unavailable backups to proximity, reinstating their usability. How to effectively leverage both the VNF and its failed hot backups to ensure VNF reliability, meet users’ recovery latency demands, and minimize the overall cost of hot backup migration and redeployment is a challenging problem. To address this challenge, we propose a hybrid approach combining an optimized Kuhn–Munkres algorithm and dynamic strategy selection for cost-efficient hot backup migration. The problem is first formulated as an integer linear programming model and proven Non-deterministic Polynomial-time hard (NP-hard). To address computational complexity, we propose an optimized Kuhn–Munkres algorithm with dynamic strategy selection. The Kuhn–Munkres algorithm accelerates backup migration through network preprocessing and multi-constraint candidate filtering, while adaptively choosing between migration and redeployment via real-time cost analysis. Through extensive experiments, our hybrid migration algorithm achieves equivalent user demand satisfaction as traditional methods while reducing backup VNF (BVNF) migration costs by 15%. The proposed approach combines an optimized Kuhn–Munkres algorithm for efficient candidate selection with dynamic cost-aware strategy switching, ensuring reliable latency-sensitive service in mobile edge environments.