GRM-SFCOD: Dynamic Pricing-Based Online Deployment for Reliable Multi-Replica Service Function Chains
Virtual Network Functions (VNFs) deployed on commodity servers exhibit failure rates two orders of magnitude higher than carrier-grade hardware, rendering service function chain (SFC) reliability a critical concern. Existing solutions are confined to offline static scenarios and single-instance serial models, which create single-point bottlenecks and constrain network service provider (NSP) revenue. This paper proposes GRM-SFCOD, which is a General Reliability-aware Multi-replica SFC Online Deployment algorithm. We introduce a primary-backup replica pool that parallelizes VNFs into lightweight instances while provisioning redundant backups for fault tolerance. The online deployment problem is formulated as a Mixed-Integer Nonlinear Program (MINLP) that maximizes NSP revenue; its NP-hardness is proved via reduction from the Multidimensional Knapsack Problem. To enable efficient online decisions, we design a dynamic pricing mechanism with exponentially scaling resource prices, decomposing the problem into (i) replica allocation based on marginal reliability gain and (ii) VNF placement via an improved Genetic Algorithm. Simulations demonstrate a ∼9.68% lower deployment cost compared to uniform-allocation baselines, ∼17% higher resource utilization than Best-Fit heuristics, and an attainment of ∼81% of offline optimal revenue with orders-of-magnitude lower computational overhead.