GPSO: A Graph-based Heuristic Algorithm for Service Function Chain Placement in Data Center Networks

Network Function Virtualization (NFV) is a promising technology. Connecting Virtual Network Functions (VNFs) forms Service Function Chains (SFCs). SFCs can flexibly orchestrate and expand network functions. However, the SFCs perform network functions that require very high reliability, even reaching the level of physical switches. Therefore, the influence of physical machines and network links can no longer be ignored when considering the reliability of SFCs. This paper proposes the Graph-based Particle Swarm Optimization (GPSO) algorithm to address the SFC placement problem. GPSO adopts a novel velocity update strategy that can adapt to the non-Euclidean structure of the physical machine topology in the data center. Compared to traditional heuristic algorithms, GPSO only needs 57% execution time and can achieve 110% fitness value. Moreover, the GPSO algorithm can trade-off reliability and resource utilization. The evaluation results show that GPSO achieves higher reliability than the state of the art algorithms under the threshold of 80% resource utilization.