Service Function Chaining and Embedding With Heterogeneous Faults Tolerance in Edge Networks

In the 5G-and-beyond era, ultra-reliable low latency communication (URLLC) services are ubiquitous in edge networks. To enhance the performance metrics and the quality of service (QoS), URLLC services are delivered via a sequence of software-based network functions, also known as a service function chain (SFC). Towards reliable SFC delivery, it is imperative to incorporate fault-tolerance during SFC deployments. However, deploying an SFC with fault-tolerance is challenging because the protection mechanism needs to jointly consider multiple concurrent physical/virtual network failures and hardware/software failures. Considering these concurrent heterogeneous failures, this work investigates how to effectively deliver an SFC in edge networks with the objective of minimizing bandwidth resource consumption. First, we introduce the concept of k-heterogeneous-faults-tolerance and propose an augmented protection graph, called k-connected service function slices layered graph (KC-SLG). Based on the KC-SLG, we formulate a novel problem called k-heterogeneous-faults-tolerant SFC embedding and propose an effective algorithm, called fault-tolerant service function graph embedding (FT-SFGE). FT-SFGE employs two proposed techniques: k-connected network slicing (KC-NS) and k-connected function slicing (KC-FS). Via thorough mathematical proofs, we show that KC-NS is 2-approximate. Extensive simulations show that KC-FS has the best average cost-efficiency when k = 2, and FT-SFGE outperforms the schemes directly extended from the state-of-the-art.