Service Function Chaining and Embedding With Heterogeneous Faults Tolerance in Edge Networks
Danyang Zheng, Gangxiang Shen, Yongcheng Li, Xiaojun Cao, Biswanath Mukherjee
Abstract
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${k}$ </tex-math></inline-formula> -heterogeneous-faults-tolerance and propose an augmented protection graph, called <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${k}$ </tex-math></inline-formula> -connected service function slices layered graph (KC-SLG). Based on the KC-SLG, we formulate a novel problem called <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${k}$ </tex-math></inline-formula> -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: <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${k}$ </tex-math></inline-formula> -connected network slicing (KC-NS) and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${k}$ </tex-math></inline-formula> -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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${k}$ </tex-math></inline-formula> = 2, and FT-SFGE outperforms the schemes directly extended from the state-of-the-art.