Internet-connected devices generate service function chain (SFC) requests for reliability-sensitive applications such as smart factories and intelligent healthcare. To facilitate reliable SFC provisioning, one can employ dedicated SFC protection approaches to protect the primary service function path (SFP) by constructing a fault-disjointed backup SFP. Notably, the construction processes of the fault-disjointed primary and backup SFPs are interdependent, and the direct application of existing SFC embedding approaches to construct these SFPs by separate processes may not effectively optimize overall resource consumption. In this work, for the first time, we comprehensively study how to embed and protect an SFC through collaborative processes that have provable bounds. We formally define the problem of SFC embedding and protection (SFCEP), for which we develop the novel techniques of a backup SFP identifier (BSI) and resource-aware Bellman–Ford loop (RBL) to address the challenges posed by collaborative embedding and protection. On the basis of these techniques, we propose an efficient algorithm called optimal SFC embedding and protection (Opt-SEP). When the network resources are sufficient to accommodate an incoming SFC request, we prove that Opt-SEP can minimize the overall resource cost of creating a pair of fault-disjointed primary and backup SFPs. Moreover, for cases in which the network resources are limited, our extensive simulation results show that Opt-SEP significantly outperforms the benchmarks.

Emerging 5G technologies can significantly reduce end-to-end service latency for applications requiring strict quality of service (QoS). With network function virtualization (NFV), to complete a client’s request from those applications, the client’s data can sequentially go through multiple service functions (SFs) for processing/analysis but introduce additional processing delay. To reduce the processing delay from the serially-running SFs, network function parallelism (NFP) that allows multiple SFs to run in parallel is introduced. In this work, we study how to apply NFP into the SF chaining and embedding process such that the latency, including processing and propagation delays, can be jointly minimized. We introduce a novel augmented graph to address the parallel relationship constraint among the required SFs. Considering parallel relationship constraints, we propose a novel problem called parallelism-aware service function chaining and embedding (PSFCE). For this problem, we propose a near-optimal maximum parallel block gain (MPBG) first optimization algorithm when computing resources at each physical node are enough to host the required SFs. When computing resources are limited, we propose a logarithm-approximate algorithm, called parallelism-aware SFs deployment (PSFD), to jointly optimize processing and propagation delays. We conduct extensive simulations on multiple network scenarios to evaluate the performances of our schemes. Accordingly, we find that (i) MPBG is near-optimal, (ii) the optimization of end-to-end service latency largely depends on the processing delay in small networks and is impacted more by the propagation delay in large networks, and (iii) PSFD outperforms the schemes directly extended from existing works regarding end-to-end latency.

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.

Network function virtualization (NFV) is introduced to effectively deliver end-to-end network services for the emerging Internet of Things (IoT), multiaccess edge computing and 5G communication techniques. In NFV, the network service request can be accommodated in the form of a service function chain (SFC). The SFC will have to reserve abundant resources such as link bandwidth, service functions, and computation in the physical network to meet the demands of customers. Minimizing the cost from the resource reservation in NFV remains challenging, even though a few works in the literature proposed cost-optimization methodologies with assumptions to guarantee their correctness. In this paper, we comprehensively investigate how to minimize the cost when delivering network services as SFCs with provable bounds and fewer assumptions. We formally define the problem of minimum cost service function chaining and embedding (MC-SFCE) and propose an algorithm, namely, COst Factor-based SFCE Optimization with ShortCut (COFO-SC), for MC-SFCE. Novel mathematical analysis is provided to demonstrate the correctness of our approaches and related bounds. Our extensive simulations and analysis also show that the proposed COFO-SC outperforms the schemes directly extended from the existing work.

In network function virtualization (NFV), the client’s service requests will go through multiple service functions (SFs). The instances of the required SFs will be hosted on the geographically-distributed physical nodes in physical networks (PNs). The failure of any physical nodes or virtual nodes (i.e., SF instances) will impact the delivery of services and the client’s experience. It is essential for service providers to take the node failure and network reliability into account. Different from physical node failures that will affect the PN’s topology and connectivity, virtual node failures impact the services delivery of certain clients. As a result, applying traditional backup schemes that are designed for physical node failures may not efficiently provide protection for virtual node failures. In this work, we define and mathematically formulate a new latency-bounded off-site virtual node protection (LOVNP) problem in NFV. After proving the NP-hardness of the LOVNP problem, we introduce a novel shared protection technique called pairwise node protection to effectively facilitate the protection of node failures in NFV. Then, we propose an efficient heuristic algorithm called protection centrality based pairwise node protection (PC-PNP) to optimize the LOVNP problem and prove that PC-PNP has a logarithm-approximation boundary. Our extensive simulations and analysis show that the proposed algorithm significantly outperforms the algorithms that are extended from the existing work.