Optimizing search space for dynamic sfc routing: A minimum spanning tree-based grey wolf algorithm
Zahida Sharif, Muhammed Basheer Jasser, Angela Amphawan, Kok Lim Alvin You, Tse Kian Neo · Siti Hasmah Digital Library-MMU Institutiona Repository (Multimedia University)
In Network Function Virtualization Infrastructure (NFVI), the dynamic nature of Service Function Chain (SFC) mapping poses significant challenges, particularly for routing optimization. Fluctuating network conditions and user demands rapidly expand the routing search space, making real-time identification of optimal paths computationally expensive. An effective routing strategy therefore requires the construction of an efficient search space that ensures full node connectivity while selecting only qualitative links in terms of latency, bandwidth, and resource availability. Achieving these objectives simultaneously remains a major challenge, as conventional algorithms designed for rigid or strong tree structures are often unsuitable for dynamic chain orchestration in NFV environments. To address this issue, this work focuses on routing search space optimization by reducing computational overhead and eliminating infeasible routing options from the discrete solution space. A modified Grey Wolf Optimization (GWO) algorithm is proposed, specifically tailored for discrete routing scenarios in dynamic SFC mapping. The proposed approach employs a discrete initialization strategy, enforces a Minimum Spanning Tree (MST) based connectivity constraint to guarantee end-to-end reachability, and integrates a penalty function to suppress redundant or overlapping routing solutions. This design ensures that optimization is performed over a compact, connectivity-aware, and quality-driven search space. Simulations results validate the effectiveness of the proposed search space optimization strategy, demonstrating significant performance improvements across different network scales. The proposed approach achieves up to 91 % reduction in execution time and 82.8 % reduction in end-to-end delay, confirming its suitability for real-time dynamic SFC routing. In addition, improved bandwidth efficiency is observed, reflected by reductions of 51%, 59%, and 66% in average available bandwidth for small, medium, and large topologies, respectively. These quantitative gains highlight the benefits of preoptimizing the routing search space and confirm its effectiveness for scalable and adaptive NFV environments.