Latency-Sensitive Parallel Multi-Path Service Flow Routing With Segmented VNF Processing in NFV-Enabled Networks

In the context of Software Defined Networking (SDN) scenarios, the deployment of multi-path routing has been trending as one of the practical approaches. It serves the two-fold objective of improving the reliability of Service Function Chains (SFCs) and reducing end-to-end delays through parallel processing; this latter being this paper's focal point given it is one of the fundamental objectives of 6G. The literature encloses numerous publications revolving around the exploitation of Virtual Network Function (VNF) duplication and optimal placement to enable parallel processing. However, very little attention has been allocated to segmented VNFs with parallel multi-path data traffic flow routing to catalyze service completion. In reality, the application of segmented task processing is now widely used in our Internet life (e,g, real-time video on Youtube). In order to realize the ultra-low end-to-end delay of SFC, we introduce the segmented VNF processing window and implement VNF processing tasks in batches/windows with multi-path routing. Herein, a novel Parallel Multi-Path service flow Routing with processing Windows (PMPRW) scheme is proposed. The PMPRW is formulated as a Mixed Integer Linear Program (MILP), owing to the complexity of which, a Column-Generation (CG) based framework is developed to generate accurate sub-optimal solutions that achieve the same performance as the optimal solution. In order to accelerate the process and enhance the performance, we propose an extended Column Fixing (CF) strategy to help generate new columns in CG. Extensive simulations are conducted to gauge the merit of PMPRW and demonstrate its superiority (as opposed to single-path routing). PMPRW achieves desirable performance by concurrently reducing the overall end-to-end delay (e.g., 22% through parallel dual-path routing).