Minimizing the Latency of Embedding Dependence-Aware SFCs into MEC Network via Graph Theory

Integrating Network Function Virtualization (NFV) into Multi-Access Edge Computing (MEC) network has been proposed. In the NFV-enabled MEC network, Service Function Chains (SFCs) are proposed to orchestrate Virtual Network Functions (VNFs) required by Network Service Requests (NSRs) for adapting to the various NSRs. NSRs are initiated as a set of requests for VNFs, and those requests should be mapped onto specific VNF instances in the executing-order, which also means embedding dependence-aware SFCs into the physical network. It is extremely challenging to optimize the latency when embedding SFCs into the MEC network because the executing-order constraint of VNFs in SFCs causes trouble for measuring the latency of designed SFC embedding schemes. For these reasons, we investigate how to minimize the latency when embedding SFCs into the heterogeneous MEC network under the condition of considering the dependency and concurrency of VNFs. Above all, a resource management model based on graph theory, element graph, is proposed to express the dependency of various resources in the NFV-enabled MEC network, which overcomes the problems caused by heterogeneity. Furthermore, relying on graph theory, we propose a universal evaluating model that can flexibly measure the latency cost of any designed service chain. Depending on the element graph and evaluating model, the Genetic Algorithm (GA) is adopted to optimize the latency of embedding SFCs, which can adaptively orchestrate the optimal VNFs for any SFC to minimize the latency.